Egg Octree
This code allows to split an Egg object and build an octree.
What is an Octree ? (from Wikipedia)
An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants.
How does this implementation work ?
Give it an egg object, with a vertexpool and a list of vertices. You also give a minimum cell size. A new egg object is created, with a tree containing all the cells. The cells are in fact the leaves of the tree : they are small geoms containing a list of vertices.
Why do I need it ?
This code will be useful if you use big geoms in Panda (for example, a single terrain mesh). Panda performs culling at the geom level, so if you add a big geom to the scenegraph, Panda will display and collide 100% of it. Dividing the geometry can speed up the display and the collisions.
If you’re not convinced, I succeeded in colliding a sphere against a 50 000 polys mesh, at 200~350 fps on a 1.8gz cpu with a nVidia Go 7400. Just give a try with a single geom 
How to use it ?
-
Display : divide your mesh in large cells, so that the number of cells does not exceed a dozen. Indeed, sending too many nodes to the render is quite expensive
-
Collision : divide the mesh as much as you want ! I tried with thousands of cells successfully. Actually, searching a cell in a tree is much faster than in a 3d array. Since the collision data is not displayed, we’re not stuck with the number of graphical nodes limitation
Hi,
Here is a class (well, a function packed into a class) that builds an octree from a source EggData.
It actually determines for each tree leaf all the contained triangles, nothing more. By “contains” I intend : “has its AABB containing the triangle center”.
It’s not optimized and quite slow when building octrees on big meshes (approx. 1 minute for a 20 000 triangles mesh). Anyway the octree can be saved to the egg format.
Updated on 2007-03-20 :
It’s now optimized with spatial indexation, so the generation of the octree is very fast
Updated on 2007-03-25 :
Solved the test bug in the recursive function
EggOctree.py
from pandac.PandaModules import *
import math
class EggOctree(object):
def build(self, sourceNode, destNode, cellSize, collide=False):
snode = sourceNode
snode.triangulatePolygons(0xff)
# First, extract the <VertexPool>
vpool = snode.getFirstChild()
assert type(vpool) == EggVertexPool, 'First child must be a <VertexPool>'
# Loop on the vertices determine the bounding box
minBB = Point3D()
maxBB = Point3D()
nverts = vpool.getHighestIndex()
for iv in range(nverts + 1) :
vtx = vpool[iv]
vtxPos = vtx.getPos3()
# Sets the X, Y or Z components
i = 0
for set in [Point3D.setX, Point3D.setY, Point3D.setZ] :
if vtxPos[i] < minBB[i] :
set(minBB, vtxPos[i])
if vtxPos[i] > maxBB[i] :
set(maxBB, vtxPos[i])
i += 1
minBB -= Vec3D(0.001, 0.001, 0.001)
maxBB += Vec3D(0.001, 0.001, 0.001)
# Number of leaves x,y,z
bboxSize = maxBB - minBB
self.ncx = math.ceil(bboxSize.getX() / cellSize.getX())
self.ncy = math.ceil(bboxSize.getY() / cellSize.getY())
self.ncz = math.ceil(bboxSize.getZ() / cellSize.getZ())
# Depth of the tree x,y,z
self.depthX = math.ceil(math.log(self.ncx) / math.log(2))
self.depthY = math.ceil(math.log(self.ncy) / math.log(2))
self.depthZ = math.ceil(math.log(self.ncz) / math.log(2))
self.depth = max(self.depthX, self.depthY, self.depthZ)
self.cells = [[[
{'min':
Point3D(minBB.getX() + x * cellSize.getX(),
minBB.getY() + y * cellSize.getY(),
minBB.getZ() + z * cellSize.getZ()),
'max':
Point3D(minBB.getX() + (x+1) * cellSize.getX(),
minBB.getY() + (y+1) * cellSize.getY(),
minBB.getZ() + (z+1) * cellSize.getZ()),
'group':EggGroup('leaf_%d_%d_%d' % (x,y,z)) }
for z in range(self.ncz)]
for y in range(self.ncy)]
for x in range(self.ncx)]
print 'Cell grid is %dx%dx%d' % (len(self.cells), len(self.cells[0]), len(self.cells[0][0]))
if collide :
for x in range(self.ncx) :
for y in range(self.ncy) :
for z in range(self.ncz) :
self.cells[x][y][z]['group'].addObjectType('barrier')
# Iterate on the <Polygon>s (should be triangles)
poly = snode.getNextChild()
while poly != None :
if isinstance(poly, EggPolygon) :
# Get the triangle center
polyCenter = Point3D(0,0,0)
for i in range(3) :
polyCenter += poly.getVertex(i).getPos3()
polyCenter /= 3.0
# Add the triangle to the corresponding cell group
cx = int(math.floor((polyCenter.getX()-minBB.getX()) / cellSize.getX()))
cy = int(math.floor((polyCenter.getY()-minBB.getY()) / cellSize.getY()))
cz = int(math.floor((polyCenter.getZ()-minBB.getZ()) / cellSize.getZ()))
self.cells[cx][cy][cz]['group'].addChild(poly)
poly = snode.getNextChild()
# Add the vertex data
destNode.addChild(vpool)
self.nleaves = self.recur(destNode, 0, 0,0,0)
print self.nleaves, 'leaves added'
def recur(self, node, depth, x, y, z) :
if depth < self.depth :
nnode = EggGroup('')
delt = int(math.pow(2, self.depth - depth - 1))
nchilds = 0
nchilds += self.recur(nnode, depth+1, x, y, z)
nchilds += self.recur(nnode, depth+1, x + delt, y, z)
nchilds += self.recur(nnode, depth+1, x, y + delt, z)
nchilds += self.recur(nnode, depth+1, x + delt, y + delt, z)
nchilds += self.recur(nnode, depth+1, x, y, z + delt)
nchilds += self.recur(nnode, depth+1, x + delt, y, z + delt)
nchilds += self.recur(nnode, depth+1, x, y + delt, z + delt)
nchilds += self.recur(nnode, depth+1, x + delt, y + delt, z + delt)
if nchilds > 0 :
node.addChild(nnode)
return nchilds
else :
# We are in a leaf
if x < self.ncx and y < self.ncy and z < self.ncz :
node.addChild(self.cells[x][y][z]['group'])
return 1
else :
return 0
Example of use :
egg = EggData()
egg.read(Filename('g2.egg'))
egg.getFirstChild()
sourceNode = egg.getNextChild() # the sourcenode must contain a VertexPool and a list of Polygons
if self.np != None :
self.np.removeNode()
self.np = None
ed = EggData()
ed.setCoordinateSystem(egg.getCoordinateSystem())
# Here, it's a quadtree since there will be only 1 leaf along the Y axis
self.octree.build(sourceNode, ed, Vec3D(3, 100, 3))
ed.writeEgg(Filename('g2_octree.egg'))
ed = None
self.np = loader.loadModel('g2_octree.egg')
self.np.reparentTo(render)Sphere vs mesh @ 220 fps :
Only collisions @ 360 fps :
[/img]
