# Voxel data to mesh data

## Recommended Posts

Basically i have a set of images that produce a 3d object (raytracing)

Now that i have this situated in a 3d grid, i would like to produce a mesh from it. One could just create a box for each pixel but this will reduce drawing  speed.

Im looking for a way to match these pixel boxes into bigger ones. Any ideas?

##### Share on other sites

Put those voxels into floating point volume (still 1s or 0s), blur it so values become smooth, use marching cubes to get triangles.

To improve quality of triangles you could finally use something like this: https://github.com/wjakob/instant-meshes

##### Share on other sites

I dont know what actually marching cubes produce but i need to get a set of convex hulls, instead of triangles themselves, so my idea is to somehow create bigger boxes out of smaller ones

##### Share on other sites
8 hours ago, _WeirdCat_ said:

Im looking for a way to match these pixel boxes into bigger ones. Any ideas?

What I do is build an octree top down.  You start out with one cube containing the whole object, then see where the data is, and then subdivide it into eight smaller cubes. Wash, rinse and repeat until you get to the level you want. If you want the size of your new smallest cubes to match exactly your original ones, you can just make the starting big cube a power of two of your original size.

##### Share on other sites

What do you mean to subdivide a cube into 8 smaller ones, not to mention that cube has 6 sides so wherr are additional 2? Where i subdivide that and what will be the result

Let me show you sample pics lets say selected red cube is a pixel where data is now how do i subdivide that and where?

##### Share on other sites

It's called an octree.

https://en.wikipedia.org/wiki/Octree

If you look at a cube you can fit 8 smaller cubes with an edge length of half the size exactly inside it.  Then you can take each one of those cubes and do the same thing. The trick is you only do it to cubes that have data inside them.

Edited by Gnollrunner

##### Share on other sites

Oh i see it now, however this should need another algorithm that merges cubes, what do you mean by wash rinse repeat)?

Dividing space into smaller cubes than cell size seems a waste of data.

I need some kind of inverse octree generation ;p where you merge these 8 into one. :)

##### Share on other sites

Let me be a bit more explicit....

First thing you do is get the size of your original object in voxels. We'll call it I, J, K.

Now you take the maximum  of I, J and K and round that up to the nearest power of 2. For example if your object is 490 by 496 by 832 voxels, the largest is 832 and you round that up to 1024. We'll call that number S...

Now you calculate the depth of your octree, call it D.  So that is 2^(D-1) = S. So for 1024, D=11, including the root voxel. You can just do some calculation on the highest order bit number of S to get D. You can do a loop and bit shifts and mask to get the number easily. I think you might have to add or subtract one in places.

Now you can create a coordinate system you can use to address voxels. Each one has 3 coordinates like your original voxels. Also each level of the tree has it's own coordinate system.  In the top level there is only one voxel so it's (0 to 0,0 to 0, 0 to 0),  For the second level you have eight voxels so each one has coordinates ranging from (0 to 1,0 to 1, 0 to 1). The third level has (0 to 3, 0 to 3, 0 to 3), the fourth has (0 to 7, 0 to 7, 0 to 7) ...... all the way to (0 to 1023, 0 to 1023, 0 to 1024) ....

But how do you generate these numbers? It's easy, every time you subdivide a voxel. The new numbers are based on it's parent. So if the parent has (IP, JP, KP) the children's voxel coordinates are as follows:

Child 0 = (IP*2,    JP*2,       KP*2    )
Child 1 = (IP*2+1, JP*2,      KP*2    )
Child 2 = (IP*2    , JP*2+1,  KP*2    )
Child 3 = (IP*2+1, JP*2+1,  KP*2    )
Child 4 = (IP*2,     JP*2,      KP*2+1)
Child 5 = (IP*2+1, JP*2,      KP*2+1)
Child 6 = (IP*2    , JP*2+1,  KP*2+1)
Child 7 = (IP*2+1, JP*2+1,  KP*2+1)

