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

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

commit after merge with vlastimil

Line 
1// ===================================================================
2// $Id: $
3//
4// ktball.h
5//      CKTB accelerating data structure for ray-shooting
6//
7// Class: CKTB
8//
9// REPLACEMENT_STRING
10//
11// Initial coding by Vlasta Havran
12
13#ifndef __KTBALL_H__
14#define __KTBALL_H__
15
16// GOLEM headers
17#include "configh.h"
18//#include "ktbi.h"
19#include "ktbai.h"
20#include "ktbtrav.h"
21#include "gzstream.h"
22
23namespace GtpVisibilityPreprocessor {
24
25// forward declarations
26class CKTBAllocMan;
27class RayPacket2x2;
28
29// ----------------------------------------------------------
30// ----------------------------------------------------------
31// ----------------------------------------------------------
32// the CASDS describing CKTB itself, the interface object to
33// the other objects for CKTB tree building up and traversing
34class CKTB
35//  : public CASDS_BB
36{
37protected:
38  // True if the data structure is built up
39  bool builtUp;
40 
41  // the box bounding the whole scene
42  AxisAlignedBox3 bbox;
43 
44  // the number of objects in the case the object list is
45  // not copied to this->objlist
46  int countObjects;
47
48  // precomputed cost for intersection of kd-tree with arbitrary ray
49  float _expectedIntersectionCost;
50 
51  // the class which serves as builder of CKTB tree
52  CKTBAllocManPredecessor *buildClass;
53
54  // the class that provides traversing through CKTB tree
55  CKTBNodeIteratorPredecessor *traversalClass;
56
57  // if we use min boxes enhancement
58  bool makeMinBoxes;
59  // if we want to make boxing with only tight boxes
60  bool makeTightMinBoxes;
61
62  // the size of 2D buffer
63  int size2D;
64  int index2D;
65  // the indices in the buffer
66  int indexRead, indexWrite;
67  // the distance between two rays, where a new buffer of box nodes is written
68  int distSLCTS;
69
70  // Whether we use SLCTS boxes for FindNearest
71  bool useSLCTS;
72 
73  // construct traversal class for CKTB Trees
74  void AllocTraversalClass();
75
76  // provide the parameters for construction of CKTB tree to stream
77  void ProvidePars(ostream &app);
78
79  // builds up CKTB tree without unbounded objects. The 'boxToInclude
80  // is a box that can be optionally given and the kd-tree constructed
81  // must contain such a box. The 'boxToBoundObjects' when given, is
82  // a box to which the objects boxes are bounded. This is used for special
83  // cases such a multilevel kd-trees.
84  void BuildingUp(ObjectContainer& objlist,
85                  const AxisAlignedBox3 *boxToInclude = 0,
86                  const AxisAlignedBox3 *boxToBoundObjects = 0,
87                  bool verbose = true);
88
89  // create the array of pointers to objects addressable by object uniqueID
90  void CreatePointerArray(ObjectContainer &arrobjlist,
91                          int objCounterOffset);
92
93  // checks the boxes of all objects if they are not flat somehow
94  bool CheckBoxes(ObjectContainer& objlist); 
95
96protected:
97  // statistics
98  int numElemCells;
99  int numEmptyElemCells;
100  float emptyVolume;
101  float nonEmptyVolume;
102  int numSolidsInElemCells;
103  int actMaxListLen;
104  int numHierCells;
105  int actMaxDepth;
106  float sumSurfaceAreaLeaves;
107  float sumSurfaceAreaMULcntLeaves;
108  float sumSurfaceAreaInteriorNodes;
109 
110public:
111  // default constructor
112  CKTB();
113
114  // default destructor
115  ~CKTB();
116
117  void BuildUp(const ObjectContainer &objlist);
118
119  // functions that allows correctly traverse recursively allowing to have
120  // the same traversal stack
121  void TraversalReset();
122
123  void StatsReset() {
124    if (traversalClass)
125      traversalClass->DynamicStatsReset();
126  }
127 
128  bool HandleUnboundeds() const { return true;}
129 
130  void GetBBox(AxisAlignedBox3 &box) { box = bbox;}
131   
132  void PrintStats();
133
134  // Delete all the data structures
135  void Remove();
136 
137  void ProvideID(ostream &app);
138 
139  float ExpectecteRayIntersectionCost() const {
140    return _expectedIntersectionCost;
141  }
142 
143  // describe the toplogy of CKTB to a given stream
144  void DescribeTopology(const string &filename,
145                        int objCounterOffset,
146                        int format) { }
147 
148  // Not yet implemented
149  bool RestoreTopology(const string &filename,
150                       long int streamOffset,
151                       const ObjectContainer &objects,
152                       int objCounterOffset,
153                       int format) { return true; }
154 
155  // allocate new build class and return it
156  CKTBAllocManPredecessor* AllocBuildClass();
157 
158  CKTBNodeIteratorPredecessor* GetTraversalClass() {
159    return traversalClass;
160  }
161 
162  CKTBAllocManPredecessor* GetBuildClass() {
163    return buildClass;
164  }
165  void SetBuildClass(CKTBAllocManPredecessor *build) {
166    buildClass = build;
167  }
168  void DeleteBuildClass();
169 
170  // Here are the functions required from CASDS interface
171  void GatherStats(bool itself = false);
172  void GatherPostStats();
173  void* Locate(const Vector3 &loc);
174 
175  int FindNearestI(const SimpleRay &ray);
176  int FindNearestI(const SimpleRay &ray, const Vector3 &boxMin, const Vector3 &boxMax);
177  void SetOffset(int offset) { traversalClass->SetOffset(offset); }
178  int FindNearestI_16oneDir(SimpleRayContainer &rays, int offset, int copyOffset) {
179    return traversalClass->FindNearestI_16oneDir(rays, offset, copyOffset);
180  }
181  int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset) {
182    return traversalClass->FindNearestI_16oneDirNoSSE(rays, offset);
183  }
184  int FindNearestI_16twoDir(SimpleRayContainer &rays) {
185    return traversalClass->FindNearestI_16twoDir(rays);
186  }
187 
188#ifdef __SSE__
189#ifdef _USE_HAVRAN_SSE 
190  // The same operations for packets of rays, if implemented by
191  // a particular ASDS, otherwise it is emulated by decomposition
192  // of a packet to individual rays and traced individually.
193  void FindNearestI(RayPacket2x2 &raypack);
194  void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
195#endif
196#else
197  void FindNearestI(RayPacket2x2 &raypack) { }
198  void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax) { }
199#endif // __SSE__
200
201  // Loading and saving
202  void ExportBinLeaf(OUT_STREAM &stream, SKTBNodeT *leaf);
203  SKTBNodeT* ImportBinLeaf(IN_STREAM &stream,
204                           SKTBNodeT **nodeToLink,
205                           const ObjectContainer &objects);
206
207  void ExportBinInterior(OUT_STREAM &stream, SKTBNodeT *interior);
208  SKTBNodeT *ImportBinInterior(IN_STREAM  &stream,
209                               SKTBNodeT **nodeToLink); 
210
211  SKTBNodeT * ImportNextNode(IN_STREAM &stream,
212                             SKTBNodeT **nodeToLink,
213                             const ObjectContainer &objects);
214
215  bool ExportBinTree(const string &filename);
216  bool ImportBinTree(const string &filename, ObjectContainer &objects);
217
218 
219protected: 
220  // The 2D array of pointers to the interior nodes with boxes.
221  SKTBNodeT ***buffer;
222  int sizeBuffer, size1D;
223  void AllocBuffer(int size2D, int size1Dv);
224
225  struct STraversalData
226  { 
227    SKTBNodeT *mNode;
228    int        dir;
229    int        depth;
230    STraversalData() {}
231
232    STraversalData(SKTBNodeT *n): mNode(n)
233    { }
234   
235    STraversalData(SKTBNodeT *n, int ndir, int ndepth):
236      mNode(n), dir(ndir), depth(ndepth) { }
237  };
238};
239
240}
241
242#endif // __KTBALL_H__
Note: See TracBrowser for help on using the repository browser.