HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_HashGrid.C
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: Utility Library (C++)
7  *
8  * COMMENTS:
9  * This class implements a grid-based data structure for
10  * storing spacial data (ie. points) with a fixed radius of
11  * influence. It can be used to quickly determine the set
12  * of elements affecting a given point in space.
13  */
14 
15 #ifndef __UT_HashGrid_C__
16 #define __UT_HashGrid_C__
17 
18 #include "UT_HashGrid.h"
19 #include "UT_Map.h"
20 #include "UT_IntArray.h"
21 #include "UT_Vector3.h"
22 #include "UT_Vector3Array.h"
23 
24 // We limit the number of cells in any one dimension to
25 // 21 bits. This gives us 63 bits used in total, so
26 // fits in the size of an int64.
27 #define ut_CELL_SHIFT 21
28 #define ut_CELL_SHIFT2 42
29 #define ut_CELL_MASK (( ((int64) 1) << ut_CELL_SHIFT)-1)
30 
31 static const int ut_NUM_CELL_NEIGHBOURS = 27;
32 
33 template <typename utPtr>
35  bool fullinit, unsigned int sz)
36  : myOrigin(origin),
37  myCellWidth(cellsize),
38  myMaxElements(0),
39  myGridSet(),
40  myCellArray(0), // We may want to initialize to sz/factor.
41  myFullInit(fullinit),
42  myPositions(sz),
43  myElements(sz)
44 {
45  myCellWidth2 = myCellWidth * myCellWidth;
46  myInvCellWidth = 1.0f / myCellWidth;
47 
48  // This is likely user error, but the result is catastropic so
49  // we just bail.
50  if (myOrigin.isNan())
51  myOrigin = 0;
52 }
53 
54 template <typename utPtr>
55 int64
57 {
58  int64 memuse = inclusive ? sizeof(*this) : 0;
59  memuse += myPositions.getMemoryUsage(false);
60  memuse += myElements.getMemoryUsage(false);
61  memuse += myCellArray.getMemoryUsage(false);
62  for (exint i = 0; i < myCellArray.entries(); i++)
63  {
64  memuse += myCellArray(i).myIndices.getMemoryUsage(false);
65  }
66  memuse += myGridSet.getMemoryUsage(false);
67  return memuse;
68 }
69 
70 // Insert a new element in to the grid set.
71 template <typename utPtr>
72 bool
74 {
75  // Start by getting the cell this point should
76  // be in, creating it if it does not already
77  // exist.
79  UT_HashGridCell<utPtr> *othercell;
80  int i, j, k;
81  int newindex;
82  int pointindex = myPositions.entries();
83 
84  myPositions.append(p);
85  myElements.append(t);
86 
87  // Refuse to pollute with nans.
88  if (p.isNan())
89  return true;
90 
91  i = SYSfastFloor((p.x() - myOrigin.x()) * myInvCellWidth);
92  j = SYSfastFloor((p.y() - myOrigin.y()) * myInvCellWidth);
93  k = SYSfastFloor((p.z() - myOrigin.z()) * myInvCellWidth);
94 
95  cell = getCell(i, j, k, true);
96 
97  // Append the element to the cell's list.
98  newindex = cell->myIndices.append(pointindex) + 1;
99 
100  if (newindex > myMaxElements)
101  myMaxElements = newindex;
102 
103  if (myFullInit)
104  {
105  for (int dz = -1; dz <= 1; dz++)
106  {
107  for (int dy = -1; dy <= 1; dy++)
108  {
109  for (int dx = -1; dx <= 1; dx++)
110  {
111  // Already did center.
112  if (!dx && !dy && !dz)
113  continue;
114 
115  othercell = getCell(i+dx, j+dy, k+dz, true);
116  newindex = othercell->myIndices.append(pointindex) + 1;
117 
118  if (newindex > myMaxElements)
119  myMaxElements = newindex;
120  }
121  }
122  }
123  }
124 
125  return true;
126 }
127 
128 // Insert a new element in to the grid set.
129 template <typename utPtr>
130 void
132 {
133  utPtr blankelem = utPtr();
134  UT_Vector3 zero(0, 0, 0);
135 
136  myPositions.appendMultiple(zero, nblanks);
137  myElements.appendMultiple(blankelem, nblanks);
138 }
139 
140 // Generates a list of elements close to the given point.
141 template <typename utPtr>
142 void
144  UT_Array<utPtr> &list) const
145 {
146  list.entries(0);
147 
148  // Trivial to look up nans.
149  if (p.isNan())
150  {
151  return;
152  }
153  if (myFullInit)
154  {
155  const UT_HashGridCell<utPtr> *cell = getCell(p);
156  int i, n;
157 
158  if (cell)
159  {
160  n = cell->myIndices.entries();
161 
162  list.setCapacityIfNeeded(n);
163 
164  for (i = 0; i < n; i++)
165  {
166  int index = cell->myIndices(i);
167  if ((p - myPositions(index)).length2() < myCellWidth2)
168  list.append(myElements(index));
169  }
170  }
171  }
172  else
173  {
174  int i, j, k;
175  int ptnum, npts;
176  const UT_HashGridCell<utPtr> *currcell;
177 
178  i = SYSfastFloor((p.x() - myOrigin.x()) * myInvCellWidth);
179  j = SYSfastFloor((p.y() - myOrigin.y()) * myInvCellWidth);
180  k = SYSfastFloor((p.z() - myOrigin.z()) * myInvCellWidth);
181 
182  // We rely on the caller not wiping out the list, thus
183  // there is no real advantage in pre-sizing it.
184 
185  for (int dz = -1; dz <= 1; dz++)
186  {
187  for (int dy = -1; dy <= 1; dy++)
188  {
189  for (int dx = -1; dx <= 1; dx++)
190  {
191  currcell = getCell(i+dx, j+dy, k+dz);
192  if (currcell)
193  {
194  npts = currcell->myIndices.entries();
195  for (ptnum = 0; ptnum < npts; ptnum++)
196  {
197  int index = currcell->myIndices(ptnum);
198 
199  if ( (p - myPositions(index)).length2() < myCellWidth2)
200  list.append(myElements(index));
201  }
202  }
203  }
204  }
205  }
206  }
207 }
208 
209 // Generates a list of elements close to the given point.
210 template <typename utPtr>
211 void
213  UT_IntArray &list) const
214 {
215  list.entries(0);
216 
217  // Trivial to look up nans.
218  if (p.isNan())
219  {
220  return;
221  }
222  if (myFullInit)
223  {
224  const UT_HashGridCell<utPtr> *cell = getCell(p);
225 
226  if (cell)
227  {
228  list.concat(cell->myIndices);
229  }
230  }
231  else
232  {
233  int i, j, k;
234  const UT_HashGridCell<utPtr> *currcell;
235 
236  i = SYSfastFloor((p.x() - myOrigin.x()) * myInvCellWidth);
237  j = SYSfastFloor((p.y() - myOrigin.y()) * myInvCellWidth);
238  k = SYSfastFloor((p.z() - myOrigin.z()) * myInvCellWidth);
239 
240  // We rely on the caller not wiping out the list, thus
241  // there is no real advantage in pre-sizing it.
242  list.entries(0);
243 
244  for (int dz = -1; dz <= 1; dz++)
245  {
246  for (int dy = -1; dy <= 1; dy++)
247  {
248  for (int dx = -1; dx <= 1; dx++)
249  {
250  currcell = getCell(i+dx, j+dy, k+dz);
251  if (currcell)
252  {
253  list.concat(currcell->myIndices);
254  }
255  }
256  }
257  }
258  }
259 }
260 template <typename utPtr>
261 void
263 {
264  myMaxElements = 0;
265 
266  myGridSet.clear();
267 
268  myCellArray.entries(0);
269  myCellArray.setCapacity(0);
270 
271  myPositions.entries(0);
272  myPositions.setCapacity(sz);
273 
274  myElements.entries(0);
275  myElements.setCapacity(sz);
276 }
277 
278 template <typename utPtr>
279 void
281  bool fullinit, unsigned int sz)
282 {
283  reset(sz);
284 
285  myCellWidth = cellsize;
286  myOrigin = origin;
287  myFullInit = fullinit;
288 }
289 
290 template <typename utPtr>
292 UT_HashGrid<utPtr>::getCell(const UT_Vector3 &p, bool create)
293 {
294  int xi, yi, zi; // x, y and z indices
295 
296  xi = SYSfastFloor((p.x() - myOrigin.x()) * myInvCellWidth);
297  yi = SYSfastFloor((p.y() - myOrigin.y()) * myInvCellWidth);
298  zi = SYSfastFloor((p.z() - myOrigin.z()) * myInvCellWidth);
299 
300  return getCell(xi, yi, zi, create);
301 }
302 
303 template <typename utPtr>
306 {
307  int xi, yi, zi; // x, y and z indices
308 
309  xi = SYSfastFloor((p.x() - myOrigin.x()) * myInvCellWidth);
310  yi = SYSfastFloor((p.y() - myOrigin.y()) * myInvCellWidth);
311  zi = SYSfastFloor((p.z() - myOrigin.z()) * myInvCellWidth);
312 
313  return getCell(xi, yi, zi);
314 }
315 
316 template <typename utPtr>
318 UT_HashGrid<utPtr>::getCell(int xi, int yi, int zi, bool create)
319 {
320  exint index;
321  index = zi & ut_CELL_MASK;
322  index <<= ut_CELL_SHIFT;
323  index += yi & ut_CELL_MASK;
324  index <<= ut_CELL_SHIFT;
325  index += xi & ut_CELL_MASK;
326 
327  // Locate the cell number from the hash table.
328  exint arrayindex = -1;
329  auto &&it = myGridSet.find(index);
330  if (it != myGridSet.end())
331  {
332  arrayindex = it->second;
333  }
334 
335  if (arrayindex >= 0)
336  return &myCellArray(arrayindex);
337  else if (create)
338  {
339  exint cellindex = myCellArray.append();
340 
341  // Add this cell to the hash table.
342  myGridSet[index] = cellindex;
343 
344  return &myCellArray(cellindex);
345  }
346  else
347  return NULL;
348 }
349 
350 template <typename utPtr>
352 UT_HashGrid<utPtr>::getCell(int xi, int yi, int zi) const
353 {
354  exint index;
355  index = zi & ut_CELL_MASK;
356  index <<= ut_CELL_SHIFT;
357  index += yi & ut_CELL_MASK;
358  index <<= ut_CELL_SHIFT;
359  index += xi & ut_CELL_MASK;
360 
361  // Locate the cell number from the hash table.
362  exint arrayindex = -1;
363  auto &&it = myGridSet.find(index);
364  if (it != myGridSet.end())
365  {
366  arrayindex = it->second;
367  }
368 
369  if (arrayindex >= 0)
370  return &myCellArray(arrayindex);
371  else
372  return NULL;
373 }
374 
375 #endif // __UT_HashGrid.C
SYS_FORCE_INLINE bool isNan() const
void insertBlanks(int nblanks)
Definition: UT_HashGrid.C:131
UT_HashGrid(fpreal cellsize, const UT_Vector3 &origin, bool fullinit, unsigned int sz=0)
Definition: UT_HashGrid.C:34
exint concat(const UT_Array< T > &a)
Takes another T array and concatenate it onto my end.
Definition: UT_ArrayImpl.h:414
SYS_FORCE_INLINE T & x(void)
Definition: UT_Vector3.h:498
png_uint_32 i
Definition: png.h:2877
void reset(unsigned int sz=0)
Definition: UT_HashGrid.C:262
SYS_FORCE_INLINE T & z(void)
Definition: UT_Vector3.h:502
long long int64
Definition: SYS_Types.h:107
GLdouble n
Definition: glcorearb.h:2007
void findCloseElements(const UT_Vector3 &p, UT_Array< utPtr > &list) const
Definition: UT_HashGrid.C:143
int64 exint
Definition: SYS_Types.h:116
UT_IntArray myIndices
Definition: UT_HashGrid.h:40
int64 getMemoryUsage(bool inclusive) const
Definition: UT_HashGrid.C:56
#define ut_CELL_SHIFT
Definition: UT_HashGrid.C:27
void findAllCloseIndices(const UT_Vector3 &p, UT_IntArray &idxlist) const
Definition: UT_HashGrid.C:212
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:453
SYS_FORCE_INLINE T & y(void)
Definition: UT_Vector3.h:500
double fpreal
Definition: SYS_Types.h:270
GLuint index
Definition: glcorearb.h:785
exint append(void)
Definition: UT_Array.h:95
void setCapacityIfNeeded(exint mincapacity)
Definition: UT_Array.h:408
#define ut_CELL_MASK
Definition: UT_HashGrid.C:29
A class that defines a cubic grid cell.
Definition: UT_HashGrid.h:32
bool insert(const UT_Vector3 &p, utPtr t)
Definition: UT_HashGrid.C:73