Create mapping from voxel grid cube to connected edges

Accelerated Computing CUDA CUDA Programming and Performance
1

Hi all,

Right now I have a voxelgrid of cubes, and each cube shares edges with neighboring cubes. I want to have one large edge array, which has all the shared cube edges in the grid. And I want a mapping such that for each cube, it has 12 pointers into the edge array. I can figure this out in 2d easily because its easy to draw, but 3d is a little crazier. Anyone have any advice on how to approach this?

Some background on why I need this: I’m currently using the CUDA SDK Marching Cubes example, but currently it generates triangles as one large vertex array where every 3 vertices defines a triangle. What I want is the more traditional approach, where you have one vertex array, and then an index array where the elements reference the vertex array. That way I can easily make smooth vertex normals by averaging connected faces. If its just one giant vertex array there is no efficient way to find all the triangles connected to a vertex.

Since all the vertices generated in marching cubes lies on the cube edges of the voxel grid, I can just use this edge array as my vertex array. But the tricky part is how to actually make this array and the mapping from voxel->edge array

Thank you!
Bobby

2

How many edges the cube has? You will be surprised but the answer is 3. Imagine 3 edges coming from the corner of the cube with lowerest coordinates. Then all other edges just belong to other cubes. If our cube has coordinates (x,y,z), the neiboring cubes have coordinates (x+1,y,z), (x,y+1,z), (x,y,z+1), (x+1,y+1,z), (x+1,y,z+1), (x,y+1,z+1). You can imagine the edge as a vector. Then the corner of the cube have edges (1,0,0), (0,1,0), (0,0,1). The cube with coordinates (x+1,y,z) have edges (0,1,0) and (0,0,1) that belong to our cube. The cube (x+1,y+1,z) has only one edge (0,0,1) that belongs to our cube. So if you store 4 elements for the cube you can access them like that:

edge1 = cube[x][y][z][0];

edge2 = cube[x][y][z][1];

edge3 = cube[x][y][z][2];

edge4 = cube[x+1][y][z][1];

edge5 = cube[x+1][y][z][2];

edge6 = cube[x][y+1][z][0];

edge7 = cube[x][y+1][z][2];

edge8 = cube[x][y][z+1][0];

edge9 = cube[x][y][z+1][1];

edge10 = cube[x+1][y+1][z][2];

edge11 = cube[x+1][y][z+1][1];

edge12 = cube[x][y+1][z+1][0];

Now which points edge7 connect? The answer is (x,y+1,z) and (x,y+1,z)+(0,0,1)=(x,y+1,z+1).

Now which cubes edge7 connect? It is more harder. We see that coordinate z is changes along the edge this means that neibour cube has the same z coordinate. Now all others coordinates change. Where we have +1, the cube has large coordinate. Where we have +0, the cube has smaller coordinates. So the edge connects cubes (x,y,z) and (x-1,y+1,z). Other 2 cubes that has the same edge are (x,y+1,z) and (x-1,y,z).

3

This is a tricky problem. If you just want smooth normals you could evaluate the gradient of the density field you’re generating the mesh from.