#include <CGAL/AABB_tree.h>

Definition

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.

See Also: AABBTraits; AABBPrimitive

Examples:: AABB_tree/AABB_custom_example.cpp, AABB_tree/AABB_custom_indexed_triangle_set_array_example.cpp, AABB_tree/AABB_custom_indexed_triangle_set_example.cpp, AABB_tree/AABB_custom_triangle_soup_example.cpp, AABB_tree/AABB_face_graph_triangle_example.cpp, AABB_tree/AABB_halfedge_graph_edge_example.cpp, AABB_tree/AABB_insertion_example.cpp, AABB_tree/AABB_polyhedron_edge_example.cpp, AABB_tree/AABB_polyhedron_facet_distance_example.cpp, AABB_tree/AABB_polyhedron_facet_intersection_example.cpp, AABB_tree/AABB_ray_shooting_example.cpp, AABB_tree/AABB_segment_3_example.cpp, and AABB_tree/AABB_triangle_3_example.cpp.

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

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

Operations
template<typename ConstPrimitiveIterator , typename... T>
void	rebuild (ConstPrimitiveIterator first, ConstPrimitiveIterator beyond, T &&...)
	Equivalent to calling `clear()` and then `insert(first,last,t...)`. More...

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.

Advanced
void	build ()
	After one or more calls to `AABB_tree::insert()` the internal data structure of the tree must be reconstructed. More...

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 >
boost::optional< typename Intersection_and_primitive_id < Ray >::Type >	first_intersection (const Ray &query) const

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

template<typename Ray >
boost::optional< Primitive_id >	first_intersected_primitive (const Ray &query) const

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 in order to return the exact distance to the set of primitives, the algorithms need the hint to be exactly on the primitives; if this is not the case, and if the hint happens to be closer to the query point than any of the primitives, then the hint is returned. 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 `accelerate_distance_queries()` is called. This KD-tree provides very good hints that allow the algorithms to run much faster than with a default hint (such as the `reference_point` of the first primitive). The set of potential hints is a sampling of the union of the primitives, which is obtained, by default, by calling the method `reference_point` of each of the primitives. However, such a sampling with one point per primitive may not be the most relevant one: if some primitives are very large, it helps inserting more than one sample on them. Conversely, a sparser sampling with less than one point per input primitive is relevant in some cases.
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...

Member Typedef Documentation

template<typename AABBTraits >

typedef AABBTraits::Object_and_primitive_id CGAL::AABB_tree< AABBTraits >::Object_and_primitive_id

Deprecated:

Constructor & Destructor Documentation

template<typename AABBTraits >

CGAL::AABB_tree< AABBTraits >::AABB_tree ( const AABBTraits & traits = AABBTraits())

Constructs an empty tree, and initializes the internally stored traits class using traits.

template<typename AABBTraits >

template<typename InputIterator , typename... T>

CGAL::AABB_tree< AABBTraits >::AABB_tree	(	InputIterator	first,
		InputIterator	beyond,
		T &&	...
	)

Builds the datastructure from a sequence of primitives.

Parameters

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...). For compilers that do not support variadic templates, overloads up to 5 template arguments are provided. The tree stays empty if the memory allocation is not successful.

Member Function Documentation

template<typename AABBTraits >

template<typename ConstPointIterator >

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.

Template Parameters

ConstPointIterator is an iterator with value type Point_and_primitive_id.

template<typename Tr >

template<typename Query , typename OutputIterator >

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.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class AABBTraits.

template<typename Tr >

template<typename Query , typename OutputIterator >

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.

template<typename AABBTraits >

template<typename Query >

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.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class AABBTraits.

template<typename AABBTraits >

template<typename Query >

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.

template<typename AABBTraits >

const Bounding_box CGAL::AABB_tree< AABBTraits >::bbox ( ) const

Returns the axis-aligned bounding box of the whole tree.

Precondition: !empty()

template<typename Tr >

void CGAL::AABB_tree< Tr >::build ( )

After one or more calls to AABB_tree::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 AABB_tree::build() explicitly to ensure that the next call to query functions will not trigger the reconstruction of the data structure.

template<typename Tr >

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.

Precondition: !empty()

template<typename Tr >

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.

Precondition: !empty()

template<typename Tr >

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.

Precondition: !empty()

template<typename Tr >

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.

Precondition: !empty()

template<typename Tr >

template<typename Query >

bool CGAL::AABB_tree< Tr >::do_intersect ( const Query & query) const

Returns true, iff the query intersects at least one of the input primitives.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class AABBTraits.

template<typename AABBTraits >

template<typename Ray , typename SkipFunctor >

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.

Template Parameters

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.

template<typename AABBTraits >

template<typename Ray , typename SkipFunctor >

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.

Template Parameters

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.

template<typename AABBTraits >

template<typename InputIterator , typename... T>

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. For compilers that do not support variadic templates, overloads up to 5 template arguments are provided.

template<typename AABBTraits >

template<typename Query >

size_type CGAL::AABB_tree< AABBTraits >::number_of_intersected_primitives ( const Query & query) const

Returns the number of primitives intersected by the query.

Template Parameters

Query must be a type for which do_intersect predicates are defined in the traits class AABBTraits.

template<typename AABBTraits >

template<typename ConstPrimitiveIterator , typename... T>

void CGAL::AABB_tree< AABBTraits >::rebuild	(	ConstPrimitiveIterator	first,
		ConstPrimitiveIterator	beyond,
		T &&	...
	)

Equivalent to calling clear() and then insert(first,last,t...).

For compilers that do not support variadic templates, overloads up to 5 template arguments are provided.

template<typename Tr >

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.

Precondition: !empty()

template<typename Tr >

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.

Precondition: !empty()

Definition

Types

Creation

Operations

Advanced

Intersection Tests

Intersections

Distance Queries

Accelerating the Distance Queries

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation