Mesh Voxelizer in Voraldo13
This is a project which has been sitting on the back burner for a long time, something of a longer term aspirational project, which was enabled by the new interface to my software rasterizer. The problem statement is relatively simple: given a textured mesh, create an equivalent voxel model. There are a number of ways to approach the problem.
This approach is something I have had in my head for a long time - basically, start by containing the model into some equivalent of a graphics API's normalized device coordinates ( NDC ). Pass it through the rasterization process and keep all the fragments, regardless of whether or not they would pass depth testing. This collection of fragments now each has a three dimensional point representing it's location inside of the NDC and a texture sample that comes from the barycentric interpolated texcoords during the raster process.
Ok, great - that's all relatively simple - but the output looks like this ( click to play ):
I had anticipated this, and it's really quite intuitive when you think about it. The parts of the model which are perpendicular to the view direction have good density, and create a reasonable representation of the surface. But as the represented surface becomes more and more parallel to the view ray, you start to see these artifacts where not enough fragments were created to properly represent the surface. This is because there are only a few fragments generated on these parallel surfaces - when viewed from the front, the side panels of the car only cover a few pixels during the raster process. When the rasterizer evaluates those polygons, the small number of output fragments means that we do not get proper sampling to reconstruct a full representation of the surface.
Compensating for the Artifacts
I had this whole thing worked out in my notes for probably about a year before actually doing it - the overhead of porting the rasterizer was the primary obstacle. Once I had that working with a good enough interface to do what I wanted with it, the solution is really quite simple. Just render the model from three views - this ensures that you have good sampling along the three orthogonal directions, you essentially want to look at the model from the x, y, and z directions. By combining the output from the three views, you end up with a much more reasonable approximation.
Ok that's still not right. Need to align the three views, so that when combined, they overlap with the same orientation.
Once you do that, you can get a fairly decent representation of the whole model, when viewed from all angles. While there are still some artifacts, I had some pretty reasonable success on this model. This is the Lotus Esprit model from Gran Turismo 2. You can see it here with Voraldo13's thin lens DoF implementation. Higher poly models and higher resolution textures might start to require some filtering or multiple sampling, in order to get a reasonable approximation. I will return to this for the next version of Voraldo, and try to make a more general interface for loading an arbitrary model with multiple textures.
There are multiple ways to determine if a point is inside a mesh. There is one very cool one that I have seen for 2d, which generalizes to 3d. To determine if a point is inside a manifold mesh ( watertight, it defines a continuous surface ), you can iterate through all the triangles, take the vector from a known point outside the mesh, and intersect it with each one. The number of triangles with which the vector intersects will indicate whether you were inside or outside of the mesh, at the query point: an odd number means it is inside, while an even number means it is outside. If you think about it, it's fairly intuitive, odd means it left, or left, came back in, and left again, etc, while an even number means it either started outside, for the zero case, or went out and then back in, etc. I believe I have also heard Keenan Crane talk about this before, I've been meaning to watch his course on discrete differential geometry, as well as probably also his course on computer graphics.