OctTrees

(L) [2007/09/15] [phkahler] [OctTrees] Wayback!

Hi,

It's been a few years since I've really been in contact with the RTRT crowd. After letting my code sit for a while I ran across the kd-tree phenomenon. I was impressed with the results people were getting, but I still feel that structure is fundamentally flawed - I'll explain why in a minute. People were getting millions of rays per second, and I left off at a few hundred thousand, so I sat down and made several of the improvements I always wanted to make to my raytracer. I got over 1 Million rays per second on a 2GHz AMD64 tracing the bunny (maybe 1.1 - 1.3M). Then I got a dual core [SMILEY Smile] Anyways...

I've always been an OctTree fan. The choice was not entirely arbitrary. Realtime Raytracing has always implied animation to me. One of the key advantages of ray tracing is the O(log n) rendering time. Given that, it makes no sense to build a structure that involves looking at all the geometry every frame - That's O(n) at the very least and KDTrees are O(n*log(n)). Now I see people are starting to realize this and moving to BVHs again [SMILEY Smile] I don't have all the answers, as I said my code still seems slower that others, but I can animate things in O(log n). I've also got answers to all the questions raised by EAH in the last Ray Tracing News - where he considers a "room full of dice" and "pickup sticks". Here's what I'm doing:

The octtree is axially aligned and has nodes of 2^n size, where n is any integer. All nodes can contain primitives. Primitives may occupy more than one node. Nodes contain pointers to up to 8 children. Null pointers are used where no child is present. Using this structure, primitives can figure out which nodes they should occupy regardless of the other geometry. There is no criteria for splitting nodes. In the simplest method, a primitive finds it's bounding box, and passes that along with a "this" pointer to a generic function to insert it into the tree. A node size is selected based on the bounding box dimmensions, and the tree is followed down to the nodes of that size that still intersect the bounding box. That's a very rough bound. For triangles, I use the smallest node size greater or equal to half the largest dimmension of the b-box. I also incude a planar constraint - the nodes must be cut by the plane of the triangle. This is still not optimal, I'll get around to requiring that the node contain part of the triangle, which will allow smaller nodes if that turns out to be faster. Pickup sticks will be handled by using appropriate sized octtree nodes and "painting" the bounding volume in them.

Because the primitives fit into nodes regardless of the other primitives, this like the teapot in stadium are trivial. The stadium would go in node much closer to the root, and the teapot way down the branches. Room full of dice? same thing. Now there are some drawbacks to this, but consider a building full of offices and what type of culling will happen. The tree is recursed top down, so all the big geometry is tested first - well not all of it, only the local big geometry, then the local small stuff, then the farther big stuff, etc...

This post is getting long, so I'll stop and see if there are any questions before I ramble on. But first the real teaser: My tree traversal is a recursive function. At each node, it is determined which children the ray hits and then recusion is done on them in order of intersection (after primitive intersection on the parent of course). After each child node, there is an early exit if the next child is farter away than the closest hit so far. The magic is this: Determination of which children are hit involves no condition checking (not even null pointer checks), just a bunch of bit twiddling and a single switch statement [SMILEY Smile] More on this later...
_________________
--Paul

The OctTree Guy

(L) [2007/09/15] [rogon] [OctTrees] Wayback!

Octtrees are a fine data-structures, but you have to ask yourself, why are the boxes of uniform size? Is it necessarily a good thing to be of uniform size?

First, the teapot in the stadium issue is not so much about representation as it is of avoiding node traversal. Let's say the teapot is 0.125 m and the stadium is is 128.0m, i.e. a difference of 128.0 / 0.125 = 1024 = 2^10. That means that when I send out a ray from the teapot towards the environment, it will take at least 10 nodes to get to stadium geometry.

Secondly, the reason that kD-trees are so attractive is not the kD-tree structure itself, but that the surface area heuristic is so nice. It has been shown to accelerate ray lookups by quite a factor. The reason is that it prunes "empty space" very efficiently, thus in the teapot/stadium case, the ray would very quickly (i.e. few steps) arrive at the stadium geometry (or outside the scene bounding box).

Thanks,

Rogon.

OctTrees back