Polygon Voxelization


I am trying to convert a polygon mesh into a voxel data-structure.

I don’t need the voxel data to be on the GPU, because I only want to use it to analyze the mesh, but I would like to utilize the GPU to rasterize the polygons and find which voxel cells they occupy.

The idea is to render the mesh slice by slice to a 2D texture, download the texture and store the voxel slice in RAM.

For this I use an orthographic projection with near and far plane having the distance of one voxel cell.

By rendering polygons filled and without backface-culling I can tag all the voxel-cells that the area of a polygon touches.

Now the problem are polygons that are exactly orthogonal to the camera. If I have a wall and the camera looks top down, the wall-polygon won’t be rasterized at all, and no voxel-cells will be tagged.

I thought that rendering polygons in wireframe-mode would guarantee me a one-pixel wide border around polygons, but when one looks exactly orthogonal onto a polygon it seems never to be rasterized, even in wireframe-mode. Though that should be fixable by simply rendering lines manually.

Now to the real problem:
Since I render the world slice by slice, everything outside those slices shall be discarded, which is achieved through near/far plane clipping. However, if I render lines to capture the borders of orthogonal polygons, those lines are, of course, also clipped at the planes. Thus if a polygon is inside the rendered slice, but a piece of the border is outside, nothing might be rendered.

I have a few ideas how one could fix this, but most of them mean heavy and complicated preprocessing. The only “easy” solution would be to render the world slice by slice 3 times, once from every major axis and than merging the results for which cells were tagged.

The problem is, that this operation is supposed to be as fast as possible. I can spare a few seconds for it, but not much more. So I would rather have one rendering pass that is a bit slower, than to repeat it 3 times.

So, any ideas are welcome. I have no knowledge of geometry shaders, but if they could be useful, that would be OK. Tesselation is out of the question, because I do not have the proper hardware.


Check out this paper from 1999. The approach they describe seems similar the one you propose. More recent papers on the same topic exist, and some of them make better use of the GPU. However, from your post it seems that you are just looking for something that works, at least in the short-term.

Never mind, I solved it using a geometry shader.

The GS takes triangles and outputs lines, which guarantee me a one-pixel wide rasterization. Additionally the GS knows the near and far clipping plane, clips the lines manually and inserts lines parallel to the clipping planes, to cap the output.

Now I only need to render the geometry twice (but from the same view-point), once filled and once with the lines as borders and that should be enough to properly tag all voxel cells.

@thinks: Thanks for the link, I’ll take a look at it.