source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktb.h @ 2592

Revision 2592, 11.8 KB checked in by bittner, 17 years ago (diff)

havran ray caster update

Line 
1// ===================================================================
2// $Id: $
3//
4// ktb.h
5//      definition of classes for CKTB tree building up and traversal
6//
7// Class: CKTBNodeAbstract, SKTBNode, CKTBAllocMan, CKTBNodeIterator
8//
9// REPLACEMENT_STRING
10//
11// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
12// Initial coding by Vlasta Havran, February 2007
13
14#ifndef __KTB_H__
15#define __KTB_H__
16
17// GOLEM headers
18#include "configh.h"
19#include "AxisAlignedBox3.h"
20#include "Intersectable.h"
21#include "Containers.h"
22#include "allocgo2.h"
23#include "ktbconf.h"
24#include "sbbox.h"
25#include "Vector3.h"
26
27// standard headers
28#include <vector>
29
30namespace GtpVisibilityPreprocessor {
31
32// Forward declarations
33class CRayPacket2x2;
34
35// 12 Bytes representation of the node
36// This is only due to writing simplification
37#undef SKTBNodeT
38#define SKTBNodeT CKTBNodeAbstract::SKTBNode
39
40//===============================================
41// Representation of one node of CKTB
42class CKTBNodeAbstract
43{
44public:
45  // maximal height of the CKTB tree
46  enum { MAX_HEIGHT = 32 };
47
48  // the basic element of CKTB tree .. node of tree
49  // it must be accessible by more classes
50
51  // but must be declared because of compilation
52  struct SKTBNode {
53    // the axis, where cut is performed or type of node in general
54    CKTBAxes::Axes  nodeType;
55
56    union {
57      float splitPlane; // the position of splitting plane
58      ObjectContainer *objlist; // object list for a leaf or tagged interior node
59      SKTBNodeT *parentBoxNode; // the pointer to the same node type
60      int        depth; // the depth of the node (useful only for minBoxes)
61    };
62   
63    // SKTBNode *left; // pointer to the left child is implict in DFS order
64    union {
65      Intersectable *object; // the pointer to the object, if only one object
66      SKTBNodeT  *right; // pointer to the right child
67      SBBox     *encbox; // enclosing bounding box for this node
68      SBBox     *minbox; // minimum bounding box for this node
69    };
70
71    bool IsLeaf() const {
72      return ( nodeType == CKTBAxes::EE_Leaf);
73    }
74    bool IsEmptyLeaf() const {
75      return (this == 0);
76    }
77  }; // struct SKTBNode
78
79public:
80
81  // It was _KTB_R2
82  // default constructor
83  CKTBNodeAbstract() { }
84  // default destructor
85  virtual ~CKTBNodeAbstract() { }
86
87  bool IsEmptyLeaf_(const SKTBNode *p) const {
88    assert(p->nodeType == CKTBAxes::EE_Leaf);
89    return (p->objlist == NULL);
90  }
91
92  bool IsFullLeaf_(const SKTBNode *p) const {
93    return ((p->nodeType == CKTBAxes::EE_Leaf) &&
94            (p->objlist != NULL));
95  }
96 
97  bool IsLeaf_(const SKTBNode *p) const
98  { return (p->nodeType == CKTBAxes::EE_Leaf); }
99 
100  bool HasMinBox_(const SKTBNode *p) const
101  { return ( p->nodeType >= CKTBAxes::EE_X_axisBox); }
102
103  // ------------------------------------------------------
104  // Common functions for iterator and allocator
105
106  CKTBAxes::Axes GetNodeType(const SKTBNode *nodep) const {
107    return nodep->nodeType;
108  }
109  SKTBNode* GetLeft(const SKTBNode *nodep) const {
110    return (SKTBNode*)(nodep+1); // We assume linking in DFS order
111  }
112  // We assume linking in DFS order, this is for EncBox
113  SKTBNode* GetLeftLong(const SKTBNode *nodep) const {
114    return (SKTBNode*)(((char*)nodep) + 3*sizeof(SKTBNode));
115  }
116  SKTBNode* GetRight(const SKTBNode *nodep) const {
117    return nodep->right;
118  }
119  SKTBNodeT* GetLinkNode(const SKTBNodeT *nodep) const {
120    return nodep->right;
121  } 
122  ObjectContainer* GetObjList(const SKTBNode *nodep) const {
123    return nodep->objlist;
124  }
125
126  SKTBNode* GetParentBoxNode(const SKTBNode *nodep) const {
127    return (SKTBNode*)(nodep+1)->parentBoxNode;
128  }
129
130  // This can be used only for nodes X_AxisBox, Y_AxisBox, Z_AxisBox
131  int GetDepth(const SKTBNode *nodep) const {
132    return (int)((nodep+1)->nodeType);
133  }
134#ifdef _SHORT_FORM_MINBOX
135  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
136    return (SKTBNode*)(nodep+2);
137  }
138#else
139  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
140    return (SKTBNode*)(((char*)nodep) + 4*sizeof(SKTBNode));
141  } 
142#endif // _SHORT_FORM_MINBOX
143
144}; // CKTBNodeAbstract
145
146//----------------------------------------------------------------
147// this class should be used as the base class for allocating
148// and connecting the nodes in the CKTB tree and for
149// for manipulating the nodes during building up
150class CKTBAllocMan:
151  public CKTBNodeAbstract
152{
153protected:
154#ifdef LEAVES_ARRAYS
155  CObjectArray arrayAlloc;
156#endif
157 
158  // the direction of traversal through CKTB tree
159  enum EDirection { LEFT = 0, RIGHT = 1, NOWHERE = 2 };
160
161//#ifdef _KTB_R2
162  SKTBNode* _AllocEmptyLeaf() {
163#ifdef _KTB_CONSTR_STATS
164    _stats_emptyLeftNodeCount++;
165#endif
166    return (SKTBNode*)0;
167  }
168protected:
169  // data required as the input parameter for construction of CKTB tree
170  int maxDepthAllowed; // maximal depth of CKTB tree
171  int maxListLength; // maximal list length of CKTB tree 
172public:
173  // default constructor
174  CKTBAllocMan() { InitForConstructor(); }
175
176  // default destructor
177  virtual ~CKTBAllocMan() { }
178
179  // init the stack of auxiliary variables from min to max
180  virtual void InitAux(int min, int max, int maxItemsAtOnce);
181 
182  // forget the content that is created by previous kd-tree construction
183  // or just init for the first use.
184  void InitForConstructor();
185 
186  // the function, which reads the parameters from envinroment/commandline
187  virtual void InitPars();
188 
189  // -------------------------------------------------------
190  // allocate and free functions for SKTBNode
191  CAllocContinuous *alloc2; // the allocator saving space
192  SKTBNodeT *root; // this is the root node of the whole tree
193 
194  // This is the node to return from the allocation functions
195  // Here it can be implemented some linking when DFS order allocation,
196  // so the node can be different than the representation of the real
197  // node with the information
198  SKTBNodeT *nodeToLink;
199
200  // Create the representation of the interior node
201  SKTBNodeT* AllocInteriorNode(int axis, float position,
202                               int cntLeft, int cntRight);
203
204  // Create the representation of the interior node with box, where box
205  // can be used during the traversal
206  SKTBNodeT* AllocInteriorNodeWithBox(int axis, float position,
207                                      int cntLeft, int cntRight,
208                                      const SBBox &tsbox,
209                                      SKTBNodeT* prevMinBoxNode,
210                                      int depthStore);
211 
212  // Create the representation of the node with the bounding box
213  SKTBNodeT* AllocEncBoxNode(const SBBox &sbox);
214 
215  // Create the representation of the leaf. Note that possibly there
216  // can be special cases, such as 0, 1, 2, or 3 objects, or in general
217  // N objects.
218  SKTBNodeT* AllocLeaf(int cntObjects);
219 
220  // -------------------------------------------------------
221  // linking and setting functions for CKTB tree
222
223  // Set the pointers to children for the interior node
224  void SetInteriorNodeLinks(SKTBNodeT *node,
225                            SKTBNodeT *leftChild,
226                            SKTBNodeT *rightChild);
227  void SetInteriorNodeLeft(SKTBNodeT *node,
228                           SKTBNodeT *leftChild);
229  void SetInteriorNodeRight(SKTBNodeT *node,
230                            SKTBNodeT *rightChild);
231
232  // Set the objects list to the leaf. The object list is used as it is
233  // ... it is not copied !!
234  virtual int SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist);
235
236  // -------------------------------------------------------
237  // inquiry functions for CKTB tree nodes for current node
238
239  // returns the pointer to the root node of tree
240  virtual SKTBNode *GetRootNode() { return root;}
241
242  // postprocessing of CKTB tree after its initial construction
243  virtual void PostBuild();
244
245  // provides the information on the method used for CKTB tree
246  // and some setting parameters to given stream
247  virtual void ProvideID(ostream &app) = 0;
248 
249  // ---- Get Statistical Data ---------------------------------
250  void GetKTBTreeStats(int &nodes, int &leaves, int &emptyLeaves)
251  {
252#ifdef _KTB_CONSTR_STATS
253    nodes = _stats_interiorCount + _stats_bboxCount + _stats_minbboxCount
254      + _stats_leafNodeCount + _stats_emptyLeftNodeCount;
255    leaves = _stats_leafNodeCount + _stats_emptyLeftNodeCount;
256    emptyLeaves = _stats_emptyLeftNodeCount;
257#endif
258  }
259
260  // constructs the CKTB tree for given objectlist and given bounding box
261  virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
262                             const AxisAlignedBox3 &box,
263                             bool verbose = true) = 0;
264
265  // deletes all the structure starting from the root node
266  virtual void Remove();
267
268  // The current depth in the tree
269  inline int GetDepth() const {return _currDepth;}
270  void IncDepth() {_currDepth++;}
271  void DecDepth() {_currDepth--;}
272 
273  // --------------------------------------------------------------
274  // Statistics
275public:
276#ifdef _KTB_CONSTR_STATS
277  int _stats_interiorCount;
278  int _stats_bboxCount;
279  int _stats_minbboxCount;
280  int _stats_leafNodeCount;
281  int _stats_emptyLeftNodeCount;
282
283  // maximal depth of the currently built path during building up
284  int _maxDepth; 
285  // Sum of depths of leaf nodes (empty + full)
286  unsigned long int _sumLeafDepth;
287  // Sum of depths of empty leaves
288  unsigned long int _sumFullLeafDepth;
289  // The count of object references in leaves
290  unsigned long int _sumObjectRefCount;
291  // The maximum number of object references in a leaf
292  unsigned long int _maxObjectRefInLeaf;
293  // Surface area of leaves and interior nodes
294  float _sumSurfaceAreaLeaves;
295  float _sumSurfaceAreaMULcntLeaves;
296  float _sumSurfaceAreaInteriorNodes;
297#endif // _KTB_CONSTR_STATS
298
299  // General statistics on the depth of current node
300  // the depth of the currently accessed node during building up
301  int _currDepth;
302};
303
304//------------------------------------------------------
305// class which enables to use some functions with direct
306// access to the members of the tree
307// traversal classes should be derived from this class
308class CKTBNodeIterator:
309  public CKTBNodeAbstract
310{
311protected:
312  int rayOffset; 
313public:
314  // default constructor
315  CKTBNodeIterator() { }
316  // default destructor
317  ~CKTBNodeIterator() { }
318
319  ObjectContainer* GetObjList(const SKTBNode *nodep) const {
320    return nodep->objlist;
321  }
322 
323  float GetSplitValue(const SKTBNode *nodep) const {
324    return nodep->splitPlane;
325  }
326   
327#ifdef _SHORT_FORM_MINBOX
328  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
329    return (nodep+1)->minbox;
330  } 
331#else // _SHORT_FORM_MINBOX
332  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
333    // Here is the overlapping to save some memory !!!
334    return (SBBox*)(((char*)nodep)+24);
335  } 
336#endif // _SHORT_FORM_MINBOX
337 
338  ObjectContainer* GetTagObjList(const SKTBNode *node) const {
339    return node->objlist;
340  }
341
342  // test the objects in the full leaf p and if finds the closest intersection
343  // with object so tmin<= t <= tmax, returns the pointer to that
344  // object, t is returned in tmax
345  int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p);
346  int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p, int rayIndex);
347
348  // test the objects in the full leaf and finds out any intersection
349  // in this case returns the pointer to the object, otherwise NULL
350  int HitAnyObj(const SimpleRay &ray, const SKTBNode *p);
351
352  // ------------------------------------------------------------------------
353  // Only abstract functions to simplify the interface
354
355  // this resets the nesting to start from the zero depth (root)
356  virtual void ResetTraversalDepth() = 0;
357
358  // sets the bbox and the root node for this traversal class
359  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot) = 0;
360
361  // Find the minimum box on containg a point or leaf, if there are
362  // no boxes on the way from a point to the leaf containing the point
363  virtual const SKTBNode* Locate(const Vector3 &point);
364}; // class CKTBNodeIterator
365
366}
367
368#endif // __KTB_H__
Note: See TracBrowser for help on using the repository browser.