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

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

havran ray caster update

Line 
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
20namespace 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
29int
30CKTBNodeIterator::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
52int
53CKTBNodeIterator::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  // rayIndex += rayOffset;
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
80int
81CKTBNodeIterator::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
104const CKTBNodeAbstract::SKTBNode*
105CKTBNodeIterator::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.
116void
117CKTBAllocMan::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
145void
146CKTBAllocMan::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
169void
170CKTBAllocMan::InitPars()
171{
172  Environment::GetSingleton()->GetIntValue("BSP.maxDepthAllowed",
173                                           maxDepthAllowed);
174  Environment::GetSingleton()->GetIntValue("BSP.maxListLength",
175                                           maxListLength);
176}
177
178void
179CKTBAllocMan::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
185void
186CKTBAllocMan::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
195SKTBNodeT*
196CKTBAllocMan::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
238SKTBNodeT*
239CKTBAllocMan::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
342void
343CKTBAllocMan::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
355// Set the pointers to children for the interior node
356void
357CKTBAllocMan::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
367void
368CKTBAllocMan::SetInteriorNodeRight(SKTBNodeT *node,
369                                   SKTBNodeT *rightChild)
370{
371  node->right = rightChild;
372}
373
374 
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.
378SKTBNodeT*
379CKTBAllocMan::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 !!
422int
423CKTBAllocMan::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
Note: See TracBrowser for help on using the repository browser.