I have a 3D triangle mesh with the following properties:

  • unique vertices (triangles are stored as 3 vertex indices, the indices are stored in a point set backed up with an octree and a tolerance, to ensure that they are unique)
  • watertight: each edge of the triangle mesh is shared by exactly two triangles
  • The following adjacency matrices are available: triangle<->vertices, triangle<->edges, edges<->vertices, where a<->b means that I can access a for b, and b for a, in O(1).
  • a bounding volume hierarchy (BVH) of the triangles is available.

I want to accurately compute whether a point is inside, outside, or on the surface mesh in O(log(N_triangles)).

Computing whether a point is on the surface mesh is easy, I just use the BVH to find the closest triangle to the point, and perform a point triangle intersection.

I am attempting to computing whether a point is inside/outside the mesh using odd/even-count ray casting but I don't know how to handle some the following cases (when the point does not lie on the triangle):

  • intersection(ray, triangle) -> single point
    • triangle vertex
    • point on triangle edge
    • point inside triangle
  • intersection(ray, triangle) -> edge (ray lies on the plane of the triangle)
    • triangle edge (ray coincides with a triangle edge)
    • line segment whose endpoints are not any triangle vertices
    • line segment with one triangle vertex as end point

When the intersection result is a single point, the following approaches seem to work correctly:

  • a point inside the triangle (not a vertex or a point on an edge), I increase the count by one.
  • a triangle vertex, I add the vertex to a set and increase the count by one, so that vertices are only counted once.
  • a point on an edge, I add the edge to a set and increase the count by one, so that that point is only counted once.

When the intersection point is a line segment, that's a bit more complicated.

I guess that for each triangle where this happen I could take the vertices of the adjacent triangles, project them to a 2d plane with normal in ray direction, and check if the ray intersects that plane, but I am not sure if this will work, nor what to do when e.g. all these points lie on a plane (because all the adjacent triangles lie in the same plane as the triangle).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.