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).