source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbs.h @ 2632

Revision 2632, 11.5 KB checked in by bittner, 17 years ago (diff)
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, January 2008
12
13#ifndef __KTBS_H__
14#define __KTBS_H__
15
16// GOLEM headers
17#include "configh.h"
18#include "ktbconf.h"
19#include "ktb.h"
20#include "ktb8b.h"
21#include "ktbai.h"
22#include "Containers.h"
23#include "IntersectableWrapper.h"
24
25namespace GtpVisibilityPreprocessor {
26
27// forward declarations
28class SKTBNode;
29
30#ifndef _KTB8Bytes
31// Use 12 Bytes representation
32#define CKTBAllocManPredecessor CKTBAllocMan
33#undef  SKTBNodeT
34#define SKTBNodeT CKTBNodeAbstract::SKTBNode
35#else
36// Use 8 Bytes representation per node
37#define CKTBAllocManPredecessor CKTB8BAllocMan
38#undef  SKTBNodeT
39#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode
40#endif
41
42#ifndef INFINITY
43#define INFINITY 10e10
44#endif
45
46// --------------------------------------------------------------- 
47// The base class for KD-tree with irregular change of axes, where
48// the splitting plane can be positioned.
49class CKTBSBuildUp:
50  public CKTBAllocManPredecessor
51{
52protected:
53  struct SSplitState
54  {
55    // counts
56    int   cntAll;       // the number of all objects in the bounding box
57    int   cntLeft;      // the count of bounding boxes on the left
58    int   cntRight;     // the count of bounding boxes on the right
59    int   thickness;    // the count of bounding boxes straddling the splitting plane
60
61    // The buckets
62    int   bucketN; // the number of buckets
63    int   *bucketMin; // the buckets for left (minimum) boundaries
64    int   *bucketMax; // the buckets for right (max) boundaries
65
66    CKTBAxes::Axes  axis;  // the axis, where the splitting is proposed
67    float sizeb[3];     // the size of the box for x, y, and z
68    SBBox box;          // the box, that is subdivided
69
70    // derived values from basic ones
71    float width;        // the size of bounding box along the axis
72    float frontw;       // the size of the bounding box in another axis (depth)
73    float topw;         // the size of the bounding box in next next axis (height)
74    float areaSplitPlane; // the area of the splitting plane
75    float areaSumLength; // the size of the bounding as sum of height and depth
76    float areaWholeSA2; // the half of the surface area of the whole box for this node
77
78    // The position for this splitting plane to be evaluated
79    float position; // the distance from the left boundary of the box for this node
80    // The position for the next position, makes sense only for free interval (thickness=0)
81    float position2; // the distance from the left boundary of the box for this node
82   
83    // The evaluation best cost until now
84    float bestCost;
85    // The position to be used
86    float bestPosition;
87    // The second best position - NOT USED AT THE MOMENT FOR SAMPLING !!!
88    float bestPosition2;
89    // Which mechanism to be used for splitting, either 0,1, or 2 splitting planes
90    int   bestTwoSplits;
91
92    // setting the evaluation for split cases that must not be done
93    float WorstEvaluation() const { return MAXFLOAT;}
94   
95    // The initialization for the first axis to be tested.
96    void InitXaxis(int cnt, const SBBox &box);
97    void InitYaxis(int cnt, const SBBox &box);
98    void InitZaxis(int cnt, const SBBox &box);
99
100    // Normalize the best cost by surface area of the box
101    void NormalizeCostBySA2() { bestCost /= areaWholeSA2;}
102
103    SSplitState():bucketN(0), bucketMin(0), bucketMax(0) { }
104    ~SSplitState() { delete []bucketMin; delete []bucketMax;}
105
106    void InitBuckets() {
107      assert(bucketMin);
108      assert(bucketMax);
109      for (int i = 0; i < bucketN; i++) {
110        bucketMin[i] = 0;
111        bucketMax[i] = 0;
112      } // for
113    }
114  };
115
116  // splitting state for current search
117  SSplitState state;
118 
119  // structure for prefered and required params for evaluation functions
120  // and the termination criteria
121  struct SReqPrefParams
122  {
123    //if any position on required axis is preferred for next subdivision step
124    float reqPosition; // then reqPosition>0
125    // if any axis is prefered for next step
126    bool  useReqAxis;
127    // the prescribed axis for the next subdivision
128    CKTBAxes::Axes reqAxis;
129
130    // -------------- AUTOMATIC TERMINATION CRITERIA ---------------------
131    // the ratio of improvement for the cost by subdivision and not-subdividing
132    // for the previous subdivision
133    float ratioLast;
134    // the ratio of improvement for the subdivision in the previous step
135    float ratioLastButOne;
136    // the number of subdivision from the root node, where the improvement
137    // in the cost failed
138    int   failedSubDivCount;
139    void Init() {
140      reqPosition = Limits::Infinity;
141      useReqAxis = false;
142      reqAxis = CKTBAxes::EE_Leaf;
143 
144      ratioLast = 1000.0;
145      ratioLastButOne = 1000.0;
146      failedSubDivCount = 0;
147    }
148  };
149
150  // initialize required and preferenced parameters before first subdivision
151  void InitReqPref(SReqPrefParams *pars);
152
153  // the array of preferred parameters used as a stack
154  SReqPrefParams *pars;
155 
156  // --------------------------------------------------------------------
157  bool verbose;
158
159  // ---------------------------------
160  // The selection of the axis
161  int _algorithmForAxisSelection;
162 
163  //  ---- termination criteria -----
164  int algorithmAutoTermination; // the algorithm for automatic termination criteria
165  int maxDepthAllowed; // maximal depth of CKTB tree
166  int maxListLength; // maximal list length of CKTB tree
167  int maxCountTrials; // maximum number of trials for automatic termination criteria
168  // the cutting off empty space in leaves
169  bool cutEmptySpace; // if to cut off empty space in leaves in postprocessing
170  int absMaxAllowedDepth; // maximal depth from the root - mut not be surpassed
171  // maximal depth allowed for cutting within the leaf .. cut off empty space
172  int maxEmptyCutDepth; // must be <0,1,2,3,4,5,6> since six planes are enough
173  // This is working variable, denoting the depth of the leaf to be created.
174  int startEmptyCutDepth;
175
176  // Biasing the empty cuts (no objects are split). The cost is multiplied
177  // by the coefficient which is assumed to be 0.8-0.9
178  float  biasFreeCuts;
179 
180  // flag if to put minimum enclosing boxes sparsely during the construction
181  bool    makeMinBoxes;
182  // if we make tight boxes if we put min box !
183  bool    makeTightMinBoxes;
184  // parameters to drive the minboxes construction
185  int     minObjectsToCreateMinBox, minDepthDistanceBetweenMinBoxes;
186  float   minSA2ratioMinBoxes;
187  // Make min box here
188  bool   makeMinBoxHere;
189
190  // two next axes are stored in oaxes for each axis
191  static const CKTBAxes::Axes oaxes[3][2]; 
192
193  // for some functions it is necessary to have determined the following costs
194  float       Ct; // traversal cost - going in given direction != decision
195  float       Ci; // intersection cost - average intersection cost with object
196 
197  // ------ data to create the tree --------------------
198  int         initcnt;      // initial number of objects
199  SBBox       wBbox; // the box of the world in float values
200  Vector3   boxSize;   // the size of world bounding box in float
201  float       wholeBoxArea; // the surface area of the scene bounding box
202
203  // if to print out the tree during construction
204  bool _printCuts;
205
206  // ------------------------------------------------------
207  // A structure for a single step of subdivision
208  struct SInputData {
209    // the list of objects associated with the interior node
210    ObjectContainer *objlist;
211   
212    // the traversal bounding box of the scene (not necessarily tight)
213    SBBox box;
214    // the box, which is tight and it lies inside the traversal box
215    SBBox tightbox;
216   
217    // the number of objects in the node (= number_of_boundaries/2)
218    int count;
219
220    // ----------------------------
221    // The mode of subdivision
222    ESubdivMode modeSubDiv;
223
224    // Some prescribed parameters to be used
225    SReqPrefParams pars;
226
227    // ----------------------------------
228    // Axis to be used if prescribed
229    CKTBAxes::Axes axis;
230    // the position to be used for MakeOneCut
231    float position;
232    float position2;
233
234    // if 1 or 2 splits
235    int twoSplits;
236    // the best cost
237    float bestCost;
238
239    // if to make subdivision on the left node
240    int makeSubdivisionLeft;
241    // if to make subdivision on the right node
242    int makeSubdivisionRight;
243
244    // -----------------------------------
245    // When the min boxes was inserted as the first one
246    int lastDepthForMinBoxes;
247    // The surface area for the last minimum box inserted
248    float lastMinBoxSA2;
249    // The pointer to the last inserted minimum box
250    SKTBNodeT* lastMinBoxNode;
251  private:
252    void Init() {
253      objlist = 0;
254      box.Initialize();
255      tightbox.Initialize();
256      count = 0;
257      pars.Init();
258      makeSubdivisionLeft = makeSubdivisionRight = 1;
259      lastDepthForMinBoxes = 0;
260      lastMinBoxSA2 = INFINITY;
261      lastMinBoxNode = 0;
262    }
263   
264  public:
265
266    // -----------------------------------
267    // Implicit constructor
268    SInputData() {
269      Init();
270    }
271    ~SInputData() {
272      Free();
273    }
274
275    void Free() {
276      delete objlist;
277      objlist = 0;
278    }
279   
280    void CopyBasicData(SInputData *d) {
281      box = d->box;
282      count = 0;
283      modeSubDiv = d->modeSubDiv;
284      pars = d->pars;
285      axis = d->axis;
286      position = d->position;
287      // added 12/2007 VH
288      position2 = d->position2;
289      //
290      makeSubdivisionLeft = d->makeSubdivisionLeft;
291      makeSubdivisionRight = d->makeSubdivisionRight;     
292      // Intentionally, do not copy vectors of items
293      lastDepthForMinBoxes = d->lastDepthForMinBoxes;
294      lastMinBoxSA2 = d->lastMinBoxSA2;
295      lastMinBoxNode = d->lastMinBoxNode;
296    }
297  };
298
299  // Stack of data to be used
300  SInputData *stackID;
301  // current index
302  int         stackIndex;
303  // the maximum depth of tree
304  int         maxTreeDepth;
305  // the depth of the stack
306  int         stackDepth;
307 
308  SInputData* AllocNewData() {
309    int i = stackIndex;
310    stackIndex++;
311    assert(stackIndex < stackDepth);
312    return &(stackID[i]);
313  }
314  // Free the last data allocated
315  void FreeLastData() { stackIndex--; }
316
317  // returns a box enclosing all the objects in the node
318  void GetTightBox(const SInputData &i, SBBox &tbox);
319
320  // Compute if to subdivide and where
321  SKTBNodeT* SubDiv(SInputData *d);
322  // creates one cut inside CKTB tree
323  SKTBNodeT* MakeOneCut(SInputData *i);
324
325  SInputData* Init(ObjectContainer *objlist, const AxisAlignedBox3 &box);
326
327  // make the full leaf from current node
328  SKTBNodeT* MakeLeaf(SInputData *d);
329
330  // It goes through the splitting plane positions and computes the cost
331  void GetSplitPlaneOpt(SInputData *d, int axisToTest);
332
333  // Given the splitting plane position, it computes the cost
334  void EvaluateCost(SSplitState &state);
335  void EvaluateCostFreeCut(SSplitState &state);
336
337  // setting the evaluation for split cases that must not be done
338  float WorstEvaluation() const { return MAXFLOAT;}
339
340  // update the best value for evaluation
341  int UpdateEvaluation(float &eval, const float &newEval);
342
343public:
344  // default constructor
345  CKTBSBuildUp();
346
347  // default destructor
348  virtual ~CKTBSBuildUp();
349
350  // provide info about construction method
351  virtual void ProvideID(ostream &app); 
352 
353  // constructs the KD-tree for given objectlist and given bounding box
354  // returns NULL in case of failure, in case of success returns
355  // the pointer to the root node of constructed KD-tree.
356  virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
357                             const AxisAlignedBox3 &box,
358                             bool verbose = true);
359};
360
361}
362
363#endif // __KTBS_H__
364
Note: See TracBrowser for help on using the repository browser.