source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktb8b.cpp @ 2592

Revision 2592, 14.1 KB checked in by bittner, 17 years ago (diff)

havran ray caster update

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