Say you have an irregular 3D object (meaning that it's not necessarily a cube or a sphere, but can be anything else), what would be the best approach to test if a certain point in 3D space is inside or outside such object?
So, basically to know if the point has "penetrated" or not the object.
Thanks
Point inside (or outside) 3d object
One possible means of testing if a point is inside an arbitrarily complex object is to pick a second point somewhere that you know is not inside the object, and test the line segment formed by the two points against the object, counting the number of times that it intersects the shell or mesh of the object. If the number of intersections is odd, then the point is inside. Otherwise, the point is outside. Consider a simple circle. For a point inside the circle to a point outside it, the line will cross the shell exactly once. For a point outside to a point outside, the line will either not cross the shell at all, or will pass across the circle, crossing once as it enters and once again as it leaves.
Author
Thank you for the suggestion, clever method indeed. I do not have any binary or tree subdivision so I guess I should test every mesh triangle for intersection. Might be slow...
What's the use-case for the intersection? Can you get away with an approximate answer by either using a low-poly version of the model, or using a set of simple shapes. For instance, if this is for collision detection between objects or characters in a game, you can represent the head with a sphere, the limbs with cylinders or boxes.
Even if you need 'perfect' tests, you can optimize quite a bit by defining volumes that are definitely intersecting or not intersecting:
1. a bounding sphere or box the completely encloses the object: if the point fails this test, the point cannot be inside the object
2. a couple large spheres or boxes completely contained inside the object: if these tests 'pass' the point is definitely inside the object.
3. if '1' passes and '2' fails, then break out the complex calculations.
Even if you need 'perfect' tests, you can optimize quite a bit by defining volumes that are definitely intersecting or not intersecting:
1. a bounding sphere or box the completely encloses the object: if the point fails this test, the point cannot be inside the object
2. a couple large spheres or boxes completely contained inside the object: if these tests 'pass' the point is definitely inside the object.
3. if '1' passes and '2' fails, then break out the complex calculations.
The object is probably made out of polgons, so you can test each one as a plane to see which side the given point is on. One way is to go in a certain order and make sure the Z value in the cross product of two edges of the (rotated into XY plane) polygon is consistent (all positive or all negative depending on the way you go).
If you can determine a normal to the surface of the object at any point of the surface, you can cast a ray from the point in an arbitrary direction and find the first intersection with the object. You can determine if the intersection is from the inside or from the outside by looking at the sign of the dot product of the ray direction with the normal at the point of intersection.
I just thought of an algorithm to test if a point is inside a polyhedron that is probably slower but more robust. For each triangle in the mesh, consider the tetrahedron formed by the point of interest and the vertices of the triangle. You can compute the solid angle at the point of interested, as indicated here (keep the sign of the angle depending on the winding of the vectors to the vertices). The sum of all the solid angles will be either -4pi, 0 or +4pi. The point is outside the polyhedron if and only if the sum is 0, and the expected inaccuracies of floating-point numbers shouldn't be much of a factor, because the other possible results are very far away.
[s]What I just described is the computation of a generalization of the winding number for a particular mapping from the sphere into itself. It can be described very precisely using the language of homology, but that's probably not worth doing.[/s] [EDIT: I am not sure that was correct.]
[s]What I just described is the computation of a generalization of the winding number for a particular mapping from the sphere into itself. It can be described very precisely using the language of homology, but that's probably not worth doing.[/s] [EDIT: I am not sure that was correct.]
Author
If you can determine a normal to the surface of the object at any point of the surface, you can cast a ray from the point in an arbitrary direction and find the first intersection with the object. You can determine if the intersection is from the inside or from the outside by looking at the sign of the dot product of the ray direction with the normal at the point of intersection.
To give more details, the application that I'm developing allows to style hair directly using the mouse. And so I'd like to test collision with the underlying mesh, which can be each time different (human head, animal body, a random object). I do not need to intercept the exact point of intersection or collision: I just need to stop hair styling if the point currently being moved collides with the model.
In this regard, I think the quoted suggestion by Alvaro is probably the most suitable and easiest to implement...
If you decompose the arbitrary object into convex hulls which approximates the original model, then checking inside/outside of hulls is much simpler.
There is a library that creates convex hulls from meshes, I read it somewhere in an article about occlusion.
but the author said it wasn't perfect and had unstable cases.
also, this problem is complicated and also may not have solutions for certain meshes. there are meshes with no inside at all.
and also again, float imprecision can create holes in a mesh because two polygons edges don't match perfectly, so only for that reason I would say it could be an idea to look for other kind of solutions than purely geometrical ones.
(eg. like rendering from inside towards a point outside, then do a classic 2d pixel inflation for the previously mentioned floating issue, then search for holes (non rendered pixels), repeat through depth peeling according to a heuristically found number of possible re-foldings (concavity degree)..)
but the author said it wasn't perfect and had unstable cases.
also, this problem is complicated and also may not have solutions for certain meshes. there are meshes with no inside at all.
and also again, float imprecision can create holes in a mesh because two polygons edges don't match perfectly, so only for that reason I would say it could be an idea to look for other kind of solutions than purely geometrical ones.
(eg. like rendering from inside towards a point outside, then do a classic 2d pixel inflation for the previously mentioned floating issue, then search for holes (non rendered pixels), repeat through depth peeling according to a heuristically found number of possible re-foldings (concavity degree)..)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
