# How to implement a Cube 2: Sauerbraten octree?

I found this image of subdividing a cube based on octree model for the game "Cube 2: Sauerbraten octree". How can such an octree subdivision algorithm can be implemented?

I also need a generalized version of this which can be applicable for any rectangular cuboid having different length, width and height.

How can this be done?

Edit 1:

Consider a volume as

vol = ExampleData[{"TestImage3D", "MRbrain"}];


I can partition it in the following way:

{w, d, h} = ImageDimensions[vol];

Manipulate[ImagePartition[vol, {w/np, d/np, h/np}], {np, 1, 10, 1}]


This gives me a list of all the subvolumes. However, I cannot do the partition into the higher levels and display the partitions in the way as displayed in the mathematica demonstration or in the wikipedia image.

Edit 2:

ImageAssemble[
ImagePartition[vol, {w/2, d/2, h/2}] /.


This gives me

I can break one subpart as

ImageAssemble[
ImagePartition[
ImagePartition[vol, {w/2, d/2, h/2}][[1, 1, 2]], {w/4, d/4,
h/4}] /. i_Image3D :> ImagePad[i, 20, 0]]


And the corresponding result is:

I am still trying to figure it out how to assemble the second one replacing the corresponding part in the first image.

Edit 2:

Now I can split the volume at the second level.

temp = vol;
{w, d, h} = ImageDimensions[temp];
temp1 = ImagePartition[temp, {Floor[w/2], Floor[d/2], Floor[h/2]}];
temp2 = temp1[[1, 1, 2]];
temp3 = ImagePartition[temp2, {Floor[w/4], Floor[d/4], Floor[h/4]}];
temp3reconstructed =
ImageAssemble[temp3 /. i_Image3D :> ImagePad[i, 5, 0]];
temp1[[1, 1, 2]] =
ImageResize[
temp3reconstructed, {Floor[w/2], Floor[d/2], Floor[h/2]}];
temp1reconstructed =
ImageAssemble[temp1 /. i_Image3D :> ImagePad[i, 5, 0]]


and the output is:

• @Kuba I have looked into the quadTree implementation (demonstrations.wolfram.com/QuadtreeSubdivision) and this wikipedia pages (en.wikipedia.org/wiki/Octree; en.wikipedia.org/wiki/Cube_2:_Sauerbraten) – Majis Jan 29 '18 at 13:53
• @Kuba The quadTree implementation only works for square images. – Majis Jan 29 '18 at 13:54
• Have you tried implementing anything, or do you want us to write the whole thing for you and give you the code? – user484 Jan 29 '18 at 14:41
• @Rahul See my edit. This is what I have done so far and I am still trying to progress further. Whenever I reach up to anything, I will update. – Majis Jan 29 '18 at 15:21