This post was originally published on my previous blog
A few words on Voxelization and SAT
In this post we will create a script for voxelize any kind of mesh in unity. Voxelization could be useful in physical simulations, terrain representation and every situation where we need to manipulate the hollow inside of a mesh. A great post about Voxelization can be found “here”, on Wolfire blog. The post explains how the voxelization of a triangle mesh is done in Overgrowth, we will use the same method in unity.
The creation of a voxel model that reproduces the mesh is achived trough a 3d grid of cubes and an intersection test for each triangle against each cube. The author states that he uses a AABB-AABB intersection test to check if a cube and a triangle are intersected. This is very fast and appropriate for most situations, but we want the general solution.
A slower but precise way to test the intersection is to use the Separating Axis Theorem. This paper explains the use of the SAT for Triangle-AABB intersection.
An implementation in C++ of this algorithm was written by Mike Vandelay and can be found planet-source-code.com. I rewrote the same code in unityscript.
Basically the SAT works like this
Take 13 axes: 3 axes are the cube face normals, 1 axis is the triangle face normal, 9 are the dot product between the first 3 axes and the triangles edges.
Project the AABB and the triangle on each axis. If the projections intersects on an axis, then the AABB and the triangle are intersected, otherwise they aren’t. here a much more detailed explanation of the SAT.
Now, let’s see how implement all this in unity.
The complete script for voxelization can be found here on my github.
We are going to use a grid for creating a voxel model. Each Grid is formed by cubes of the same size, these are the grid properties:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
All the public method call a CheckBound() function that check if the cube specified by the x, y, z variable is inside the grid, then the real implementation of the method is called. e.g.
1 2 3 4 5 6 7 8
Off course, inside the AABCGrid class and in the possible inheritors, only the unchecked method should be called for faster code.
Creating the voxel shell
Once the grid is defined, we need to ‘set’ all the cubes that are intersected by a triangle of the mesh. This is done in the AABCGrid.FillGridWithGameObjectMeshShell() method.
The result will be a voxel shell, an empty shape that reproduces the mesh.
Ignore the part relative to the normals of the triangles, I’m going to explain that later.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
The code finds the AABB of each triangle (2), then performs the SAT intersection test on each cube intersected by AABB (3).
triangles (1) the triangle in the grid. (2) the triangle with its AABB and the AABCs intersected by the AABB. (3) the AABCs intersected by the triangle
Filling the hollow inside
When this method is finished we will have a voxel model that reproduce the mesh. But we have not finished yet, we may need also to know which voxel (AABC) is inside the mesh and which is out. In order to do that we use the scan fill algorithm like the post on overgrowth blog explains, except for a little thing: we don’t start to fill the cube when the normal of the last triangle faces to the left, instead we mark ‘Begin’ and ‘End’ cubes in FillGridWithGameObjectMeshShell(). If the z component of the triangle is positive, we decrease cubeNormalSum[x, y, z] by one, else we increase it. When all the triangles have been processed, a positive cubeNormalSum means that the cube is a ‘Begin’ cube, if it is negative then the cube is an ‘End’ cube.
We can’t just check the normal of the last triangle because we don’t know the order of the triangles, we neither traverse the entire grid during the creation of the voxel shell.
The method FillGridWithGameObjectMesh() does the real scan lining once that FillGridWithGameObjectMeshShell() ends. It traverses all the grid, starting from the cube at 0, 0, 0. If a ‘Begin’ cube is found, an ‘End’ cube is searched. If an ‘End’ cube is found, all the cubes between the last ‘Begin’ and ‘End’ are set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
Performance are mainly determined by the number of triangles in the mesh and the side length of the AABCs. Here they are some of the tests made on my laptop:
Laptop specs: HP g6-1359el Intel Core i5-2450M - 2,5 GHz AMD Radeon HD 7450M
Mesh: construction_worke Time spent: 0.4051636s Triangles: 4020 Cube side: 0.05
Mesh: construction_worker Time spent: 1.088864s Triangles: 4020 Cube side: 0.02
Time spent: 1.926165s Triangles:760 Cube side: 0.03
Memory could be saved storing cubeSet using a 3D bitarray class and cubeNormalSum using a 3D array of bytes
Try it yourself
For testing purpose there is also a VoxelizationTest.js script on my github. Attach it to an object with a mesh to try this voxelization script. Remember to enable Gizmos in the game window, otherwise the AABCs will not appear!