KdTree Class Reference

Kd tree builder. More...

#include <KdTree.h>

List of all members.

Classes

struct  Event
 Triangle extents used for sorting during exact SAH. More...
struct  SplitInfo
 Used to return spliting plane info from exact search. More...

Public Member Functions

void bestPriceExact (Event *events, float minimum, float maximum, float step, float init, unsigned Eventcount, unsigned count, SplitInfo &info)
 Find best spliting position.
template<bool initial>
void buildTree (Triangle *__restrict faces, __m128 minimum, __m128 maximum, unsigned node, unsigned *indices, unsigned count, unsigned depth)
 Build node using aproximate min-max binning.
void buildNodeExact (Triangle *__restrict faces, __m128 minimum, __m128 maximum, unsigned node, unsigned *indices, unsigned count, unsigned depth)
 Build node using exact SAH.
 KdTree (Scene &scene)
 Build new tree for scene.
 ~KdTree (void)
 Free host and if necesary video card memory.
bool prepareCudaTexture (float3 &minimum, float3 &maximum, cudaArray *&cudaTree, uint4 *&triangles, cudaArray *&vertices, cudaArray *&normalsOut)
 Prepare tree for use in CUDA.

Public Attributes

float3 mini
 Minimum extent of the root node, prepared for CUDA.
float3 maxi
 Maximum extent of the root node, prepared for CUDA.
int vertexSum
 Total number of vertices of objects included in the grid.
int facesSum
 Total number of faces of objects included in the grid.
Vertex * transformed
 Vertices of objects in grid, transformed into world space.
Vertex * normals
 Normals associated with vertices. Has one normal for each vertex.
Triangle * triangles
 Temporal triangle indexes collected from all scene objects.
GrowArray< KdNode > nodes
 Nodes of the tree.
GrowArray< Triangle > nodeTriangles
 Faces of the tree.
TailPool< unsigned > * nodePrimitives
 Temporal indicies used to pass relevant faces to children nodes.
bool videoAllocated
 True if video memory is allocated.
cudaArray * savedTree
 Saved pointer for video memory dealocation.
uint4 * savedTriangles
 Saved pointer for video memory dealocation.
cudaArray * savedVertices
 Saved pointer for video memory dealocation.
cudaArray * savedNormals
 Saved pointer for video memory dealocation.

Private Types

enum  EventType { ENDS, INPLANE, STARTS }
 The type of event in exact SAH build. More...

Private Member Functions

void addEvent (Event *events, float minimum, float maximum, unsigned &count)
 Add new event to the events array.


Detailed Description

Kd tree builder.

Member Enumeration Documentation

enum KdTree::EventType [private]

The type of event in exact SAH build.

The element must be in this order, as thir integer values are used for sorting the events.

Enumerator:
ENDS  The triangle end at this position.
INPLANE  The triangle is coplanar with the spliting plane.
STARTS  The triangle starts at this position.


Constructor & Destructor Documentation

KdTree::KdTree ( Scene &  scene  ) 

Build new tree for scene.

Parameters:
scene The scene for whitch the tree should be build.


Member Function Documentation

void KdTree::addEvent ( Event events,
float  minimum,
float  maximum,
unsigned &  count 
) [inline, private]

Add new event to the events array.

Parameters:
[in,out] events The array of events.
minimum The minimum extent of triangle for this event.
maximum The maximum extent of triangle for this event.
[in,out] count The current number of events. Return new number of events.

void KdTree::bestPriceExact ( Event events,
float  minimum,
float  maximum,
float  step,
float  init,
unsigned  Eventcount,
unsigned  count,
SplitInfo info 
)

Find best spliting position.

Parameters:
[in] events Store the triangles extent.
minimum The minimum extent of current node.
size The size of current node.
step The area of node sides that are cut by spliting plane.
init The area of node sides that are not cut by spliting plane.
Eventcount The number of events.
count The number of triangles. Must by provided separately because some events might be inplane events. Therefore one cannot be deduced simply from the other.
[out] info Return the infor about spliting plane.

void KdTree::buildNodeExact ( Triangle *__restrict  faces,
__m128  minimum,
__m128  maximum,
unsigned  node,
unsigned *  indices,
unsigned  count,
unsigned  depth 
)

Build node using exact SAH.

Parameters:
faces The source triangles colectected from all scene objects.
minimum The minimum extent of the new node.
maximum The maximum extent of the new node.
node The node number assigned to the new node.
indices The indices to the triangles witch belongs to this node
count The number of triangles for this node
depth The depth of the cell in the tree

template<bool initial>
void KdTree::buildTree ( Triangle *__restrict  faces,
__m128  minimum,
__m128  maximum,
unsigned  node,
unsigned *  indices,
unsigned  count,
unsigned  depth 
) [inline]

Build node using aproximate min-max binning.

Template Parameters:
initial True if building the root node. In that case, the indices are ignored and the faces are accessed directly.
Parameters:
faces The source triangles colectected from all scene objects.
minimum The minimum extent of the new node.
maximum The maximum extent of the new node.
node The node number assigned to the new node.
indices The indices to the triangles witch belongs to this node
count The number of triangles for this node
depth The depth of the cell in the tree

bool KdTree::prepareCudaTexture ( float3 &  minimum,
float3 &  maximum,
cudaArray *&  cudaTree,
uint4 *&  triangles,
cudaArray *&  vertices,
cudaArray *&  normalsOut 
)

Prepare tree for use in CUDA.

Copy the tree data to video card's linear memory. Uses texture to store the nodes,vertices,normals and linear memory to store triangles.

Parameters:
minimum Returns minimum extent of the root node.
maximum Returns maximum extent of the root node.
cudaTree Pointer to tree nodes in video memory
triangles Pointer to triangles in video memory
vertices Pointer to vertices in video memory
normalsOut Pointer to normals in video memory
Returns:
true if succesfull, false if out of memory


Member Data Documentation

Faces of the tree.

Referenced from tree nodes. Has size of total number of triangles referenced in leaf nodes. This can be several time the number in totalPoly.

Triangle* KdTree::triangles

Temporal triangle indexes collected from all scene objects.

Warning:
This is here for debuging and could be removed in later versions.


The documentation for this class was generated from the following files:

Generated on Fri Jan 23 00:21:49 2009 for Raytracer by  doxygen 1.5.7.1