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?
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
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
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.
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?
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.
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. :)
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.
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 
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?
