[2632] | 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 | |
---|
| 25 | namespace GtpVisibilityPreprocessor { |
---|
| 26 | |
---|
| 27 | // forward declarations |
---|
| 28 | class 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. |
---|
| 49 | class CKTBSBuildUp: |
---|
| 50 | public CKTBAllocManPredecessor |
---|
| 51 | { |
---|
| 52 | protected: |
---|
| 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 | |
---|
| 343 | public: |
---|
| 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 | |
---|