Boosting the Render with a KD-Tree

I'm astonished with the speed increase of my renders with the use of a KD-Tree! A KD-Tree is a binary space partitioning data-structure that sub-divides the space, dramatically decreasing the time spent in the Ray-Objects intersections. Take a look on the KD-Tree entry at Wikipedia.

The folowing render consists of a 19.500 triangles mesh rendered into a 320x200 pixels image, with 4 rays-per-pixel with standard Raytracing. Without the KD-Tree it took 1 hour to render, using KD-Tree it took only 2 minutes!!!

(19.500 tris 320p x 200p x 4 rays/p : 2 mins with KD-Tree)

I'm sure that the result could be even faster with the ringht KD-Tree settings.

An even better result was the gargoyle int the previous post. Without the KD-Tree it took 1 hour to render, with the KD-Tree it took only 24 seconds!!!!! In that case I used a tree with a depth of 20 and with a minumum number of objects per node of 100.

To be effective, the KD-Tree must be balanced. I'm using the following method to do so:

• Split a bounding box of a node of the tree, I choose the axis along which the bounding-box is longer;
• And split it in the median of the positions of the objects in the node on that axis .

I think now I'm almost ready for Bi-Directional Path-tracing or Photon Mapping...