How do you know if you are 'inside' a set of triangles?

Question

If you have a set of 'regular' connected triangles such as this:

geodesic mesh sphere

...and you know the vertices / normals of every triangle, what is an efficient method to test whether or not another point is 'inside' or 'contained within' the set of triangles?

Thanks!

Do you always have convex shapes (as in this example) or can they be arbitrary? — Vincent van der Weele, Jan 22 '14 at 14:43
the only constraint is that they will be closed, non-intersecting bodies. For example, they could be the shape of a 'kidney bean' or an 'hourglass', but it will always be only one body. — HotDogCannon, Jan 22 '14 at 14:53

score 5 · Accepted Answer · edited May 23 '17 at 12:07

5

From the given point, cast a straight line. Test intersection of the line with every triangle and count all intersections found on the same side of the point. If this count is odd, you are inside.

To make computation easy, use x=x0, y=y0 for the line and project everything on the XY plane. Use How to determine if a point is in a 2D triangle? and finally check the z value of the intersection.

edited May 23 '17 at 12:07

Community

1
1

answered Jan 22 '14 at 14:56

1

It's the brute force approach. A more efficient approach (for large meshes and if there are enough location queries to amortize the initial cost) for ray casting would build a hierarchical spatial data structure (BSP tree, k-d tree, Octree) to cull lots of triangles during the query and significantly reduce the total number of ray / triangle intersection tests. Since here the ray direction is actually fixed, a simpler 2D spatial data structure in the xy plane could even be used instead. – user3146587 Jan 22 '14 at 18:01

How do you know if you are 'inside' a set of triangles?

1 Answers1