Point inside Mesh

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

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.

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

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)

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.

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.

Ahh! I see, works very nicely!
Thank you very much

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.