Voxelizing mesh data: OBJ to Voxels

Introduction

The following documents a software tool to convert 3D models to voxelized versions. There are a number of reasons why one might want to do this. There are games that are voxel based, turning traditional mesh models into voxels allows them to be used in those environments. Low resolution voxel representations of meshes can be used to facilitate various physical simulations since they contain volume rather than just a skin of the object they represented. There are various operations that are much faster with voxel representations, these include ray tracing, visibility analysis and shadow generation. Besides computer graphics applications volumetric data is used across a wide range of scientific and engineering disciplines, although in those cases it is more common to create the volumetric data directly from real world scanners.

In this particular implementation the source 3D model is expected to be stored in the OBJ format and the destination model is saved as a vox model. The utility can also generate an output OBJ file and a scene file for PovRay, these later two are mostly intended for testing purposes. Other output 3D model formats can readily be supported, the underlying primitive is just a voxel (cubic 3D pixel) with a colour value or other material description.

There are some limitations of the vox format which impact the conversion process but are not inherent to this voxelation algorithm itself. For example, the vox format only has a 255 colour palette in the form of a lookup table. The software here creates such a palette for vox but could easily generate a wider colour space for other export formats.

This implementation is a simple command line utility, while fully functional it is mostly intended as a proof of concept of the approach taken. The usage string is as follows.

Usage: obj2vox [options] objfile
Options
   -n n   Maximum number of voxels on a side, default: 50
   -s n   Number of face subsamples, default: 100
   -v     Save vox file, default: off
   -o     Save obj file, default: off
   -p     Save povray file, default: off

The most fundamental parameter is the maximum number of voxel allowed in any one of the three orthogonal axes. This can range from 1 (simply a cube) upwards. The only real limitation is the memory requirements. The effect of different maximum voxels is shown below along with the original mesh model in the top left.

Figure 1: The effect of the -n command line option

Characteristics of the algorithm

• It may be surprising but the performance is not dependent on the density of the voxels, that is, a coarse voxelation or a dense voxelation take the same time to compute. This was a deliberate design goal since one does not want to be comparing every face with every voxel, fancy data tree structures not withstanding.

• The performance is linearly dependent on the number of triangles in the mesh and the degree of subsampling.

• Colour information is important, this is not just a geometry voxelation like many of the alternative solutions. The colour extracted from the mesh may be any of the three standard ways colour is expressed in the OBJ format. That is, a simple colour per face ("kd" value in OBJ material file), a per vertex colour (not part of the official OBJ format but a commonly used extension where the "v" vertex lines also contain 3 r,g,b values), or a texture map ("map_Kd" in the OBJ material file indexed by the uv coordinates defined on the OBJ "vt" lines).

  
  Figure 2: Example using a model with vertex colours

• The mesh need not be manifold, that is, the voxelation is applied to the mesh surface only and not the interior of enclosed spaces.

• The voxelated volume is transformed to the same coordinate system as the original mesh for OBJ and PovRay export. Of course, it would be easy to keep the voxels in their own coordinate system if that was required. vox models are always in voxel coordinates.

• The voxelation model is always larger than the corresponding mesh, that is, the mesh is entirely contained within the voxel model. Note this is generally true for all voxelation algorithms and not unique to this one.

• The extension to just point clouds would be trivial. Currently only the vertices indexed by faces are involved in the voxelation, but that could be readily relaxed.

• Do the meshes need to be oriented?
  Answer: No, but the voxels will be axis aligned. So one gets cleaner volumes for axis aligned meshes, the Mawson bust example example below isn't which is why the base is so jagged and the voxels are at an angle to the model "up" direction. I "think" this is best left as a human task, and for the intended applications it will only be applied to models with a sensible "up" orientations.

  
  Figure 3: The effect of a model not aligned to the coordinate system

• Are there cubes inside?
  Answer: No, it is not required for the purpose of the current application, indeed it was important that isolated surfaces could be voxelized, see door example.. It is a fairly easy 3D flood fill for a solid model (as required by some physics processes voxelized models are used for) but one has to be assured the mesh is manifold.

  
  Figure 4: Manifold meshes are not required, voxelation is applied to the surfaces

• What other solutions exist?
  Answer: There are lots of pure geometry voxelizations, they all seemed to have their own limitations. Some are computationally expensive, some only deal with point clouds, almost all did not handle textured meshes.

• Why choose vox format?
  Answer: vox is purely one choice of many and only chosen due to the immediate requirements of this project. vox is pretty limited in terms of colour especially, and it's a pain creating models with multiple chunks to get around the 256³ limit on volume size. But none of these limitations are fundamental to the current implementation, indeed the OBJ and PovRay exports can support any (within reason) voxel density, extent and colours.

• What is the main limitation?
  Answer: The main limitation, although most of the other solutions have the same issue, is the volume needs to reside in RAM. A voxel requires 5 bytes, an unsigned char flag and an unsigned int colour index. So a 256x256x256 volume (single vox chunk) is "only" 84MB. 1024³ is 5.4GB. For denser volumes, one could readily modify what I've done to create a sub volume multi-pass solution. For the current likely applications 256³ are likely to be sufficient.