![]() |
TrinityCore
|
A sparse 3D grid of point-based data. More...
#include <PointHashGrid.h>
Classes | |
class | BoxIterator |
class | CellIterator |
class | Entry |
class | Iterator |
class | SphereIterator |
Protected Member Functions | |
void | initOffsetArray () |
Private Types | |
typedef SmallArray< Entry, expectedCellSize > | Cell |
typedef Table< Point3int32, Cell > | CellTable |
Private Member Functions | |
PointHashGrid (const ThisType &) | |
PointHashGrid & | operator= (const ThisType &) |
bool | find (const Value &v, Point3int32 &foundCellCoord, Cell *&foundCell, int &index) |
Private Attributes | |
Vector3int32 | m_offsetArray [3 *3 *3] |
int | m_epoch |
float | m_cellWidth |
float | m_invCellWidth |
AABox | m_bounds |
int | m_size |
CellTable | m_data |
MemoryManager::Ref | m_memoryManager |
A sparse 3D grid of point-based data.
The space cost for n elements is O(n). For data with approximately uniform density (with respect to the radius hint), the time cost of searching for neighbors is O(1).
You can move members of the data set by first removing them and then adding them with a new location.
Template argument PosFunc must provide a static getPosition
method and EqualsFunc must provide a static equals
method, as described below. You can either write classes that support these yourself, provide template specializations of G3D::PositionTrait and G3D::EqualsTrait, or rely on the default template specializations, which already exist for common G3D classes like G3D::Point3. For example:
If the Value class defines operator==
, then the Equalsfunc is optional, so you can just write:
The simplest way to define these is often to make them both methods of the parameter class itself, e.g.,
|
private |
One cell of the grid.
|
private |
|
private |
Intentionally unimplemented: prevent copy construction.
|
inline |
radiusHint | the radius that will typically be used with beginBallIntersection and beginBoxIntersection. If two Values are equal, their positions must be within this radius as well. You can later change this value with clearAndSetRadiusHint(). |
|
inline |
If radiusHint is negative, it is automatically chosen to put about 5 values in each grid cell (which means about 27 * 5 values for each beginIntersection call).
|
inline |
Iterate through all members. It is an error to mutate the HashGrid while iterating through it. Each member can be accessed by "dereferencing" the iterator:
for (Grid::Iterator i = grid.begin(); i != grid.end(), ++i) { const Value& = *i; ... }
|
inline |
Finds all values whose positions are within sphere. It is an error to mutate the PointHashGrid while iterating through it.
|
inline |
Finds all values whose positions are within box. It is an error to mutate the PointHashGrid while iterating through it.
exact | If false, the iterator will execute more quickly but will likely return some values that lie outside the box. Set exact = false if you are going to test the results against the yourself box anyway. |
|
inline |
|
inline |
|
inline |
|
inline |
Removes all data.
shrink | If true, underlying structures are deallocated as they are freed. |
|
inline |
|
inline |
|
inline |
Returns a conservative bounding box around the contents. This is conservative because it is not updated when elements are removed.
|
inline |
Returns true if there is a value that is exactly equal to v. This will check all neighboring cells to avoid roundoff error at cell boundaries.
|
inline |
|
inline |
|
inline |
|
inline |
Calls delete on all of the values, which are assumed to be pointers. This is a helper to avoid requiring you to iterate through the data structure, removing and deleting each one. Clears the PointHashGrid at the end.
Using objects (instead of pointers) or reference counted pointers is recommended over using pointers and this deleteAll method.
|
inline |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
Locate the cell and index within that cell containing v. Called by remove() and contains().
|
inline |
Compute the grid cell index of a real position. This is used extensively internally by PointHashGrid. It is useful to calling code to determine when an object is about to move between cells.
|
inline |
Appends results
|
inlineprotected |
Initializes m_offsetArray.
|
inline |
Insert v at position p given by getPosition(v, p)
. Multiple elements that are equal may be inserted; all copies will be in the data structure.
|
inline |
Inserts all elements of the array.
|
private |
Intentionally unimplemented: prevent assignment.
|
inline |
|
inline |
If there are multiple copies of an element, you must delete them multiple times.
shrinkIfNecessary | If true, deallocate underlying data structures as they are emptied. False increases performace at the cost of memory overhead for dynamic structures. |
|
inline |
Returns the number of elements.
|
private |
Conservative bounds; the actual data may be smaller.
|
private |
Extent of a cell along one dimension.
|
private |
Non-empty cells indexed by grid position. Actual 3D position is position * m_cellWidth
|
private |
Incremented every time the data structure is mutated. Used by the iterators to determine if the data structure has changed since iteration began.
|
private |
1.0 / cell width
|
private |
|
private |
The cube of +/-1 along each dimension. Initialized by initOffsetArray.
|
private |
Number of elements.