Converting a 3D model to a voxel field

Question

I need to write some code to convert an array of quads into a voxel field. Making it work should be easy, but making it fast won't be so trivial.

Does anyone know of any libs or source code that I can use? I'm sure someone must've done this before.

edit: The algorithm needs to fill the inside of the model with voxels too. Just a shell won't do.

Answer 1

The voxelation link posted by @Alexandre C. looks good.

Here's a brief overview of how we solved this problem when converting regular quad/triangle models to a cubical array of indices of refraction/epsilon values for a photonics/EM simulation.

1. Create a BSP tree of your scene. (Yes, really)
2. Iterate at regular intervals over X,Y,Z across your model or solution space. (The interval in each axis should be equal to the desired voxel dimensions.)

3. At each point in your x/y/z loop, check the point against the BSP tree. If it's inside an entity, create a voxel at that point, and set it's attributes (color, texture coordinates, etc) based on the source model (as referenced from your BSP node). (Optimization Hint: If your inner-most loop is along the Y axis (vertical axis) and you're creating terrain or an XZ-oriented surface, you can exit the Y loop whenever you create a voxel.)

4. Save

5. Profit!

Building the BSP is the only semi-complicated part (and it's a lot easier than it looks at first glance), but it's been documented out the ying-yang all over the web. This will work for pretty much any model shape, and also gives you a nice tree you can use for collision detection and visibility determination, among other things.

Also, note that this whole process should happen at compile time or using a dedicated tool (which would, obviously, produce a file containing the tree and voxel field that you would use at run time). If you're using XNA, it's pretty easy to import anything into the content pipeline.

Answer 2

Check Marching cubes algorithm. I guess you need reverse it in context of your problem!;)