Geant4  10.00.p01
UVoxelizer.hh
Go to the documentation of this file.
1 //
2 // ********************************************************************
3 // * This Software is part of the AIDA Unified Solids Library package *
4 // * See: https://aidasoft.web.cern.ch/USolids *
5 // ********************************************************************
6 //
7 // $Id:$
8 //
9 // --------------------------------------------------------------------
10 //
11 // UVoxelizer
12 //
13 // Class description:
14 //
15 // Voxelizer used for UPolycone, UPolyhedra, UTessellatedSolid
16 // and UMultiUnion.
17 //
18 // 19.10.12 Marek Gayer
19 // Created from original implementation in ROOT
20 // --------------------------------------------------------------------
21 
22 #ifndef UVoxelizer_HH
23 #define UVoxelizer_HH
24 
25 #include <vector>
26 #include <string>
27 #include <map>
28 
29 #include "UBits.hh"
30 #include "UBox.hh"
31 #include "VUFacet.hh"
32 #include "VUSolid.hh"
33 #include "UUtils.hh"
34 #include "UTransform3D.hh"
35 
36 struct UVoxelBox
37 {
38  UVector3 hlen; // half length of the box
39  UVector3 pos; // position of the box
40 };
41 
42 struct UVoxelInfo
43 {
44  int count;
45  int previous;
46  int next;
47 };
48 
50 {
51 // friend class UVoxelCandidatesIterator;
52 
53  public:
54 
55  template <typename T>
56 
57  // Binary search
58  static inline int BinarySearch(const std::vector<T>& vec, T value)
59  {
60  // Binary search in an array of doubles. If match is found, function returns
61  // position of element. If no match found, function gives nearest
62  // element smaller than value.
63  typename std::vector<T>::const_iterator begin = vec.begin(), end = vec.end();
64  int res = std::upper_bound(begin, end, value) - begin - 1;
65  return res;
66  }
67 // int BinarySearch(int n, const T *array, T value);
68 
69 #ifdef USOLIDSONLY
70  void Voxelize(std::vector<VUSolid*>& solids, std::vector<UTransform3D*>& transforms);
71 #endif // USOLIDSONLY
72 
73  void Voxelize(std::vector<VUFacet*>& facets);
74 
75  void DisplayVoxelLimits();
76  void DisplayBoundaries();
77  void DisplayListNodes();
78 
79  UVoxelizer();
80  ~UVoxelizer();
81 
82  // Method displaying the nodes located in a voxel characterized by its three indexes:
83  void GetCandidatesVoxel(std::vector<int>& voxels);
84  // Method returning in a vector container the nodes located in a voxel characterized by its three indexes:
85  int GetCandidatesVoxelArray(const UVector3& point, std::vector<int>& list, UBits* crossed = NULL) const;
86 
87  int GetCandidatesVoxelArray(const std::vector<int>& voxels, const UBits bitmasks[], std::vector<int>& list, UBits* crossed = NULL) const;
88 
89  int GetCandidatesVoxelArray(const std::vector<int>& voxels, std::vector<int>& list, UBits* crossed = NULL)const;
90 
91  // Method returning the pointer to the array containing the characteristics of each box:
92  inline const std::vector<UVoxelBox>& GetBoxes() const
93  {
94  return fBoxes;
95  }
96  inline const std::vector<double>& GetBoundary(int index) const
97  {
98  return fBoundaries[index];
99  }
100 
101  bool UpdateCurrentVoxel(const UVector3& point, const UVector3& direction, std::vector<int>& curVoxel) const;
102 
103  inline void GetVoxel(std::vector<int>& curVoxel, const UVector3& point) const
104  {
105  for (int i = 0; i <= 2; ++i)
106  {
107  const std::vector<double>& boundary = GetBoundary(i);
108  int n = BinarySearch(boundary, point[i]);
109  if (n == -1) n = 0;
110  else if (n == (int) boundary.size() - 1) n--;
111  curVoxel[i] = n;
112  }
113  }
114 
115  inline int GetBitsPerSlice() const
116  {
117  return fNPerSlice * 8 * sizeof(unsigned int);
118  }
119 
120  bool Contains(const UVector3& point) const;
121 
122  double DistanceToNext(const UVector3& point, const UVector3& direction, std::vector<int>& curVoxel) const;
123 
124  double DistanceToFirst(const UVector3& point, const UVector3& direction) const;
125 
126  double SafetyToBoundingBox(const UVector3& point) const;
127 
128  inline int GetVoxelsIndex(int x, int y, int z) const
129  {
130  if (x < 0 || y < 0 || z < 0) return -1;
131  int maxX = fBoundaries[0].size();
132  int maxY = fBoundaries[1].size();
133  int index = x + y * maxX + z * maxX * maxY;
134  return index;
135  }
136 
137  inline int GetVoxelsIndex(const std::vector<int>& voxels) const
138  {
139  return GetVoxelsIndex(voxels[0], voxels[1], voxels[2]);
140  }
141 
142  inline bool GetPointVoxel(const UVector3& p, std::vector<int>& voxels) const
143  {
144  for (int i = 0; i <= 2; ++i)
145  if (p[i] < *fBoundaries[i].begin() || p[i] > *fBoundaries[i].end()) return false;
146 
147  for (int i = 0; i <= 2; ++i)
148  voxels[i] = BinarySearch(fBoundaries[i], p[i]);
149 
150  return true;
151  }
152 
153  inline int GetPointIndex(const UVector3& p) const
154  {
155  int maxX = fBoundaries[0].size();
156  int maxY = fBoundaries[1].size();
157  int x = BinarySearch(fBoundaries[0], p[0]);
158  int y = BinarySearch(fBoundaries[1], p[1]);
159  int z = BinarySearch(fBoundaries[2], p[2]);
160  int index = x + y * maxX + z * maxX * maxY;
161  return index;
162  }
163 
164  inline const UBits& Empty() const
165  {
166  return fEmpty;
167  }
168 
169  inline bool IsEmpty(int index) const
170  {
171  return fEmpty[index];
172  }
173 
174  void SetMaxVoxels(int max);
175 
176  void SetMaxVoxels(const UVector3& reductionRatio);
177 
178  inline int GetMaxVoxels(UVector3& ratioOfReduction)
179  {
180  ratioOfReduction = fReductionRatio;
181  return fMaxVoxels;
182  }
183 
184  int AllocatedMemory();
185 
186  inline long long GetCountOfVoxels() const
187  {
188  return fCountOfVoxels;
189  }
190 
191  inline long long CountVoxels(std::vector<double> boundaries[]) const
192  {
193  long long sx = boundaries[0].size() - 1;
194  long long sy = boundaries[1].size() - 1;
195  long long sz = boundaries[2].size() - 1;
196  return sx * sy * sz;
197  }
198 
199  /*
200  inline int GetCandidates(std::vector<int> &curVoxel, std::vector<int> *&candidates, std::vector<int> &space) const
201  {
202  int voxelsIndex;
203  int emptys = fEmpty.GetNbits();
204  if (!emptys || ((voxelsIndex = GetVoxelsIndex(curVoxel)) >= 0) && !fEmpty[voxelsIndex])
205  {
206  if (emptys)
207  {
208  candidates = &fCandidates[voxelsIndex];
209  }
210  else
211  {
212  GetCandidatesVoxelArray(curVoxel, space, NULL);
213  candidates = &space;
214  }
215  return candidates->size();
216  }
217  return 0;
218  }
219  */
220 
221  inline const std::vector<int>& GetCandidates(std::vector<int>& curVoxel) const
222  {
223  int voxelsIndex = GetVoxelsIndex(curVoxel);
224  if (voxelsIndex >= 0 && !fEmpty[voxelsIndex])
225  {
226  return fCandidates[voxelsIndex];
227  }
228  return fNoCandidates;
229  }
230 
231  inline int GetVoxelBoxesSize() const
232  {
233  return fVoxelBoxes.size();
234  }
235 
236  inline const UVoxelBox& GetVoxelBox(int i) const
237  {
238  return fVoxelBoxes[i];
239  }
240 
241  inline const std::vector<int>& GetVoxelBoxCandidates(int i) const
242  {
243  return fVoxelBoxesCandidates[i];
244  }
245 
246  inline int GetTotalCandidates() const
247  {
248  return fTotalCandidates;
249  }
250 
251  static double MinDistanceToBox(const UVector3& aPoint, const UVector3& f);
252 
253  static void SetDefaultVoxelsCount(int count);
254 
255  static int GetDefaultVoxelsCount();
256 
257  void BuildBoundingBox();
258 
259  void BuildBoundingBox(UVector3& amin, UVector3& amax, double tolerance = 0);
260 
261  private:
262 
264 
265  std::vector<UVoxelBox> fVoxelBoxes;
266 
267  std::vector<std::vector<int> > fVoxelBoxesCandidates;
268 
269  mutable std::map<int, std::vector<int> > fCandidates;
270 
271  const std::vector<int> fNoCandidates;
272 
273  long long fCountOfVoxels;
274 
275  void BuildEmpty();
276 
277  std::string GetCandidatesAsString(const UBits& bits);
278 
279  void CreateSortedBoundary(std::vector<double>& boundaryRaw, int axis);
280 
281  void BuildBoundaries();
282 
283  void BuildReduceVoxels(std::vector<double> fBoundaries[], UVector3 reductionRatio);
284 
285  void BuildReduceVoxels2(std::vector<double> fBoundaries[], UVector3 reductionRatio);
286 
287 #ifdef USOLIDSONLY
288  void BuildVoxelLimits(std::vector<VUSolid*>& solids, std::vector<UTransform3D*>& transforms);
289 #endif // USOLIDSONLY
290 
291  void BuildVoxelLimits(std::vector<VUFacet*>& facets);
292 
293  void DisplayBoundaries(std::vector<double>& fBoundaries);
294 
295  void BuildBitmasks(std::vector<double> fBoundaries[], UBits bitmasks[]);
296 
297  void SetReductionRatio(int maxVoxels, UVector3& reductionRatio);
298 
299  void CreateMiniVoxels(std::vector<double> fBoundaries[], UBits bitmasks[]);
300 
302 
303  std::vector<UVoxelBox> fBoxes; // Array of box limits on the 3 cartesian axis
304 
305  std::vector<double> fBoundaries[3]; // Sorted and if need skimmed fBoundaries along X,Y,Z axis
306 
307  std::vector<int> fCandidatesCounts[3];
308 
310 
312 
316 
318 
320 
321  double fTolerance;
322 
324 };
325 
326 
327 #ifdef USOLIDSONLY
328 
329 /*
330 class UVoxelCandidatesIterator
331 {
332 private:
333  unsigned int mask;
334  int curInt, curBit, carNodes, n, sliceX, sliceY, sliceZ;
335  unsigned int *maskX, *maskY, *maskZ;
336  unsigned int *maskXLeft, *maskYLeft, *maskZLeft;
337  bool nextAvailable;
338 
339 public:
340  UVoxelCandidatesIterator(const UVoxelizer &f, const UVector3 &point);
341 
342  int Next();
343 };
344 */
345 
346 #endif // USOLIDSONLY
347 
348 #endif
int GetVoxelsIndex(const std::vector< int > &voxels) const
Definition: UVoxelizer.hh:137
static int fDefaultVoxelsCount
Definition: UVoxelizer.hh:263
UVector3 hlen
Definition: UVoxelizer.hh:38
void DisplayBoundaries()
Definition: UVoxelizer.cc:270
const std::vector< double > & GetBoundary(int index) const
Definition: UVoxelizer.hh:96
int GetVoxelsIndex(int x, int y, int z) const
Definition: UVoxelizer.hh:128
double DistanceToNext(const UVector3 &point, const UVector3 &direction, std::vector< int > &curVoxel) const
Definition: UVoxelizer.cc:1056
G4double z
Definition: TRTMaterials.hh:39
int GetTotalCandidates() const
Definition: UVoxelizer.hh:246
void CreateMiniVoxels(std::vector< double > fBoundaries[], UBits bitmasks[])
Definition: UVoxelizer.cc:646
void SetMaxVoxels(int max)
Definition: UVoxelizer.cc:1124
void BuildEmpty()
Definition: UVoxelizer.cc:50
int fMaxVoxels
Definition: UVoxelizer.hh:319
bool UpdateCurrentVoxel(const UVector3 &point, const UVector3 &direction, std::vector< int > &curVoxel) const
void GetVoxel(std::vector< int > &curVoxel, const UVector3 &point) const
Definition: UVoxelizer.hh:103
bool Contains(const UVector3 &point) const
Definition: UVoxelizer.cc:997
Definition: UBox.hh:33
long long GetCountOfVoxels() const
Definition: UVoxelizer.hh:186
std::vector< UVoxelBox > fBoxes
Definition: UVoxelizer.hh:303
int fTotalCandidates
Definition: UVoxelizer.hh:309
int GetMaxVoxels(UVector3 &ratioOfReduction)
Definition: UVoxelizer.hh:178
void BuildVoxelLimits(std::vector< VUSolid * > &solids, std::vector< UTransform3D * > &transforms)
double DistanceToFirst(const UVector3 &point, const UVector3 &direction) const
Definition: UVoxelizer.cc:1007
std::vector< double > fBoundaries[3]
Definition: UVoxelizer.hh:305
static int BinarySearch(const std::vector< T > &vec, T value)
Definition: UVoxelizer.hh:58
int GetVoxelBoxesSize() const
Definition: UVoxelizer.hh:231
void BuildReduceVoxels2(std::vector< double > fBoundaries[], UVector3 reductionRatio)
Definition: UVoxelizer.cc:584
void BuildBoundaries()
Definition: UVoxelizer.cc:207
static double MinDistanceToBox(const UVector3 &aPoint, const UVector3 &f)
Definition: UVoxelizer.cc:1021
void BuildBoundingBox()
Definition: UVoxelizer.cc:424
std::vector< std::vector< int > > fVoxelBoxesCandidates
Definition: UVoxelizer.hh:267
const std::vector< int > fNoCandidates
Definition: UVoxelizer.hh:271
UVector3 pos
Definition: UVoxelizer.hh:39
int GetCandidatesVoxelArray(const UVector3 &point, std::vector< int > &list, UBits *crossed=NULL) const
Definition: UVoxelizer.cc:867
void BuildBitmasks(std::vector< double > fBoundaries[], UBits bitmasks[])
Definition: UVoxelizer.cc:298
const G4int n
long long CountVoxels(std::vector< double > boundaries[]) const
Definition: UVoxelizer.hh:191
const UVoxelBox & GetVoxelBox(int i) const
Definition: UVoxelizer.hh:236
bool GetPointVoxel(const UVector3 &p, std::vector< int > &voxels) const
Definition: UVoxelizer.hh:142
int previous
Definition: UVoxelizer.hh:45
UVector3 fReductionRatio
Definition: UVoxelizer.hh:317
int fNPerSlice
Definition: UVoxelizer.hh:301
std::string GetCandidatesAsString(const UBits &bits)
Definition: UVoxelizer.cc:389
UBits fBitmasks[3]
Definition: UVoxelizer.hh:311
const std::vector< int > & GetCandidates(std::vector< int > &curVoxel) const
Definition: UVoxelizer.hh:221
T max(const T t1, const T t2)
brief Return the largest of the two arguments
UBox fBoundingBox
Definition: UVoxelizer.hh:314
const std::vector< int > & GetVoxelBoxCandidates(int i) const
Definition: UVoxelizer.hh:241
void GetCandidatesVoxel(std::vector< int > &voxels)
Definition: UVoxelizer.cc:777
static int GetDefaultVoxelsCount()
Definition: UVoxelizer.cc:1156
int GetPointIndex(const UVector3 &p) const
Definition: UVoxelizer.hh:153
std::vector< UVoxelBox > fVoxelBoxes
Definition: UVoxelizer.hh:265
double fTolerance
Definition: UVoxelizer.hh:321
long long fCountOfVoxels
Definition: UVoxelizer.hh:273
int GetBitsPerSlice() const
Definition: UVoxelizer.hh:115
void BuildReduceVoxels(std::vector< double > fBoundaries[], UVector3 reductionRatio)
Definition: UVoxelizer.cc:490
std::vector< int > fCandidatesCounts[3]
Definition: UVoxelizer.hh:307
void CreateSortedBoundary(std::vector< double > &boundaryRaw, int axis)
Definition: UVoxelizer.cc:189
void DisplayListNodes()
Definition: UVoxelizer.cc:403
void DisplayVoxelLimits()
Definition: UVoxelizer.cc:173
std::map< int, std::vector< int > > fCandidates
Definition: UVoxelizer.hh:269
const std::vector< UVoxelBox > & GetBoxes() const
Definition: UVoxelizer.hh:92
void SetReductionRatio(int maxVoxels, UVector3 &reductionRatio)
Definition: UVoxelizer.cc:477
double SafetyToBoundingBox(const UVector3 &point) const
Definition: UVoxelizer.cc:1014
int AllocatedMemory()
Definition: UVoxelizer.cc:1136
const UBits & Empty() const
Definition: UVoxelizer.hh:164
static void SetDefaultVoxelsCount(int count)
Definition: UVoxelizer.cc:1151
void Voxelize(std::vector< VUSolid * > &solids, std::vector< UTransform3D * > &transforms)
UVector3 fBoundingBoxSize
Definition: UVoxelizer.hh:315
UBits fEmpty
Definition: UVoxelizer.hh:323
Definition: UBits.hh:38
bool IsEmpty(int index) const
Definition: UVoxelizer.hh:169
UVector3 fBoundingBoxCenter
Definition: UVoxelizer.hh:313