template<typename T>
class DtSpatialSubdivision< T >
The DtSpatialSubdivision class represents a uniform spatial container. The container is divided up into a lattice of cells, with resolution specified at creation. Its purpose is to efficiently store and search objects spatially, with each cell being a container for the objects in it. The DtSpatialSubdivision is a rectangular area (or rectangular solid if 3D) containing some number of these cells.
-------------------
|\ \ \
| \________\________\
| |\ \ \
| | \ \ \
| | \--------\--------\
|\| | | |
| \ | | |
| |\ | | |
| | \ | | |
| | \--------\--------\
\| | | |
\ | | |
\ | | |
\ | | |
\--------\--------\
A 2 x 2 x 2 Spatial Subdivision
DtSpatialSubdivision is a templated container, similar to the std::list or std::vector classes. As such, it can hold any specified item. The intended use is to store elements that have spatial properties - elements that have an actual volume, position, orientation, and so on.
This class provides a minimal interface to make it easy for users to extend the types of elements contained within it by writing examination and modification classes outside of this one. Thus no mechanism for examination or modification, outside of points, is provided. This greatly facilitates extending existing capabilities and adding new ones. As a result, the spatial subdivision functionality is spread out across an entire family of classes.
This class is not threadsafe.
Class Invariant
A fully constructed spatial subdivision must always respect the following:
- A positive cell size in any dimension where the number of cells is greater than one.
- The number of cells in each dimension must be greater than or equal to 1 at all times. The smallest number of cells in any dimension is 1. If a subdivision is created or resized with an extent that is either uninitialized or has an empty dimension, the number of cells in that dimension is still one, and the cell size will be zero.
- The same number of cells in the container as equals the dimensions multiplied together.
Creating Spatial Subdivision Objects
The DtSpatialSubdivision is the container class. When instantiating this class, you must specify the type of object contained using the template parameter. To create a spatial subdivision, do the following:
- Note
- To change the type of contained element, change the template parameter - DtGdbnode*.
Spatial Subdivision Intersectors
The spatial subdivision intersector classes know how to intersect a primitive and a spatial subdivision, and apply a specified operation to the results of the intersection through a functor interface.
The functor interface allows for tremendous flexibility in the type and complexity of operations that are performed on the spatial subdivision. By changing the functor supplied to the intersect() member function, different operations can be performed, such as inserting elements into the spatial subdivision, gathering elements of specific characteristics from the spatial subdivision, or simply accumulating all cells in the spatial subdivision that are part of the intersection. The following are the most primitive examples of intersectors, though others are available:
- DtSsChordIntersector - This class intersects a specified chord and spatial subdivision, applying a functor to the intersection results.
- DtSsExtentIntersector - This class intersects a specified extent and spatial subdivision, applying a functor to the intersection results. Note that this class also provides a function for determining the min/max intersected cell indices, which can sometimes be more useful than the actual full intersection call.
Creating new intersector classes is probably one of the most useful extensions to the spatial subdivision classes. For instance, an intersector class for spheres or cylinders or other implicit surfaces would enable efficient selection of all elements within a specified radius of a location (or line).
To create a new intersector class, there is no need to derive from any parent class. The intersector class merely needs to know how to intersect the specified primitive with the spatial subdivision and to allow user-specified processing of the results.
So, to create a sphere intersector you could test every cell for inclusion with the specified sphere, using the properties of the spatial subdivision (cell deltas, location, and so on) to calculate the cells to test, and to pass these cells to the user-specified functor. This would be useful when selecting all cells within a blast radius. To take it a step further, a new functor could also be derived that would know how to intersect all the elements of a cell, such as DtGdbNodes, with the specified primitive. Used together, the new sphere intersector and sphere intersection functor could be used to select all polygons within the blast radius of a detonation.
Spatial Subdivision Functors
The spatial subdivision functors are simple classes that are used by the spatial subdivision intersectors to perform different operations on the results of intersection tests. These operations include insertion of elements into spatial subdivision cells (DtSsInsertionFunctor), accumulation of spatial subdivision cells for later analysis (DtSsAccumulationFunctor), among others.
While simple, these functors differ from standard functors in the following important ways:
- The functors are passed by reference, not by value. They do not have to maintain state, but they are expected to.
- The functors return a Boolean to indicate whether or not they are done processing inputs, and not whether or not an error occurred. This is to allow for efficient processing of intersection results. For instance if a functor is looking for any intersection of a chord and a polygon, it can stop processing after the first intersection is found, simply by returning true. To determine if an error occurred, the functor *must *either maintain internal error state or use exceptions.
The following are examples of functors:
- DtSsFunctor - This is the base class for all spatial subdivision functors. It does not perform any operation.
- DtSsAccumulationFunctor - DtSsAccumulationFunctor contains a container, which it uses to store elements passed in to its function operator (please see the function definition for more details). Thus it can be used to accumulate the set of cells comprising the intersection of a primitive with the spatial subdivision.
- DtSsInsertionFunctor - DtSsInsertionFunctor is used to insert one object into another, for instance in inserting elements into the spatial subdivision cells.
To create a new type of spatial subdivision functor, derive your new functor from the DtSsFunctor class. To use this functor, pass it as a parameter to an existing spatial subdivision intersector or other utility class, or to a newly created spatial subdivision utility class.
- Note
- Be sure that the new functor adheres to the interface of the DtSsFunctor classes.
Spatial Subdivision Inserters
The spatial subdivision inserter classes are utility classes that combine the appropriate intersector with an insertion functor, in order to facilitate inserting of elements of the appropriate type into a spatial subdivision.
To insert an element into a spatial subdivision container, you use an inserter class. The following example show how the terrain database now creates the spatial subdivision for the terrain polygons. The terrain() function returns the root terrain polygon node (DtGdbNode*).
if (!terrainInserter.
insert(terrain(), *myTerrainSpatialSubdivision))
{
}
