Break down cubes into 8 smaller cubes recursively (when the cubes are defined by a mid point and size)

Question

I'm having trouble getting this working so a bit of help would be appreciated.

Short version: Given a mid point and size of a cube, I need to split it into 8 smaller ones (2x2x2), and possibly repeat for each of those. The resulting coordinates are the only thing that's needed.

I'm writing some octree style code, and I'm trying to allow it to accept inputs at different depths (depth relates to the spacing between points, which is 2^depth, eg. depth 0 has a 1 unit grid, depth -1 has 0.5, depth 1 has 2). I need it to be able to get a coordinate at a higher depth, and break it down into cubes that fit the actual depth.

For example, if I have the point (0,0,0) at depth 1, and the scene is depth 0, I need to break it into 8 pieces, and move each one +-0.5 units to fit it into the old cube (2^(depth-1)).

If the scene is at depth -1, I will need to break it into 8 pieces, then break those into 8 more pieces. I basically need it to give 8^(difference in depth) results, it sounds quite easy to do but it's totally stumped me with it going wrong.

#Set up structure
octreeRange = ( 1, -1 )
octreeStructure = set()
for x in octreeRange:
    for y in octreeRange:
        for z in octreeRange:
            octreeStructure.add( ( x, y, z ) )

#octreeStructure is the 8 coordinates that a cube can split into

def recursiveCoordinate( coordinate, coordinateInfo, minDepthLevel, octreeStructure ):

    newDictionary = {}

    #Turn into list if isn't already list
    if type( coordinateInfo ) != list:
        coordinateInfo = [coordinateInfo,minDepthLevel]

    coordinateDepth = coordinateInfo[1]

    #Run function again for each coordinate that has a depth too high
    if coordinateDepth > minDepthLevel:
        coordinateInfo[1] -= 1
        moveAmount = pow( 2, coordinateDepth-1 )
        for i in octreeStructure:
            newCoordinate = [i[j]*moveAmount+coordinate[j] for j in xrange( 3 )]
            newDictionary.update( recursiveCoordinate( newCoordinate, coordinateInfo, minDepthLevel, octreeStructure ) )

    else:
        newDictionary[tuple( coordinate )] = coordinateInfo

    return newDictionary

minDepthLevel = 0
grid = {}
#grid[(x, y, z)] = [block ID, depth level]
grid[(1.5,0,0)] = [1,2]

newGrid = {}
for coordinate in grid:
    newGrid.update( recursiveCoordinate( coordinate, grid[coordinate], minDepthLevel, octreeStructure ) )
print len( newGrid.keys() ) 

For a visual idea, take this image. The mid point is in the middle, defined at depth level 2, when the scene is level 0. The solid black lines are the first iteration, and the dashed lines would be the 2nd and final iteration. I'm needing the coordinates of all the mid points of the dashed line cubes.

I guess another method would be to calculate the size of the cube based on the depth, then split it into the required number of parts, but that would require 3 nested loops potentially going through thousands of values, so I'd like to avoid the nested loop way if possible.

Edit: A quick thing I did in paint as a 2D example, you can see why I thought it would have been super easy. The final result after 3 iterations on this would produce 64 coordinates that would fit in the scene.

Answer 1

I'm still not quite sure if this is what you want, but here is how I woud do it:

First, I would create a class representing points in 3D space:

class Point3D:
    """Representation of a point in 3D space."""
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

    def __add__(self, other):
        """Add two points.

        >>> Point3D(1, 2, 3) + Point3D(100, 200, 300)
        Point3D(101, 202, 303)
        """
        x = self.x + other.x
        y = self.y + other.y
        z = self.z + other.z
        return Point3D(x, y, z)

    def __mul__(self, a):
        """Multiply a point with a number.

        >>> Point3D(1, 2, 3) * 2
        Point3D(2, 4, 6)
        """
        x = self.x * a
        y = self.y * a
        z = self.z * a
        return Point3D(x, y, z)

    def __rmul__(self, a):
        """Multiply a number with a point.

        >>> 2 * Point3D(1, 2, 3)
        Point3D(2, 4, 6)
        """
        return self.__mul__(a)

    def __repr__(self):
        return 'Point3D({p.x}, {p.y}, {p.z})'.format(p=self)

This allows for more readable code when calculating center points of derived cubes.

Then I would create a class which represents cubes. Instances have the ability to be divided into eight parts and know about their "depth", which is reduced for the divided cubes.

The eight directions in which a center point must be shifted are obtained using itertools.product and are represented as Point3D objects with their individual coordinates set to -1/+1. (I have given the shorter name DIR to what you called octreeStructure.)

Cube objects have a helper function _divide which goes down one level, this is used in the recursive function divide which goes from the depth of the cube down to a target depth.

Note the two-dimensional list comprehension which is used to produce a flattened list.

from __future__ import division
from itertools import product

class Cube:
    """Representation of a cube."""

    # directions to all eight corners of a cube
    DIR = [Point3D(*s) for s in product([-1, +1], repeat=3)]

    def __init__(self, center, size, depth=0):
        if not isinstance(center, Point3D):
            center = Point3D(*center)
        self.center = center
        self.size = size
        self.depth = depth

    def __repr__(self):
        return 'Cube(center={c.center}, size={c.size}, depth={c.depth})'.format(c=self)

    def _divide(self):
        """Divide into eight cubes of half the size and one level deeper."""
        c = self.center
        a = self.size/2
        d = self.depth - 1
        return [Cube(c + a/2*e, a, d) for e in Cube.DIR]

    def divide(self, target_depth=0):
        """Recursively divide down to the given depth and return a list of
        all 8^d cubes, where d is the difference between the depth of the
        cube and the target depth, or 0 if the depth of the cube is already
        equal to or less than the target depth.

        >>> c = Cube(center=(0, 0, 0), size=2, depth=1)
        >>> len(c.divide(0))
        8
        >>> len(c.divide(-1))
        64
        >>> c.divide(5)[0] is c
        True
        >>> c.divide(-1)[0].size
        0.5
        """
        if self.depth <= target_depth:
            return [self]
        smaller_cubes = self._divide()
        return [c for s in smaller_cubes for c in s.divide(target_depth)]

Your example is done like this:

# minDepthLevel = 0
# grid = {}
# grid[(1.5,0,0)] = [1,2]
# not sure what this ^ 1 means

cube = Cube((1.5, 0, 0), 4, 2)
grid = {c.center: [1, c.depth] for c in cube.divide(0)}