Library of Assembled Shared Sources
|
an 4-ary AABB tree More...
#include <qbvh_tree.h>
Public Member Functions | |
void | reset () |
Reset the tree to an empty one. | |
void | reset (TObjectIterator first, TObjectIterator last) |
Reset the tree to a new one with objects in the range [first, last) | |
const TAabb | aabb () const |
Return the total bounding box of all objecs in the tree. | |
bool | contains (const TPoint &point, const TInfo *info=0) const |
Check whether there's any object in the tree that contains point. | |
template<typename OutputIterator> | |
OutputIterator | find (const TPoint &point, OutputIterator result, const TInfo *info=0) const |
Find all objects that contain point. | |
template<typename OutputIterator> | |
OutputIterator | find (const TAabb &box, OutputIterator result, const TInfo *info=0) const |
Find all objects that intersect with box. | |
template<typename OutputIterator> | |
OutputIterator | find (const TRay &ray, TParam tMin, TParam tMax, OutputIterator result, const TInfo *info=0) const |
Find all objects that have an intersection with ray in the interval [tMin, tMax]. | |
TObjectIterator | intersect (const TRay &ray, TReference t, TParam tMin=0, const TInfo *info=0) const |
Find the first object that is intersected by ray, so that t >= tMin and t is minimized. | |
bool | intersects (const TRay &ray, TParam tMin=0, TParam tMax=std::numeric_limits< TValue >::infinity(), const TInfo *info=0) const |
Check whether there's any object in the tree that is intersected by ray in the interval [tMin, tMax]. | |
const Neighbour | nearestNeighbour (const TPoint &point, const TInfo *info=0) const |
Find the object that is closest to point. | |
template<typename RandomIterator> | |
RandomIterator | rangeSearch (const TPoint ¢er, TParam maxRadius, size_t maxCount, RandomIterator first, const TInfo *info=0) const |
Find all objects that are within maxRadius from center, up to maxCount. | |
bool | isEmpty () const |
Returns true if there are no objects in the tree. | |
const TObjectIterator | end () const |
Returns an iterator not pointing to any object, used to indicate when no object is found. | |
void | swap (TSelf &other) |
Swap the contents of this tree with another. | |
an 4-ary AABB tree
This BVH is much like an AABB tree, but with a branching factor of 4. It is constructed in similar fashion, by recursively splitting the objects into 2 sets along an axis, but then the sets are split again, totalling 4 sets per node.
This tree, when used with SAHSplitHeuristics, should be the fastest for ray intersection tests. For other operations, it's generally faster than AabbTree if AVX is available. But as always, YMMV.
The QbvhTree does NOT own the objects. You must keep them yourself!
Definition at line 141 of file qbvh_tree.h.
void lass::spat::QbvhTree< O, OT, SH >::reset | ( | ) |
Reset the tree to an empty one.
Is equivalent to:
Definition at line 418 of file qbvh_tree.inl.
References swap().
void lass::spat::QbvhTree< O, OT, SH >::reset | ( | TObjectIterator | first, |
TObjectIterator | last ) |
Reset the tree to a new one with objects in the range [first, last)
Is equivalent to:
Definition at line 434 of file qbvh_tree.inl.
References swap().
RandomIterator lass::spat::QbvhTree< O, OT, SH >::rangeSearch | ( | const TPoint & | center, |
TParam | maxRadius, | ||
size_t | maxCount, | ||
RandomIterator | first, | ||
const TInfo * | info = 0 ) const |
Find all objects that are within maxRadius from center, up to maxCount.
If more than maxCount objects within maxRadius are found, then the closest maxCount objects are returned.
center | The center of the search sphere. |
maxRadius | The maximum radius of the search sphere. |
maxCount | The maximum number of objects to find. |
first | An output iterator to a container of Neighbour objects that will be filled with the found objects. |
info | Optional information to pass to the object traits. |
The range [first, last) will contain the found objects and form a heap, so that first points to the farthest object from center: its squared distance to center is the largest in the range, and gives you the effective maximum radius of the search sphere.
Definition at line 595 of file qbvh_tree.inl.
References isEmpty().
const QbvhTree< O, OT, SH >::TObjectIterator lass::spat::QbvhTree< O, OT, SH >::end | ( | ) | const |
Returns an iterator not pointing to any object, used to indicate when no object is found.
This iterator can be used as the return value of the find functions when no object is found. You can compare those return values to the end() function to check if an object was found.
Definition at line 626 of file qbvh_tree.inl.
void lass::spat::QbvhTree< O, OT, SH >::swap | ( | TSelf & | other | ) |
Swap the contents of this tree with another.
Is equivalent to:
Definition at line 643 of file qbvh_tree.inl.