XNA Check if a 3D point is inside a model (fbx)

Question

My friends and I are developing a 3D Printer. We finished the hardware things including the programming of the microcontroller. Now we want to analyse existing 3D models. This includes a way to check if specifc coordinates (3d) are inside or outside of a 3D model (FBX model) we want to print. At the moment we are looking on Unity3D and XNA. I figured out what I can do with the bounding boxes, but this is not a smart way to solve the problem in XNA. So my question is there any smart way to get this information.

Thank you very much for support ;-)

Answer 1

Algorithm

You are looking for a way to determine if a point lies inside a concave hull. This can be done by extending the Point in Polygon algorithm to three dimensions.

The idea is that you cast a ray through the point and calculate the intersections with the hull (polygons) of your volume. If the number of ray-triangle intersections on either side of the point is odd, it lies inside of the volume.

If performance is an issue, simplified bounding volumes can still be useful. If calculating ray-polygon intersections is expensive, you would first check if the point lies inside an approximated hull for the mesh, that has a lower cost on performance (e.g. bounding boxes, convex hulls). That way you can discard points early.

Here is another detailed explanation of the Point in Polygon algorithm and an implementation in C:

• Determining Whether A Point Is Inside A Complex Polygon

Chosing the right programming environment

I am not sure why exactly you want to use XNA or even Unity for this task. Of course, both offer the ability to load 3D models, but there are definitely simpler and more efficient alternatives.

For the aforementioned algorithm you need access to the vertex positions and triangle definitions of the model, nothing more. If FBX is not a requirement, I would suggest looking into the Wavefront OBJ file format. It is a text based format, easy to understand/parse and supported by almost all professional 3D modelling applications.

• Wavefront OBJ specification
• OBJ file examples

If FBX is required, you could still try to parse them yourself or just use an existing 3D converter.

Answer 2

I'd use Voxels for such task. Your 3D printer has some resolution along all axes so you could assume similar resolution for your voxel space. Translation of voxel field values to printer movements will be relatively easy so the hardest thing is to convert your mesh into voxels. I'm sure you can find some library for that.

You can start here: Know any voxel graphics C++ libraries?

Answer 3

A very quick solution (requiring absolutely no math) for testing if a point is inside a solid (closed set of surfaces) is to use a 3D game engine as you have already surmised. As Lucius points out, it is sort of using a crane to crush a fly. But, it will work with very little effort.

To confirm this, I have done this before using Panda3D (and I wouldn't be surprised if just about any 3D engine could be used).

The collision detection is what was useful. As Lucius pointed out, you want to detect surfaces. So, use what Panda calls a "RayCollider" (basically a line) and see how many times it intersects the surfaces of your 3D model. Panda already has the helper functions for doing this and there are many full-code examples included using RayColliders for detecting surfaces when you download the SDK.

Then, it is a straight forward matter of iterating through all x,y,z space and using the panda helper functions for moving the origin of your ray. If it collides with an odd number of surfaces - you're inside. Otherwise, you're outside.

Compared to Panda3D's full-code examples, this task is actually quite trivial. The learning curve will mostly be spent familiarizing yourself with the engine rather than the math.