HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_PointGrid.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_PointGrid (UT Library, C++)
7  *
8  * COMMENTS: Point-in-grid acceleration structure
9  */
10 
11 #ifndef __UT_PointGrid_h__
12 #define __UT_PointGrid_h__
13 
14 #include "UT_ValArray.h"
15 #include "UT_Vector3.h"
16 #include "UT_VectorTypes.h"
17 #include "UT_VoxelArray.h"
18 #include "UT_BitArray.h"
19 
20 template <typename T>
22 
23 /// @brief Iteration over a range of keys returned from a UT_PointGrid query.
24 ///
25 /// An iterator is used to iterate over the results of a query into
26 /// UT_PointGrid. of a given range. The UT_PointGrid query functions return
27 /// iterators already rewound, so in most cases there is no need for
28 /// an explicit rewind() call.
29 template <typename T>
31 {
32 public:
33  typedef typename T::indextype indextype;
34  typedef typename T::keytype keytype;
35 
37 
38  // Use default copy constructor.
39  // UT_PointGridIterator(const UT_PointGridIterator &src);
40 
41  /// @{
42  /// Standard iterator methods.
43  void rewind();
44  bool atEnd() const;
45  void advance();
46  /// @}
47 
48  /// @{
49  /// Query state of the iterator
50  keytype getValue() const;
51  keytype operator *() const { return getValue(); }
52  /// @}
53 
54  /// The total number of keys over which this iterator will iterate.
55  exint entries() const;
56 
57  /// The total number of occupied point grid voxels over which this
58  /// iterator will iterate.
59  exint numSequences() const { return mySequences->entries(); }
60 
61  /// Test to see whether the iterator is valid.
62  bool isValid() const { return myGrid != 0; }
63 
64 protected:
65 
67  {
70  };
71 
73 
75  queuetype &queue);
76 
77  void advanceSequence();
78 
84  friend class UT_PointGrid<T>;
85 };
86 
87 /// @brief Iteration over a range of elements
88 /// This class implements a point-in-grid acceleration structure
89 /// that does a multithreaded build to handle large particle counts
90 /// and provides linear time lookups into the grid structure.
91 /// It's similar in spirit to particle acceleration techniques
92 /// used on GPUs:
93 /// Green, Simon. Particle Simulation using CUDA. CUDA 4.0 SDK
94 template <typename T>
95 class UT_PointGrid
96 {
97 public:
98 
99  /// Create a point grid with the specified accessor.
100  /// @note The point grid is not valid until build() is called.
101  UT_PointGrid(const T &accessor): myAccessor(accessor)
102  {
103  // The accessor's indextype must be signed so we can
104  // store it in a UT_VoxelArray.
105  SYS_STATIC_ASSERT(std::numeric_limits<indextype>::is_signed);
106  }
107 
108  /// The index and key type for the point grid, derived from the accessor
109  /// type.
110  typedef typename T::indextype indextype;
111  typedef typename T::keytype keytype;
112 
114 
115  typedef T accessortype;
118 
119  /// Constructs the point grid over the specified world-space coordinates
120  /// and resolution. The points will be read from the accessor provided
121  /// when the object was created.
122  /// @note This function asserts on canBuild(), to catch the case that
123  /// the indextype or keytype types can not represent the number of points
124  /// or the size of the grid.
125  bool build(const UT_Vector3 &orig, const UT_Vector3 &size,
126  int xres, int yres, int zres);
127 
128  /// Returns true if all point elements will fit into the specified
129  /// indextype and keytpe data types without overflow, given the provided
130  /// resolution.
131  bool canBuild(int xres, int yres, int zres);
132 
133  /// Returns an iterator over the points occupying the grid voxel at the
134  /// specified index.
135  /// @note The iterator will be created rewound.
136  /// @note The queue object should be created with createQueue(), and
137  /// only one iterator at a time can be created with a particular queue.
138  UT_PointGridIterator<T> getKeysAt(int x, int y, int z,
139  queuetype &queue) const;
140 
141  /// Returns an iterator over all points that have invalid keys or did not
142  /// fit in the bounding box of the grid.
143  /// @note The iterator will be created rewound.
144  /// @note The queue object should be created with createQueue(), and
145  /// only one iterator at a time can be created with a particular queue.
147 
148  /// Queries the grid voxels within radius of position.
149  /// Returns an iterator over the keys corresponding to the points.
150  /// @note The iterator will be created rewound. It may return keys
151  /// from points that are in the voxels but outside the provided radius.
152  /// The caller must cull these out manually if so desired.
153  /// @note The queue object should be created with createQueue(), and
154  /// only one iterator at a time can be created with a particular queue.
157  fpreal radius) const;
158 
159  /// Returns true if any voxels within radius of the position contain
160  /// points.
161  bool hasCloseKeys(const UT_Vector3 &position, fpreal radius) const;
162 
163  /// Returns the total number of points.
164  exint entries() const { return myIdxKeys.entries(); }
165 
166  /// Returns number of points contained in a given voxel.
167  exint entriesAt(int x, int y, int z) const;
168 
169  /// Convert a world space position to a grid index.
170  /// Always returns true if boundsCheck is false, else returns true only
171  /// if the index is valid for the grid
172  bool posToIndex(UT_Vector3 position, int &x, int &y, int &z,
173  bool boundsCheck = true) const;
174 
175  /// Returns true if the specified index is valid for the underlying grid.
176  bool isValidIndex(int x, int y, int z) const
177  {
178  return myBegins.isValidIndex(x, y, z);
179  }
180 
181  /// Returns the total memory usage (in bytes) of the grid.
182  int64 getMemoryUsage() const;
183 
184  /// Returns the key at the specified index.
185  keytype getKeyAt(indextype idx) const { return myIdxKeys(idx).key;}
186 
187  /// X-resolution of the underlying grid.
188  int getXRes() const { return myBegins.getXRes(); }
189  /// Y-resolution of the underlying grid.
190  int getYRes() const { return myBegins.getYRes(); }
191  /// Z-resolution of the underlying grid.
192  int getZRes() const { return myBegins.getZRes(); }
193  /// Resolution of the underlying grid along the specified axis.
194  int getRes(int axis) const { return myBegins.getRes(axis); }
195 
196  /// Returns the voxel size of the underlying grid.
197  const UT_Vector3 &getVoxelSize() const { return myVoxelSize; }
198 
199  /// Creates a queue that can be used for querying this point grid. Any
200  /// number of queueus can be created for a point grid, but only one
201  /// iterator can use a particular queue at a time. Typically each thread
202  /// in a multithreaded operation will have its own queue.
203  static queuetype *createQueue() { return new queuetype; }
204 
205  /// Destroys a queue created with createQueue().
206  static void destroyQueue(queuetype *queue) { delete queue; }
207 
208 protected:
209  static const indextype INVALIDINDEX;
211 
212  // Gets the key begin/end indices for the given voxel.
213  // Returns false is none exist or the indices are invalid.
214  bool getKeysAt(int x, int y, int z,
215  indextype &begin, indextype &end) const;
216 
217 
218  // The most commons use of this struct has an exint grididxtype
219  // and a uint32 key; rather than have the compiler extend this to
220  // 16 bytes, we try to pack to 12. Any slower access times are more
221  // than made up for by much faster sorting, which is memory bound.
223  {
224  grididxtype grididx;
225  keytype key;
226  };
228 
229  grididxtype indexToGridIdx(int x, int y, int z);
230 
231  void gridIdxToIndex(grididxtype idx, int &x, int &y, int &z);
232 
233  bool calcBounds(const UT_Vector3 &pos, fpreal radius,
234  int &xmin, int &ymin, int &zmin,
235  int &xmax, int &ymax, int &zmax) const;
236 
237  // STL-style comparator for sorting by grididx.
239  {
240  public:
241  inline bool operator()(const UT_GridIdxKey &a,
242  const UT_GridIdxKey &b) const
243  {
244  return a.grididx < b.grididx;
245  }
246  };
247 
248  bool shouldMultithread() const
249  {
250  return myAccessor.entries() > 1000;
251  }
252 
254  computeGridIdx,
255  UT_ValArray<bool> &, tileoccupied);
256 
257  void computeGridIdxPartial(UT_ValArray<bool> &tileoccupied,
258  const UT_JobInfo &info);
259 
261  findIdxRanges,
262  UT_ValArray<UT_Vector3T<int> > &, bboxmins,
263  UT_ValArray<UT_Vector3T<int> > &, bboxmaxs,
264  indextype, numValidKeys);
265 
267  UT_ValArray<UT_Vector3T<int> > &bboxmaxs,
268  indextype numValidKeys,
269  const UT_JobInfo &info);
270 
271  THREADED_METHOD1(UT_PointGrid<T>, tileoccupied.entries() > 20,
272  uncompressTiles,
273  const UT_ValArray<bool> &, tileoccupied);
274 
275  void uncompressTilesPartial(const UT_ValArray<bool> &tileoccupied,
276  const UT_JobInfo &info);
277 
286 
287 };
288 
289 /// @brief Generic UT_Vector3Array based accessor for UT_PointGrid.
290 ///
291 /// This class provides the required functions to serve as an accessor for
292 /// building a UT_PointGrid over the points provided in the UT_Vector3Array
293 /// passed to the constructor.
294 /// See GEO_PointGrid for an accessor over the points in a GEO_Detail.
295 template <typename INDEX, typename KEY>
297 {
298 public:
299  // indextype must be signed.
300  typedef INDEX indextype;
301  typedef KEY keytype;
302 
303  /// Invalid key value.
304  static const keytype INVALIDKEY;
305 
306  /// Create an accessor for the provided array of positions and keys.
307  /// @note This class will not take ownership of the provided arrays;
308  /// it merely provides an interface for UT_PointGrid::build().
310  const UT_ValArray<keytype> &keys,
311  const UT_BitArray *valid = NULL):
312  myV3Array(positions),
313  myKeyArray(keys),
314  myValidArray(valid)
315  {
316  UT_ASSERT(myV3Array.entries() == myKeyArray.entries());
318  myValidArray->size() == myKeyArray.entries());
319  }
320 
321  /// Returns the number of points.
323  {
324  return myV3Array.entries();
325  }
326 
327  /// Returns the position for a given index.
329  {
330  return myV3Array(idx);
331  }
332 
333  /// Gets the key for a given index.
335  {
336  if (!myValidArray)
337  return myKeyArray(idx);
338  return myValidArray->getBit(idx) ? myKeyArray(idx) : INVALIDKEY;
339  }
340 
341  /// Returns the maximum possible key value, used by
342  /// UT_PointGrid::canBuild().
344  {
346  }
347 
349  {
350  // The accessor doesn't own any data.
352  }
353 
354  void build() {}
355 
356 protected:
360 };
361 
364 
365 #include "UT_PointGridImpl.h"
366 
367 #endif
void gridIdxToIndex(grididxtype idx, int &x, int &y, int &z)
const UT_Vector3Array & myV3Array
Definition: UT_PointGrid.h:357
#define SYS_PACKED_STRUCT_HINT_END
Definition: SYS_Types.h:441
#define SYS_STATIC_ASSERT(expr)
UT_PointGridIterator< T > findCloseKeys(const UT_Vector3 &position, queuetype &queuetype, fpreal radius) const
keytype getValue() const
bool getBit(exint index) const
Definition: UT_BitArray.h:251
Iteration over a range of elements This class implements a point-in-grid acceleration structure that ...
Definition: UT_PointGrid.h:21
keytype getKey(indextype idx) const
Gets the key for a given index.
Definition: UT_PointGrid.h:334
T::keytype keytype
Definition: UT_PointGrid.h:111
SYS_PACKED_STRUCT_HINT_END grididxtype indexToGridIdx(int x, int y, int z)
UT_Vector3 myOrig
Definition: UT_PointGrid.h:281
queuetype * mySequences
Definition: UT_PointGrid.h:79
T::indextype indextype
Definition: UT_PointGrid.h:110
int getXRes() const
X-resolution of the underlying grid.
Definition: UT_PointGrid.h:188
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:847
UT_Vector3 myInvVoxelSize
Definition: UT_PointGrid.h:284
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
UT_Vector3 mySize
Definition: UT_PointGrid.h:282
int getYRes() const
Y-resolution of the underlying grid.
Definition: UT_PointGrid.h:190
exint entries() const
The total number of keys over which this iterator will iterate.
bool calcBounds(const UT_Vector3 &pos, fpreal radius, int &xmin, int &ymin, int &zmin, int &xmax, int &ymax, int &zmax) const
keytype operator*() const
Definition: UT_PointGrid.h:51
bool hasCloseKeys(const UT_Vector3 &position, fpreal radius) const
GLint y
Definition: glcorearb.h:102
UT_PointGridIterator< T > getKeysAt(int x, int y, int z, queuetype &queue) const
int getZRes() const
Z-resolution of the underlying grid.
Definition: UT_PointGrid.h:192
GLsizeiptr size
Definition: glcorearb.h:663
exint grididxtype
Definition: UT_PointGrid.h:113
UT_VoxelArray< indextype > myEnds
Definition: UT_PointGrid.h:279
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
T::indextype indextype
Definition: UT_PointGrid.h:33
static void destroyQueue(queuetype *queue)
Destroys a queue created with createQueue().
Definition: UT_PointGrid.h:206
long long int64
Definition: SYS_Types.h:100
static const keytype INVALIDKEY
Invalid key value.
Definition: UT_PointGrid.h:304
const UT_BitArray * myValidArray
Definition: UT_PointGrid.h:359
UT_ValArray< UT_PointGridSequence > queuetype
Definition: UT_PointGrid.h:72
THREADED_METHOD1(UT_PointGrid< T >, shouldMultithread(), computeGridIdx, UT_ValArray< bool > &, tileoccupied)
void computeGridIdxPartial(UT_ValArray< bool > &tileoccupied, const UT_JobInfo &info)
Generic UT_Vector3Array based accessor for UT_PointGrid.
Definition: UT_PointGrid.h:296
exint entries() const
Returns the total number of points.
Definition: UT_PointGrid.h:164
UT_PointGrid(const T &accessor)
Definition: UT_PointGrid.h:101
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
int getYRes() const
bool shouldMultithread() const
Definition: UT_PointGrid.h:248
UT_Vector3T< int > myBBoxMin
Definition: UT_PointGrid.h:285
int64 exint
Definition: SYS_Types.h:109
UT_PointGridIterator< T > getInvalidKeys(queuetype &queue) const
bool posToIndex(UT_Vector3 position, int &x, int &y, int &z, bool boundsCheck=true) const
UT_Vector3Grid::queuetype UT_Vector3GridQueue
Definition: UT_PointGrid.h:363
static const indextype INVALIDINDEX
Definition: UT_PointGrid.h:209
UT_PointGridVector3ArrayAccessor(const UT_Vector3Array &positions, const UT_ValArray< keytype > &keys, const UT_BitArray *valid=NULL)
Definition: UT_PointGrid.h:309
GLuint GLuint end
Definition: glcorearb.h:474
static queuetype * createQueue()
Definition: UT_PointGrid.h:203
int getRes(int axis) const
Resolution of the underlying grid along the specified axis.
Definition: UT_PointGrid.h:194
exint size() const
Definition: UT_BitArray.h:46
bool operator()(const UT_GridIdxKey &a, const UT_GridIdxKey &b) const
Definition: UT_PointGrid.h:241
int getXRes() const
UT_Vector3 myVoxelSize
Definition: UT_PointGrid.h:283
keytype getKeyAt(indextype idx) const
Returns the key at the specified index.
Definition: UT_PointGrid.h:185
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
exint entriesAt(int x, int y, int z) const
Returns number of points contained in a given voxel.
void findIdxRangesPartial(UT_ValArray< UT_Vector3T< int > > &bboxmins, UT_ValArray< UT_Vector3T< int > > &bboxmaxs, indextype numValidKeys, const UT_JobInfo &info)
void uncompressTilesPartial(const UT_ValArray< bool > &tileoccupied, const UT_JobInfo &info)
SYS_PACKED_STRUCT_HINT_BEGIN(UT_GridIdxKey, 4)
Definition: UT_PointGrid.h:222
const UT_Vector3 & getVoxelSize() const
Returns the voxel size of the underlying grid.
Definition: UT_PointGrid.h:197
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:446
int getZRes() const
indextype entries() const
Returns the number of points.
Definition: UT_PointGrid.h:322
double fpreal
Definition: SYS_Types.h:263
UT_PointGrid< UT_PointGridVector3ArrayAccessor< int32, exint > > UT_Vector3Grid
Definition: UT_PointGrid.h:362
int64 getMemoryUsage() const
Returns the total memory usage (in bytes) of the grid.
static const grididxtype INVALIDGRIDIDX
Definition: UT_PointGrid.h:210
THREADED_METHOD3(UT_PointGrid< T >, shouldMultithread(), findIdxRanges, UT_ValArray< UT_Vector3T< int > > &, bboxmins, UT_ValArray< UT_Vector3T< int > > &, bboxmaxs, indextype, numValidKeys)
exint numSequences() const
Definition: UT_PointGrid.h:59
bool isValid() const
Test to see whether the iterator is valid.
Definition: UT_PointGrid.h:62
const UT_ValArray< keytype > & myKeyArray
Definition: UT_PointGrid.h:358
bool build(const UT_Vector3 &orig, const UT_Vector3 &size, int xres, int yres, int zres)
GLint GLenum GLint x
Definition: glcorearb.h:408
int getRes(int axis) const
Iteration over a range of keys returned from a UT_PointGrid query.
Definition: UT_PointGrid.h:30
const UT_PointGrid< T > * myGrid
Definition: UT_PointGrid.h:83
UT_VoxelArray< indextype > myBegins
Definition: UT_PointGrid.h:279
UT_Vector3 getPos(indextype idx) const
Returns the position for a given index.
Definition: UT_PointGrid.h:328
UT_PointGridIterator< T >::queuetype queuetype
Definition: UT_PointGrid.h:117
bool isValidIndex(int x, int y, int z) const
Returns true if the given x, y, z values lie inside the valid index.
UT_Vector3T< int > myBBoxMax
Definition: UT_PointGrid.h:285
bool isValidIndex(int x, int y, int z) const
Returns true if the specified index is valid for the underlying grid.
Definition: UT_PointGrid.h:176
UT_ValArray< UT_GridIdxKey > myIdxKeys
Definition: UT_PointGrid.h:278
bool canBuild(int xres, int yres, int zres)
UT_PointGridIterator< T > iterator
Definition: UT_PointGrid.h:116