Break cubes into 8 small cubes recursively (when the cubes are determined by the midpoint and size)

Question

I am having problems getting this job, so it will be very helpful for us to help.

Short version: given the midpoint and size of the cube, I need to split it into 8 smaller ones (2x2x2) and, possibly, repeat for each of them. The resulting coordinates are the only thing needed.

I am writing an octree style code, and I am trying to allow it to accept inputs at different depths (depth refers to the distance between points, which 2^depth, for example, depth 0 has 1 unit of mesh, depth -1 has 0.5, depth 1 - 2). I need it so that it can get the coordinate at a higher depth and break it into cubes that correspond to the actual depth.

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

If the scene is at a depth of -1, I need to break it into 8 parts, and then break it into 8 parts. I basically need it to give results 8^(difference in depth), it sounds pretty easy, but it completely made me go 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 midpoint is in the middle, defined at depth level 2, when the scene is at level 0. Solid black lines are the first iteration, and dashed lines will be the second and last iteration. I need the coordinates of all the midpoints of the dashed lines.

, , , 3 , , .

: , 2D-, , , . 64 , .

Answer 1

, , , :

-, , :

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)

.

, . "", .

, , itertools.product Point3D , -1/+ 1. ( DIR , octreeStructure.)

_divide, , divide, .

, .

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)]

:

# 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)}