Blog Image


About Gray

Gray (Greiners Raytracer) is a hobby/research project of mine. It is a program that simulates light to produce computer generated images. The technique used is called ray tracing, where a large number of rays are cast against mathematical 3D models to simulate the interaction between light and materials. The result is beautiful computer generated images, like the ones we are used to see in special effects in movies.

SAH KD-tree

Programming Posted on Sun, February 07, 2010 16:13:34

First screenshot from my new SAH KD-tree. The bunny is visualized using the voxels only.

To better visualize the voxels traversal I implemented an interactive tool that allows me to trace a single ray while showing only the inspected voxels in that trace. This tool is very valuable debugging the KD-tree.

Need for speed

Programming Posted on Sun, February 07, 2010 16:08:29

One 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.