Once I got the basic system of units that could be deformed and would gradually regenerate themselves, the next step was to implement a system to import custom meshes and turn them into these voxel units, or "voxelize" them. Basically this is just taking a model and filling it up with little boxes that can be destroyed individually. In the clip below you see a cat where the left half is the original model and the right half is the voxelized version of it:

In my voxel object system, every collection of voxels that make up one object, or

`VoxelUnit`

, is made up of a bounding box full of voxels that can be activated and deactivated as needed. Even something like a sphere is technically a full box of voxels, but the voxels that are not part of the sphere are made completely inactive and it's as if they were not a part of the shape.Although each step is very involved, there are, conceptually, only a few steps in actually voxelizing a model:

- import the model into a usable structure
- calculate the bounding box of the model and create an empty
`VoxelUnit`

- activate the voxels that intersect with the model's faces
- fill in the middle of the model if desired

I only implemented functionality to import .objs with triangular faces, but allowing for other formats should mostly just affect how the model is imported. It may also affect the detection of voxels intersecting faces if the faces are quads or a mixture of quads and tris.

I set up a simple struct to hold all of the mesh data in a way that would be easily accessible:

struct Obj

{

vector<Vector3> vertices;

//each tri is a vector of length 3 of the actual vertex values

//rather than a vertex index for ease of access

vector<vector<Vector3>> tris;

//the normal for each tri

vector<Vector3> normals;

//bounding box dimensions

Vector3 boxDimensions;

//the left, bottom, back corner of the model

Vector3 bottomLeftBack;

}

To determine the

`boxDimensions`

and `bottomLeftBack`

I keep track of the highest and lowest values in each dimension of the points as the bottom, left, back corner and top, right, front corner of the bounding box. These corner points do not necessarily correspond to a vertex, just the highest and lowest value of any vertex in the object in each dimension. Once all the vertices are loaded in, the `boxDimensions`

can be found by subtracting the bottom, left, back corner from the top, right, front corner. It is important to hold onto `bottomLeftBack`

for later to align our `VoxelUnit`

with the model vertices.The face normals will also be useful later for determining intersection with faces. You may be able to read them in from your model file, but I am just calculating them to be safe; to do that you simply find the cross product of the vectors that represent two of the sides and share a starting point:

for(int i=0;i<obj->tris.size();i++)

{

Vector3 u = obj->tris[i][1] - obj->tris[i][0];

Vector3 v = obj->tris[i][2] - obj->tris[i][0];

Vector3 norm = u.Cross(v);

norm.Normalize();

obj->normals.push_back(norm);

}

Once you have the model data in an accessible format it is time to create a

`VoxelUnit`

the size of the `Obj`

`boxDimensions`

. To do this I set up an additional constructor for `VoxelUnit`

that takes in an `Obj*`

and a voxel size so that it can construct the model using the `Obj`

to the level of detail as determined by the voxel size.The first thing that needs to be done is, given the dimensions of the bounding box of the model, determine how many voxels across the object will be in each direction. This is pretty straightforward, and very similar to determining it based on just dimensions, but you have to be a bit more careful and conservative about tweaking the dimensions to come to an even voxel count in each direction. Because the object is based on a model, we want to make sure the new bounding box will fully encompass the model.

VoxelUnit::VoxelUnit(Obj* obj,float voxelSize)

{

//just get the original necessary dimensions

mDimensions=obj->boxDimensions;

mVoxelSize=voxelSize;

//determine the number of voxels across each dimension will fit in the bounding box

mVoxelsDim=mDimensions/mVoxelSize;

//number of voxels must be an integer

//using the ceiling function so as not to round down and clip off parts of the model

mVoxelsDim=Vector3(ceil(mVoxelsDim.x),ceil(mVoxelsDim.y),ceil(mVoxelsDim.z));

//calculate new actual dimensions

mDimensions=mVoxelsDim*mVoxelSize;

//set the position to the center of the object for easier intersection checking

mPosition=obj->bottomLeftBack+(obj->boxDimensions/2);

}

Next you need to populate your

`Voxel`

array; this is the most involved and time-consuming part of the process because to determine whether or not each `Voxel`

is active I am checking finding each edge of each `Voxel`

and checking them against faces until it either finds one it intersects with, or runs out of faces to check.For each

`Voxel`

at index x,y,z:

//set a temporary depth and timer value

mVoxels[x][y][z].depth=EMPTY;

mVoxels[x][y][z].regenTimer=0;

//find the middle position of the voxel

Vector3 pos=mPosition-(mVoxelsDim*mVoxelSize/2);

Vector3 index(x,y,z);

pos+=index*mVoxelSize;

//find the upper and lower bounds of the individual voxel

Vector3 rightTopFront=pos+(Vector3(1,1,1)*(mVoxelSize/2));

Vector3 leftBottomBack=pos-(Vector3(1,1,1)*(mVoxelSize/2));

//holder for the edges

vector<vector<Vector3>> edges;

//holder for a single edge with two Vector3 endpoints

vector<Vector3> edge;

//find top right edge

edge.push_back(rightTopFront);

edge.push_back(Vector3(rightTopFront.x,rightTopFront.y,leftBottomBack.z));

