# Convert points into an octree

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
calculatedGrid = convertCoordinates( grid, minDepthLevel )

#Get maximum depth level
xMax = max( calculatedGrid.keys(), key=itemgetter( 0 ) )
xMin = min( calculatedGrid.keys(), key=itemgetter( 0 ) )
yMax = max( calculatedGrid.keys(), key=itemgetter( 1 ) )
yMin = min( calculatedGrid.keys(), key=itemgetter( 1 ) )
zMax = max( calculatedGrid.keys(), key=itemgetter( 2 ) )
zMin = min( calculatedGrid.keys(), key=itemgetter( 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, relativeValues, relativeValues )

#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 and str( x ).isdigit() for x in allPointValues )
if everythingIsPoint:
editDictionary( octreeData, dictionaryPath[:-1]+[allPointValues] )
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 += startingCoordinates
newCoordinate += startingCoordinates
newCoordinate += startingCoordinates
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 ):
#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]
blockID = newList[coordinates]
newCube = pm.polyCube( h=cubeSize, w=cubeSize, d=cubeSize )
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.

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

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

• Thanks for the tips, with the names I always have a bit of trouble trying to summarise what they mean within a couple of words haha. The roundToMultiple one basically calculates the minimum exponent needed to have multiple^exponent higher than all the args. Your suggested way is quite good though, I was wondering how to get rid of the 2 closestPower=0`'s – Peter Mar 13 '15 at 14:18
• As to the except - is it mainly you don't do it because you want to see any other unrelated errors pop up, or is it because landing one of those errors (GeneratorExit, etc) and continuing could mess up the execution of the code later on? I get why it can lead to misdiagnosing an error, but is it still important if the code is working normally, and in this case, either needs to do the thing or return 0? – Peter Mar 13 '15 at 14:25