# Point inside Mesh

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

## 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 on other sites
Quote:
 Original post by MetaKnightIs 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 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 on other sites
Quote:
 Original post by Nik02For 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.

##### Share on other sites
Quote:
 Original post by Nik02There 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 on other sites
Quote:
Quote:
 Original post by Nik02For 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.

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 on other sites
Quote:
Original post by MetaKnight
Quote:
 Original post by Nik02There 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 on other sites
Ahh! I see, works very nicely!
Thank you very much

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

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631431
• Total Posts
3000039
×