K-d Trees

A k-d tree is a hierarchical subdivision of space in which:

• each node of the hierarchy corresponds to an AABB;
• leaf nodes store the primitives in the corresponding AABB;
• internal nodes have 2 children (always):
  • the children are separated by a plane;
  • the plane can be anywhere inside the parent's AABB;
  • the plane's normal is parallel to $x$ at one level, then $y$ at the next level, then $z$ at the next level, then back to $x$ at the next level, and so on.

The hierarchical structure is shown in 2D below. For any internal node, you can determine the separating line because it is the only line that is shown to go from one edge to the other of the node's AABB. The bold line below is the separating line of the root AABB.

Ray tracing in a k-d tree is the same as in an octtree, except that only two children are considered at each internal node.

Finding which children are intersected, and in which order, is very efficient because the ray needs only to be intersected with the separating plane.

There are many ways to choose the plane. The easiest ways yield poor performance, with more AABB tests and more triangle tests than necessary.

Even Split

The separating plane cycles through $x$, then $y$, then $z$ and splits the AABB into two identical halves each time.

This can cut many triangles so that they appear in both halves. It can also put a lot of triangles in one half and very few in the other half, resulting in an unbalanced tree with greater depth.

Triangle Median

The separating plane cycles through $x$, then $y$, then $z$ and splits the AABB such that there are an equal number of triangle centre points in each half.

This results in a balanced tree, but may still have triangles that appear in both halves.

Surface Area Heuristic (SAH)

The separating plane is chosen (in any of $x$, $y$, or $z$) to minimize a cost function. The cost function is a rough estimate of the cost of traversing the tree for the "average ray".

Let:

• $K_i$ be the cost of a ray/triangle intersection;
• $K_b$ be the cost of a ray/AABB intersection;
• $N(B)$ be the number of triangles stored in bounding box, $B$;
• $A(B)$ be the surface area of bounding box $B$;
• $P(B)$ be the probability that a ray intersects bounding box $B$.

Then the cost, $C_\textrm{leaf}(B)$, of processing a leaf node, $B$, is

$C_\textrm{leaf}(B) = K_i \; N(B)$

The cost, $C_\textrm{int}(B)$, of processing an internal node, $B$, with children $B_1$ and $B_2$ is, on average

$C_\textrm{int}(B) = K_b + P(B_1) \; C(B_1) + P(B_2) \; C(B_2)$

The probabilty that a ray intersects child $B_1$, given that is intersects parent $B$ is, assuming uniformly distributed rays:

$P(B_1) = { \Large A(B_1) \over \Large A(B) }$

And we can very, very roughly estimate $C(B_1)$ as

$C(B_1) \approx K_i N(B_1)$

The above approximation is not realistic, as it assumes that $B_1$ has no children of its own. But it works in practice.

So the cost function for an internal node is

$C_\textrm{int}(B) \approx K_b + { \Large A(B_1) \over \Large A(B) } \; K_i \; N(B_1) + { \Large A(B_2) \over \Large A(B) } \; K_i \; N(B_2)$

The separating plane is chosen to minimize $C_\textrm{int}(B)$. This is done in the $x$ direction, for example, by considering all triangle vertices that are minimum or maximum in the $x$ direction. Each triangle has two such vertices, in general.

Then a plane perpendicular to the $x$ direction is put at each such vertex and the cost function is computed.

This is repeated in the $y$ and $z$ directions and the plane of minimum cost is chosen as the separting plane.

The algorithm can be done in time $\cal{O}( n \log^2 n )$ for $n$ triangles. See the following paper for a description of that algorithm, and of a faster $\cal{O}( n \log n )$ algorithm:

Ingo Wald and Vlastimil Havran. "On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)" in Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, 2006.