Octree Test
January 9th, 2010
That’s mathematics, son. You can argue with me, but you can’t argue with figures.
Commentary and code follows.
Commentary
A note about this octree code: it’s doing a lot of extra work for the visualization, partly because it looks cool and partly so that I’m sure to grok its every nuance while I work out the details.
You don’t need to draw cubes for an octree to work — in fact, it’s faster if you don’t. You just note the two defining points of a master bounding box, and define subdivisions of that box as all eight octants around its center. Any further subdivisions are just the same thing again: octants around the center of a subdivision, ad infinitum.
To reference any particular octree node, you only need know its octant path — e.g. “3, 7, 2, 1, 4″ — and the position and dimensions are inferred from the number of steps in the path (which is the number levels deep it is), as well as the octant path you took to get there. I’ll be working that up next, for use in my cubitecture code.
Pymel code:
This code places cubes randomly inside an ever-increasing range, checking for collisions with an octree.
### start octree test
### http://zoomy.net/2010/01/09/octree-test/
select(ado=1)
delete()
from pymel import *
import pymel.core.datatypes as dt
import random
global steps
steps = 0
global subnodes, contents, maxObjects, topNode, octantRef, stepNodes
stepNodes = {} # {node:step} -- creation step of each node, for animation
subnodes = {} # {node:[subnodes]}
contents = {} # {node:[objects]}
maxObjects = 10 # mamimum number of objects allowed per node
octantRef = {"---": 3, "--+": 5, "+-+": 4, "+--":2, "-+-": 1, "-++": 7, "+++": 6, "++-": 0} # which vertex to scale from, based on octant
def init():
global topNode, subnodes, stepNodes
topNode = polyCube(sz=1,sy=1,sx=1,d=1,h=1,w=1)[0]
stepNodes[topNode] = 0
subnodes[topNode] = [None, None, None, None, None, None, None, None]
contents[topNode] = []
# place a cube at random within an increasingly large range
def placeCube():
global steps
steps += 1
limit = steps
obj = polyCube(sz=1,sy=1,sx=1,d=1,h=1,w=1,name="c"+str(steps))[0]
xform(t=(random.uniform(-limit,limit),
random.uniform(-limit,limit),
random.uniform(-limit,limit)))
setKeyframe(obj, attribute = "visibility", v = 0, t = steps-1)
setKeyframe(obj, attribute = "visibility", v = 1, t = steps)
return obj
# detect if any part of obj bb is inside node bb
# detect if any part of obj bb is inside node bb
def inside(obj, node):
obb = obj.getBoundingBox()
nbb = node.getBoundingBox()
return obb.intersects(nbb)
# detect if obj bb is entirely inside node bb
def enclosed(obj, node):
bb = obj.getBoundingBox()
nbb = node.getBoundingBox()
# all the vertices of the bb
bbverts = [bb[0],
[bb[0][0], bb[0][1], bb[1][2]],
[bb[0][0], bb[1][1], bb[1][2]],
[bb[0][0], bb[1][1], bb[0][2]],
[bb[1][0], bb[1][1], bb[0][2]],
[bb[1][0], bb[0][1], bb[1][2]],
[bb[1][0], bb[0][1], bb[0][2]],
bb[1]]
for x in bbverts:
if not nbb.contains(x): return False
return True
# gets obj1's octant relative to obj2 in format [+++]
def getOctant(obj1, obj2):
loc1 = obj1.t.get()
loc2 = obj2.t.get()
quadString = ""
if loc1[0] > loc2[0]:
quadString = "+" # [+, , ]
else:
quadString = "-" # [-, , ]
if loc1[1] > loc2[1]:
quadString = quadString + "+" # [ ,+, ]
else:
quadString = quadString + "-" # [ ,-, ]
if loc1[2] > loc2[2]:
quadString = quadString + "+" # [ , ,+]
else:
quadString = quadString + "-" # [ , ,-]
return quadString
# split node into subnodes
def subdivide(node):
global subnodes, maxObjects, steps
# make a note of old pivot
oldLoc = node.getPivots()[0]
for i, item in enumerate(subnodes[node]):
if item == None: # replace "None" placeholders with nodes
# set new pivot based on octant, corresponding to i
vLoc = node.vtx[i].getPosition()
node.setPivots(vLoc)
new = node.duplicate()[0]
new.scale.set(node.scale.get()*.5)
subnodes[new] = [None, None, None, None, None, None, None, None]
contents[new] = []
subnodes[node][i] = new
steps += 1
stepNodes[new] = steps
# set pivot back for appropriate scaling animation
node.setPivots(oldLoc)
xform(node, cp=1) # center pivot
# reassign contents of the node into the new nodes
for i, subnode in enumerate(subnodes[node]):
for obj in contents[node]:
if inside(obj, subnode):
contents[subnode].append(obj)
contents[node] = []
# make the node a subnode of a new node, grown toward obj
def superdivide(node, obj):
global topNode, subnodes, octantRef, contents, steps, stepNodes
# determine which vtx to scale from using octantRef
octant = getOctant(obj, topNode)
i = octantRef[octant]
oldLoc = topNode.getPivots()[0]
vLoc = topNode.vtx[i].getPosition()
topNode.setPivots(vLoc)
oldTopNode = topNode
# while the point still isn't in the largest node, make a larger one
while not enclosed(obj, topNode):
steps += 1
new = duplicate(topNode)[0]
stepNodes[new] = steps
# make former topNode a subnode of new, with index based on octant
subnodes[new] = [None, None, None, None, None, None, None, None]
subnodes[new][i] = topNode
contents[new] = []
newScale = topNode.s.get()*2
new.scale.set(newScale)
topNode = new
# set pivots back for appropriate scaling animation
oldTopNode.setPivots(oldLoc)
contents[new] = [obj]
def findCollisions(obj):
global topNode, contents
if not inside(obj, topNode): return 0
for node in findNodes(obj):
for member in contents[node]:
if inside(obj, member):
return 1
return 0
# assuming obj is in octree, find nodes containing obj
# which have no subnodes that entirely contain obj
def findNodes(obj):
global topNode, subnodes
verified = [topNode] # list of nodes known to contain obj
toCheck = [topNode] # list of nodes to check for subnodes
again = 1
while again == 1:
again = 0
for node in toCheck:
# remove supernode from list of nodes to check
toCheck.remove(node)
# check each node's subnodes
for subnode in subnodes[node]:
# if it's found to be in a subnode
if (not subnode == None) and inside(obj, subnode):
verified.append(subnode)
# add node to list of nodes to check
toCheck.append(subnode)
again = 1
if enclosed(obj, subnode):
verified.remove(node)
return verified
# place obj in octree
def updateOctree(obj):
global topNode, maxObjects, subnodes, contents
# if obj isn't in the octree
while not enclosed(obj, topNode):
superdivide(topNode, obj) # expand tree
inNodes = findNodes(obj) # get nodes that contain obj
for node in inNodes:
if len(contents[node]) >= maxObjects: # if too full
# minimum scale = 1; this prevents infinitely small nodes for 10 objs in the same place - shouldn't happen if collision detection works properly
if node.scale.get()[0] > 1:
subdivide(node)
# otherwise update contents dict
elif not obj in contents[node]:
contents[node].append(obj)
def iterate():
maxTries = 25
for i in range(maxTries):
obj = placeCube()
if findCollisions(obj) == 0:
updateOctree(obj)
return 1
else: # couldn't find an empty space
delete(obj)
def promptNumber():
result = cmds.promptDialog(
title='Subdivide Octree',
message='Number of Iterations:',
text="50",
button=['OK', 'Cancel'],
defaultButton='OK',
cancelButton='Cancel',
dismissString='Cancel')
if result == 'OK':
return int(cmds.promptDialog(query=True, text=True))
else: return 0
number = promptNumber()
startTime=timerX()
init()
# progress bar, enabling "Esc"
gMainProgressBar = mel.eval('$tmp = $gMainProgressBar');
cmds.progressBar( gMainProgressBar,
edit=True,
beginProgress=True,
isInterruptable=True,
maxValue=number
)
# build cubes and octree
for x in range(number):
if cmds.progressBar(gMainProgressBar, query=True, isCancelled=True ) :
break
cmds.progressBar(gMainProgressBar, edit=True, step=1)
iterate()
cmds.progressBar(gMainProgressBar, edit=True, endProgress=True)
# then animate growth
gMainProgressBar = mel.eval('$tmp = $gMainProgressBar');
cmds.progressBar(gMainProgressBar, edit=True, beginProgress=True)
cmds.progressBar( gMainProgressBar,
edit=True,
beginProgress=True,
isInterruptable=True,
maxValue=len(stepNodes)
)
for x in stepNodes:
cmds.progressBar(gMainProgressBar, edit=True, step=1)
frame = stepNodes[x]
newscale = x.s.get()[0]
setKeyframe(x, attribute = "scale", v = 0, t = frame)
setKeyframe(x, attribute = "scale", v = newscale, t = frame+4)
cmds.progressBar(gMainProgressBar, edit=True, endProgress=True)
totalTime = timerX(startTime=startTime)
print("Total Time: "+str(totalTime))
select(cl=1)
# select all octree nodes for visual differentiation
for x in stepNodes:
select(x, add=1)
playbackOptions(min=0,max=steps+30)
currentTime(steps+30)
play()
### end
« previously: Expanding Octree | Home | next: The Cube of all Cubes »