HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_HashGrid.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: 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 
16 #ifndef __UT_HashGrid_h__
17 #define __UT_HashGrid_h__
18 
19 #include "UT_Map.h"
20 #include "UT_IntArray.h"
21 #include "UT_Array.h"
22 #include "UT_Vector3.h"
23 #include "UT_Vector3Array.h"
24 
25 /// A class that defines a cubic grid cell.
26 template <typename utPtr>
28  public:
30  {
31  }
32 
34 
36 };
37 
38 template <typename utPtr>
39 class UT_HashGrid {
40 
41 public:
42  /// Constructor takes a floating point value to indicate
43  /// the size of each grid cell to be stored by the, and
44  /// optionally takes a size parameter to determine the
45  /// initial size of the grid cell array. The constructor
46  /// also requires an origin about which the point set will
47  /// be roughly centred. fullinit determines whether or
48  /// not a point is associated with all surrounding grid
49  /// cells immediately upon addition, or if a point should
50  /// only ever be associated with one grid cell. In the
51  /// second case, each query requires that 27 grid cells be
52  /// checked instead of 1. This is essentially a trade off
53  /// between the cost of building the data structure and the
54  /// cost of making point queries. If the number of point
55  /// queries is likely to outnumber the number of points
56  /// added to the tree, then fullinit = true is recommended.
57  UT_HashGrid(fpreal cellsize, const UT_Vector3 &origin,
58  bool fullinit, unsigned int sz = 0);
59 
60  /// Trivial destructor
62 
63  int64 getMemoryUsage(bool inclusive) const;
64 
65  int getNumCells() const { return myCellArray.entries(); }
66 
67  /// Inserts a new element in to the set using the given
68  /// point to determine that element's location in the grid.
69  /// Returns true if successful.
70  bool insert(const UT_Vector3 &p, utPtr t);
71 
72  /// Inserts blank elements so our index list will match an external
73  /// structure with holes.
74  void insertBlanks(int nblanks);
75 
76  /// Finds all elements close to the given point and returns
77  /// a list of those elements.
78  inline void findCloseElements(const UT_Vector3 &p,
79  UT_Array<utPtr> &list) const;
80 
81  /// Finds all close indices, does no distance lookups! This is
82  /// every index within +/- one cell
83  inline void findAllCloseIndices(const UT_Vector3 &p,
84  UT_IntArray &idxlist) const;
85 
86  /// Resets the structure by clearing all elements from it
87  /// and optionally reinitializing the cell array to the
88  /// given size.
89  void reset(unsigned int sz = 0);
90 
91  /// Additional reset function that also changes the cell
92  /// width and origin for the structure.
93  void reset(fpreal cellsize,
94  const UT_Vector3 &origin,
95  bool fullinit,
96  unsigned int sz = 0);
97 
98  /// These lookup our element and positions using the hash grid's index
99  /// which corresponds to the order in which you called insert.
100  inline UT_Vector3 getPos(int idx) const { return myPositions(idx); }
101  inline utPtr getElement(int idx) const { return myElements(idx); }
102 
103  inline fpreal getCellWidth() const { return myCellWidth; }
104 
105 private:
106  typedef UT_Array<UT_HashGridCell<utPtr> > ut_CellArray;
107 
108  /// Helper functions used to get a grid cell from the
109  /// hash table, or generate a new one if necessary.
110  UT_HashGridCell<utPtr> *getCell(const UT_Vector3 &p,
111  bool create);
112  UT_HashGridCell<utPtr> *getCell(int i, int j, int k,
113  bool create);
114  const UT_HashGridCell<utPtr>*getCell(const UT_Vector3 &p) const;
115  const UT_HashGridCell<utPtr>*getCell(int i, int j, int k) const;
116 
117 private:
118  UT_Vector3 myOrigin;
119  fpreal myCellWidth;
120  fpreal myCellWidth2;
121  fpreal myInvCellWidth;
122 
123  int myMaxElements;
124 
125  UT_Map<exint,exint> myGridSet;
126  ut_CellArray myCellArray;
127 
128  bool myFullInit;
129 
130  UT_Vector3Array myPositions;
131  UT_ValArray<utPtr> myElements;
132 
133 };
134 
135 #include "UT_HashGrid.C"
136 
137 #endif
int getNumCells() const
Definition: UT_HashGrid.h:65
void insertBlanks(int nblanks)
Definition: UT_HashGrid.C:131
~UT_HashGrid()
Trivial destructor.
Definition: UT_HashGrid.h:61
UT_HashGrid(fpreal cellsize, const UT_Vector3 &origin, bool fullinit, unsigned int sz=0)
Definition: UT_HashGrid.C:34
UT_Vector3 getPos(int idx) const
Definition: UT_HashGrid.h:100
void reset(unsigned int sz=0)
Definition: UT_HashGrid.C:262
void findCloseElements(const UT_Vector3 &p, UT_Array< utPtr > &list) const
Definition: UT_HashGrid.C:143
utPtr getElement(int idx) const
Definition: UT_HashGrid.h:101
UT_IntArray myIndices
Definition: UT_HashGrid.h:35
int64 getMemoryUsage(bool inclusive) const
Definition: UT_HashGrid.C:56
void findAllCloseIndices(const UT_Vector3 &p, UT_IntArray &idxlist) const
Definition: UT_HashGrid.C:212
long long int64
Definition: SYS_Types.h:116
GLdouble t
Definition: glad.h:2397
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:648
GLint j
Definition: glad.h:2733
fpreal64 fpreal
Definition: SYS_Types.h:277
A class that defines a cubic grid cell.
Definition: UT_HashGrid.h:27
fpreal getCellWidth() const
Definition: UT_HashGrid.h:103
bool insert(const UT_Vector3 &p, utPtr t)
Definition: UT_HashGrid.C:73