PDA

View Full Version : How to identify if a point is inside a mesh

07-15-2006, 02:34 AM
Hello, this is my second post here in the message boards. I have another problem that I'm really stuck on. I'm using c++.

My question is, if given a point in 3d space, how am I going to identify if it is INSIDE, ON THE SURFACE, or OUTSIDE of my mesh. I represented my mesh by identifying it's vertices and its polygons with its faces. So thats where I'm stuck. My mesh is assumed to be enclosed and no hollow areas are available.

Thanks.

V-man
07-15-2006, 08:12 AM
For inside of a surface, you can look up barycentric coordinates.

For inside or outside of a mesh, you can shoot a ray from the point to some random direction. If it crosses the mesh an odd number of times, it is inside, else outside. I have a lib that can tell you if an intersection occured. http://ee.1asphost.com/vmelkon/glhlibrary.html
Search for the word "intersection" in the header file.

07-17-2006, 08:19 AM
pseudocodes/codes are very much appreciated.
Thanks.

Overmind
07-17-2006, 11:28 AM
I assume P is the point you're interested in.

R is a ray originating in P in some arbitrary direction (let's say (1,0,0)).

Ray R = Ray(P, Vector(1,0,0));
int intersections = 0;
foreach(Triangle T in your Mesh) {
if(R intersects T)
intersections++;
}
if(intersections % 2 == 1) {
// INSIDE
} else {
// OUTSIDE
}As for "exactly on the surface", you should code a special case in the ray-triangle intersection. If the intersection is only a short way from the beginning of the ray, you can count this as "on the surface", and abort the whole algorithm.

It shouldn't be a problem to find some code for ray-triangle intersection with google, it's pretty common.

Tin Whisker
07-17-2006, 01:58 PM
My question is, if given a point in 3d space, how am I going to identify if it is INSIDE, ON THE SURFACE, or OUTSIDE of my mesh.Just out of curiosity, what kind of mesh is this (e.g., is it closed, is it convex), and what do you need this test for?