Convert points into an octree

Question

I set about doing it as a challenge (and it's still far from finished) but I hit lots of problems. The main one that caused most of them was it can't deal with even numbers (it can be (1,1),(1,-1),(-1,1),(-1,-1), but nothing with a 0), so I had to multiply everything by 2 and add 1, which caused such a headache later on (which I won't bother going into as it should hopefully be fixed by now).

I don't know how they're normally coded anyway, so I just made it up as I went along until I had something that worked. Anyway, is the way I've done it alright, or is it not so good?

It calculates which path the points should take from the highest depth (eg. 9 = 16-8+4-2-1 or +1,-1,+1,-1,-1 ), and put them into the dictionary based on those values. If an entire branch (8 coordinates) gets filled, and all the blocks have the same ID, it'll go up a level, and set the branch to that ID to save space. Likewise, if there's nothing in it, it'll be set to False.

If you want to try out the code on a larger grid, scroll down a bit and there's a line to uncomment where it'll download a grid of 400k points (be warned, it took 70 seconds to process for me). Here's a picture of it in 3d, where I deleted a corner so you can see how it works.

#import pymel.core as pm
import math
from operator import itemgetter

minDepthLevel = 0

class EditError( Exception ):
    pass
def editDictionary( dictionaryName, listOfValues, canOverwriteKeys=True ):
    reducedDictionary = dictionaryName
    for i in listOfValues[:-2]:
        if type( reducedDictionary ) != dict and canOverwriteKeys:
            reducedDictionary = {}
        try:
            if reducedDictionary.get( i, None ) == None:
                canOverwriteKeys = True
                raise EditError()
            elif type( reducedDictionary[i] ) != dict:
                raise EditError()
        except EditError:
            reducedDictionary[i] = {}
        except:
            print "Something went wrong"
            return
        reducedDictionary = reducedDictionary[i]
    if canOverwriteKeys or ( not canOverwriteKeys and not reducedDictionary.get( listOfValues[-2], None ) ):
        reducedDictionary[listOfValues[-2]] = listOfValues[-1]
        return True
    else:
        return False

def roundToMultiple( multiple, *args ):
    maxPower = 0
    for i in args:
        if i:
            try:
                closestPower = int( math.ceil( math.log( abs( i ), multiple ) ) )
            except:
                closestPower = 0
        else:
            closestPower = 0
        if closestPower > maxPower:
            maxPower = closestPower
    return maxPower


grid = {}
grid[(0,0,0)] = 1
grid[(0,0,1)] = 1
grid[(1,0,0)] = 1
grid[(1,0,1)] = 1
grid[(0,1,0)] = 1
grid[(0,1,1)] = 1
grid[(1,1,0)] = 1
grid[(1,1,1)] = 1
grid[(3,0,-1)] = 1
grid[(10,0,-3)] = 1

grid[(2,1,1)] = 1
grid[(2,1,0)] = 1
grid[(2,0,1)] = 1
grid[(2,0,0)] = 1
grid[(3,1,1)] = 1
grid[(3,1,0)] = 1
grid[(3,0,1)] = 1
grid[(3,0,0)] = 5 #To demonstrate blocks not grouping if different ID


#Convert to new format that gets rid of even values
def convertCoordinates( dictionaryName, minDepthLevel=0 ):
    newDictionary = {}
    addAmount = pow( 2, minDepthLevel )
    for coordinate in dictionaryName.keys():
        newDictionary[tuple( i*2+addAmount for i in coordinate )] = dictionaryName[coordinate]
    return newDictionary

#Uncomment to use a grid of 400,000 points, it will take a while to calculate
#grid = cPickle.loads(zlib.decompress(base64.b64decode(urllib.urlopen("http://pastee.co/OQ5POF/raw").read()))); minDepthLevel = 0
calculatedGrid = convertCoordinates( grid, minDepthLevel )

#Get maximum depth level
xMax = max( calculatedGrid.keys(), key=itemgetter( 0 ) )[0]
xMin = min( calculatedGrid.keys(), key=itemgetter( 0 ) )[0]
yMax = max( calculatedGrid.keys(), key=itemgetter( 1 ) )[1]
yMin = min( calculatedGrid.keys(), key=itemgetter( 1 ) )[1]
zMax = max( calculatedGrid.keys(), key=itemgetter( 2 ) )[2]
zMin = min( calculatedGrid.keys(), key=itemgetter( 2 ) )[2]
maxDepthLevel = roundToMultiple( 2, xMax, xMin, yMax, yMin, zMax, zMin )

#Start octree dictionary
octreeRange = ( 1, -1 )
octreeStructure = set()
for x in octreeRange:
    for y in octreeRange:
        for z in octreeRange:
            octreeStructure.add( ( x, y, z ) )
octreeDepthName = "Depth"
octreeDataName = "Data"
octreeData = {"Depth":maxDepthLevel, "Data": dict.fromkeys( octreeStructure, False )}


originalCoordinates = dict.fromkeys( calculatedGrid.keys() )
for absoluteCoordinate in originalCoordinates.keys():
    #Find the path down the depth levels
    multiplierList = {0: [], 1: [], 2: []}
    for key in multiplierList.keys():
        maxMultiplier = pow( 2, maxDepthLevel )
        totalMultiplier = 0
        while maxMultiplier > pow( 2, minDepthLevel )*0.9:
            #Detect if it should be positive or negative
            currentMultiplier = maxMultiplier
            if absoluteCoordinate[key] > totalMultiplier:
                multiplierList[key].append( 1 )
            elif absoluteCoordinate[key] < totalMultiplier:
                multiplierList[key].append( -1 )
                currentMultiplier *= -1
            else:
                multiplierList[key].append( 1 )
                print "Something is wrong, coordinate value is even"
            #Append to total
            totalMultiplier += currentMultiplier
            maxMultiplier /= 2.0

    originalCoordinates[absoluteCoordinate] = multiplierList

#Write into dictionary
for relativeCoordinate in originalCoordinates:

    #Get the coordinates for each depth level
    relativeValues = originalCoordinates[relativeCoordinate]
    relativeCoordinates = zip( relativeValues[0], relativeValues[1], relativeValues[2] )

    #Fill with True
    dictionaryFix = [("Data")]*( len( relativeCoordinates )*2 )
    dictionaryFix[1::2] = relativeCoordinates
    dictionaryFix.append( calculatedGrid[relativeCoordinate] )
    editDictionary( octreeData, dictionaryFix )

    #Fill empty values with False
    currentDepth = 0
    maxDepth = octreeData["Depth"]-minDepthLevel
    while currentDepth < maxDepth:
        depthDictionaryPath = dictionaryFix[:-1]
        currentDictionaryDepth = reduce( dict.__getitem__, depthDictionaryPath[:-1-currentDepth*2], octreeData )
        for i in octreeStructure:
            if currentDictionaryDepth.get( i, None ) == None:
                currentDictionaryDepth[i] = False
                editDictionary( octreeData, depthDictionaryPath[:-1-currentDepth*2]+[i, False], False )
        #Fill in depth
        editDictionary( octreeData, depthDictionaryPath[:-2-currentDepth*2]+["Depth", currentDepth+minDepthLevel], False )
        currentDepth += 1

    #Move up a level if all values are 1
    dictionaryPath = dictionaryFix[:-2]
    while True:
        allValuesAtDepth = reduce( dict.__getitem__, dictionaryPath, octreeData )
        allPointValues = [allValuesAtDepth.get( coordinate, None ) for coordinate in octreeStructure]
        everythingIsPoint = all( x == allPointValues[0] and str( x ).isdigit() for x in allPointValues )
        if everythingIsPoint:
            editDictionary( octreeData, dictionaryPath[:-1]+[allPointValues[0]] )
            dictionaryPath = dictionaryPath[:-2]
        else:
            break


#Calculate points
def formatOctree( dictionaryValue, minDepthLevel, startingCoordinates=[0, 0, 0] ):
    allPoints = {}
    currentDepth = dictionaryValue["Depth"]
    depthMultiplier = pow( 2, currentDepth )
    #Amount to add to the position
    if minDepthLevel > 0:
        addAmount = 1-pow( 2, ( minDepthLevel-1 ) )
    else:
        depthIncrement = minDepthLevel+1
        addAmount = pow( 2, minDepthLevel )/2.0 
        while depthIncrement < 0:
            addAmount += pow( 2, depthIncrement )/2.0
            depthIncrement += 1
    differenceInDepth = currentDepth-minDepthLevel
    for key in dictionaryValue["Data"].keys():
        newCoordinate = [depthMultiplier*i for i in key]
        newCoordinate[0] += startingCoordinates[0]
        newCoordinate[1] += startingCoordinates[1]
        newCoordinate[2] += startingCoordinates[2]
        newDictionaryValue = dictionaryValue["Data"][key]

        if newDictionaryValue and str( newDictionaryValue ).isdigit():
            cubeSize = 2**currentDepth
            #Increment position if conditions are met
            if ( currentDepth and minDepthLevel >= 0 ) or ( currentDepth <= 0 and minDepthLevel < 0 ):
                moveCubeAmount = addAmount
            #Fix for strange behaviour when minDepthLevel = -1
            elif differenceInDepth > 0:
                moveCubeAmount = 1
                #Fix for stranger behaviour when minDepthLevel = -1 and it's a big generation
                if differenceInDepth > 1:
                    moveCubeAmount -= 0.25
            else:
                moveCubeAmount = 0

            totalMovement = tuple((i-1)/2+moveCubeAmount for i in newCoordinate)
            allPoints[totalMovement] = [cubeSize, newDictionaryValue]
        elif type( newDictionaryValue ) == dict:
            allPoints.update( drawCubes( newDictionaryValue, minDepthLevel, newCoordinate ) )
    return allPoints

newList = formatOctree( octreeData, minDepthLevel )

'''
for coordinates in newList.keys():
    cubeSize = newList[coordinates][0]
    blockID = newList[coordinates][1]
    newCube = pm.polyCube( h=cubeSize, w=cubeSize, d=cubeSize )[0]
    pm.move( newCube, coordinates )
    pm.addAttr( newCube, shortName = 'id', longName = "blockID", attributeType = "byte" )
    pm.setAttr( "{0}.id".format( newCube ), blockID )
''' 
import zlib, base64
inputLength = len( cPickle.dumps( grid ) )
octreeLength = len( cPickle.dumps( octreeData ) )
print "Length of input:  {0}".format( inputLength )
print "Length of octree: {0}".format( octreeLength )
print "{0}% efficiency".format( round( float( inputLength )/octreeLength, 2 )*100 )
print "Length of output:  {0}".format( len( cPickle.dumps( newList ) ) )

octreeData is self explanatory, and formatOctree( octreeData, depthLevel ) returns a list that you can use, in the format dictionary[(x,y,z)] = [block size, block ID].
minDepthLevel is the level in which it'll input the points from the grid, where the space between points is determined by \$2^{minDepthLevel}\$. It's best to leave this at 0 if you manually input stuff.

Answer 1

General comment

Python has a style guide called PEP 8. You are free to follow it or not but if except if you have a good reason, it's probably better to try to stick to it. Among other things, the naming convention is not followed.

You'll find tools to check your code (pep8) but also to fix it ([autopep8`]3). You'll also find various other tools to check your code quality : pylint, pychecker, pyflakes, etc.

In roundToMultiple

From Idioms and Anti-Idioms in Python

Because except: catches all exceptions, including SystemExit, KeyboardInterrupt, and GeneratorExit (which is not an error and should not normally be caught by user code), using a bare except: is almost never a good idea.

I'll let you think about it and catch only the relevant exceptions.

You can rewrite :

    if closestPower > maxPower:
        maxPower = closestPower

    maxPower = max(closestPower, maxPower)

Also, if I were you, I'd define a function like :

def roundToMultiple( multiple, i):
    maxPower = 0
    if i:
         try:
            return int( math.ceil( math.log( abs( i ), multiple ) ) )
        except:
            pass
    return 0

def max_power( multiple, *args ):
    return max(roundToMultiple(multiple, i) for i in args)

(The naming kind of sucks because I have no idea what these functions are supposed to be).