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.

KD-Tree construction

ProgrammingPosted by Søren Greiner Thu, February 11, 2010 11:45:44
My Kd-Tree is pretty much working now. Tree is constructed with complexity O(n*log(n)) which is expected from a well designed Kd-Tree generator. My implemention goes like this:
First 3 arrays are created containing split-candidates for the 3 different axis x,y and z. Each split candidate is defined like this:
struct SSplit
real fSplit; // Split position of event
uint32 iItem; // Atom the split belongs to
bool bLeft; // true if event is a left event, false if it is a right event
uint32 nLeft; // number of objects left to split position
uint32 nRight; // number of objects right to split position

Next 3 other arrays are created which are simply pointers to the same split-candidates. I have implemented an < operator for the pointer, so we can sort the pointers instead of the split candidates. Handling of pointers are much more light weight than handling the split candidates themselves.

Now the split candidate pointers are sorted using standard C++ sort functions. This sorting is kept for the rest of the algorithm to avoid having to resort splits for every node that is computed.

Next the call to the recursive algorithm starts. For each set of split candidates, the best splitting candidate is chosen as the one with the lowest cost. The split candidates are then split into a left side and a right side, and each branch is split recursively until the algorithm decides that a leaf node is cheaper than a branch.

The cost function computes the cost by looking at the number of objects on each side of the split and the probability of hitting that side (surface area relative to parent area) and goes like this:
fCost = fCostTraversel + fCostIntersect*(nl*al + nr*ar)/fArea;

Since the split candidates are already sorted the number of objects on left and right side of each split candidate (this number is used in the cost function) is done by simply counting the objects while iterating through them from left to right and right to left.

Each KdTreeNode takes up 12 bytes which are spend like this:
struct KdTreeNode
real m_fSplit; // Splitting position according to split plane m_eAxis
KdTreeNode* m_pChild; // Pointer to two nodes
KdTreeItem* m_pItems; // Pointer to items in leaf node
unsigned int m_eType : 1; // ENodeType, leaf=0, branch=1
unsigned int m_eAxis : 2; // ENodeAxis, x=0,y=1,z=2
unsigned int m_iItemCount : 29; // Number of KdTreeItems in leaf

Fill in only if you are not real

The following XHTML tags are allowed: <b>, <br/>, <em>, <i>, <strong>, <u>. CSS styles and Javascript are not permitted.