[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" |
---|
[2629] | 22 | #include "IntersectableWrapper.h" |
---|
[2582] | 23 | |
---|
| 24 | namespace GtpVisibilityPreprocessor { |
---|
| 25 | |
---|
| 26 | // forward declarations |
---|
| 27 | class 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 | |
---|
[2629] | 45 | class AxisAlignedBox3Intersectable: |
---|
| 46 | public IntersectableWrapper<AxisAlignedBox3> |
---|
| 47 | { |
---|
| 48 | public: |
---|
| 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 | // --------------------------------------------------------------- |
---|
[2582] | 63 | // The base class for KD-tree with irregular change of axes, where |
---|
| 64 | // the splitting plane can be positioned. |
---|
| 65 | class CKTBABuildUp: |
---|
| 66 | public CKTBAllocManPredecessor |
---|
| 67 | { |
---|
| 68 | public: |
---|
| 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 | |
---|
[2629] | 237 | //---------------------------------------------------------------- |
---|
[2582] | 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 | |
---|
[2629] | 251 | // -------------- AUTOMATIC TERMINATION CRITERIA ---------------- |
---|
[2582] | 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 | |
---|
| 580 | protected: |
---|
| 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 | |
---|
[2629] | 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 | |
---|
[2582] | 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); |
---|
| 639 | public: |
---|
| 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 | |
---|
| 646 | public: |
---|
| 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 | |
---|