source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbai.h @ 2629

Revision 2629, 21.7 KB checked in by bittner, 17 years ago (diff)

commit after merge with vlastimil

Line 
1// ============================================================================
2// $Id: $
3//
4// ktbai.h
5//     classes for building up the different KD-trees
6//
7// Class: CKTBBuildUp, CKTBBuildUp_new
8//
9// REPLACEMENT_STRING
10//
11// Initial coding by Vlasta Havran, February 2007
12
13#ifndef __KTBAI_H__
14#define __KTBAI_H__
15
16// GOLEM headers
17#include "configh.h"
18#include "ktbconf.h"
19#include "ktb.h"
20#include "ktb8b.h"
21#include "Containers.h"
22#include "IntersectableWrapper.h"
23
24namespace GtpVisibilityPreprocessor {
25
26// forward declarations
27class SKTBNode;
28
29#ifndef _KTB8Bytes
30// Use 12 Bytes representation
31#define CKTBAllocManPredecessor CKTBAllocMan
32#undef  SKTBNodeT
33#define SKTBNodeT CKTBNodeAbstract::SKTBNode
34#else
35// Use 8 Bytes representation per node
36#define CKTBAllocManPredecessor CKTB8BAllocMan
37#undef  SKTBNodeT
38#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode
39#endif
40
41#ifndef INFINITY
42#define INFINITY 10e10
43#endif
44
45class AxisAlignedBox3Intersectable:
46    public IntersectableWrapper<AxisAlignedBox3>
47{
48public:
49  AxisAlignedBox3Intersectable(const AxisAlignedBox3 &item):
50    IntersectableWrapper<AxisAlignedBox3>(item) { }
51
52  AxisAlignedBox3 GetBox() const { return mItem;}
53
54  int Type() const
55  {
56    // This is not ture, but for our purposes it is OK
57    return Intersectable::TRIANGLE_INTERSECTABLE;
58  }
59
60};
61
62// --------------------------------------------------------------- 
63// The base class for KD-tree with irregular change of axes, where
64// the splitting plane can be positioned.
65class CKTBABuildUp:
66  public CKTBAllocManPredecessor
67{
68public:
69  // The definition of flags
70  enum EBoundaryType {
71    EE_LeftBoundary = 1,
72    EE_InLeftList = 1,
73    EE_RightBoundary = 2,
74    EE_InRightList = 2,
75    EE_BothBoundaries = 3,
76    EE_ToBeRemoved = 4
77  };
78 
79  // the item in the list for all objects
80  struct SSolid
81  {
82    Intersectable *obj; // pointer to the object itself
83    unsigned int flags; // the flags to be set, they are common for all boundaries
84
85    // query functions
86    inline bool InFirstList() const { return (flags & EE_InLeftList); }
87    inline bool InSecondList() const { return (flags & EE_InRightList); }
88    inline bool InBothLists() const { return (flags == EE_BothBoundaries); }
89    inline bool ToBeRemoved() const { return (flags & EE_ToBeRemoved); }
90    inline bool ToBeRemovedOnly() const { return (flags == EE_ToBeRemoved); }
91    inline unsigned int Flags() const { return flags;}
92    // Setting functions
93    inline void SetInFirstList() { flags |= 1; }
94    inline void SetInSecondList() { flags |= 2; }
95    inline void SetToRemove() { flags |= 4; }
96    inline void SetToRemoveOnly() { flags = 4; }
97   
98    inline void ResetFlags() { flags = 0;}
99    SSolid() { ResetFlags(); }
100  };
101
102  // The container of the object entries
103  typedef vector<SSolid> SSolidVec;
104 
105  // the array of all objects in the scene
106  SSolidVec solidArray;
107
108  // the item of the boundary list - either left or right boundary
109  // of the axis-aligned bounding box of the object. This structure
110  // is intentionally of small size, namely 12 or 16 Bytes.
111
112  struct SItem
113  {
114    float pos;  // boundary values for all three axes
115    struct SSolid *obj; // the pointer to the object with flags
116
117    // The axis represented by the item (CKTBAxes::Axes)
118    uint1 axis; // = (X=0, Y=1, Z=2)
119    // the type of boundary (low, high)
120    uint1 typeLoHi;
121    // only allignment to 12 Bytes
122    //uint2 dummy;
123    // -------------------------------------------------
124    // some basic functions
125    SItem(float posN, SSolid *objN, int axisN, EBoundaryType LoHiN) {
126      pos = posN; obj = objN; axis = axisN; typeLoHi = (uint1)LoHiN;
127    }
128    // Simply constructor, just initializing flags
129    SItem() {obj = 0; axis = 255; typeLoHi = 0; }
130    //SItem& operator=(const SItem &src) {
131    //  this->pos = src.pos; this->obj = src.obj;
132    //  this->axis = src.axis; this->typeLoHi = src.typeLoHi;
133    //  return *this;
134    // }
135
136    // Simple query functions
137    inline bool IsLeftBoundary() const {
138      return (typeLoHi ==  EE_LeftBoundary);
139    }
140    inline bool IsRightBoundary() const {
141      return (typeLoHi == EE_RightBoundary);
142    }   
143    // Simple set functions
144    void SetLeftBoundary() { typeLoHi = EE_LeftBoundary; }
145    void SetRightBoundary() { typeLoHi = EE_RightBoundary; }
146    // For quicksort
147    friend bool operator<(const SItem &a, const SItem &b) {
148      if (a.pos < b.pos)
149        return -1;
150      else
151        if (a.pos > b.pos)
152          return 1;
153        else
154          // the coordinates are equal
155          if ( (a.IsRightBoundary()) &&
156               (b.IsLeftBoundary()) )
157            return -1; // right_boundary < left_boundary
158          else
159            if ( (a.IsLeftBoundary()) &&
160                 (b.IsRightBoundary()) )
161              return 1; // left_boundary > right_boundary
162      // coordinates are equal, the same value and type, order is correct
163      return 0;
164    }
165  };
166
167  // Here is the extended element for RadixSort
168  struct SItemRadix:
169    public SItem
170  {
171    // the pointer needed to chain the data during sorting
172    SItemRadix *next;
173    // Basic operations
174    SItemRadix(): SItem() { next = 0;}
175    // This is necessary constructor
176    SItemRadix(const SItem &it) {
177      memcpy(this, &it, sizeof(SItem));
178      next = 0;
179    }
180    // This is necessary copy operator
181    SItemRadix& operator=(const SItem &it) {
182      memcpy(this, &it, sizeof(SItem));
183      next = 0;
184      return *this;
185    }
186  };
187 
188
189  // ---------------------------------------------------------
190  // The declaration of container with object boundaries
191  typedef vector<SItem> SItemVec;
192  typedef vector<SItemRadix> SItemVecRadix;
193
194  // ---------------------------------------------------------
195  // Sorting by QuickSort and RadixSort
196
197  // QuickSort
198  // compare function for SItem*
199  static int Compare(const SItem *p, const SItem *q);
200  // bounding box sorting by Quick Sort
201  void SortOneAxis(SItemVec &itemvec, int cnt, int * const stackQuickSort);
202
203  // -------------------------------------
204  // For Radix Sort
205  // Radix sort int 2^8=256 classes and three
206  // passes .. 4x8 bits=32 bits
207  bool _useRadixSort;
208  enum { RXBITS30 = 11 }; // the number of bits used for one phase of Radix Sort
209  enum { // the number of buckets for RadixSort
210         RXBUFS30 = 1 << RXBITS30,
211         RXBUFS30_2 = 1 << (RXBITS30-1)};
212  // This is one bucket of radix soft
213  struct SRadix {
214    SItemRadix *beg, *end;
215  };
216  // for 3-passes radix sort over the vectored data
217  void CopyToAuxArray(const SItemVec &bounds, SItemVecRadix &aux);
218  void RadixPassHoffset11(SItemVecRadix &bounds, int bit, SRadix *rb,
219                          float offset, SItemRadix **start);
220  void RadixPass11(SItemRadix **start, int cnt, int bit, SRadix *rb);
221  void RadixPassOffset10(SItemRadix **start, int cnt, int bit, SRadix *rb,
222                         float offset);
223  void CopyFromAuxArray(SItemRadix *aux, SItemVec &bounds);
224
225  // forward declaration
226  struct SInputData;
227  // sorts all three axes, cnt is the number of elems
228  void SortAxes(SInputData *data);
229  // initialization of the bounding box for a given object
230  void LoadBB(SBBox &bb, SSolid *obj);
231
232  // test if the lists are correctly sorted
233  void Check3List(SInputData *data);
234  void Check1List(SItemVec *vec, int axis, int countExpected);
235  void Check1List(SInputData *data, int axis, int countExpected);
236   
237  //----------------------------------------------------------------
238  // Termination criteria and fixing the splitting plane orientation
239
240  // structure for prefered and required params for evaluation functions
241  // and the termination criteria
242  struct SReqPrefParams
243  {
244    //if any position on required axis is preferred for next subdivision step
245    float reqPosition; // then reqPosition>0
246    // if any axis is prefered for next step
247    bool  useReqAxis;
248    // the prescribed axis for the next subdivision
249    CKTBAxes::Axes reqAxis;
250
251    // -------------- AUTOMATIC TERMINATION CRITERIA ----------------
252    // the ratio of improvement for the cost by subdivision and not-subdividing
253    // for the previous subdivision
254    float ratioLast;
255    // the ratio of improvement for the subdivision in the previous step
256    float ratioLastButOne;
257    // the number of subdivision from the root node, where the improvement
258    // in the cost failed
259    int   failedSubDivCount;
260    void Init() {
261      reqPosition = Limits::Infinity;
262      useReqAxis = false;
263      reqAxis = CKTBAxes::EE_Leaf;
264 
265      ratioLast = 1000.0;
266      ratioLastButOne = 1000.0;
267      failedSubDivCount = 0;     
268    }
269  };
270
271  // initialize required and preferenced parameters before first subdivision
272  void InitReqPref(SReqPrefParams *pars);
273
274  // ------------------------------------------------------
275  // A structure for a single step of subdivision
276  struct SInputData {
277    // the traversal bounding box of the scene (not necessarily tight)
278    SBBox box;
279    // the number of objects in the node (= number_of_boundaries/2)
280    int count;
281    // the number of reserved boundaries in the node (>=2*count)
282    int cntReserved;
283
284    // The list of x-boundaries, y-boundaries, z-boundaries
285    SItemVec *xvec;
286    SItemVec *yvec;
287    SItemVec *zvec;
288
289    // only for allignment, it can be used for different purpose
290    int algorithmBreakAx;
291
292    // ----------------------------
293    // The mode of subdivision
294    ESubdivMode modeSubDiv;
295
296    // Some prescribed parameters to be used
297    SReqPrefParams pars;
298
299    // ----------------------------------
300    // Axis to be used if prescribed
301    CKTBAxes::Axes axis;
302    // the position to be used for MakeOneCut
303    float position;
304    float position2;
305    // the number of objects to be duplicated
306    int cntThickness;
307    // the iterator to be used for splitting
308    SItemVec::iterator bestIterator;
309    // if 1 or 2 splits
310    int twoSplits;
311    // the best cost
312    float bestCost;
313
314    // if to make subdivision on the left node
315    int makeSubdivisionLeft;
316    // if to make subdivision on the right node
317    int makeSubdivisionRight;
318
319    // -----------------------------------
320    // When the min boxes was inserted as the first one
321    int lastDepthForMinBoxes;
322    // The surface area for the last minimum box inserted
323    float lastMinBoxSA2;
324    // The pointer to the last inserted minimum box
325    SKTBNodeT* lastMinBoxNode;
326  private:
327    void Init() {
328      box.Initialize();
329      algorithmBreakAx = 0;
330      count = 0; cntReserved = 0;
331      xvec = yvec = zvec = 0;
332      pars.Init();
333      cntThickness = 0;
334      makeSubdivisionLeft = makeSubdivisionRight = 1;
335      lastDepthForMinBoxes = 0;
336      lastMinBoxSA2 = INFINITY;
337      lastMinBoxNode = 0;
338    }
339  public:
340
341    // -----------------------------------
342    // Implicit constructor
343    SInputData() {
344      Init();
345    }
346    ~SInputData() {
347      Free();
348    }
349   
350    // Allocate at least for one object
351    void Alloc(int sizeN = 2) {
352      if (!xvec)
353        xvec = new GALIGN16 vector<SItem>;
354      assert(xvec);
355      if (!yvec)
356        yvec = new GALIGN16 vector<SItem>;
357      assert(yvec);
358      if (!zvec)
359        zvec = new GALIGN16 vector<SItem>;
360      assert(zvec);
361      cntReserved = sizeN;
362      // cout << "SizeN = " << sizeN << endl;
363      xvec->reserve(sizeN); xvec->resize(0);
364      yvec->reserve(sizeN); yvec->resize(0);
365      zvec->reserve(sizeN); zvec->resize(0);
366      count = 0;
367    } // Alloc
368    void Free() {
369      delete xvec; xvec = 0;
370      delete yvec; yvec = 0;
371      delete zvec; zvec = 0;
372      count = cntReserved = 0;
373    } // Free
374    void Reserve(int sizeN) {
375      assert(xvec);
376      assert(yvec);
377      assert(zvec);
378      if (sizeN > cntReserved) {
379        xvec->reserve(sizeN);
380        yvec->reserve(sizeN);
381        zvec->reserve(sizeN);
382        cntReserved = sizeN;
383      }
384    } // Reserve
385    void Resize(int sizeN) {
386      assert(sizeN >= 0);
387      assert(xvec);
388      assert(yvec);
389      assert(zvec);
390      xvec->resize(sizeN);
391      yvec->resize(sizeN);
392      zvec->resize(sizeN);
393      count = sizeN*2;
394    } // Reserve
395
396    // Return the item using the index
397    SItemVec* GetItemVec(int i) {
398      assert((i >= 0) && (i < 3));
399      return (&xvec)[i];
400    }
401    void CopyBasicData(SInputData *d) {
402      box = d->box;
403      count = 0;
404      algorithmBreakAx = d->algorithmBreakAx;
405      modeSubDiv = d->modeSubDiv;
406      pars = d->pars;
407      axis = d->axis;
408      position = d->position;
409      // added 12/2007 VH
410      position2 = d->position2;
411      cntThickness = d->cntThickness;
412      //
413      makeSubdivisionLeft = d->makeSubdivisionLeft;
414      makeSubdivisionRight = d->makeSubdivisionRight;     
415      // Intentionally, do not copy vectors of items
416      lastDepthForMinBoxes = d->lastDepthForMinBoxes;
417      lastMinBoxSA2 = d->lastMinBoxSA2;
418      lastMinBoxNode = d->lastMinBoxNode;
419    }
420  };
421
422  // Stack of data to be used
423  SInputData *stackID;
424  // current index
425  int         stackIndex;
426  // the maximum depth of tree
427  int         maxTreeDepth;
428  // the depth of the stack
429  int         stackDepth;
430  // Return the new data to be used
431  SInputData* AllocNewData() {
432    int i = stackIndex;
433    stackIndex++;
434    return &(stackID[i]);
435  }
436  SInputData* AllocNewData(int cnt) {
437    int i = stackIndex;
438    stackID[i].Alloc(cnt);
439    stackIndex++;
440    return &(stackID[i]);
441  }
442  // Free the last data allocated
443  void FreeLastData() { stackIndex--; }
444   
445  // ---------------------------------------------------------------------
446  // upper-level function for building up CKTB tree
447
448  // creates all the auxiliary structures for building up CKTB tree
449  SInputData* Init(ObjectContainer *objlist, const AxisAlignedBox3 &box);
450
451  void DeleteAuxiliaryData() {
452    for (int i = 0; i < stackDepth; i++) {
453      stackID[i].Free();
454    }
455  }
456 
457  // ---------------------------------------------------------------------
458  // Working with boundaries of objects
459 
460  // make the full leaf from current node
461  SKTBNodeT* MakeLeaf(SInputData *i);
462
463  // breaks the list into two list for a given axis and value
464  void BreakAx(SInputData *i, int axis,
465               SInputData *right,
466               int &cntL, int &cntR);
467  // breaks the list into two list for a given axis and value
468  void BreakAxPosition(SInputData *i, int axis,
469                       SInputData *right,
470                       int &cntL, int &cntR);
471
472  // split the list in the other than splitting axis into two lists
473  void DivideAx_I(SInputData *i, int axis,
474                  SInputData *right,
475                  int &cntL, int &cntR);
476  // also split and set the boundaries to be only in the first list
477  void DivideAx_II(SInputData *i, int axis,
478                   SInputData *right,
479                   int &cntL, int &cntR);
480  // split the list in the other than splitting axis into two lists
481  void DivideAx_I_opt(SInputData *i, int axis,
482                      SInputData *right,
483                      int cntL, int cntR);
484  // also split and set the boundaries to be only in the first list
485  void DivideAx_II_opt(SInputData *i, int axis,
486                       SInputData *right,
487                       int cntL, int cntR);
488  // reduce bounding boxes of objects split by the splitting plane
489  void ReduceBBoxes(SInputData *i, int axis,
490                    SInputData *right,
491                    const float &position);
492  // Remove the objects from the containter
493  void RemoveObjects(SItemVec *, int cntObjects);
494  void RemoveObjectsReset(SItemVec *, int cntObjects);
495
496  // Computes the tight bounding box and the number of changed planes
497  // when the tight box is used
498  int GetEBox(const SInputData &i, SBBox &tbox);
499
500  // returns a box enclosing all the objects in the node
501  void GetTightBox(const SInputData &i, SBBox &tbox);
502 
503  // creates one cut inside CKTB tree
504  SKTBNodeT* MakeOneCut(SInputData *i);
505  // recursive function for creation of CKTB tree
506  SKTBNodeT* SubDiv(SInputData *i);
507
508  // ------ Methods for building up CKTB tree ------------------
509  // returns 1 to supress to call the following criteria
510  struct SSplitState
511  {
512    // counts
513    int   cntAll;       // the number of all objects in the bounding box
514    int   cntLeft;      // the count of bounding boxes on the left
515    int   cntRight;     // the count of bounding boxes on the right
516    int   thickness;    // the count of bounding boxes straddling the splitting plane
517
518    CKTBAxes::Axes  axis;  // the axis, where the splitting is proposed
519    float sizeb[3]; // the size of the box for x, y, and z
520    SBBox box; // the box, that is subdivided
521   
522    // derived values from basic ones
523    float width;        // the size of bounding box along the axis
524    float frontw;       // the size of the bounding box in another axis (depth)
525    float topw;         // the size of the bounding box in next next axis (height)
526    float areaSplitPlane; // the area of the splitting plane
527    float areaSumLength; // the size of the bounding as sum of height and depth
528    float areaWholeSA2; // the half of the surface area of the whole box for this node
529
530    // The iterator valid for current position
531    SItemVec::iterator it;   
532    // The position for this splitting plane to be evaluated
533    float position; // the distance from the left boundary of the box for this node
534    // The position for the next position, makes sense only for free interval (thickness=0)
535    float position2; // the distance from the left boundary of the box for this node
536   
537    // The evaluation best cost until now
538    float bestCost;
539    // The position to be used
540    SItemVec::iterator bestIterator;
541    // The number of objects stradling the spliting plane for best position
542    int   bestThickness;
543    // Which mechanism to be used for splitting, either 0,1, or 2 splitting planes
544    int   bestTwoSplits;
545
546    // setting the evaluation for split cases that must not be done
547    float WorstEvaluation() const { return MAXFLOAT;}
548   
549    // The initialization for the first axis to be tested.
550    void InitXaxis(int cnt, const SBBox &box);
551    void InitYaxis(int cnt, const SBBox &box);
552    void InitZaxis(int cnt, const SBBox &box);
553    // This function can be called only if InitXaxis was called before
554    void ReinitYaxis(int cnt, const SBBox &box);
555    // This function can be called only if InitXaxis was called, and subsequently
556    // the function ReinitYaxis was called.
557    void ReinitZaxis(int cnt, const SBBox &box);
558    // Normalize the best cost by surface area of the box
559    void NormalizeCostBySA2() { bestCost /= areaWholeSA2;}
560  };
561
562  // splitting state for current search
563  SSplitState state;
564
565  // Evaluating the cost, given the state and the values of splitting
566  void EvaluateCost(SSplitState &state);
567
568  // Evaluating the cost, given the state and the values of splitting
569  // for free cuts
570  void EvaluateCostFreeCut(SSplitState &state);
571 
572  // ----- statistical data ---------
573  int cntDuplicate;     // count of duplicated objects until now
574  bool resetFlagsForBreakAx;
575
576  // ------ debugging data ----------
577  // if to print out the tree during construction
578  bool _printCuts;
579 
580protected:
581
582  // ---------------------------------
583  // The selection of the axis
584  int _algorithmForAxisSelection;
585 
586  //  ---- termination criteria -----
587  int algorithmAutoTermination; // the algorithm for automatic termination criteria
588  int maxDepthAllowed; // maximal depth of CKTB tree
589  int maxListLength; // maximal list length of CKTB tree
590  int maxCountTrials; // maximum number of trials for automatic termination criteria
591  // the cutting off empty space in leaves
592  bool cutEmptySpace; // if to cut off empty space in leaves in postprocessing
593  int absMaxAllowedDepth; // maximal depth from the root - mut not be surpassed
594  // maximal depth allowed for cutting within the leaf .. cut off empty space
595  int maxEmptyCutDepth; // must be <0,1,2,3,4,5,6> since six planes are enough
596  // This is working variable, denoting the depth of the leaf to be created.
597  int startEmptyCutDepth;
598
599  // Biasing the empty cuts (no objects are split). The cost is multiplied
600  // by the coefficient which is assumed to be 0.8-0.9
601  float  biasFreeCuts;
602 
603  // ---------- Special improvements on the kd-tree construction --------
604  // flag if to split bounding boxes during splitting
605  bool    splitClip;
606  // flag if to put minimum enclosing boxes sparsely during the construction
607  bool    makeMinBoxes;
608  // if we make tight boxes if we put min box !
609  bool    makeTightMinBoxes;
610  // parameters to drive the minboxes construction
611  int     minObjectsToCreateMinBox, minDepthDistanceBetweenMinBoxes;
612  float   minSA2ratioMinBoxes;
613  // Make min box here
614  bool   makeMinBoxHere;
615 
616  // two next axes are stored in oaxes for each axis
617  static const CKTBAxes::Axes oaxes[3][2];
618
619  // ------ data to create the tree --------------------
620  int         initcnt;      // initial number of objects
621  SBBox       wBbox; // the box of the world in float values
622  Vector3   boxSize;   // the size of world bounding box in float
623  float       wholeBoxArea; // the surface area of the scene bounding box
624 
625  // for some functions it is necessary to have determined the following costs
626  float       Ct; // traversal cost - going in given direction != decision
627  float       Ci; // intersection cost - average intersection cost with object
628
629  // just if to be verbose
630  bool verbose;
631 
632  // the main function of this class .. returns the best splitting plane
633  // in X axis, requires InitXaxis() to be called before or InitYaxis() or InitZaxis()
634  // optimized version
635  void GetSplitPlaneOpt(SItemVec *vec, int axisToTest);
636  void GetSplitPlaneOpt2(SItemVec *vec, int axisToTest);
637  void GetSplitPlaneOpt3(SItemVec *vec, int axisToTest);
638  void GetSplitPlaneOptUnroll4(SItemVec *vec, int axisToTest);
639public:
640  // setting the evaluation for split cases that must not be done
641  float WorstEvaluation() const { return MAXFLOAT;}
642
643  // update the best value for evaluation
644  int UpdateEvaluation(float &eval, const float &newEval);
645
646public:
647  // default constructor
648  CKTBABuildUp();
649
650  // default destructor
651  virtual ~CKTBABuildUp();
652
653  // provide info about construction method
654  virtual void ProvideID(ostream &app); 
655 
656  // constructs the KD-tree for given objectlist and given bounding box
657  // returns NULL in case of failure, in case of success returns
658  // the pointer to the root node of constructed KD-tree.
659  virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
660                             const AxisAlignedBox3 &box,
661                             bool verbose = true);
662};
663
664}
665
666#endif // __KTBAI_H__
667
Note: See TracBrowser for help on using the repository browser.