# Relative position of a point with respect to a 3D non-convex polyhedron with triangular facets

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