edges.push_back(edge);

edge.clear();

//find bottom right edge

edge.push_back(Vector3(rightTopFront.x,leftBottomBack.y,rightTopFront.z));

edge.push_back(Vector3(rightTopFront.x,leftBottomBack.y,leftBottomBack.z));

edges.push_back(edge);

edge.clear();

//continue like this for each of the twelve edges

Who's that Pokemon? |

`Voxel`

's edges I checked each edge against every face in the model until one of them intersected or I ran out of faces. As you might imagine, that was very very very time consuming. To cut down on this time, I decided to generate an index range for each `Voxel`

edges would only be checked against faces whose bounding boxes in terms of `Voxel`

indices contained that `Voxel`

. This was incredibly effective at cutting down time. A low quality (high voxel size) import of my test teapot model went from taking upwards of half and hour to taking under a minute. This allowed me to decrease the voxel size, thus increasing the import quality, while keeping the import time reasonable.To find these index-based bounding boxes for each face, I first found the face's true-coordinate bounding box in very much the same way I did with the entire model, and then I used the

`VoxelUnit`

's traits to get the bounding box in terms of object-specific indices:

//create a local structure to hold the limits

struct Limits

{

Vector3 upper;

Vector3 lower;

};

//vector to hold the limits for all the faces

//want to hold onto them so they don't need to be recalculated

vector<Limits> indexLims;

//find limits for every face

for(int i=0;i<obj->tris.size();i++)

{

Limits lim;

//set limits to the upper and lower limits of the whole VoxelUnit

lim.upper=mPosition-(mDimensions/2);

lim.lower=mPosition+(mDimensions/2);

//narrow down to the limits of the actual limits of just the one face

for(int j=0;j<obj->tris[i].size();j++)

{

if(obj->tris[i][j].x>lim.upper.x)

lim.upper.x=obj->tris[i][j].x;

if(obj->tris[i][j].x<lim.lower.x)

lim.lower.x=obj->tris[i][j].x;

if(obj->tris[i][j].y>lim.upper.y)

lim.upper.y=obj->tris[i][j].y;

if(obj->tris[i][j].y<lim.lower.y)

lim.lower.y=obj->tris[i][j].y;

if(obj->tris[i][j].z>lim.upper.z)

lim.upper.z=obj->tris[i][j].z;

if(obj->tris[i][j].z<lim.lower.z)

lim.lower.z=obj->tris[i][j].z;

}

//the bottom, left, back corner of the VoxelUnit

Vector3 bottomCorner=mPosition-(mDimensions/2);

//find index values at the limits

lim.upper-=bottomCorner;

lim.lower-=bottomCorner;

lim.upper/=mVoxelSize;

lim.lower/=mVoxelSize;

//indices must be integers

lim.lower=Vector3((int)lim.lower.x,(int)lim.lower.y,(int)lim.lower.z);

//be conservative with upper limit so as to not cut off any results

lim.upper=Vector3(ceil(lim.upper.x),ceil(lim.upper.y),ceil(lim.upper.z));

indexLims.push_back(lim);

}

After having determined the index bounds for each face, a quick check to make sure the current

`Voxel`

index is within the face's index bounds before more in-depth checking can be put in place to significantly cut down on the voxelization time:

//for each Voxel at index x,y,z

for(int i=0;i<edges.size();i++)

{

bool collides=false;

//check each face

for(int j=0;j<obj->tris.size();j++)

{

//if the Voxel is outside of the face index bounds, skip this face

if(x>indexLims[j].upper.x || x<indexLims[j].lower.x

|| y>indexLims[j].upper.y || y<indexLims[j].lower.y

|| z>indexLims[j].upper.z || z<indexLims[j].lower.z)

continue;

//check triangle/segment collision to see if edge intersects face

collides=segmentTriangleCollision(obj->tris[j],

obj->normals[j],

edges[i]);

//if it does intersect, stop checking faces

if(collides)

break;

}

if(collides)

{

//fill it in if it's touching the model

mVoxels[x][y][z].depth=CENTER;

//voxel already active, stop checking edges

break;

}

}

Hollow teapot |

Teapot filled in |

`Voxel`

s that intersect with the model faces you will end up with a shell of the model. It will look like a voxelized version of the mesh until part of it is destroyed at which point you will see that it is hollow. This may be what you're going for in some cases, but I really was hoping to create solid objects. In order to do this I go through the newly generated `Voxel`

s and reevaluate each `EMPTY`

one. This involves checking to see whether there is an active `Voxel`

in both directions along each axis going through the `Voxel`

being looked at. If there is an active one at some point in every direction then that currently empty `Voxel`

is actually in the middle of the object and should be active.This solution is not without flaws, though. This will fill in any intentional holes in the model as well in any place which is completely encased in the rest of the object. Because of this, I have left the option of leaving the object hollow.

Hollow Object:

Solid Object:

A sheet of voxelized cat. |

Check back for more updates on this project. I plan to continue it by adding more robust, non-destructive collisions, so the objects could actually be used as terrain or other mobile assets. I also plan to, at some point, get most of the calculations running through the GPU using OpenCL for increased processing speed and efficiency.