Looking for some pointers for voxelisation strategies

Question

To voxelise a mesh basically means to be able to determine for a point(x,y,z) if it is either inside or outside a mesh.

A mesh here is just a raw set of triangles. Being outside the mesh means that there is a ray from the point (with any direction) that does not intersect the mesh from any viewpoint.

For a well behaved, closed, non intersecting mesh, that is easy: Trace a ray in any direction, if the number of intersections is odd, the point is inside.

But for a "bad" mesh, composed of open parts this is terrible. For example the mesh could be two cubes connected by an open cylinder that sticks into both of them.

ZBuffer rendering solves this fine for one viewpoint. But the issue is for any viewpoint. To me the problem is well defined, but not obvious to solve.

I am looking for some pointers on how to approach this problem. There must be tons of research for it. Any links to papers? Or am I missing something in how to think about the problem?

Answer 1

It's possible if all of the surfaces on your meshes have a "sidedness" to them, i.e. they have a front side and a back side.

Then to determine if a point is inside the mesh you can trace a ray from the point in any direction, and keep a count of intersections like this:

• if the ray goes through the back side and out the front side (i.e. emerging from the inside to the outside), then add one.
• if the ray goes through the front side and out the back side, (i.e. entering the inside from the outside), then subtract one.
• if the mesh surface is double sided, do not add or subtract anything.

If the final count is positive, or if the point lies exactly on any surface, then the point is inside the mesh.

You need to add the restriction that it's never possible to see an exposed back side of a surface from outside the mesh. This is equivalent to saying that the mesh should always render correctly from all exterior viewpoints with back-face culling turned on.

For the example with the cube and open cylinder, for the cube to be solid, its surfaces should be single sided (making them double-sided would mean defining a hollow cube with infinitely thin walls).

The mesh surface of the cylinder would also have to be single-sided, or else it also would have infinitely thin walls, and points inside the cylinder (that aren't inside the cubes) would not be inside the mesh. As long as the ends of the cylinder are stuck inside the cube, the restriction is not broken since you can never see an exposed back side of a face.

If one of the cubes is removed, then the restriction is not met and this algorithm will fail.