just another diary

Tuesday, April 5, 2011

Working on KD-tree.

Trying to implement KD-tree for the ray tracer, I solve appearing problems with both environment and the language itself.
Anyway, the result can be found any moment on the github.

Currently I am working on KD-tree, on the build-tree function, to be specific. The most difficult part of it seems to be a SAH function (surface area heuristics).

And the next difficult part would be a traverse-kd-tree function, which is implemented, but I am looking for good testing techniques for it: a 3D geometrical data is difficult to visualize either in console or on screen.


  1. If you've ever used mental ray, they visualize the depth via color. Basically the greater the tree traversal to the primitive, the greater the brightness of it. If your tree had a max depth of 4, and you are drawing the primitive whose depth is 3, you simply color the object depth/maxdepth, or 75% RGB in this case. Expensive traversals visually stand out as being brighter. You could use hue as a heuristic for the number leaves in a tree.

  2. Great hint, thanks!
    Though I used to play with Brazil and V-Ray, but Mental is pretty straightforward for me, too. I guess, any raytracer would provide enough information for described idea.


My Blog List

Powered by Blogger.