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