So now each of our children has coordinates. So what do we do with them?  We subdivide our tree all the way down to level D, but we do it recursively in a "depth first" traversal.  Once we get to  leaf voxels,  we can use the child's coordinates to check the original voxel matrix which you provided, and it's coordinates will exactly match your matrix! (assuming I didn't mess up).

So let's talk about subdivision. We allocate 8 new voxels and have the parent point to them. Then we call a recursive function on each of them. Once we get to the leaf voxels we grab data from the original table using our coordinates. If there is data, save it in the voxel and our function returns true, if not, our function returns false.  When we return to the parent function, it deletes all child voxels for which it's function returned false. If they all return false we delete them all and that function itself returns false to it's parent. If there is at least one with a sub-voxel remaining (i.e. there is data below) it returns true.

So now when we get back to the top we have our octree with your skull in it.  The leaf nodes have I, J, K indexes which you can easily translate into X,Y, Z however you like.  You can also calculate the X, Y, Z bounds of your higher level nodes with a a simple calculation using depth and that will work for ray tracking nicely.

Edited by Gnollrunner

##### Share on other sites
On 11/6/2018 at 9:59 PM, _WeirdCat_ said:

I dont know what actually marching cubes produce but i need to get a set of convex hulls, instead of triangles themselves, so my idea is to somehow create bigger boxes out of smaller ones

Marching cubes and marching tetrahedra will generate the surface of the voxel set, as a triangle list; the so-called "iso-surface."

You could then generate lower LOD levels from this. Or do you mean that you wish to keep the cubic appearance of the mesh, but reduce triangle count, without changing the appearance? The easiest way of doing this would probably be to pre-process the voxel field and remove all the interior voxels, before generating the geometry.

But well, what is your goal? To reduce the number of draw calls? Transform fewer vertices? Reduce overdraw? Save memory? Need to know what we're optimizing for, here

##### Share on other sites
37 minutes ago, Gnollrunner said:

Let me be a bit more explicit....

First thing you do is get the size of your original object in voxels. We'll call it I, J, K.

Now you take the maximum  of I, J and K and round that up to the nearest power of 2. For example if your object is 490 by 496 by 832 voxels, the largest is 832 and you round that up to 1024. We'll call that number S...

Now you calculate the depth of your octree, call it D.  So that is 2^(D-1) = S. So for 1024, D=11, including the root voxel. You can just do some calculation on the highest order bit number of S to get D. You can do a loop and bit shifts and mask to get the number easily. I think you might have to add or subtract one in places.

Now you can create a coordinate system you can use to address voxels. Each one has 3 coordinates like your original voxels. Also each level of the tree has it's own coordinate system.  In the top level there is only one voxel so it's (0 to 0,0 to 0, 0 to 0),  For the second level you have eight voxels so each one has coordinates ranging from (0 to 1,0 to 1, 0 to 1). The third level has (0 to 3, 0 to 3, 0 to 3), the fourth has (0 to 7, 0 to 7, 0 to 7) ...... all the way to (0 to 1023, 0 to 1023, 0 to 1024) ....

But how do you generate these numbers? It's easy, every time you subdivide a voxel. The new numbers are based on it's parent. So if the parent has (IP, JP, KP) the children's voxel coordinates are as follows:

Child 0 = (IP*2,    JP*2,       KP*2)
Child 1 = (IP*2+1, JP*2,      KP*2)
Child 2 = (IP*2    , JP*2+1,  KP*2)
Child 3 = (IP*2+1, JP*2+1,  KP*2)
Child 4 = (IP*2,     JP*2,      KP*2)
Child 5 = (IP*2+1, JP*2,      KP*2)
Child 6 = (IP*2    , JP*2+1,  KP*2)
Child 7 = (IP*2+1, JP*2+1,  KP*2)

So now each of our children has coordinates. So what do we do with them?  We subdivide our tree all the way down to level D, but we do it recursively in a "depth first" traversal.  Once we get to  leaf voxels,  we can use the child's coordinates to check the original voxel matrix which you provided, and it's coordinates will exactly match your matrix! (assuming I didn't mess up).

So let's talk about subdivision. We allocate 8 new voxels and have the parent point to them. Then we call a recursive function on each of them. Once we get to the leaf voxels we grab data from the original table using our coordinates. If there is data, save it in the voxel and our function returns true, if not, our function returns false.  When we return to the parent function, it deletes all child voxels for which it's function returned false. If they all return false we delete them all and that function itself returns false to it's parent. If there is at least one with a sub-voxel remaining (i.e. there is data below) it returns true.

So now when we get back to the top we have our octree with your skull in it.  The leaf nodes have I, J, K indexes which you can easily translate into X,Y, Z however you like.  You can also calculate the X, Y, Z bounds of your higher level nodes with a a simple calculation using depth and that will work for ray tracking nicely.

I've only looked quickly at your solution (way too early for more) but it looks like you're describing a culling system to be able to extract a minimum set of voxels to test for intersection when ray-tracing? I got the impression that OP was done with the voxel raytracing and now wanted to generate a mesh, and render it somehow?

## Create an account

Register a new account

1. 1
Rutin
25
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633311
• Total Posts
3011306
• ### Who's Online (See full list)

There are no registered users currently online

×