Jump to content
  • Advertisement
_WeirdCat_

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?

IMG_20181106_204250.png

Share this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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?

Screenshot_20181107-194921.png

Screenshot_20181108-154527.png

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!