![]() |
Class AABB_tree<AT> 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 AT. The template parameter AT stands for a traits class which must be a model of the concept AABBTraits.
#include <CGAL/AABB_tree.h>
AABB_tree<AT>::size_type; | |
Unsigned integral size type.
|
typedef AT::FT | FT; | Number type returned by the distance queries. |
typedef AT::Point_3 | Point; | Type of 3D point. |
typedef AT::Primitive | Primitive; | Type of input primitive. |
typedef AT::Bounding_box | Bounding_box; | Type of bounding box. |
typedef std::pair<Point, Primitive::Id> | ||
Point_and_primitive_id; | ||
typedef std::pair<CGAL::Object, Primitive::Id> | ||
Object_and_primitive_id; |
AABB_tree<AT> tree; | |
Constructs an empty tree.
| |
template < class InputIterator> | |
AABB_tree<AT> tree ( InputIterator begin, InputIterator beyond); | |
Builds the AABB tree data structure. Type InputIterator can be any const iterator such that Primitive has a constructor taking a InputIterator as argument. The tree stays empty if the memory allocation is not successful.
|
void | tree.build () | After one or more calls to insert , the internal data structure of AABB_tree<AT> 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. |
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 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.
For this reason, the user can provide his own set of sample points:
Note that, in some cases, the user is not able to provide ids of the primitives on which the points lie. In these cases, providing a default value for the ids of the hints is possible. Still, the user should be aware that if she uses the closest_point_and_primitive method, there is a (tiny) chance that a hint is returned, along with this default value as corresponding primitive id. Hence, the validity of the returned primitive id should be checked in these cases.
As an alternative to using the KD-tree, the user can also provide the hints directly, by using the following methods: