Sign in to follow this  
MetaKnight

Point inside Mesh

Recommended Posts

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this