Egg Octree

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 :wink:

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

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

from pandac.PandaModules import *

import math

class EggOctree(object):

	def build(self, sourceNode, destNode, cellSize, collide=False):
		snode = sourceNode
		# 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 = [[[
					Point3D(minBB.getX() + x * cellSize.getX(),
							minBB.getY() + y * cellSize.getY(),
							minBB.getZ() + z * cellSize.getZ()),
					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) :
		# 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()))
			poly = snode.getNextChild()
		# Add the vertex data
		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 :
			return nchilds
		else :
			# We are in a leaf
			if x < self.ncx and y < self.ncy and z < self.ncz :
				return 1
			else :
				return 0

Example of use :

egg = EggData()'g2.egg'))		
sourceNode = egg.getNextChild() # the sourcenode must contain a VertexPool and a list of Polygons

if != None : = None

ed = EggData()

# Here, it's a quadtree since there will be only 1 leaf along the Y axis, ed, Vec3D(3, 100, 3))

ed = None = loader.loadModel('g2_octree.egg')

Sphere vs mesh @ 220 fps :

Only collisions @ 360 fps :


Excellent piece of work !!!
4 thumbs up for that !

Your work obviously ends the painful work of a lot of people here, who’ve done that by hands, like ThomasEgi. He would be surprised if he sees this.
We definitely need a lot more people like you here.

However, I think I found 2 faults in your code :

  1. critical :
      # Add a small margin to ensure all the polys will be added
      minBB -= Vec3D(0.001, 0.001, 0.001)
      minBB += Vec3D(0.001, 0.001, 0.001)

The min & max bounding box range need to be expanded, right ? Then it should be min & max, not min & min. It excludes a lot of tris ! Haven’t you seen that already ?

  1. non-critical : loop range
      nverts = vpool.getHighestIndex()
      for iv in range(nverts) :

Shouldn’t nverts equals to highest index + 1 ?
In Python, in range(x) means x times of loop, not until reaches index x.

And I use this to make the result so obvious :

import random

for g in geomList:

Thanks so much !

indeed … great piece of work. havent looked really close into it. but creating octree-structres is one thing. but does panda handle them correctly and doesnt do visibility checks against all tiny parts and sub-parts?

well it’s a nice step towards octree culling. once it’s completed someone should merge it into panda ( as c++ code)

big thx for your work! =)

please forgive my lack of knowledge…
Do you think it’s good for rendering ?
But wouldn’t it be the real PiTA for your GPU ?
I think it’s the perfect thing for creating collision polys.

What Thomas is referring to is a CPU process to quickly identify only triangles within the viewing frustum, and only render those. I’ve worked with an engine that did this for the world mesh, but it used a BSP (the same BSP was also used for collision detection).

With an octree, basically you start at the top level and say “does this cube intersect the viewing frustum?”, and if so you look at each of the 8 subcubes. If a cube doesn’t intersect you ignore all triangle within it.

To work for frustum culling though, you would need to either split polygons at the octree borders or somehow keep track of polygons spanning borders so that the spanning polygons are not rendered 2 or more times.

or just change the box-size so all vertices of the triangles are inside the cubes. it doesnt really matter if the cubes arent perfect as long as you size up the top-level cubes ,too so all lower-level cubes are 100%inside.

well the other thing is… creating meshes like this is one . but i think panda doesnt really know how to use those stuctures. i fear that it will simply take all lowest-level geometrie and does it usual visibility check. this might be ok if for some cases but it’s not the idea behind the octree.

You are right ! It’s now fixed

Well, you should be right, since I used this function as if it returned the length and not the highest index… I’ll check that.

You are right, this is not really optimized for rendering and I’m now using it for collisions. To use an octree for rendering you need to tune the number and size of the leaves. This is a compromise between sending too much nodes, and too much vertices to the GPU.

Concerning the collisions, AFAIK, it’s simpler : you can set the max leaf size to the maximum collision radius

It seems that Panda culls the octree branches according to their AABB, that explains why it’s faster to use an Octree.

I’m now working on a better sort algorithm to attach the triangles to the leaves faster (it’s kind of slow now). Then, i’m planning to add some LOD.

What do you think about this :

  • create with max or maya a mesh + 3 degraded versions (ex : 30%, 10%, 5% of the total vertices)
  • build 4 octrees for each version of the mesh
  • blend the 4 octrees into one so that each leaf is actually a LODNode

I can’t go with ROAM since I don’t work with heightmaps. Actually it’s hard to find good terrain algorithms that don’t use heightmaps.

An illustration with a 50 000 polys mesh running at 200~350 fps on a 1.8gz cpu with a nVidia Go 7400.
This is done with 2 octrees :

  • one for collisions with more than 3000 leaves
  • one for rendering with 8*8 leaves

The demo is framerate independent. …

Really nice work, just got a chance to check it out. Thanks for sharing.

Hi I noticed on other computers when I download this demo zip I am unable to extract the files (I get a unrecognized compression error in winzip and a similar error in WinRar) any ideas? Thanks

Just tried your new blazing code.

There is a serious flaw in it :wink:
The result of maze.egg in the collision detection sample (cellsize : 1, 1, .5) : only 507 leaves

You missed the equal sign here :

         if depth < self.depthZ :

The result is 845 leaves now.

Thanks, I have to check that, I can’t really see why the Z axis would be different from the others.

file skipped unknown compression method…Xp home OS…


I had the same problem with unpacking on WinXP. 7zip, the command line version, can handle the compression algorithm:

Great work, raytaller :slight_smile:

I grabbed gui version which also was able to handle it so thx for letting me know about this…:wink:


Code updated !
Thanks again ynjh_jo, I think the problem is now fixed. The <= was required for all dimensions. Actually, the code was only tested with a quadtree, that’s why I didn’t notice the bug.

A robust octree terrain manager would be nice, so I thank you all for testing :slight_smile:

Well, if only using <=, it wouldn’t help much. Try cellsize (1,1,1), or (1,1,1.5) or (1,1,2), still the maze. The problem remains.
The only working way is enlarging the depthZ about 4 times . But I’m sure there must be duplicated vertices if I go that way.

hm seems like this is getting along pretty well. havent tested the whole thing yet. but. 2 questions remains:

  1. does the octree for grafical stuff really works like an octree or does it still check every single leave for visibility instead of skipping them in bunches?
  2. i think it should but just want to confirm. if a mesh is split into 2 pieces willl the vertex normals remain untuched so they will be seam-less when beeing lit?