Library of Assembled Shared Sources
lass::spat::Aabb8Tree< ObjectType, ObjectTraits, SplitHeuristics > Class Template Reference

an 4-ary AABB tree More...

#include <aabb8_tree.h>

Inheritance diagram for lass::spat::Aabb8Tree< ObjectType, ObjectTraits, SplitHeuristics >:

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 &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.
 
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.
 

Detailed Description

template<typename ObjectType, typename ObjectTraits = DefaultObjectTraits<ObjectType>, typename SplitHeuristics = DefaultSplitHeuristics>
class lass::spat::Aabb8Tree< ObjectType, ObjectTraits, SplitHeuristics >

an 4-ary AABB tree

Author
Bram de Greve [BdG]

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 Aabb8Tree does NOT own the objects. You must keep them yourself!

Note
H. Dammertz, J. Hanika, and A. Keller. Shallow bounding volume hierarchies for fast SIMD ray tracing of incoherent rays. In Proceedings of the Nineteenth Eurographics conference on Rendering 2008 (EGSR '08). Eurographics Association, Goslar, DEU, 1225–1233. https://doi.org/10.1111/j.1467-8659.2008.01261.x

Definition at line 137 of file aabb8_tree.h.

Member Function Documentation

◆ reset() [1/2]

template<typename O, typename OT, typename SH>
void lass::spat::Aabb8Tree< O, OT, SH >::reset ( )

Reset the tree to an empty one.

Is equivalent to:

*this = TSelf();

Definition at line 448 of file aabb8_tree.inl.

References swap().

◆ reset() [2/2]

template<typename O, typename OT, typename SH>
void lass::spat::Aabb8Tree< 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:

*this = TSelf(first, last);

Definition at line 464 of file aabb8_tree.inl.

References swap().

◆ rangeSearch()

template<class O, class OT, typename SH>
template<typename RandomIterator>
RandomIterator lass::spat::Aabb8Tree< 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.

Parameters
centerThe center of the search sphere.
maxRadiusThe maximum radius of the search sphere.
maxCountThe maximum number of objects to find.
firstAn output iterator to a container of Neighbour objects that will be filled with the found objects.
infoOptional information to pass to the object traits.
Returns
The output iterator last, pointing to the first element beyond the last found object.

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.

Note
The output iterator must be able to handle at least maxCount objects.

Definition at line 625 of file aabb8_tree.inl.

References isEmpty().

◆ end()

template<typename O, typename OT, typename SH>
const Aabb8Tree< O, OT, SH >::TObjectIterator lass::spat::Aabb8Tree< 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 656 of file aabb8_tree.inl.

◆ swap()

template<typename O, typename OT, typename SH>
void lass::spat::Aabb8Tree< O, OT, SH >::swap ( TSelf & other)

Swap the contents of this tree with another.

Is equivalent to:

TSelf tmp = std::move(other);
other = std::move(*this);
*this = std::move(tmp);

Definition at line 673 of file aabb8_tree.inl.

Referenced by reset(), and reset().


The documentation for this class was generated from the following files: