7

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.

Hannesh
  • 7,256
  • 7
  • 46
  • 80

2 Answers2

8

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.

3Dave
  • 28,657
  • 18
  • 88
  • 151
  • I should've mentioned earlier, but the inside of the model needs to be filled in with voxels too. Although could I just keep adding voxels after hitting a poly until we hit another poly, assuming the suface is closed? – Hannesh Nov 27 '10 at 20:01
  • @Hannesh yes. The BSP will give you an "inside" or "outside" result for each point you check. There's no requirement that you stop creating voxels once you're inside a model, and you don't have to be aware of where one model stops and the next one starts. The nice thing about this approach is that, for a given XYZ value, you don't have to have any knowledge of anything that's happening around it. – 3Dave Nov 27 '10 at 20:05
  • Oh really?! :D That is the one thing I was worried most about. I need to be able to generate small chunks of the voxel field too, with a big chance of this chunk lying completely inside a model. I haven't used BSP trees before, but I think they're about to become my new best friend! – Hannesh Nov 27 '10 at 20:17
1

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

Edward83
  • 6,664
  • 14
  • 74
  • 102