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