The first version of K-d tree I wrote was a trivial median-split build, and it ran quite slow. Then I found out a technique called Surface Area Heuristic (SAH). Basically, the method works under the assumption that the time of intersecting a ray with a voxel is based on its surface area and the number of triangles inside that voxel. And to find the split plane, it will check all the bounding face of every triangles in the scene. A benefit to this approach is axis-align (or planar) triangles will be preferred, making the algorithm perfect for scene in which there are many flat, parallel surfaces.

So I spent most of my last 2 weeks reading and implementing that build. Although the build is now O(NlogN), the code is till very poorly optimized.

The code is made available at:

http://code.google.com/p/vcraytracer/source/browse/#svn/trunk/wxRaytracer/raytracer/Accel

My implementation is based on this paper:

On building fast kd-Trees for Ray Tracing, and on doing that in O(NlogN)

The SAH is described by Vlastimir Havran in his dissertation which is considered a bible for K-d tree

Heuristic ray shooting algorithm

It took me almost 3 days to understand the method, because I’m rather new to this acceleration scheme. I think I will write down some of my thoughts on this wonderful paper when I have time.