[2582] | 1 | // ===================================================================
|
---|
| 2 | // $Id: $
|
---|
| 3 | //
|
---|
| 4 | // ktb.cpp
|
---|
| 5 | //
|
---|
| 6 | // Implementation of basic functions to create kd-trees
|
---|
| 7 | //
|
---|
| 8 | // REPLACEMENT_STRING
|
---|
| 9 | //
|
---|
| 10 | // Copyright by Vlastimil Havran, 2006 - email to "vhavran AT seznam.cz"
|
---|
| 11 | // Initial coding by Vlasta Havran, 1998-2001.
|
---|
| 12 |
|
---|
| 13 | // GOLEM library
|
---|
| 14 | #include "ktb.h"
|
---|
| 15 | #include "Environment.h"
|
---|
| 16 |
|
---|
| 17 | // standard headers
|
---|
| 18 | #include <algorithm>
|
---|
| 19 |
|
---|
| 20 | namespace GtpVisibilityPreprocessor {
|
---|
| 21 |
|
---|
| 22 |
|
---|
| 23 | //-------------------------------------------------------------
|
---|
| 24 | // class CKTBNodeIterator .. implementation
|
---|
| 25 |
|
---|
| 26 | // test all objects in the leaf for intersection with ray
|
---|
| 27 | // and returns the pointer to closest one if exists
|
---|
| 28 | // and passing through parameter returns in tmax
|
---|
| 29 | int
|
---|
| 30 | CKTBNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p)
|
---|
| 31 | {
|
---|
| 32 | ObjectContainer *list = GetObjList(p);
|
---|
| 33 | if (!list) // no object
|
---|
| 34 | return 0;
|
---|
| 35 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 36 |
|
---|
| 37 | float tclosest = Limits::Infinity;
|
---|
| 38 | int intersected = 0;
|
---|
| 39 | // iterate the whole list and find out the nearest intersection
|
---|
| 40 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 41 | // if the intersection realy lies in the node
|
---|
| 42 | if ((*sc)->CastSimpleRay(ray) == Ray::INTERSECTION) {
|
---|
| 43 | // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
---|
| 44 | // tclosest = ray.
|
---|
| 45 | intersected = 1;
|
---|
| 46 | }
|
---|
| 47 | } // for all objects
|
---|
| 48 |
|
---|
| 49 | return intersected;
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 | int
|
---|
| 53 | CKTBNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p,
|
---|
| 54 | int rayIndex)
|
---|
| 55 | {
|
---|
| 56 | ObjectContainer *list = GetObjList(p);
|
---|
| 57 | if (!list) // no object
|
---|
| 58 | return 0;
|
---|
| 59 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 60 |
|
---|
| 61 | float tclosest = Limits::Infinity;
|
---|
| 62 | int intersected = 0;
|
---|
[2592] | 63 | // rayIndex += rayOffset;
|
---|
[2582] | 64 | // iterate the whole list and find out the nearest intersection
|
---|
| 65 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 66 | // if the intersection realy lies in the node
|
---|
| 67 | if ((*sc)->CastSimpleRay(ray, rayIndex)) {
|
---|
| 68 | // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
---|
| 69 | // tclosest = ray.
|
---|
| 70 | intersected = 1;
|
---|
| 71 | }
|
---|
| 72 | } // for all objects
|
---|
| 73 |
|
---|
| 74 | return intersected;
|
---|
| 75 | }
|
---|
| 76 |
|
---|
| 77 |
|
---|
| 78 | // test all objects in the leaf for intersection with ray
|
---|
| 79 | // and find any if exist .. returns this object, otherwise 0
|
---|
| 80 | int
|
---|
| 81 | CKTBNodeIterator::HitAnyObj(const SimpleRay &ray, const SKTBNode *p)
|
---|
| 82 | {
|
---|
| 83 | ObjectContainer *list = GetObjList(p);
|
---|
| 84 | if (!list) // no object
|
---|
| 85 | return 0;
|
---|
| 86 | ObjectContainer::iterator sc_end = list->end();
|
---|
| 87 |
|
---|
| 88 | float tclosest = Limits::Infinity;
|
---|
| 89 | int intersected = 0;
|
---|
| 90 | // iterate the whole list and find out the nearest intersection
|
---|
| 91 | for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 92 | Intersectable *is = (*sc);
|
---|
| 93 | // if the intersection realy lies in the node
|
---|
| 94 | if (is->CastSimpleRay(ray)) {
|
---|
| 95 | // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
---|
| 96 | // tclosest = ray.
|
---|
| 97 | return 1; // intersected
|
---|
| 98 | }
|
---|
| 99 | } // for all objects
|
---|
| 100 |
|
---|
| 101 | return 0;
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | const CKTBNodeAbstract::SKTBNode*
|
---|
| 105 | CKTBNodeIterator::Locate(const Vector3 & /*position*/)
|
---|
| 106 | {
|
---|
| 107 | cerr << "Locate vector - Not yet implemented" << endl;
|
---|
| 108 | return (SKTBNode*)0;
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 | // ---------------------------------------------------------------------
|
---|
| 112 | // Allocator for KTB tree
|
---|
| 113 |
|
---|
| 114 | // forget the content that is created by previous kd-tree construction
|
---|
| 115 | // or just init for the first use.
|
---|
| 116 | void
|
---|
| 117 | CKTBAllocMan::InitForConstructor()
|
---|
| 118 | {
|
---|
| 119 | #ifdef _KTB_CONSTR_STATS
|
---|
| 120 | _stats_interiorCount = 0;
|
---|
| 121 | _stats_bboxCount = 0;
|
---|
| 122 | _stats_minbboxCount = 0;
|
---|
| 123 | _stats_leafNodeCount = 0;
|
---|
| 124 | _stats_emptyLeftNodeCount = 0;
|
---|
| 125 | // Aggregate statistics
|
---|
| 126 | _sumLeafDepth = 0;
|
---|
| 127 | _sumFullLeafDepth = 0;
|
---|
| 128 | // The count of object references in leaves
|
---|
| 129 | _sumObjectRefCount = 0;
|
---|
| 130 | // The maximum number of object references in a leaf
|
---|
| 131 | _maxObjectRefInLeaf = 0;
|
---|
| 132 | // surface areas
|
---|
| 133 | _sumSurfaceAreaLeaves = 0.f;
|
---|
| 134 | _sumSurfaceAreaMULcntLeaves = 0.f;
|
---|
| 135 | _sumSurfaceAreaInteriorNodes = 0.f;
|
---|
| 136 | #endif
|
---|
| 137 |
|
---|
| 138 | // This is the statistics
|
---|
| 139 | _currDepth = 0;
|
---|
| 140 | _maxDepth = -1;
|
---|
| 141 | InitPars();
|
---|
| 142 | }
|
---|
| 143 |
|
---|
| 144 | // init the stack of auxiliary variables from min to max
|
---|
| 145 | void
|
---|
| 146 | CKTBAllocMan::InitAux(int /*min*/, int /*maxD*/, int maxItemsAtOnce)
|
---|
| 147 | {
|
---|
| 148 | // The size of one entry
|
---|
| 149 | int sizeEntryV = sizeof(SKTBNode);
|
---|
| 150 | // The number of entries to be allocated at once in a block
|
---|
| 151 | // (=size of the block)
|
---|
| 152 | int numEntriesInBlock = 1024;
|
---|
| 153 | // the allignment
|
---|
| 154 | int allignEntrySizeV = sizeof(SKTBNode);
|
---|
| 155 | int allignBlockSizeV = 128;
|
---|
| 156 |
|
---|
| 157 | // Create an allocator in DFS order
|
---|
| 158 | alloc2 = new CAllocContinuous(sizeEntryV, numEntriesInBlock,
|
---|
| 159 | maxItemsAtOnce,
|
---|
| 160 | allignEntrySizeV,
|
---|
| 161 | allignBlockSizeV);
|
---|
| 162 | assert(alloc2);
|
---|
| 163 | // the first allocation is enabled by this command
|
---|
| 164 | alloc2->AllocNewBlock();
|
---|
| 165 | return;
|
---|
| 166 | }
|
---|
| 167 |
|
---|
| 168 | // Read some basic parameters from the environment file
|
---|
| 169 | void
|
---|
| 170 | CKTBAllocMan::InitPars()
|
---|
| 171 | {
|
---|
| 172 | Environment::GetSingleton()->GetIntValue("BSP.maxDepthAllowed",
|
---|
| 173 | maxDepthAllowed);
|
---|
| 174 | Environment::GetSingleton()->GetIntValue("BSP.maxListLength",
|
---|
| 175 | maxListLength);
|
---|
| 176 | }
|
---|
| 177 |
|
---|
| 178 | void
|
---|
| 179 | CKTBAllocMan::PostBuild()
|
---|
| 180 | {
|
---|
| 181 | // Here it can be some postprocessing of the tree, such as branches
|
---|
| 182 | // collapsing for the same content of leaves etc.
|
---|
| 183 | }
|
---|
| 184 |
|
---|
| 185 | void
|
---|
| 186 | CKTBAllocMan::Remove()
|
---|
| 187 | {
|
---|
| 188 | // Release the all memory by blocks, so all the interior nodes
|
---|
| 189 | // and leaves representations. This should be fast.
|
---|
| 190 | alloc2->ReleaseMemory();
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 |
|
---|
| 194 | // Create the representation of the interior node
|
---|
| 195 | SKTBNodeT*
|
---|
| 196 | CKTBAllocMan::AllocInteriorNode(int axis, float position,
|
---|
| 197 | int cntLeft, int cntRight)
|
---|
| 198 | {
|
---|
| 199 | #ifdef _DEBUG
|
---|
| 200 | nodeToLink = 0;
|
---|
| 201 | #endif
|
---|
| 202 |
|
---|
| 203 | #ifdef _KTB_CONSTR_STATS
|
---|
| 204 | _stats_interiorCount++;
|
---|
| 205 | #endif
|
---|
| 206 |
|
---|
| 207 | // Just to satisfy the compiler
|
---|
| 208 | cntLeft = cntLeft;
|
---|
| 209 | cntRight = cntRight;
|
---|
| 210 |
|
---|
| 211 | // Alloc a single node
|
---|
| 212 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
|
---|
| 213 | nodeToLink = n;
|
---|
| 214 | if (n == 0) {
|
---|
| 215 | // we have to insert a special node that links only
|
---|
| 216 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 217 | assert(nodeToLink);
|
---|
| 218 | nodeToLink->nodeType = CKTBAxes::EE_Link;
|
---|
| 219 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(1));
|
---|
| 220 | // This is the link
|
---|
| 221 | nodeToLink->right = n;
|
---|
| 222 | } // if n
|
---|
| 223 |
|
---|
| 224 | assert(n);
|
---|
| 225 | assert(nodeToLink);
|
---|
| 226 |
|
---|
| 227 | // Set the interior node
|
---|
| 228 | assert((axis >=0) && (axis < 3));
|
---|
| 229 | n->nodeType = (CKTBAxes::Axes)axis;
|
---|
| 230 | n->splitPlane = position;
|
---|
| 231 |
|
---|
| 232 | // Return the setupped node, but do not forget to
|
---|
| 233 | // use in the parent node to use nodeToLink !!!!
|
---|
| 234 | return n;
|
---|
| 235 | }
|
---|
| 236 |
|
---|
| 237 | // Create the representation of the interior node
|
---|
| 238 | SKTBNodeT*
|
---|
| 239 | CKTBAllocMan::AllocInteriorNodeWithBox(int axis, float position,
|
---|
| 240 | int cntLeft, int cntRight,
|
---|
| 241 | const SBBox &tsbox,
|
---|
| 242 | SKTBNodeT* prevMinBoxNode,
|
---|
| 243 | int depthStore)
|
---|
| 244 | {
|
---|
| 245 | #ifdef _DEBUG
|
---|
| 246 | nodeToLink = 0;
|
---|
| 247 | if ( (position < tsbox.Min(axis)) ||
|
---|
| 248 | (position > tsbox.Max(axis)) ) {
|
---|
| 249 | cerr << "Something wrong with the tree axis = " << axis;
|
---|
| 250 | cerr << " Min(axis) = " << tsbox.Min(axis)
|
---|
| 251 | << " splitValue = " << position
|
---|
| 252 | << " Max(axis) = " << tsbox.Max(axis) << endl;
|
---|
| 253 | abort();
|
---|
| 254 | }
|
---|
| 255 | #endif
|
---|
| 256 |
|
---|
| 257 | #ifdef _KTB_CONSTR_STATS
|
---|
| 258 | _stats_interiorCount++;
|
---|
| 259 | #endif
|
---|
| 260 |
|
---|
| 261 | // Just to satisfy the compiler
|
---|
| 262 | cntLeft = cntLeft;
|
---|
| 263 | cntRight = cntRight;
|
---|
| 264 |
|
---|
| 265 | #ifdef _SHORT_FORM_MINBOX
|
---|
| 266 | // Alloc a single node + node to store the pointer to box, in total 24 Bytes
|
---|
| 267 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(2));
|
---|
| 268 | nodeToLink = n;
|
---|
| 269 | if (n == 0) {
|
---|
| 270 | // we have to insert a special node that links only
|
---|
| 271 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 272 | assert(nodeToLink);
|
---|
| 273 | nodeToLink->nodeType = CKTBAxes::EE_Link;
|
---|
| 274 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(2));
|
---|
| 275 | // This is the link
|
---|
| 276 | nodeToLink->right = n;
|
---|
| 277 | } // if n
|
---|
| 278 |
|
---|
| 279 | assert(n);
|
---|
| 280 | assert(nodeToLink);
|
---|
| 281 |
|
---|
| 282 | // Set the interior node
|
---|
| 283 | assert((axis >=0) && (axis < 3));
|
---|
| 284 | n->nodeType = (CKTBAxes::Axes)(axis + (int)CKTBAxes::EE_X_axisBox);
|
---|
| 285 | n->splitPlane = position;
|
---|
| 286 |
|
---|
| 287 | // Set the box itself
|
---|
| 288 | // the address to the parent min box node
|
---|
| 289 | (n+1)->parentBoxNode = prevMinBoxNode;
|
---|
| 290 |
|
---|
| 291 | // Here we simply allocate box to the address in the node
|
---|
| 292 | SBBox *badr = new SBBox;
|
---|
| 293 | assert(badr);
|
---|
| 294 | (n+1)->minbox = badr;
|
---|
| 295 | // and store the depth for debugging
|
---|
| 296 | (n+1)->nodeType = CKTBAxes::Axes(depthStore);
|
---|
| 297 |
|
---|
| 298 | #else // _SHORT_FORM_MINBOX
|
---|
| 299 | // Alloc two single nodes (24 Bytes) + two nodes for box (24 Bytes) = 48 Bytes
|
---|
| 300 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(4));
|
---|
| 301 | nodeToLink = n;
|
---|
| 302 | if (n == 0) {
|
---|
| 303 | // we have to insert a special node that links only
|
---|
| 304 | nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 305 | assert(nodeToLink);
|
---|
| 306 | nodeToLink->nodeType = CKTBAxes::EE_Link;
|
---|
| 307 | n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(4));
|
---|
| 308 | // This is the link
|
---|
| 309 | nodeToLink->right = n;
|
---|
| 310 | } // if n
|
---|
| 311 |
|
---|
| 312 | assert(n);
|
---|
| 313 | assert(nodeToLink);
|
---|
| 314 |
|
---|
| 315 | // Set the interior node
|
---|
| 316 | assert((axis >=0) && (axis < 3));
|
---|
| 317 | n->nodeType = (CKTBAxes::Axes)(axis + (int)CKTBAxes::EE_X_axisBox);
|
---|
| 318 | n->splitPlane = position;
|
---|
| 319 |
|
---|
| 320 | // Set the min box node itself
|
---|
| 321 |
|
---|
| 322 | // the address to the parent min box node
|
---|
| 323 | (n+1)->parentBoxNode = prevMinBoxNode;
|
---|
| 324 | // and store the depth for debugging
|
---|
| 325 | (n+1)->nodeType = CKTBAxes::Axes(depthStore);
|
---|
| 326 | (n+1)->minbox = 0; // only to make it zero for debugging
|
---|
| 327 |
|
---|
| 328 | // Here we simply allign to 48 Bytes, since we have one node of size 12 Bytes,
|
---|
| 329 | // and SBBox takes 24 Bytes, so we just want to align to the boundary of 8 Bytes.
|
---|
| 330 | SBBox *badr = (SBBox*)(((char*)n)+24);
|
---|
| 331 | #endif // _SHORT_FORM_MINBOX
|
---|
| 332 |
|
---|
| 333 | // and copy the box content
|
---|
| 334 | *(badr) = tsbox;
|
---|
| 335 |
|
---|
| 336 | // Return the set node, but do not forget to
|
---|
| 337 | // use in the parent node to use nodeToLink !!!!
|
---|
| 338 | return n;
|
---|
| 339 | }
|
---|
| 340 |
|
---|
| 341 | // Set the pointers to children for the interior node
|
---|
| 342 | void
|
---|
| 343 | CKTBAllocMan::SetInteriorNodeLinks(SKTBNodeT *node,
|
---|
| 344 | SKTBNodeT *leftChild,
|
---|
| 345 | SKTBNodeT *rightChild)
|
---|
| 346 | {
|
---|
| 347 | leftChild = leftChild; // to satisfy the compiler
|
---|
| 348 |
|
---|
| 349 | // Check on correctness of DFS order
|
---|
| 350 | assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+4 == leftChild) );
|
---|
| 351 |
|
---|
| 352 | node->right = rightChild;
|
---|
| 353 | }
|
---|
| 354 |
|
---|
[2592] | 355 | // Set the pointers to children for the interior node
|
---|
| 356 | void
|
---|
| 357 | CKTBAllocMan::SetInteriorNodeLeft(SKTBNodeT *node,
|
---|
| 358 | SKTBNodeT *leftChild)
|
---|
| 359 | {
|
---|
| 360 | leftChild = leftChild; // to satisfy the compiler
|
---|
| 361 |
|
---|
| 362 | // Check on correctness of DFS order
|
---|
| 363 | assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+4 == leftChild) );
|
---|
| 364 | }
|
---|
| 365 |
|
---|
| 366 | // Set the pointers to children for the interior node
|
---|
| 367 | void
|
---|
| 368 | CKTBAllocMan::SetInteriorNodeRight(SKTBNodeT *node,
|
---|
| 369 | SKTBNodeT *rightChild)
|
---|
| 370 | {
|
---|
| 371 | node->right = rightChild;
|
---|
| 372 | }
|
---|
| 373 |
|
---|
| 374 |
|
---|
[2582] | 375 | // Create the representation of the leaf. Note that possibly there
|
---|
| 376 | // can be special cases, such as 0, 1, 2, or 3 objects, or in general
|
---|
| 377 | // N objects.
|
---|
| 378 | SKTBNodeT*
|
---|
| 379 | CKTBAllocMan::AllocLeaf(int cntObjects)
|
---|
| 380 | {
|
---|
| 381 | #ifdef _DEBUG
|
---|
| 382 | nodeToLink = 0;
|
---|
| 383 | #endif
|
---|
| 384 |
|
---|
| 385 | #ifdef _KTB_CONSTR_STATS
|
---|
| 386 | _stats_leafNodeCount++;
|
---|
| 387 | _sumLeafDepth += _currDepth;
|
---|
| 388 | if (cntObjects) {
|
---|
| 389 | _sumFullLeafDepth += _currDepth;
|
---|
| 390 | // The count of object references in leaves
|
---|
| 391 | _sumObjectRefCount += cntObjects;
|
---|
| 392 | // The maximum number of object references in a leaf
|
---|
| 393 | if (cntObjects > _maxObjectRefInLeaf)
|
---|
| 394 | _maxObjectRefInLeaf = cntObjects;
|
---|
| 395 | }
|
---|
| 396 | else
|
---|
| 397 | _stats_emptyLeftNodeCount++;
|
---|
| 398 | #endif
|
---|
| 399 |
|
---|
| 400 | // Alloc a single node
|
---|
| 401 | SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
|
---|
| 402 | nodeToLink = n;
|
---|
| 403 | if (n == 0) {
|
---|
| 404 | // we have to insert a special node that links only
|
---|
| 405 | n = nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
|
---|
| 406 | assert(nodeToLink);
|
---|
| 407 | // Allocate a new block for the next allocation
|
---|
| 408 | alloc2->AllocNewBlock();
|
---|
| 409 | } // if n
|
---|
| 410 |
|
---|
| 411 | n->nodeType = CKTBAxes::EE_Leaf;
|
---|
| 412 | n->objlist = 0;
|
---|
| 413 | n->right = 0;
|
---|
| 414 |
|
---|
| 415 | // Return the node
|
---|
| 416 | return n;
|
---|
| 417 | }
|
---|
| 418 |
|
---|
| 419 | // if active node is empty, then is replaced by full leaf with
|
---|
| 420 | // the object list. In success returns 0, for failure returns 1.
|
---|
| 421 | // The object list is used as it is .. it is not copied !!
|
---|
| 422 | int
|
---|
| 423 | CKTBAllocMan::SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist)
|
---|
| 424 | {
|
---|
| 425 | assert(node);
|
---|
| 426 | assert(node->nodeType == CKTBAxes::EE_Leaf);
|
---|
| 427 |
|
---|
| 428 | if ( (objlist == NULL) ||
|
---|
| 429 | (objlist->size() == 0) ) {
|
---|
| 430 | node->objlist = 0;
|
---|
| 431 | }
|
---|
| 432 | else {
|
---|
| 433 | // Set the pointer to the list of objects
|
---|
| 434 | node->objlist = (ObjectContainer *)objlist;
|
---|
| 435 | }
|
---|
| 436 |
|
---|
| 437 | return 0;
|
---|
| 438 | }
|
---|
| 439 |
|
---|
| 440 | } // namespace
|
---|