source: GTP/trunk/App/Demos/Illum/pathmap/KDTree.hpp @ 2197

Revision 2197, 4.4 KB checked in by szirmay, 18 years ago (diff)
Line 
1// declaration of kd-tree members
2
3#pragma once
4
5#include "malloc.h"
6#include "Heap.hpp"
7#include "Vector.hpp"
8#include "BoundingBox.hpp"
9#include "Intersectable.hpp"
10
11#include "Ray.hpp"
12#include "HitRec.hpp"
13#include "Material.hpp"
14
15#define KDTREE_CACHE_LINE_BYTES                                 128
16
17/*! This class implements a kd-tree. Splitting, termination and cutting of empty space is
18based on cost estimation. Memory representation uses cache-line sized sub-trees and
19mapping of an unbalanced tree into an array. */
20class KDTree {
21        unsigned int nCacheLines;               //!< #cache line sized memory segments used
22        unsigned int maxNCacheLines;    //!< #nodes per cache line
23        unsigned int nCacheLineNodes;   //!< #nodes per cache line
24        unsigned int nCacheLineBytes;   //!< bytes per cache line
25
26        BoundingBox     boundingBox;            //!< bounding box containing all objects
27
28        float* poolNodeTable;                   //!< memory allocated for nodes
29        float* nodeTable;                               //!< array aligned on cache lines
30
31        unsigned int            nObjects;       //!< #objects
32        Intersectable**         objects;        //!< array objects
33
34        //! minimum heap to store indices of free nodes during the build
35        Heap<unsigned int>* freeNodes;
36
37        //! stack to implement the recursive traversal algorithm
38        struct TraverseStack{
39                float rayMin;                           //!< minimum distance from origin
40                float rayMax;                           //!< maximum distance from origin
41                unsigned int tNode;                     //!< node index of kd-tree node to be traced
42        } *traverseStack;
43        unsigned int depth;
44        unsigned int currentDepth;
45
46        float epsilon;
47
48        //! traces the tree defined by root node index 'nodeID',
49        //! and frees the memory occupied by the object lists
50        void deleteLeaves(unsigned int nodeID);
51
52        //! recursive algorithm to build the tree
53        void build(unsigned int nodeID, //!< node index of kd-tree node to be created
54                unsigned int* boundsArray,      //!< array of duplicated object indices,
55                                                                        //!< first bit tells mimima and maxima apart
56                unsigned int nObjects,          //!< #objects (boundsArray's size is 2*nObjects)
57                BoundingBox& limits,            //!< kd-tree node volume
58                unsigned char axisNmask);       //!< bits 5,4,3 indicate z,y,x failed cut attempts
59                                                                        //!< bits 1,0 identify cut axis to be used
60
61        //! qSort an array segment of object extremes
62        void quickSort(unsigned int* lo0, unsigned int* hi0, unsigned char axis);
63        //! compare two object extrema according to the coordinate specified
64        bool inline compare(unsigned int aIndex, unsigned int bIndex, unsigned char axis);
65        //! return the value of the object extreme referenced
66        float inline getBoundValue(unsigned int * extremeIndex, unsigned char axis);
67        //! binary search: finds the position of value 'loc' in a sorted array partition
68        unsigned int* findBound(unsigned int* extremeArrayStart, unsigned int nBounds, float loc, unsigned char axis);
69       
70        //! tell if a node is a leaf
71        bool inline isLeaf(unsigned int xnode);
72        //! retrieve the node indices corresponding to the children of the specified node
73        //! return false if the node is a leaf
74        bool inline followChildren(unsigned int& parent, unsigned int &leftChild, unsigned int &rightChild);
75
76        //! retrieve the node indices corresponding to the children of the specified node
77        //! if they are not suitable to be the root of a free sub-tree, return false
78        bool inline getFreeNodes(unsigned int parent, unsigned int& leftFree, unsigned int& rightFree);
79
80        //! accumulate object extrema
81        inline void createBoundingBox (Intersectable** iObjects, int nObjects)
82        {
83                if(!nObjects)
84                        return;
85                boundingBox.minPoint = iObjects [0]->bbox.minPoint;
86                boundingBox.maxPoint = iObjects [0]->bbox.maxPoint;
87                for (int i=1; i<nObjects; i++) {
88                        // check accumulate operators of Vector class
89                        boundingBox.minPoint <= iObjects [i]->bbox.minPoint;
90                        boundingBox.maxPoint >= iObjects [i]->bbox.maxPoint;
91                }
92        }
93
94        /*! If the node referenced by oNode is on the last level of a cache-line sized sub-tree,
95        a pointer to a free node is placed, and the index of this free
96        node is returned. Else, originalNode is returned. */
97        inline unsigned int makePointer(unsigned int originalNode);
98
99public:
100        KDTree (Intersectable** objects, int nObjects);
101        ~KDTree () {
102                deleteLeaves(0);
103                delete traverseStack;
104                free(poolNodeTable);
105        }
106
107        bool traverse (const Ray& ray, HitRec& hitRec, float minT, float maxT);
108        bool traverseBackSide (const Ray& ray, HitRec& hitRec, float minT, float maxT);
109        BoundingBox& getBoundingBox()
110        {
111                return boundingBox;
112        }
113
114        Intersectable* forbidden;
115};
Note: See TracBrowser for help on using the repository browser.