Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an octree, with a high poly rabbit inside it, and a 12 polygon platform.

The deal is this. You're shooting a ray at the rabbit. He of course dodges (or you miss).

shoot rabbit

The yellow beam is your death laser.

The "candidate" triangles that are selected due to the parts of the octree you hit are shown in purple.

shoot rabbit 2

So clearly you have this striping that occurs, because the root node was hit, you ended up testing any polys in the root node. And the polys that are on the borders of the octree subdivision end up in the root node, with the subdivision algorithm I'm using.

So I want to reduce the number of polys in the root node.

If I just move the bunny to the corner, corner rabbit

With the bunny in the corner raytracing the entire scene takes 1/3 the time (35s vs 95s if the bunny is in the middle). I believe this is because less of the bunny's triangles are in the root, and octree root-only hits check fewer polygons.

I'm surveying ways to improve performance. Basically to push the tris as far down the tree as possible, so that the objects are mostly in the leaves.

I tried doing this naively, and used this subdivision algorithm which I made up:

split root into 8 CANDIDATE CHILDREN
foreach TRI in root:
  foreach of the 8 CANDIDATE CHILDREN
    if the CANDIDATE CHILD partially contains TRI (at least one vertex of TRI)
CLEAR tris in root

This pushes triangles down the hierarchy into leaf nodes. But I get holes from certain angles, with weird miss patterns:

(expected) expected holeless scene

holes from one angle:

holes from one angle

same scene, different angle:

same scene, different angle

I think it's because I'm clearing the root. (Because when I don't clear the root, raytracing works correctly, all angles)

Have I "pushed" the polygons down the tree correctly? Can any one guess why I have holes?

How do you improve the performance of your octree?

Do I have to split the triangles? I'm trying to avoid that, so I don't get thinner and thinner triangles/multiply the scene geometry any more than I need to.

I'm also aware that KD trees and that they should outperform octrees, but they also require poly splitting, I'm really looking for ways to improve my octree here.

share|improve this question
Primitives should always be in the leaves. Also consider using a B+Tree with non-uniform partitioning (cuboids within a cuboid don't need to be distributed equally) and partition the space according to whether it has primitives or not. Also -1 for shooting death rays at innocent bunnies :). – Jonathan Dickinson Feb 17 '12 at 13:04
I think your 'edit' section has pretty much answered your own question; you should post it as an answer, and accept it. – Trevor Powell Feb 17 '12 at 22:51
up vote 1 down vote accepted

I understand now why I get holes. I'm using a bad AABB-triangle partial containment scheme: an AABB "partially contained" a triangle iff the AABB contained at least one a vertex of the triangle. mostly empty

E's are "empty", according to the bad "Triangle partially in AABB" detection scheme.

I guess this means that if you want to push everything down to leaf nodes, you must split the triangles.

share|improve this answer
Split the triangles, or push triangles into every leaf node that they intersect with; not just the ones which contain their vertices. – Trevor Powell Feb 18 '12 at 5:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.