Octree division

Question

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

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.

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,

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)
      add TRI to CANDIDATE CHILD
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)

holes from one 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.

Answer 1

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.

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.