## Need for speed

ProgrammingPosted by Søren Greiner Sun, February 07, 2010 16:08:29One of the biggest problems with my current implementation of Gray is speed. My current implementation uses a simple KD-Tree that divides the geometry into two partions, a left and a right partion. The split plane is chosen as the center of the longest axis in the bound box. The Kd-tree builds very fast, but is not very efficient. Furthermore I support instancing of modelmeshes, which means that the same geometry can be reused.

So first I compute bounding boxes for all meshes (or spheres or isosurfaces) and construct a KD-Tree containing all these models. Then if a model is a triangle-mesh this mesh is subdivided in its own KD-tree.

This implementation behaves well if models are small and placed apart (no overlap). So e.g. a field of bunnies renders very fast. But many scenes contains overlapping structures. The Sponza Atrium models makes Gray grind forever, because the meshes overlaps a lot and because the camera would be placed inside the model.

So since, last winter (2009) I have been working on and off with a new Surface Area Heuristics KD-tree. My hope is that this new tree will make Gray perform much better in my current worst case scenarios.