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 trianglesThe 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 pointtriangle vertex point on triangle edgepoint inside triangleintersection(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 verticesline 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).
Relative position of a point with respect to a 3D non-convex polyhedron with triangular facets
computational geometry