CGAL 5.0 - 3D Fast Intersection and Distance Computation (AABB Tree)
|
#include <CGAL/AABB_tree.h>
Class AABB_tree is a static data structure for efficient intersection and distance computations in 3D.
It builds a hierarchy of axis-aligned bounding boxes (an AABB tree) from a set of 3D geometric objects, and can receive intersection and distance queries, provided that the corresponding predicates are implemented in the traits class AABBTraits. An instance of the class AABBTraits
is internally stored.
AABBTraits
AABBPrimitive
Public Member Functions | |
AABBTraits::Primitive::Datum_reference | datum (Primitive &p) const |
Returns the datum (geometric object) represented p . | |
Types | |
typedef AABBTraits::FT | FT |
Number type returned by the distance queries. | |
typedef AABBTraits::Point_3 | Point |
Type of 3D point. | |
typedef AABBTraits::Primitive | Primitive |
Type of input primitive. | |
typedef Primitive::Id | Primitive_id |
Identifier for a primitive in the tree. | |
typedef Primitives::size_type | size_type |
Unsigned integral size type. | |
typedef AABBTraits::Bounding_box | Bounding_box |
Type of bounding box. | |
typedef AABBTraits::Point_and_primitive_id | Point_and_primitive_id |
3D Point and Primitive Id type | |
typedef AABBTraits::Object_and_primitive_id | Object_and_primitive_id |
template<typename Query > | |
using | Intersection_and_primitive_id = AABBTraits::Intersection_and_primitive_id< Query > |
An alias to AABBTraits::Intersection_and_primitive_id<Query> | |
Creation | |
AABB_tree (const AABBTraits &traits=AABBTraits()) | |
Constructs an empty tree, and initializes the internally stored traits class using traits . More... | |
template<typename InputIterator , typename ... T> | |
AABB_tree (InputIterator first, InputIterator beyond, T &&...) | |
Builds the datastructure from a sequence of primitives. More... | |
template<typename ... T> | |
void | build (T &&...) |
After one or more calls to insert() the internal data structure of the tree must be reconstructed. More... | |
Operations | |
template<typename ConstPrimitiveIterator , typename ... T> | |
void | rebuild (ConstPrimitiveIterator first, ConstPrimitiveIterator beyond, T &&...) |
Equivalent to calling clear() and then insert(first,last,t...) . | |
template<typename InputIterator , typename ... T> | |
void | insert (InputIterator first, InputIterator beyond, T &&...) |
Add a sequence of primitives to the set of primitives of the AABB tree. More... | |
void | insert (const Primitive &p) |
Adds a primitive to the set of primitives of the tree. | |
~AABB_tree () | |
Clears and destroys the tree. | |
const AABBTraits & | traits () const |
Returns a const reference to the internally stored traits class. | |
void | clear () |
Clears the tree. | |
const Bounding_box | bbox () const |
Returns the axis-aligned bounding box of the whole tree. More... | |
size_type | size () const |
Returns the number of primitives in the tree. | |
bool | empty () const |
Returns true , iff the tree contains no primitive. | |
Intersection Tests | |
template<typename Query > | |
bool | do_intersect (const Query &query) const |
Returns true , iff the query intersects at least one of the input primitives. More... | |
template<typename Query > | |
size_type | number_of_intersected_primitives (const Query &query) const |
Returns the number of primitives intersected by the query. More... | |
template<typename Query , typename OutputIterator > | |
OutputIterator | all_intersected_primitives (const Query &query, OutputIterator out) const |
Outputs to the iterator the list of all intersected primitives ids. More... | |
template<typename Query > | |
boost::optional< Primitive_id > | any_intersected_primitive (const Query &query) const |
Returns the intersected primitive id that is encountered first. More... | |
Intersections | |
template<typename Query , typename OutputIterator > | |
OutputIterator | all_intersections (const Query &query, OutputIterator out) const |
Outputs the list of all intersections, as objects of Intersection_and_primitive_id<Query>::Type , between the query and the input data to the iterator. More... | |
template<typename Query > | |
boost::optional< typename Intersection_and_primitive_id< Query >::Type > | any_intersection (const Query &query) const |
Returns the intersection that is encountered first. More... | |
template<typename Ray , typename SkipFunctor > | |
boost::optional< typename Intersection_and_primitive_id< Ray >::Type > | first_intersection (const Ray &query, const SkipFunctor &skip) const |
Returns the intersection and primitive id closest to the source point of the ray query. More... | |
template<typename Ray , typename SkipFunctor > | |
boost::optional< Primitive_id > | first_intersected_primitive (const Ray &query, const SkipFunctor &skip) const |
Returns the primitive id closest to the source point of the ray query. More... | |
Distance Queries | |
FT | squared_distance (const Point &query) const |
Returns the minimum squared distance between the query point and all input primitives. More... | |
Point | closest_point (const Point &query) const |
Returns the point in the union of all input primitives which is closest to the query. More... | |
Point_and_primitive_id | closest_point_and_primitive (const Point &query) const |
Returns a Point_and_primitive_id which realizes the smallest distance between the query point and all input primitives. More... | |
Accelerating the Distance Queries | |
In the following paragraphs, we discuss details of the implementation of the distance queries. We explain the internal use of hints, how the user can pass his own hints to the tree, and how the user can influence the construction of the secondary data structure used for accelerating distance queries. Internally, the distance queries algorithms are initialized with some hint, which has the same type as the return type of the query, and this value is refined along a traversal of the tree, until it is optimal, that is to say until it realizes the shortest distance to the primitives. In particular, the exact specification of these internal algorithms is that they minimize the distance to the object composed of the union of the primitives and the hint. It follows that
This second observation is reasonable, in the sense that providing a hint to the algorithm means claiming that this hint belongs to the union of the primitives. These considerations about the hints being exactly on the primitives or not are important: in the case where the set of primitives is a triangle soup, and if some of the primitives are large, one may want to provide a much better hint than a vertex of the triangle soup could be. It could be, for example, the barycenter of one of the triangles. But, except with the use of an exact constructions kernel, one cannot easily construct points other than the vertices, that lie exactly on a triangle soup. Hence, providing a good hint sometimes means not being able to provide it exactly on the primitives. In rare occasions, this hint can be returned as the closest point. In order to accelerate distance queries significantly, the AABB tree builds an internal KD-tree containing a set of potential hints, when the method | |
bool | accelerate_distance_queries () const |
Constructs internal search tree from a point set taken on the internal primitives returns true iff successful memory allocation. | |
template<typename ConstPointIterator > | |
bool | accelerate_distance_queries (ConstPointIterator first, ConstPointIterator beyond) const |
Constructs an internal KD-tree containing the specified point set, to be used as the set of potential hints for accelerating the distance queries. More... | |
FT | squared_distance (const Point &query, const Point &hint) const |
Returns the minimum squared distance between the query point and all input primitives. More... | |
Point | closest_point (const Point &query, const Point &hint) const |
Returns the point in the union of all input primitives which is closest to the query. More... | |
Point_and_primitive_id | closest_point_and_primitive (const Point &query, const Point_and_primitive_id &hint) const |
Returns a Point_and_primitive_id which realizes the smallest distance between the query point and all input primitives. More... | |
typedef AABBTraits::Object_and_primitive_id CGAL::AABB_tree< AABBTraits >::Object_and_primitive_id |
CGAL::AABB_tree< AABBTraits >::AABB_tree | ( | const AABBTraits & | traits = AABBTraits() | ) |
Constructs an empty tree, and initializes the internally stored traits class using traits
.
CGAL::AABB_tree< AABBTraits >::AABB_tree | ( | InputIterator | first, |
InputIterator | beyond, | ||
T && | ... | ||
) |
Builds the datastructure from a sequence of primitives.
first | iterator over first primitive to insert |
beyond | past-the-end iterator |
It is equivalent to constructing an empty tree and calling insert(first,last,t...)
. The tree stays empty if the memory allocation is not successful.
bool CGAL::AABB_tree< AABBTraits >::accelerate_distance_queries | ( | ConstPointIterator | first, |
ConstPointIterator | beyond | ||
) | const |
Constructs an internal KD-tree containing the specified point set, to be used as the set of potential hints for accelerating the distance queries.
ConstPointIterator | is an iterator with value type Point_and_primitive_id . |
OutputIterator CGAL::AABB_tree< Tr >::all_intersected_primitives | ( | const Query & | query, |
OutputIterator | out | ||
) | const |
Outputs to the iterator the list of all intersected primitives ids.
This function does not compute the intersection points and is hence faster than the function all_intersections()
function below.
Query | must be a type for which do_intersect predicates are defined in the traits class AABBTraits . |
OutputIterator CGAL::AABB_tree< Tr >::all_intersections | ( | const Query & | query, |
OutputIterator | out | ||
) | const |
Outputs the list of all intersections, as objects of Intersection_and_primitive_id<Query>::Type
, between the query and the input data to the iterator.
do_intersect()
predicates and intersections must be defined for Query
in the AABBTraits
class.
boost::optional<Primitive_id> CGAL::AABB_tree< AABBTraits >::any_intersected_primitive | ( | const Query & | query | ) | const |
Returns the intersected primitive id that is encountered first.
in the tree traversal, iff the query intersects at least one of the input primitives. No particular order is guaranteed over the tree traversal, such that, e.g, the primitive returned is not necessarily the closest from the source point of a ray query.
Query | must be a type for which do_intersect predicates are defined in the traits class AABBTraits . |
boost::optional< typename Intersection_and_primitive_id<Query>::Type > CGAL::AABB_tree< AABBTraits >::any_intersection | ( | const Query & | query | ) | const |
Returns the intersection that is encountered first.
in the tree traversal. No particular order is guaranteed over the tree traversal, e.g, the primitive returned is not necessarily the closest from the source point of a ray query. Type Query
must be a type for which do_intersect
predicates and intersections are defined in the traits class AABBTraits.
const Bounding_box CGAL::AABB_tree< AABBTraits >::bbox | ( | ) | const |
Returns the axis-aligned bounding box of the whole tree.
!empty()
void CGAL::AABB_tree< AABBTraits >::build | ( | T && | ... | ) |
After one or more calls to insert()
the internal data structure of the tree must be reconstructed.
This procedure has a complexity of \(O(n log(n))\), where \(n\) is the number of primitives of the tree. This procedure is called implicitly at the first call to a query member function. You can call build()
explicitly to ensure that the next call to query functions will not trigger the reconstruction of the data structure. A call to AABBTraits::set_shared_data(t...)
is made using the internally stored traits.
AABB_tree< Tr >::Point CGAL::AABB_tree< Tr >::closest_point | ( | const Point & | query | ) | const |
Returns the point in the union of all input primitives which is closest to the query.
In case there are several closest points, one arbitrarily chosen closest point is returned. Method accelerate_distance_queries()
should be called before the first distance query, so that an internal secondary search structure is build, for improving performance.
!empty()
AABB_tree< Tr >::Point CGAL::AABB_tree< Tr >::closest_point | ( | const Point & | query, |
const Point & | hint | ||
) | const |
Returns the point in the union of all input primitives which is closest to the query.
In case there are several closest points, one arbitrarily chosen closest point is returned. The internal KD-tree is not used.
!empty()
AABB_tree< Tr >::Point_and_primitive_id CGAL::AABB_tree< Tr >::closest_point_and_primitive | ( | const Point & | query | ) | const |
Returns a Point_and_primitive_id
which realizes the smallest distance between the query point and all input primitives.
Method accelerate_distance_queries()
should be called before the first distance query, so that an internal secondary search structure is build, for improving performance.
!empty()
AABB_tree< Tr >::Point_and_primitive_id CGAL::AABB_tree< Tr >::closest_point_and_primitive | ( | const Point & | query, |
const Point_and_primitive_id & | hint | ||
) | const |
Returns a Point_and_primitive_id
which realizes the smallest distance between the query point and all input primitives.
The internal KD-tree is not used.
!empty()
bool CGAL::AABB_tree< Tr >::do_intersect | ( | const Query & | query | ) | const |
Returns true
, iff the query intersects at least one of the input primitives.
Query | must be a type for which do_intersect predicates are defined in the traits class AABBTraits . |
boost::optional<Primitive_id> CGAL::AABB_tree< AABBTraits >::first_intersected_primitive | ( | const Ray & | query, |
const SkipFunctor & | skip | ||
) | const |
Returns the primitive id closest to the source point of the ray query.
Ray | must be the same as AABBTraits::Ray_3 and do_intersect predicates and intersections for it must be defined. |
Skip | a functor with an operator bool operator()(const Primitive_id& id) const that returns true in order to skip the primitive. Defaults to a functor that always returns false . |
AABBTraits
must be a model of AABBRayIntersectionTraits
to call this member function.
boost::optional< typename Intersection_and_primitive_id<Ray>::Type > CGAL::AABB_tree< AABBTraits >::first_intersection | ( | const Ray & | query, |
const SkipFunctor & | skip | ||
) | const |
Returns the intersection and primitive id closest to the source point of the ray query.
Ray | must be the same as AABBTraits::Ray_3 and do_intersect predicates and intersections for it must be defined. |
Skip | a functor with an operator bool operator()(const Primitive_id& id) const that returns true in order to skip the primitive. Defaults to a functor that always returns false . |
skip
might be given some primitives that are not intersected by query
because the intersection test is done after the skip test. Also note that the order the primitives are given to skip
is not necessarily the intersection order with query
.AABBTraits
must be a model of AABBRayIntersectionTraits
to call this member function.
void CGAL::AABB_tree< AABBTraits >::insert | ( | InputIterator | first, |
InputIterator | beyond, | ||
T && | ... | ||
) |
Add a sequence of primitives to the set of primitives of the AABB tree.
InputIterator
is any iterator and the parameter pack T
are any types such that Primitive
has a constructor with the following signature: Primitive(InputIterator, T...)
. If Primitive
is a model of the concept AABBPrimitiveWithSharedData
, a call to AABBTraits::set_shared_data(t...)
is made using the internally stored traits.
size_type CGAL::AABB_tree< AABBTraits >::number_of_intersected_primitives | ( | const Query & | query | ) | const |
Returns the number of primitives intersected by the query.
Query | must be a type for which do_intersect predicates are defined in the traits class AABBTraits . |
AABB_tree< Tr >::FT CGAL::AABB_tree< Tr >::squared_distance | ( | const Point & | query | ) | const |
Returns the minimum squared distance between the query point and all input primitives.
Method accelerate_distance_queries()
should be called before the first distance query, so that an internal secondary search structure is build, for improving performance.
!empty()
AABB_tree< Tr >::FT CGAL::AABB_tree< Tr >::squared_distance | ( | const Point & | query, |
const Point & | hint | ||
) | const |
Returns the minimum squared distance between the query point and all input primitives.
The internal KD-tree is not used.
!empty()