1
$\begingroup$

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

$\endgroup$

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.