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