In Python, how do I voxelize a 3D mesh

Question

I need help on getting started in Python (which I almost know nothing of) to voxelize a 3D mesh generated from Rhino. The data input will be a .OBJ file and so will the output. The ultimate purpose for this usage is to find the shortest distance between two points within a building. But that's for later. As for now, I need to first voxelize a 3D mesh. The voxelization primitive may just be a simple cube.

so far I can read from a OBJ file parser and out of the parsed obj with V, VT, VN, F prefixes stripped, and using those coordinates to find the bounding box of 3D object. What should be the proper way to voxelize the mesh?

import objParser
import math

inputFile = 'test.obj'
vList = []; vtList = []; vnList = []; fList = []

def parseOBJ(inputFile):
list = []
vList, vtList, vnList, fList = objParser.getObj(inputFile)
print 'in parseOBJ'
#print vList, vtList, vnList, fList
return vList, vtList, vnList, fList

def findBBox(vList):
   i = 0; j=0; x_min = float('inf'); x_max = float('-inf'); y_min = float('inf');
   y_max =  float('-inf'); z_min = float('inf'); z_max = float('-inf');
   xWidth = 0; yWidth = 0; zWidth =0

print 'in findBBox'
while i < len(vList):
        #find min and max x value
        if vList[i][j] < x_min:
            x_min = float(vList[i][j])
        elif vList[i][j] > x_max:
            x_max = float(vList[i][j])

        #find min and max y value
        if vList[i][j + 1] < y_min:
            y_min = float(vList[i][j + 1])
        elif vList[i][j + 1] > y_max:
            y_max = float(vList[i][j + 1])

        #find min and max x value
        if vList[i][j + 2] < z_min:
            z_min = vList[i][j + 2]
        elif vList[i][j + 2] > z_max:
            z_max = vList[i][j + 2]

        #incriment the counter int by 3 to go to the next set of (x, y, z)
        i += 3; j=0

xWidth = x_max - x_min
yWidth = y_max - y_min
zWidth = z_max - z_min
length = xWidth, yWidth, zWidth
volume = xWidth* yWidth* zWidth
print 'x_min, y_min, z_min : ', x_min, y_min, z_min
print 'x_max, y_max, z_max : ', x_max, y_max, z_max
print 'xWidth, yWidth, zWidth : ', xWidth, yWidth, zWidth
return length, volume

def init():
    list = parseOBJ(inputFile)
    findBBox(list[0])

print init()

Answer 1

I haven't used it but you can try this one: http://packages.python.org/glitter/api/examples.voxelization-module.html

Or this tool: http://www.patrickmin.com/binvox/

If you want to do this by yourself you have two main approaches:

• A 'real' voxelization, when you take into account the mesh interior - rather complex and you need much of CSG operations. I can't help you there.

• A 'fake' one - just voxelize every triangle of your mesh. This is much simpler, all you need to do is to check the intersection of a triangle and axis-aligned cube. Then you just do:

  for every triagle:
      for every cube:
          if triangle intersects cube:
              set cube = full
          else:
              set cube = empty
  

All you need to do is to implement a BoundingBox-Triangle intersection. Ofcourse you can optimize those for loops a bit :)