Jump to content
  • Advertisement
Sign in to follow this  
MetaKnight

Point inside Mesh

This topic is 4184 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there any DirectX or XNA functions that test if a point is inside a mesh? Note: This isn't collision detection, I'm trying to make a voxel map of a mesh

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by MetaKnight
Is there any DirectX or XNA functions that test if a point is inside a mesh?

Note: This isn't collision detection, I'm trying to make a voxel map of a mesh


There isn't such a function out of the box, but it is relatively easy to implement a simple technique for this.

For each voxel position, cast 6 rays - along both positive and negative x, y and z directions. Count all the collisions with the geometry along each ray.

Now, if all of the rays' collision count with the geometry is an odd number (that is, n && 2 == 1), the current point is inside the geometry. Otherwise, it is either outside the geometry or the mesh has a hole that one of the rays escaped out from.

Direct3D utility library, D3DX, provides functions for testing a ray's collision against both a triangle and a full mesh. I haven't played with XNA so much as to remember whether similar functionality exists within it's class library (but it likely does).

Share this post


Link to post
Share on other sites
For a convex mesh, a point is inside if the point is behind all the triangle faces. Decompose a non-convex mesh into convex subsets and apply this test on all the set elements.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nik02
For each voxel position, cast 6 rays - along both positive and negative x, y and z directions. Count all the collisions with the geometry along each ray.

Now, if all of the rays' collision count with the geometry is an odd number (that is, n && 2 == 1), the current point is inside the geometry. Otherwise, it is either outside the geometry or the mesh has a hole that one of the rays escaped out from.

That's an interesting method, but isn't it limited to convex meshes? I imagine placing a voxel inside a teacup.

Admiral

Share this post


Link to post
Share on other sites
Quote:
Original post by Nik02
There isn't such a function out of the box, but it is relatively easy to implement a simple technique for this.

For each voxel position, cast 6 rays - along both positive and negative x, y and z directions. Count all the collisions with the geometry along each ray.

Now, if all of the rays' collision count with the geometry is an odd number (that is, n && 2 == 1), the current point is inside the geometry. Otherwise, it is either outside the geometry or the mesh has a hole that one of the rays escaped out from.

Direct3D utility library, D3DX, provides functions for testing a ray's collision against both a triangle and a full mesh. I haven't played with XNA so much as to remember whether similar functionality exists within it's class library (but it likely does).


Nice technique!
Just to clarify, but if I'm inside a box like so:


|-------|
| |
| * |
| |
---------



wont that give me an even number?(6)

but if I'm outside like so:



|-----------------|
| |--| |
| |* | |
| |--| |
------------------


i would get a even number?(8)

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
Quote:
Original post by Nik02
For each voxel position, cast 6 rays - along both positive and negative x, y and z directions. Count all the collisions with the geometry along each ray.

Now, if all of the rays' collision count with the geometry is an odd number (that is, n && 2 == 1), the current point is inside the geometry. Otherwise, it is either outside the geometry or the mesh has a hole that one of the rays escaped out from.

That's an interesting method, but isn't it limited to convex meshes? I imagine placing a voxel inside a teacup.

Admiral


My approach only works properly if a single voxel is smaller than the thinnest part of the mesh. For gathering the "density" of the mesh, though, this may be enough.

One way to alleviate this problem is to move the faces of the geometry by the distance of 1/2 voxel along their normals before the collision tests, so that even the thinnest parts of the mesh are registered inside the voxel.

The technique in itself isn't limited to convex meshes.

Share this post


Link to post
Share on other sites
Quote:
Original post by MetaKnight
Quote:
Original post by Nik02
There isn't such a function out of the box, but it is relatively easy to implement a simple technique for this.

For each voxel position, cast 6 rays - along both positive and negative x, y and z directions. Count all the collisions with the geometry along each ray.

Now, if all of the rays' collision count with the geometry is an odd number (that is, n && 2 == 1), the current point is inside the geometry. Otherwise, it is either outside the geometry or the mesh has a hole that one of the rays escaped out from.

Direct3D utility library, D3DX, provides functions for testing a ray's collision against both a triangle and a full mesh. I haven't played with XNA so much as to remember whether similar functionality exists within it's class library (but it likely does).


Nice technique!
Just to clarify, but if I'm inside a box like so:


|-------|
| |
| * |
| |
---------



wont that give me an even number?(6)

but if I'm outside like so:



|-----------------|
| |--| |
| |* | |
| |--| |
------------------


i would get a even number?(8)


You should consider the number of collisions per ray, not the total collision count of all the rays [smile]

After you've calculated the per-ray collision counts, combine the results so that if any of the counts is even, the point is outside of the mesh.

Share this post


Link to post
Share on other sites
I forgot to mention an important optimization for the technique:

If you can guarantee that you have a closed mesh, you don't need to test the negative directions separately. In this case, the results are exactly the same regardless of the polarity of the rays. Further, the only important point is that all dimensions (x, y, z) get recognized. This works because the triangles themselves are linearly defined using these dimensions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!