KD-Tree vs. AABB

(L) [2006/09/27] [MishoM] [KD-Tree vs. AABB] Wayback!

Hi,

After a long period of just reading and catching up, I decided to finaly take part in the discussions. My raytracer is still nonexistent, but I've been doing some reading and a lot of thinking. What I find most interesting is the pros and cons of the different acceleration structures. It seems to be the common opinion that for general purposes the best acceleration structures are different sorts of binary trees. And also it seems that the best performance is achieved using kd-trees and AABB hierarchies, but kd-trees perform better.

What do you think is the reason for the better performance of kd-trees over AABB hierarchies? Does the traversal of the kd-tree need fewer bounding box intersection tests? Or does the kd-tree partition the space into smaller boxes (when the boxes are split until each one contains only one triangle) and thus require fewer triangle intersection tests?

I'd really appreciate the opinion of those who have tried one or both methods. Also, does someone have statistics of the number of bounding box intersection tests, triangle intersection tests, number of nodes in the tree and minimal/maximal/average box size for each method? I think such information is better than rays per second count, because the real performance depends on many other factors.

MishoM

(L) [2006/09/28] [Michael77] [KD-Tree vs. AABB] Wayback!

Well, I guess there are two reasons why a kdtree is faster during traversal than a bounding volume hierarchy:

First, a kdtree node uses less memory per node causing less stress on the memory bus ( 8bytes instead of 24 bytes for a full bounding box) and is much faster to traverse. Although you probably have much more kdtree nodes than bounding volume nodes, this results in better overall performance.

The second, more important reason seems to be the fact that once you have found an intersection with a triangle in a leaf node you can stop the traversal. A bounding volume hierarchy on the other hand needs more traversal steps even if you have found an intersection since the bounding volumes can overlap. This is especially important for paket traversal since it is difficult (and probably not worth the effort) to use a priority queue for bounding volume hierarchies.

But kdtrees also have disadvantages, mainly the huge memory requirements. Also since you need to split triangles, some scenes are really difficult to handle. Triangle fans for example are a real nightmare for kdtrees and you can easily construct a scene where 1000 triangles will end up in one leaf node (or your tree depth reaches insane values). Bounding Volume hierarchies don´t have these problems.

My personal favorite is the bounding interval hierarchy though since it provides good performance while keeping memory requirements low: with 2 triangles ending up in a leaf my current implementation just needs about 2*numTriangles*12 Bytes for the acceleration structure, making handling of quite complex scenes (5 million triangles) very easy).

(L) [2006/09/28] [tbp] [KD-Tree vs. AABB] Wayback!

At the point where nodes are accessed pretty much randomly, what really matters is how many cachelines you have to touch per node; the answer being one on current x86 architectures the latency is the same for kd-tree & aabb. Note that cache size - and cacheability - isn't much of a factor because it's too small to contain anything but trivial scenes.

Briefly, if kd-tree have an edge over bvh/bih it's not because of the tighter node footprint.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/09/28] [MishoM] [KD-Tree vs. AABB] Wayback!

Well, what about this explanation which occured to me after reading your replies: when the kd-tree performs well, it wraps the triangles more tightly, resulting in fewer triangle intersection tests. At the same time the number of bounding box intersection tests probably isn't much greater, because though the bounding boxes in BVH/BIH are fewer they are bigger.

KD-Tree vs. AABB back