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

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