source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktball.cpp @ 2629

Revision 2629, 28.4 KB checked in by bittner, 17 years ago (diff)

commit after merge with vlastimil

Line 
1// ===================================================================
2// $Id: $
3//
4// ktball.cpp
5//     Implementation of interface functions for CKTB trees
6//
7// REPLACEMENT_STRING
8//
9// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
10// Initial coding by Vlastimil Havran, February 2007
11
12// GOLEM library
13#include "ktb.h"
14#include "ktbai.h"
15#include "ktbs.h"
16#include "ktball.h"
17#include "ktbtrav.h"
18#include "Environment.h"
19#include "raypack.h"
20#include "Mesh.h"
21
22// standard headers
23#include <fstream>
24#include <iomanip>
25#include <stack>
26
27namespace GtpVisibilityPreprocessor {
28
29// Static data structures fo CKTBTraversal class
30GALIGN16 CKTBTraversal::SStackElem
31CKTBTraversal::stack[CKTBTraversal::MAX_TRAVERSAL_HEIGHT];
32
33CKTBTraversal::SStackElem2
34CKTBTraversal::stack2[CKTBTraversal::MAX_TRAVERSAL_HEIGHT];
35
36CKTBTraversal::SStackElem3
37CKTBTraversal::stack3[CKTBTraversal::MAX_TRAVERSAL_HEIGHT];
38
39CKTBTraversal::SStackElem4
40CKTBTraversal::stack4[CKTBTraversal::MAX_TRAVERSAL_HEIGHT];
41
42 
43// ------------------------------------------------------------------
44// CKTB class
45//
46// Binary Space Partitioning Tree, that handles bounded objects only
47// during intersection computation other way
48
49// default constructor
50CKTB::CKTB():
51  builtUp(false),
52  buildClass(NULL), traversalClass(NULL), sizeBuffer(0),buffer(0),
53  indexRead(0), indexWrite(0)
54{
55
56}
57
58// only for creating building class of CKTB tree
59CKTBAllocManPredecessor*
60CKTB::AllocBuildClass()
61{
62  CKTBAllocManPredecessor *bc = 0;
63  bool useArray = false;
64 
65  // this should be already initialised, but we want to be sure
66  if (useArray) {
67    cout << "Using kbt-tree based on arrays" << endl;
68    // the implementation based on arrays
69    bc = new CKTBABuildUp(); // file ktbai.cpp
70  }
71  else {
72    cout << "Using kbt-tree based on sampling" << endl;
73    // the implementation based on sampling
74    bc = new CKTBSBuildUp(); // file ktbs.cpp
75  }
76   
77  if (bc == NULL) {
78    cerr << "The building class for KTB cannot be allocated"<< endl;
79    exit(3);
80  }
81
82  return bc;
83}
84
85void
86CKTB::AllocTraversalClass()
87{
88  if (traversalClass != NULL)
89    delete traversalClass;
90
91  traversalClass = NULL;
92
93  // if we use min boxes idea in the tree
94
95  Environment::GetSingleton()->GetBoolValue("BSP.minBoxes.use",
96                                            makeMinBoxes);
97  Environment::GetSingleton()->GetBoolValue("BSP.minBoxes.tight",
98                                            makeTightMinBoxes);
99  // the number of cells along ray path
100  const int size1D = 150;
101
102  // cerr<<"th1"<<endl;
103  // $$JB tmp
104  size2D = 1;
105  // cerr<<"size2d="<<size2D<<endl;
106  // initial index
107  index2D = 0;
108  AllocBuffer(size2D, size1D);
109  //  cerr<<"th2"<<endl;
110
111#if 0 
112  // -------------------------------------------------------------------
113  if (makeMinBoxes) {
114    // This class uses information about the box
115    // inside from which the ray starts from
116    traversalClass = new CKTBMinBoxesTraversal(size1D);
117  }
118  else {
119    // normal traversal always from root
120    traversalClass = new CKTBTraversal;
121  }
122#else
123  // cerr<<"th3"<<endl;
124
125  traversalClass = new CKTBTraversal;
126#endif
127
128  assert(traversalClass);
129
130  return;
131}
132
133// default destructor
134CKTB::~CKTB()
135{
136  // Print the statistics
137  PrintStats();
138 
139  Remove();
140}
141
142void
143CKTB::Remove()
144{
145  if (buildClass) {
146    // DEBUG << "Deleting build class from CKTB" << endl;
147    buildClass->Remove();
148    delete buildClass;
149    buildClass = NULL;
150  }
151
152  if (traversalClass) {
153    delete traversalClass;
154    traversalClass = NULL;
155  }
156
157  return;
158}
159
160void
161CKTB::ProvideID(ostream& app)
162{
163  app << "#CASDS = CKTB - KD-tree for only bounded objects\n";
164  //app << (int)GetID() << "\n";
165 
166  //app << "#ActMaxDepth (Dreach)\tActual maximal depth of the KD-tree"
167  //    << " reached\n";
168  //app << world->_statistics->actMaxDepth << "\n";
169
170  ProvidePars(app);
171}
172
173void
174CKTB::ProvidePars(ostream& app)
175{
176  app << "#NumberOfObjects\t\tNumber of objects inside kd-tree\n";
177  app << countObjects << "\n";
178 
179  app << "#BBox\t\t\tSize of axis-aligned box of the whole scene\n"
180      << bbox.Max().x - bbox.Min().x << ","
181      << bbox.Max().y - bbox.Min().y << ","
182      << bbox.Max().z - bbox.Min().z << "\n";
183
184#if 0 
185  bool tempvar;
186  Environment::GetSingleton()->GetBoolValue("BSP.pruning", tempvar);
187  if (tempvar) {
188    app << "#BSP.pruning \t\tPruning of CKTB disabled/enabled\n";
189    app << tempvar << "\n";
190  }
191  app << "#BSP.constrMethod \tBuilding up method for KD-tree\n";
192#endif 
193
194  if (buildClass)
195    buildClass->ProvideID(app);
196
197  return;
198}
199
200void
201CKTB::PrintStats()
202{
203  if (traversalClass)
204    traversalClass->PrintStatsTR(cout);
205}
206
207// builds up CKTB tree
208void
209CKTB::BuildUp(const ObjectContainer &alist)
210{
211  cerr<<"KTB buildup\n";
212  Remove();
213
214  // Create the list of objects to be processed.
215  ObjectContainer *objlist = new ObjectContainer;
216
217  // The minimum size
218  bbox.Initialize();
219 
220  // Copy only finite (not invisible and bounded) objects from
221  // the original list to 'objlist'
222   
223  // copy the pointers to objects to the array
224  int i = 0;
225  AxisAlignedBox3 objbox; 
226  bool hasUnboundeds = false;
227  countObjects = 0;
228  for (ObjectContainer::iterator it = ((ObjectContainer*)&alist)->begin();
229       it != alist.end(); it++, i++) {
230    Intersectable* obj = *it;
231    objbox = (*it)->GetBox();
232    // invisible objects are not added - lights etc.
233    bbox.Include(objbox);
234    // This is a regular object, add it to the list
235    objlist->push_back(obj);
236  } // for
237   
238  // prepare building up for CKTB tree
239  //  BuildingUp(*objlist);
240  BuildingUp(*objlist, NULL, NULL, true);
241
242  cerr<<"KTB buildup3\n";
243
244  delete objlist;
245
246  return;
247}
248
249bool
250CKTB::CheckBoxes(ObjectContainer &objlist)
251{
252  // the minimum size of the box at any dimension
253  const float epsilon = Limits::Small * 5.0f;
254
255  for (ObjectContainer::iterator oi = objlist.begin();
256       oi != objlist.end(); oi++) {
257    AxisAlignedBox3 box = (*oi)->GetBox();
258    Vector3 diff = box.Diagonal();
259    for (int i = 0; i < 3; i++) {
260      float d = fabs(diff[i]);
261#if 0
262      if (d < epsilon) {
263        CObject3D &obj = **(oi);
264        cerr << "CKTB::CheckBoxes - the scene incorrectly prepared, "
265              << " the size of the box = " << d << " in dimension "
266              << i << " is" << " below threshold = " << epsilon << endl;
267        cerr << "object = " << (void*)(*oi) << " uniqueID = " <<
268          (*oi)->GetUniqueID() << " description = " << endl;
269        obj.Describe(cout, 1);
270        cerr << "----------" << endl;
271        abort();
272        return true; // error
273      }
274#else
275      if (d < epsilon) {
276        int size = objlist.size();
277        *oi = objlist[size-1];
278        objlist.resize(size-1);
279        oi--; // check this object as well
280      }     
281#endif
282    } // for i   
283  } // for all objecs
284
285  return false;
286}
287
288// builds up CKTB tree without unbounded objects. The 'boxToInclude
289// is a box that can be optionally given and the kd-tree constructed
290// must contain such a box. The 'boxToBoundObjects' when given, is
291// a box to which the objects boxes are bounded. This is used for special
292// cases such a multilevel kd-trees.
293void
294CKTB::BuildingUp(ObjectContainer& objlist,
295                 const AxisAlignedBox3 *boxToInclude,
296                 const AxisAlignedBox3 *boxToBoundObjects,
297                 bool verbose)
298{
299  // the number of objects for statistics purposes - it can be different
300  // from objlist->size() since objlist need not be initialized at all!
301  countObjects = objlist.size();
302
303  // compute the estimate for the kd-tree constructed this way
304  _expectedIntersectionCost = log((float)countObjects) / log(2.0f) + 2.0;
305 
306#ifdef _DEBUG
307  // check the flatness of the boxes for all objects
308  if (CheckBoxes(objlist)) {
309    cerr << "Problem with the size of the box for some object" << endl;
310    return;
311  }
312#endif // _DEBUG
313
314  // cerr<<"hh2"<<endl;
315  // possibly remove the old building class
316  // and allocate the class for CKTB building up
317  if (buildClass)
318    delete buildClass; 
319  buildClass = AllocBuildClass();
320
321  // cerr<<"hh3"<<endl;
322
323  // and for traversal
324  AllocTraversalClass();
325  // cerr<<"hh4"<<endl;
326
327  if (boxToBoundObjects) {
328    // maximum box of the scene is given in advance
329    bbox = Intersect(bbox, *boxToBoundObjects);
330  }
331
332  // we can additionally include the user box
333  if (boxToInclude)
334    bbox.Include(*boxToInclude); 
335
336  // cerr<<"hh5"<<endl;
337
338  // build up the CKTB tree and make setup for traversal
339  SKTBNodeT *rootNode =
340    buildClass->BuildUp(objlist, bbox, verbose);
341  // cerr<<"hh6"<<endl;
342
343  traversalClass->Setup(bbox, rootNode);
344  // cerr<<"hh7"<<endl;
345
346#ifdef _DEBUG
347  //traversalClass->AssignIDs();
348#endif
349  builtUp = true;
350
351#if 0 
352  // if to clean up the whole structure
353  bool pruning;
354  Environment::GetSingleton()->GetBoolValue("BSP.pruning", pruning);
355  if (pruning)
356    // only the objects whose surfaces intersects with the subdivision
357    PruneLeaves(); // cells are not pruned from the CKTB tree
358#endif
359}
360
361// functions that allows correctly traverse recursively allowing to have
362// the same traversal stack
363void
364CKTB::TraversalReset()
365{
366  assert(traversalClass);
367  traversalClass->ResetTraversalDepth();
368}
369
370// Allocate 2D buffer of pointers to the interior nodes
371void
372CKTB::AllocBuffer(int size2D, int size1Dv)
373{
374  int i, j;
375 
376  if (buffer) {
377    for (i=0; i < sizeBuffer; i++) {
378      delete [] buffer[i];
379    } // for
380    delete [] buffer;
381    buffer = 0;
382  }
383
384  sizeBuffer = size2D;
385  this->size1D = size1Dv;
386  buffer = new SKTBNodeT ** [sizeBuffer];
387  assert(buffer);
388  for (i=0; i < sizeBuffer; i++) {
389    buffer[i] = new SKTBNodeT* [size1D];
390    assert(buffer[i]);
391    // reset the array content
392    for (j = 0; j < size1D; j++) {
393      buffer[i][j] = 0;
394    }
395  } // for
396
397  return;
398}
399
400int
401CKTB::FindNearestI(const SimpleRay &ray)
402{
403  return traversalClass->FindNearestI(ray);     
404}
405
406int
407CKTB::FindNearestI(const SimpleRay &ray, const Vector3 &boxmin, const Vector3 &boxmax)
408{
409  const AxisAlignedBox3 localbox(boxmin, boxmax);
410  return traversalClass->FindNearestI(ray, localbox);     
411}
412
413 
414#ifdef _USE_HAVRAN_SSE 
415
416#ifdef __SSE__
417// --------------------------------------------------------------
418// Ray packets
419void
420CKTB::FindNearestI(RayPacket2x2 &raypack)
421{
422  if (!makeMinBoxes)
423    raypack.SetOrigin(0); // min boxes are not used, we cannot use them here !
424  traversalClass->FindNearestI(raypack);
425}
426
427void
428CKTB::FindNearestI(RayPacket2x2 &raypack,
429                   const Vector3 &boxmin,
430                   const Vector3 &boxmax)
431{
432  if (!makeMinBoxes)
433    raypack.SetOrigin(0); // min boxes are not used, we cannot use them here !
434  traversalClass->FindNearestI(raypack, boxmin, boxmax);
435}
436
437#endif // __SSE__
438
439#endif // _USE_HAVRAN_SSE 
440
441 
442void
443CKTB::DeleteBuildClass()
444{
445  if (buildClass)
446    delete buildClass;
447  buildClass = NULL;
448}
449
450void
451CKTB::GatherStats(bool itself)
452{
453  // DEBUG << "CKTB::GatherStats called" << endl;
454  struct EDir {
455    SKTBNodeT *node;
456    int depth;
457    AxisAlignedBox3 bbox;
458  };
459  EDir stack[CKTBTraversal::MAX_TRAVERSAL_HEIGHT];
460  int stackTop = 0; // pointer to the stack
461  stack[stackTop].node = 0;
462  stack[stackTop].depth = 0;
463  stack[stackTop].bbox = bbox;
464  int tmpdir;
465#ifdef __TAGGED_KDR
466  int taggedLists = 0;
467#endif // __TAGGED_KDR
468 
469  /*
470  if (!BuiltUp) {
471    cerr << "Internal error: CASDS not built up. Giving up.\n" << flush;
472    abort();
473  }
474  */
475 
476  // average depth for all leaves
477  long avgLeafDepth = 0;
478  // for full leaves
479  long avgFullLeafDepth = 0;
480  // for empty leaves
481  long avgEmptyLeafDepth = 0;
482
483  // Surface areas  (divided by the area of the box)
484  // Surface area of leaves (empty + full)
485  double saLeaves = 0.f;
486  // Surface area of interior nodes
487  double saInteriorNodes = 0.f;
488  // Sum of surface area of (full) leaves multiplied by
489  // the number of objects in leaves
490  double sa_cntLeaves = 0.f;
491  // number of boxes enclosing tightly the objects
492  long int boxesMin = 0;
493  long int boxesMinX = 0;
494  long int boxesMinY = 0;
495  long int boxesMinZ = 0;
496  // the sum of depth of tight boxes
497  long int boxesMinDepth = 0;
498
499  // start from the root node
500  SKTBNodeT *curr = buildClass->GetRootNode();
501  // copy the box over the scene objects
502  AxisAlignedBox3 wbox = this->bbox;
503  int currDepth = 0;
504
505  if (buildClass->IsLeaf_(curr)) {
506    this->numElemCells++;
507    if (buildClass->IsEmptyLeaf_(curr)) {
508      this->numEmptyElemCells++;
509      AxisAlignedBox3 bwbox = this->bbox;
510      // Surface area for empty leaf
511      this->emptyVolume += bwbox.GetVolume();
512      saLeaves += bwbox.SurfaceArea();
513    }
514    else { // CKTB tree is single non-empty leaf
515      AxisAlignedBox3 bwbox = this->bbox;
516      this->nonEmptyVolume += bwbox.GetVolume();
517      ObjectContainer *olist = curr->objlist;
518      saLeaves += bwbox.SurfaceArea();
519      if (!olist) {
520        this->numSolidsInElemCells += olist->size();
521        this->actMaxListLen = olist->size();
522        // surface area for full leaf
523        sa_cntLeaves = bwbox.SurfaceArea() * (float)(olist->size());
524      }
525    }
526  }
527  else { // CKTB tree is not a single leaf
528    // now we access the interior node
529
530    // surface area for interior node
531    AxisAlignedBox3 bwbox = this->bbox;
532    // surface area for interior node
533    saInteriorNodes += bwbox.SurfaceArea();
534    this->numHierCells++;
535       
536    // traverse through whole CKTB tree
537    do {
538      CKTBAxes::Axes nodeType = buildClass->GetNodeType(curr);
539      if (nodeType == CKTBAxes::EE_Link) {
540        // just relink
541        curr = buildClass->GetLinkNode(curr);
542        // cout << "Link node was accessed" << endl;
543        continue;       
544      }
545     
546      if ( (nodeType == CKTBAxes::EE_X_axis)||
547           (nodeType == CKTBAxes::EE_Y_axis)||
548           (nodeType == CKTBAxes::EE_Z_axis)||
549           (nodeType == CKTBAxes::EE_X_axisBox)||
550           (nodeType == CKTBAxes::EE_Y_axisBox)||
551           (nodeType == CKTBAxes::EE_Z_axisBox)
552         ) {
553
554        // push onto the stack
555        AxisAlignedBox3 rightBox = bwbox;
556        float value = curr->splitPlane;
557        switch(nodeType) {
558          case CKTBAxes:: EE_X_axisBox: {
559            rightBox.SetMin(0, value);
560            bwbox.SetMax(0, value);
561            boxesMin++;
562            boxesMinX++;
563            boxesMinDepth += currDepth;
564            break;       
565          }
566          case CKTBAxes:: EE_X_axis: {
567            rightBox.SetMin(0, value);
568            bwbox.SetMax(0, value);
569            break;       
570          }
571          case CKTBAxes:: EE_Y_axisBox: {
572            rightBox.SetMin(0, value);
573            bwbox.SetMax(0, value);
574            boxesMin++;
575            boxesMinY++;
576            boxesMinDepth += currDepth;
577            break;       
578          }
579          case CKTBAxes:: EE_Y_axis: {
580            rightBox.SetMin(1, value);
581            bwbox.SetMax(1, value);
582            break;       
583          }
584          case CKTBAxes:: EE_Z_axisBox: {
585            rightBox.SetMin(0, value);
586            bwbox.SetMax(0, value);
587            boxesMin++;
588            boxesMinZ++;
589            boxesMinDepth += currDepth;
590            break;       
591          }
592          case CKTBAxes:: EE_Z_axis: {
593            rightBox.SetMin(2, value);
594            bwbox.SetMax(2, value);
595            break;       
596          }
597        } // switch
598     
599        stack[stackTop].node = buildClass->GetRight(curr);
600        stack[stackTop].depth = currDepth+1;
601        stack[stackTop].bbox = rightBox;
602        stackTop++;
603        // where to go
604        if ( (nodeType == CKTBAxes:: EE_X_axisBox)||
605             (nodeType == CKTBAxes:: EE_Y_axisBox)||
606             (nodeType == CKTBAxes:: EE_Z_axisBox) )
607          curr = buildClass->GetLeftMinBox(curr);
608        else
609          curr = buildClass->GetLeft(curr);
610        // the box was already set     
611        currDepth++;
612     
613        if (this->actMaxDepth < currDepth)
614          this->actMaxDepth = currDepth;
615
616        // surface area for interior node
617        saInteriorNodes += bwbox.SurfaceArea();
618        this->numHierCells++;
619
620        continue;
621      } // interior nodes
622
623      assert(nodeType == CKTBAxes::EE_Leaf);
624     
625      while ( (nodeType == CKTBAxes::EE_Leaf) && currDepth) {
626        this->numElemCells++;
627        avgLeafDepth += currDepth;
628
629        ObjectContainer *olist = buildClass->GetObjList(curr);
630       
631        // test to empty leaf
632        if (!olist) {
633          this->numEmptyElemCells++;
634          avgEmptyLeafDepth += currDepth;
635          this->emptyVolume += bwbox.GetVolume();
636          // Surface area for empty leaf
637          saLeaves += bwbox.SurfaceArea();
638        }
639        else {
640          // full leaf
641          this->nonEmptyVolume += bwbox.GetVolume();
642          avgFullLeafDepth += currDepth;
643          int length = olist->size();
644          this->numSolidsInElemCells += length;
645          // surface area for full leaf
646          saLeaves += bwbox.SurfaceArea();
647          sa_cntLeaves += bwbox.SurfaceArea() * (float)(olist->size());
648          if (this->actMaxListLen < length)
649            this->actMaxListLen = length;
650        }
651       
652        // traverse up the tree
653        stackTop--;
654        if (stackTop < 0)
655          goto FINISH;
656        // pop the node from the stack
657        curr = stack[stackTop].node;
658        currDepth = stack[stackTop].depth;
659
660        nodeType = buildClass->GetNodeType(curr);
661       
662      } // while is a leaf
663    }
664    while (stackTop >= 0);
665  } // either single leaf or tree
666
667FINISH:
668
669  cout << "BBox " << this->bbox << "\n";
670 
671#ifdef __TAGGED_KDR
672  DEBUGW << "Tagged lists = " << taggedLists << "\n";
673#endif // __TAGGED_KDR
674
675  cout << "#CntLeaves = \n" << this->numElemCells << "\n";
676  cout << "#AverageLeafDepth = \n"
677       << (float)avgLeafDepth/(float)this->numElemCells << "\n";
678  cout << "#CntFullLeaves = \n" << (this->numElemCells-this->numEmptyElemCells)
679        << "\n";
680  cout << "#AverageFullLeafDepth = \n"
681        << (float)avgFullLeafDepth/
682            (float)(this->numElemCells - this->numEmptyElemCells) << "\n";
683  cout << "#AverageEmptyLeafDepth = \n";
684  if (this->numEmptyElemCells)
685    cout << (float)avgEmptyLeafDepth / (float)this->numEmptyElemCells<<"\n";
686  else
687    cout << "undefined\n";
688
689  // Normalized the surface area
690  this->sumSurfaceAreaLeaves = saLeaves / wbox.SurfaceArea();
691  this->sumSurfaceAreaMULcntLeaves = sa_cntLeaves / wbox.SurfaceArea();
692  this->sumSurfaceAreaInteriorNodes = saInteriorNodes / wbox.SurfaceArea();
693
694  cout << "#SumSurfaceLeafArea = \n" << saLeaves << "\n";
695  cout << "#SumSurfaceLeafAreaMulCNT = \n" << sa_cntLeaves << "\n";
696  cout << "#NormSurfaceLeafArea = \n" << this->sumSurfaceAreaLeaves << "\n";
697  cout << "#NormSurfaceLeafAreaMulCNT = \n" << this->sumSurfaceAreaMULcntLeaves << "\n";
698  cout << "#SurfaceAreaInteriorNodes = \n" << this->sumSurfaceAreaInteriorNodes<<"\n"; 
699  cout << "#MinBoxesCount = \n" << boxesMin << "\n";
700  cout << "#MinBoxesXCount = \n" << boxesMinX << "\n";
701  cout << "#MinBoxesYCount = \n" << boxesMinY << "\n";
702  cout << "#MinBoxesZCount = \n" << boxesMinZ << "\n";
703  if (boxesMin)
704    cout << "#AverageMinBoxesDepth = \n"
705          << (float)boxesMinDepth/(float)boxesMin << "\n";
706
707  long int memUsed = 0;
708#ifdef _KTB8Bytes
709  memUsed += this->numHierCells*8;
710  memUsed += (this->numElemCells-this->numEmptyElemCells)*8;
711#ifdef _SHORT_FORM_MINBOX
712  memUsed += boxesMin * (sizeof(SBBox) + 2*8);
713#else
714  memUsed += boxesMin * (5*8);
715#endif
716#else // _KTB8Bytes
717  memUsed += this->numHierCells*12;
718  memUsed += (this->numElemCells-this->numEmptyElemCells)*12;
719#ifdef _SHORT_FORM_MINBOX
720  memUsed += boxesMin * (sizeof(SBBox) + 2*12);
721#else
722  memUsed += boxesMin * (4*12);
723#endif
724#endif // _KTB8Bytes
725
726  // The references to objects
727  memUsed += this->numSolidsInElemCells * sizeof(Intersectable*);
728  memUsed += (this->numElemCells-this->numEmptyElemCells) *
729    sizeof(ObjectContainer);
730  cout << "#MemUsedKBB = \n" << memUsed << "\n";
731   
732  return;
733}
734
735
736void CKTB::ExportBinLeaf(OUT_STREAM &stream, SKTBNodeT *leaf)
737{
738#define TYPE_LEAF -3
739  int type = TYPE_LEAF;
740  if (leaf->objlist == 0) {
741    // empty leaf
742    int size = 0;
743    stream.write(reinterpret_cast<char *>(&type), sizeof(int));
744    stream.write(reinterpret_cast<char *>(&size), sizeof(int));   
745    return;
746  }
747 
748  ObjectContainer::const_iterator it, it_end = leaf->objlist->end(); 
749  int size = (int)leaf->objlist->size();
750 
751  stream.write(reinterpret_cast<char *>(&type), sizeof(int));
752  stream.write(reinterpret_cast<char *>(&size), sizeof(int));
753 
754  for (it = leaf->objlist->begin(); it != it_end; ++ it)
755  {     
756    Intersectable *obj = *it;
757    int id = obj->mId;         
758     
759    //stream.write(reinterpret_cast<char *>(&origin), sizeof(Vector3));
760    stream.write(reinterpret_cast<char *>(&id), sizeof(int));
761  }
762}
763
764
765inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
766{
767  return obj1->mId < obj2->mId;
768}
769
770
771static int
772cntInterior = 0;
773
774static int
775cntInteriorA[4] = {0, 0, 0, 0};
776
777static int
778cntLeaves = 0;
779
780static int
781cntEmptyLeaves = 0;
782
783static int
784objReferences = 0;
785
786SKTBNodeT*
787CKTB::ImportBinLeaf(IN_STREAM &stream,
788                    SKTBNodeT **nodeToLink,
789                    const ObjectContainer &objects)
790{
791  int leafId = TYPE_LEAF;
792  int objId = leafId;
793  int size;
794
795  cntLeaves++;
796 
797  stream.read(reinterpret_cast<char *>(&size), sizeof(int));
798  if (size == 0) {
799    // alloc empty leaf -- ?????????? I am not sure if this works !!!
800    // since for
801    SKTBNodeT* leaf = buildClass->AllocLeaf(0);
802    *nodeToLink = buildClass->nodeToLink;
803    cntEmptyLeaves++;
804    return leaf;
805  }
806 
807  MeshInstance dummyInst(NULL);
808  SKTBNodeT* leaf = buildClass->AllocLeaf(size);
809  *nodeToLink = buildClass->nodeToLink;
810
811  ObjectContainer *newobjlist = new ObjectContainer;
812
813  objReferences += size;
814 
815  // read object ids
816  // note: this can also be done geometrically
817  for (int i = 0; i < size; ++ i)
818  {     
819    stream.read(reinterpret_cast<char *>(&objId), sizeof(int));
820    dummyInst.SetId(objId);
821     
822    ObjectContainer::const_iterator oit =
823      lower_bound(objects.begin(), objects.end(), (Intersectable *)&dummyInst, ilt);
824     
825    if ((oit != objects.end()) && ((*oit)->GetId() == objId))
826      newobjlist->push_back(*oit);
827    else
828      Debug << "error: object with id " << objId << " does not exist" << endl;
829  } // for
830
831  buildClass->SetFullLeaf(leaf, newobjlist);
832 
833  return leaf;
834}
835
836
837void CKTB::ExportBinInterior(OUT_STREAM &stream, SKTBNodeT *interior)
838{
839#define TYPE_INTERIOR -2
840  int interiorid = TYPE_INTERIOR;
841  stream.write(reinterpret_cast<char *>(&interiorid), sizeof(int));
842
843  int axis = (int)(buildClass->GetNodeType(interior));
844  float pos = buildClass->GetSplitValue(interior);
845
846  stream.write(reinterpret_cast<char *>(&axis), sizeof(int));
847  stream.write(reinterpret_cast<char *>(&pos), sizeof(float));
848}
849
850SKTBNodeT *
851CKTB::ImportBinInterior(IN_STREAM  &stream, SKTBNodeT **nodeToLink)
852{
853  int axis;
854  float pos;
855
856  stream.read(reinterpret_cast<char *>(&axis), sizeof(int));
857  stream.read(reinterpret_cast<char *>(&pos), sizeof(float));
858
859  SKTBNodeT *interiorNode =
860    buildClass->AllocInteriorNode(axis, pos, 0, 0);
861  *nodeToLink = buildClass->nodeToLink;
862
863  cntInterior++;
864  assert( (axis >= 0) && (axis < 3));
865  cntInteriorA[axis]++;
866 
867  return interiorNode;
868}
869
870
871bool CKTB::ExportBinTree(const string &filename)
872{
873  OUT_STREAM stream(filename.c_str(), OUT_BIN_MODE);
874       
875  if (!stream.is_open()) return false;
876
877  int startMark = 0xf0f0;
878  stream.write(reinterpret_cast<char *>(&startMark), sizeof(int)); 
879 
880  // export binary version of mesh
881  std::stack<SKTBNodeT *> tStack;
882  tStack.push(buildClass->GetRootNode());
883  int cntSaves = 0, cntSavesLeaf = 0, cntSavesIN = 0;
884
885  while(!tStack.empty())
886  {
887    SKTBNodeT *node = tStack.top();
888    tStack.pop();   
889
890    int nodeType = buildClass->GetNodeType(node);
891   
892    if (nodeType == CKTBAxes::EE_Link)
893    {
894      tStack.push(buildClass->GetLinkNode(node));
895    }
896    else
897    if (nodeType == CKTBAxes::EE_Leaf)
898    {
899      //Debug << "l";
900      ExportBinLeaf(stream, node);
901      cntSavesLeaf++; cntSaves++;     
902    }
903    else
904    { // interior node
905      //Debug << "i";
906      ExportBinInterior(stream, node);
907      cntSavesIN++; cntSaves++;     
908
909      tStack.push(buildClass->GetRight(node));
910      if (nodeType >= CKTBAxes::EE_X_axisBox)
911        tStack.push(buildClass->GetLeftLong(node));
912      else
913        tStack.push(buildClass->GetLeft(node));
914    }
915  } // while
916
917  int endMark = 0xf0ff;
918  stream.write(reinterpret_cast<char *>(&endMark), sizeof(int)); 
919
920  cout << "Writes " << cntSaves << " cntLeafs "
921       << cntSavesLeaf << " cntIN " << cntSavesIN << endl;
922 
923  stream.close();
924  return true; // saved
925}
926
927
928SKTBNodeT *
929CKTB::ImportNextNode(IN_STREAM &stream,
930                     SKTBNodeT **nodeToLink,
931                     const ObjectContainer &objects)
932{
933  int nodeType;
934  stream.read(reinterpret_cast<char *>(&nodeType), sizeof(int));
935
936  if (nodeType == TYPE_LEAF)
937    return ImportBinLeaf(stream, nodeToLink, objects);
938
939  if (nodeType == TYPE_INTERIOR)
940    return ImportBinInterior(stream, nodeToLink);
941
942  Debug << "error! loading failed!" << endl;
943  return NULL;
944}
945
946
947// creates the ASDS according to the file description
948bool
949CKTB::ImportBinTree(const string &filename, ObjectContainer &objects)
950{
951  // open the stream in text mode
952  IN_STREAM stream(filename.c_str(), IN_BIN_MODE);
953
954  if (!stream.is_open()) {
955    cerr << "Kd-tree description file (.kbt) cannot be opened for reading\n";
956    return true; // error
957  }
958
959  int mark;
960  stream.read(reinterpret_cast<char *>(&mark), sizeof(int));
961  if (mark != 0xf0f0) {
962    cout << "Something wrong with the tree - heading" << endl;
963    abort();
964  }
965 
966  // sort objects by their id to allow list creation in kd-tree leaves
967  //    if (!is_sorted(objects.begin(), objects.end(), ilt))
968  sort(objects.begin(), objects.end(), ilt);
969 
970  // remove all the data in the current data structure
971  CKTBAllocManPredecessor *bc = GetBuildClass();
972  if (!bc)
973    bc = buildClass = AllocBuildClass();
974  else
975    bc->Remove();
976
977  // How many items can be allocated at once
978  int maxItemsAtOnce = 1;
979  if (makeMinBoxes) {
980#ifdef _KTB8Bytes   
981    // We need to allocate for boxes the memory in a row
982    maxItemsAtOnce = 5; // 8x5=40 = 16+24;
983#else
984    maxItemsAtOnce = 4; // 12x4=48 = 24+24;
985#endif // _KTB8Bytes
986  }
987 
988  bc->InitAux(0, CKTBNodeAbstract::MAX_HEIGHT - 1, maxItemsAtOnce); 
989
990  for(int i = 0; i < 4; i++)
991    cntInteriorA[i] = 0;
992 
993  // Compute the box from all objects
994  bbox.Initialize();
995  for (ObjectContainer::iterator sc = objects.begin();
996       sc != objects.end(); sc++) {
997    AxisAlignedBox3 abox = (*sc)->GetBox();
998    bbox.Include(abox);
999  } // for
1000   
1001  // initialize the root node
1002  SKTBNodeT *node;
1003
1004  bc->root = ImportNextNode(stream, &node, objects);
1005  assert(bc->root == node);
1006
1007  std::stack<STraversalData> tStack;
1008  tStack.push(STraversalData(bc->root, 1, 0));
1009  tStack.push(STraversalData(bc->root, 0, 0));
1010  int depth, lastDepth;
1011 
1012  //int cntReads = 1, cntReadsLeaf = 0, cntReadsIN = 1;
1013  while(!tStack.empty())
1014  {   
1015    STraversalData tData = tStack.top();
1016    tStack.pop();
1017   
1018    node = tData.mNode;
1019    lastDepth = depth = tData.depth;
1020    //int nodeType = bc->GetNodeType(node);
1021    //cout << "nodeType = " << nodeType << " adr = " << (void*)node << endl;
1022
1023    SKTBNodeT *childNodeLink = 0;
1024    SKTBNodeT *childNode = ImportNextNode(stream, &childNodeLink, objects);
1025    //    cout << "childNode = " << (void*)childNode
1026    // << " linkNode = " << (void*)childNodeLink << endl;
1027
1028    if (tData.dir)
1029      bc->SetInteriorNodeRight(node, childNodeLink);
1030    else
1031      bc->SetInteriorNodeLeft(node, childNodeLink);
1032   
1033    //cntReads++;
1034    if (!bc->IsLeaf_(childNode))
1035    {
1036      //cntReadsIN++;
1037      tStack.push(STraversalData(childNode, 1, depth+1));
1038      tStack.push(STraversalData(childNode, 0, depth+1));
1039    }
1040    //else {
1041    //  cntReadsLeaf++;
1042    //  //cout << "leaf" << endl;
1043    // }
1044  } // while
1045
1046  //cout << "Last depth = " << lastDepth << endl;
1047  //cout << "Reads " << cntReads << " cntLeafs "
1048  //   << cntReadsLeaf << " cntIN " << cntReadsIN << endl;
1049 
1050  stream.read(reinterpret_cast<char *>(&mark), sizeof(int));
1051  if (mark != 0xf0ff) {
1052    cout << "Something wrong with the kd-tree in the file"
1053         << endl;
1054    abort();
1055  }
1056 
1057  if (!traversalClass)
1058    AllocTraversalClass();
1059   
1060  // Make setup for traversal
1061  traversalClass->Setup(bbox, bc->GetRootNode());
1062  // Handles unbounded objects in traversal class
1063  // traversalClass->Setup2(0);
1064 
1065  stream.close();
1066
1067  // now the tree is surely well constructed
1068  builtUp = true; 
1069
1070  cout << "Importing ktb-tree cntInterior = "
1071       << cntInterior << " cntLeaves = " << cntLeaves
1072       << " cntEmptyLeaves = " << cntEmptyLeaves << endl;
1073
1074  cout << "X-splits = " << cntInteriorA[0] << " Y-splits = " << cntInteriorA[1]
1075       << " Z-splits = " << cntInteriorA[2] << "\nref_to_objs/full_leaf = "
1076       << (float)objReferences/(cntLeaves - cntEmptyLeaves) << endl;
1077 
1078  return false; // OK
1079}
1080
1081void
1082CKTB::GatherPostStats()
1083{
1084
1085}
1086
1087void*
1088CKTB::Locate(const Vector3 &loc)
1089{
1090  return (void*)(traversalClass->Locate(loc));
1091}
1092
1093
1094} // namespace
Note: See TracBrowser for help on using the repository browser.