kdTreeAccel.cpp File Reference

An N-dimensional kd-Tree is an axis-aligned binary spatial partitioning data structure. Each internal node is split along one of the N principle axes, where the split plane is typically chosen at each node based on some sort of heuristic. This kd-Tree implementation supports several common split plane generation methods, namely: spatial midpoint, median of geometry, and surface area heuristic (SAH). Note that a kd-Tree constructed by choosing the spatial midpoint along the current split axis as the next split plane is equivalent to an Octree. Also note that though the SAH produces the best quality tree overall with respect to visibility tests, it can take a long time to build and is thus mainly suitable for static scenes (whereas other acceleration data structures may be more appropriate for dynamic geometry & animations). The SAH kd-Tree may be tweaked with several parameters. See kdTreeAccelParams for more info. The O(nlog n) SAH construction has been implemented as opposed to the O(n) or O(n^2) alternatives (using std::sort for internal sorting). This choice was made because the O(n) solutions which exist both have large constants (which diminish their utility in practice), and are nowhere near as readable or easy to understand as the relatively straightforward O(nlog n) alternative. More...

#include "kdTreeAccel.h"
#include <SurfacePoint.h>
#include <ResourceManager.h>
#include <Random.h>
#include <QtCore>
#include <Log.h>
#include <GL/gl.h>
#include <boost/static_assert.hpp>
#include <algorithm>
#include <climits>

Go to the source code of this file.

Defines

#define KD_FLAG_BITS   (3)
#define KD_LEAF_FLAG   (3)
#define KD_FLAG(node)   ((node)->flag & KD_FLAG_BITS)
#define KD_LEAF_NODE(node)   (KD_FLAG(node) == KD_LEAF_FLAG)
#define KD_INTERNAL_NODE(node)   (KD_FLAG(node) != KD_LEAF_FLAG)
#define KD_SPLIT_AXIS(node)   (KD_FLAG(node))
#define KD_SPLIT_POS(node)   ((node)->splitPos)
#define KD_NO_PRIMITIVES(node)   ((node)->noPrimitives >> 2)
#define KD_LEFT_CHILD(node)   ((kdNode*)((node)->flag & ~KD_FLAG_BITS))
#define KD_RIGHT_CHILD(node)   (KD_LEFT_CHILD(node) + 1)
#define KD_CHILD(node, n)   (((kdNode*)((node)->flag & ~KD_FLAG_BITS)) + n)
#define KD_INIT_INTERNAL(node, leftChild, splitAxis, pos)
#define KD_INIT_LEAF(node, prims, noPrims)
#define GET_PARAM(name, type)   m_buildParams.name = getValue<type>(#name, m_buildParams.name);

Detailed Description

An N-dimensional kd-Tree is an axis-aligned binary spatial partitioning data structure. Each internal node is split along one of the N principle axes, where the split plane is typically chosen at each node based on some sort of heuristic. This kd-Tree implementation supports several common split plane generation methods, namely: spatial midpoint, median of geometry, and surface area heuristic (SAH). Note that a kd-Tree constructed by choosing the spatial midpoint along the current split axis as the next split plane is equivalent to an Octree. Also note that though the SAH produces the best quality tree overall with respect to visibility tests, it can take a long time to build and is thus mainly suitable for static scenes (whereas other acceleration data structures may be more appropriate for dynamic geometry & animations). The SAH kd-Tree may be tweaked with several parameters. See kdTreeAccelParams for more info. The O(nlog n) SAH construction has been implemented as opposed to the O(n) or O(n^2) alternatives (using std::sort for internal sorting). This choice was made because the O(n) solutions which exist both have large constants (which diminish their utility in practice), and are nowhere near as readable or easy to understand as the relatively straightforward O(nlog n) alternative.

Author:
Travis Fischer (fisch0920@gmail.com)
Date:
Fall 2008

Definition in file kdTreeAccel.cpp.

Define Documentation

#define GET_PARAM ( name,
type   )     m_buildParams.name = getValue<type>(#name, m_buildParams.name);

#define KD_CHILD ( node,
n   )     (((kdNode*)((node)->flag & ~KD_FLAG_BITS)) + n)

Definition at line 82 of file kdTreeAccel.cpp.

#define KD_FLAG ( node   )     ((node)->flag & KD_FLAG_BITS)

Definition at line 67 of file kdTreeAccel.cpp.

#define KD_FLAG_BITS   (3)

Definition at line 64 of file kdTreeAccel.cpp.

#define KD_INIT_INTERNAL ( node,
leftChild,
splitAxis,
pos   ) 

Value:

do {                                                           \
      (node)->child    = (leftChild);                             \
      (node)->flag    |= (splitAxis);                             \
      (node)->splitPos = (pos);                                   \
      ASSERT(KD_INTERNAL_NODE((node)));                           \
      workBuf->log.noInternal++;                                  \
   } while(0)

Definition at line 85 of file kdTreeAccel.cpp.

#define KD_INIT_LEAF ( node,
prims,
noPrims   ) 

Value:

do {                                                           \
      (node)->noPrimitives = ((noPrims) << 2);                    \
      (node)->flag        |= (KD_LEAF_FLAG);                      \
      (node)->primitives   = (prims);                             \
      ASSERT(KD_LEAF_NODE((node)));                               \
      workBuf->log.noLeaves++;                                    \
      workBuf->log.minPrimitives  =                               \
         MIN(workBuf->log.minPrimitives, (unsigned) (noPrims));   \
      workBuf->log.maxPrimitives  =                               \
         MAX(workBuf->log.maxPrimitives, (unsigned) (noPrims));   \
      workBuf->log.avgPrimitives += (unsigned) (noPrims);         \
      workBuf->log.minDepth  =                                    \
         MIN(workBuf->log.minDepth, workBuf->depth);              \
      workBuf->log.maxDepth  =                                    \
         MAX(workBuf->log.maxDepth, workBuf->depth);              \
      workBuf->log.avgDepth += workBuf->depth;                    \
   } while(0)

Definition at line 94 of file kdTreeAccel.cpp.

#define KD_INTERNAL_NODE ( node   )     (KD_FLAG(node) != KD_LEAF_FLAG)

Definition at line 70 of file kdTreeAccel.cpp.

#define KD_LEAF_FLAG   (3)

Definition at line 65 of file kdTreeAccel.cpp.

#define KD_LEAF_NODE ( node   )     (KD_FLAG(node) == KD_LEAF_FLAG)

Definition at line 69 of file kdTreeAccel.cpp.

#define KD_LEFT_CHILD ( node   )     ((kdNode*)((node)->flag & ~KD_FLAG_BITS))

Definition at line 78 of file kdTreeAccel.cpp.

#define KD_NO_PRIMITIVES ( node   )     ((node)->noPrimitives >> 2)

Definition at line 74 of file kdTreeAccel.cpp.

#define KD_RIGHT_CHILD ( node   )     (KD_LEFT_CHILD(node) + 1)

Definition at line 80 of file kdTreeAccel.cpp.

#define KD_SPLIT_AXIS ( node   )     (KD_FLAG(node))

Definition at line 72 of file kdTreeAccel.cpp.

#define KD_SPLIT_POS ( node   )     ((node)->splitPos)

Definition at line 73 of file kdTreeAccel.cpp.

Generated on 28 Feb 2009 for Milton by doxygen 1.5.6