KDTree Splitting

Question

I am currently writing a KDTree for a physics engine (Hobby project).

The KDTree does not contain points. Instead it contains Axis Aligned bounding boxes which bound the different objects in the environment.

My problem is deciding on how to split the KDTree nodes when they get full. I am trying 2 methods:

Method1: Always split the node exactly in half on the biggest axis.

• This has the advantage of a pretty evenly spaced out tree.
• Big disadvantage: If objects are concentrated in small area of the node, redundant sub-divisions will be created. This is because all volumes are split exactly in half.

Method2: Find the area of the node which contains objects. Split the node on the plane which splits that area in half on it's biggest axis. Example - If all objects are concentrated on the bottom of the node then it split length-wise thereby dividing the bottom in two.

• This solves the problem with the method above
• When indexing something that exists on the same plane (terrain for example), it creates long and narrow nodes. If I am to add some other objects later which are not on the same plane, these elongated nodes provide very poor indexing.

So what I'm looking for here is a better way to split my KD-Tree node. Considering that this is going to be a physics engine the decision needs to be simple enough to be made in real time.

Kauslick

Answer 1

The "surface area heuristic" (SAH) is considered the best splitting method for building kd-trees, at least within the raytracing community. The idea is to add the plane so that the surface areas of the two child spaces, weighted by the number of objexts in each child, are equal.

A good reference on the subject is Ingo Wald's thesis, in particular chapter 7.3, "High-quality BSP Construction", which explains SAH better than I can.

I can't find a good link at the moment, but you should look around for papers on "binned" SAH, which is an approximation to the true SAH but much faster.

All that being said, bounding-volume hierarchies (BVH) a.k.a. AABB trees, seem to be much more popular than kd-trees these days. Again, Ingo Wald's publication page is a good starting point, probably with the "On fast Construction of SAH based Bounding Volume Hierarchies" paper, although it's been a while since I read it.

The OMPF forums are also a good place to discuss these sorts of things.

Hope that helps. Good luck!

Albino

The "binned" SAH paper you mentioned might be "Fast kd-tree Construction with an Adaptive Error-Bounded Heuristic" by Hunt, Mark, and Stoll. The core idea in this paper is to use piecewise quadratic approximations to the true SAH function by sampling it intelligently. In my experience, it's a fast and effective algorithm. – Anesthesiologist

Yeah, that looks like the one. – Albino

Answer 2

Certainly for a physics engine where the premise is lots of moving geometry, a bvh is probably the better choice, they don't traverse quite as quickly but they are much faster to build, and are much easier to refit/restructure on a frame per frame basis, and offen don't need a complete rebuild, every frame (something that can be done in parallel over a series of frames while the refitted bvh suffices in the meantime, again, refer to wald).

An exception to this in physics could be when you're dealing with entities that have no volume such as particles or photons, the building of the kd tree is simplified by the fact that you don't need to resolve the bounds of the individual primitive. It really depends on the application. A good physics engine should use a balanced combination of spatial acceleration structures, it's common practise to resolve broader phase partitioning with say a shallow octree then extend the leaf nodes with another scheme that better fits the nature of what you are doing, BSPs are ideal for static geometry, especially in 2d and when the structure isn't changing, the best thing to do is experiment with as many different schemes and structures and get a feel for how and when they work best.

Knesset