donky

#

# Initial octree covers (0, 0, 0) to (63999, 63999, 63999)

BASE_SIZE = 64000


class Octree:
    def __init__(self):
        self.outer_calls = 0
        self.max_outer_calls = 4
        self.octree = OctreeLevel(self, size=64000, pos0=(0, 0, 0))

    def get_outer_level(self, level, pos, value, idxs):
        self.outer_calls += 1
        if self.outer_calls > self.max_outer_calls:
            raise RuntimeError("Too deep")

        outerSize = level.size * 2

        # We want to set the outer corner of the new outer box to
        # encompass the existing quadrant, but expanding in the
        # direction of the position we wish to insert at.
        outerPos0 = []
        for i, offset in enumerate(level.pos0):
            sign = idxs[i]
            if sign < 0:
                # Extend in the negative direction one quadrant
                # meaning we keep the child quadrant within us.
                outerPos0.append(offset + sign * level.size)
            else:
                # We naturally extend in the positive direction
                # by having double the size of the child quadrant,
                # so we can just share this axis' base offset.
                outerPos0.append(offset)

        outerLevel = OctreeLevel(self, outerSize, tuple(outerPos0))
        outerLevel.insert_existing_quadrant(level)
        self.octree = outerLevel
        return outerLevel

    def __getattr__(self, attrName):
        return getattr(self.octree, attrName)

class OctreeLevel:
    def __init__(self, parent, size=None, pos0=None):
        self.parent = parent

        self.size = size
        self.pos0 = pos0
        self.posC = (pos0[0] + size/2, pos0[1] + size/2, pos0[2] + size/2)

        self.quadrants = None
        self.values = {}

    def insert_existing_quadrant(self, level):
        if self.quadrants is None:
            self.quadrants = [ None for i in range(8) ]
        # Validate that this level is a sub-quadrant of ours.
        for i, offset in enumerate(level.pos0):
            if offset < self.pos0[i] or offset >= self.pos0[i] + self.size:
                raise RuntimeError("Bad sub-quadrant")
        idx = calc_quadrant_index(self.posC, level.posC)
        self.quadrants[idx] = level

    def insert(self, pos, value):
        # Detect the case where we are outside of this level.
        idxs = []
        for i, offset in enumerate(pos):
            # If this is the case, we want to know the axis and the
            # direction we need to expand (i and sign respectively).
            sign = 0
            if offset < self.pos0[i]:
                sign = -1
            elif offset >= self.pos0[i] + self.size:
                sign = 1
            idxs.append(sign)

        # Check if the position falls outside any of the box walls.
        if idxs != [0,0,0]:
            print "getting outer level", pos, value, "level was", (self.pos0, self.size), "indicator", idxs
            level = self.parent.get_outer_level(self, pos, value, idxs)
            return level.insert(pos, value)

        if self.size != BASE_SIZE:
            idx = calc_quadrant_index(self.posC, pos)
            if self.quadrants is None:
                self.quadrants = [ None for i in range(8) ]
            quadrant = self.quadrants[idx]
            if quadrant is None:
                innerSize = self.size / 2
                # We need to work out where the outer corner of the sub-quadrant
                # the position falls into is, so we can create it properly.  Our
                # quadrant index is a reverse bit field of axis sign, so we can
                # use that to help us.
                innerPos0 = list(self.pos0)
                for i in range(3):
                    if idx & (1 << i):
                        innerPos0[i] += innerSize
                print "CREATE-QUADRANT", self.pos0, innerPos0
                self.quadrants[idx] = quadrant = OctreeLevel(self, innerSize, tuple(innerPos0))
            else:
                print "EXISTS-QUADRANT", self.pos0, quadrant.pos0

            print "level is", (self.pos0, self.size), "idx", idx, "getting inner level of", (quadrant.pos0, quadrant.size)
            return quadrant.insert(pos, value)

        if self.values is None:
            self.values = {}

        xValue = pos[0] - self.pos0[0]
        if xValue < 0 or xValue >= BASE_SIZE: raise RuntimeError("Bad value")
        if xValue not in self.values:
            self.values[xValue] = {}

        yValue = pos[1] - self.pos0[1]
        if yValue < 0 or yValue >= BASE_SIZE: raise RuntimeError("Bad value")
        if yValue not in self.values[xValue]:
            self.values[xValue][yValue] = {}

        zValue = pos[2] - self.pos0[2]
        if zValue < 0 or zValue >= BASE_SIZE: raise RuntimeError("Bad value")
        if zValue not in self.values[xValue][yValue]:
            self.values[xValue][yValue][zValue] = value

        print "inserted", value, "at", pos, "level was", (self.pos0, self.size)

    def lookup(self, pos):
        pass


def calc_quadrant_index(vec1, vec2):
    bits = 0
    for i in range(3):
        v = vec2[i] - vec1[i]
        if v >= 0:
            bits |= 1 << i
    return bits

if __name__ == "__main__":
    print "BEGIN"
    o = Octree()
    o.insert((100000, 100, 100), "TEST-VALUE")
    o.insert((-100000, 100, 100), "TEST-VALUE")
    print "END"