 |
The SKIRT project
advanced radiative transfer for astrophysics
|
|
The SKIRT project
advanced radiative transfer for astrophysics
|
#include <BoxSearch.hpp>
Public Member Functions | |
| BoxSearch () | |
| double | avgEntitiesPerBlock () const |
| EntityGeneratorForPosition | entitiesFor (Vec bfr) const |
| EntityGeneratorForRay | entitiesFor (Vec bfr, Vec bfk) const |
| const Box & | extent () const |
| void | loadEntities (int numEntities, std::function< Box(int m)> bounds, std::function< bool(int m, const Box &box)> intersects) |
| int | maxEntitiesPerBlock () const |
| int | minEntitiesPerBlock () const |
| int | numBlocks () const |
Private Types | |
| using | EntityGeneratorForPosition = const vector< int > & |
| using | EntityGeneratorForRay = std::unordered_set< int > |
Private Member Functions | |
| int | blockIndex (int i, int j, int k) const |
| int | blockIndex (Vec bfr) const |
Private Attributes | |
| double | _avgEntitiesPerBlock |
| vector< int > | _empty |
| Box | _extent |
| vector< vector< int > > | _listv |
| int | _maxEntitiesPerBlock |
| int | _minEntitiesPerBlock |
| int | _numBlocks |
| Array | _xgrid |
| Array | _ygrid |
| Array | _zgrid |
BoxSearch is a utility class for organizing spatial objects in a data structure that allows efficient retrieval of all objects that overlap a given point or ray. The class actually works with the bounding boxes of the objects being held, and leaves more detailed tests for containment or intersection to the client code.
The spatial objects held by a BoxSearch instance are called entities. They are identified by a unique index \(m\) ranging from 0 to \(M-1\), where \(M\) is the number of managed entities. All entities are handed to the BoxSearch instance in one go, so that they can be "bulk-loaded" into the search structure.
The current implementation proceeds as follows. First, a regular Cartesian grid is contructed that partitions 3D space into \(N_b^3\) blocks, where \(N_b\) depends on the number of entities. Each block is then assigned a list of indices for all entities that possibly intersect with the block. In an attempt to balance the list lengths, the block separation points in each coordinate direction are chosen so that the entity bounding box centers are approximately evently distributed over the blocks in that direction. Locating the block containing a given query position then boils down to three binary searches (one in each direction).
|
private |
This typedef defines the generator return type of the entitiesFor function for a position. It represents an iterable sequence of integers. We use a private typedef to hide the actual type, which in the current implementation is simply a reference to a standard vector.
|
private |
This typedef defines the generator return type of the entitiesFor function for a ray. It represents an iterable sequence of integers. We use a private typedef to hide the actual type, which in the current implementation is simply a copy of a standard unordered set.
| BoxSearch::BoxSearch | ( | ) |
The constructor creates a trivial BoxSearch instance holding no entities. Any queries will come up empty.
| double BoxSearch::avgEntitiesPerBlock | ( | ) | const |
This function returns the average number of entity references in a search block.
|
private |
This function returns the linear index in the block list vector for the block with indices (i,j,k) in the three spatial directions.
|
private |
This function returns the linear index in the block list vector for the block containing the given position.
| EntityGeneratorForPosition BoxSearch::entitiesFor | ( | Vec | bfr | ) | const |
This function returns an iterable sequence of indices \(m\) of all entities that may overlap the specified position, sorted in increasing order. The sequence may be empty.
The function guarantees that the sequence includes all entities whose bounding box overlaps the position. On the other hand, the sequence may contain entities whose bounding box does not overlap the position.
| EntityGeneratorForRay BoxSearch::entitiesFor | ( | Vec | bfr, |
| Vec | bfk | ||
| ) | const |
This function returns an iterable sequence of indices \(m\) of all entities that may overlap the specified ray (starting point and direction), in arbitrary order. The sequence may be empty.
The function guarantees that the sequence includes all entities whose bounding box overlaps the ray. On the other hand, the sequence may contain entities whose bounding box does not overlap the ray.
| const Box & BoxSearch::extent | ( | ) | const |
This function returns the extent of the search domain, i.e. the union of all entity bounding boxes.
| void BoxSearch::loadEntities | ( | int | numEntities, |
| std::function< Box(int m)> | bounds, | ||
| std::function< bool(int m, const Box &box)> | intersects | ||
| ) |
This function loads the specified number of entities \(M\) into the search structure, using the information returned by the provided callback functions. Any entities held prevously are removed and replaced by the new ones.
The bounds callback function returns the bounding box of the entity with the given index. The intersects callback function returns true if the entity with the given index possibly intersects the specified box, and false otherwise. A relaxed intersection test such as testing against the bounding box is allowed but a stricter intersection test will result in more efficient retrieval queries.
The callback functions are invoked one or more times for indices \(m\) ranging from 0 to \(M-1\), in arbitrary order. For given values of their argument(s), the callback functions must always return the same value.
| int BoxSearch::maxEntitiesPerBlock | ( | ) | const |
This function returns the largest number of entity references in a search block.
| int BoxSearch::minEntitiesPerBlock | ( | ) | const |
This function returns the smallest number of entity references in a search block.
| int BoxSearch::numBlocks | ( | ) | const |
This function returns the number of blocks in the search structure for each spatial dimension, or zero if no entities have been loaded.