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