PDA

View Full Version : containment test


Caprier
12-15-2008, 04:21 AM
I have an idea to test if a point P is inside a mesh M but as I'm not too sure of its logic, I'd like to have your opinion.

After checking that M is a closed mesh and that P is inside M's bounding box, I'll proceed like so:

I make a copy of M and flip its normals: Mf.
I use intersetRay() with the same ray on both meshes.
If there's not hit, P is outside.
If there's a single hit, it should be with Mf and P is inside.
If there are two hits, I check for the closest. If it's with Mf, P is inside. Otherwise P is outside.

As I see it, it should work with any closed mesh, even concave ones. But I might have missed something obvious. What do you guys think?
Thanks in advance for your help.

RobGalanakis
12-15-2008, 04:54 AM
1) You said in the first sentence "bounding box." I assume you mean mesh? (if it is a bounding box, you can just test P coordinates against the bounding box).
2) P is obviously the position of the ray- what is its direction?
3) There may be multiple hits- The logic you listed is mostly unnecessary. If there is no hit, P is outside. If there are any hits (1, 2, or any), if mF is hit first, P is inside, else it is outside.

Caprier
12-15-2008, 05:40 AM
Hi Rob. Thanks for answering.

P is the point from which the ray is shot, just a position in 3D space. The direction of the ray can be anything, as long as I use the same to test both flipped and unflipped meshes.
In my first sentence, I meant to test first if P is inside the world oriented bounding box of the mesh, using the .min and .max properties.
It's a very simple test and if P is outside, there's no need to test any further.

In reality, there could be multiple hits but intersectRay() only returns the first hit with a face that is not facing away from the origin of the ray (the point P). Unless I misread the reference, of course. I'll check again.

The only extra step I have compared to what you say is the single hit. This can save me the test for the closest hit, which can't be performed in this case as intersectRay() returns undefined when there's no hit.
If the point is inside a sphere, for example, I'll get only one hit, with the flipped mesh, and the corresponding position. And undefined for the other mesh.
I don't see how I can skip this step.

Anything that can spare an unnecessary test is welcome, as I need to apply this to quite a large number of points. But I want to make sure I don't miss a possibility.

ZeBoxx2
12-15-2008, 10:41 AM
might be better to use RayMeshGridIntersect
- it uses an acceleration grid, which speeds things up for complex geometry / geometry you'll be re-using a lot
- it can do a two-sided intersection test
- it can return the closest hit
- you can get the normal of the face hit (which will tell you if you hit the inside / outside)

This does make the same assumptions you do - the mesh must be closed and not self-intersecting.

Where the latter two may be a problem (though if the mesh is not closed, the 'inside' state is indeterminate, technically), you could boolean a mesh with a single vertex/face (the point) against the mesh, and test the result.

RobGalanakis
12-15-2008, 02:07 PM
Hi Rob. Thanks for answering.

P is the point from which the ray is shot, just a position in 3D space. The direction of the ray can be anything, as long as I use the same to test both flipped and unflipped meshes.
Yup, my bad- I didn't think about it correctly.

In reality, there could be multiple hits but intersectRay() only returns the first hit with a face that is not facing away from the origin of the ray (the point P). Unless I misread the reference, of course. I'll check again.
Also my bad- I was thinking about RayMeshGridIntersect, not IntersectRay. See Zeebox's reply.

Caprier
12-15-2008, 11:53 PM
I didn't know about RayMeshGridIntersect(). This should speed things up a lot.

I also completely missed the case of self-intersecting meshes.

Thank you for your help, guys. :))

CGTalk Moderation
12-15-2008, 11:53 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.