\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.10.2 - 3D Fast Intersection and Distance Computation (AABB Tree)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
AABBTraits Concept Reference
Concepts

Definition

The concept AABBTraits provides the geometric primitive types and methods for the class CGAL::AABB_tree<AABBTraits>.

Has Models:
CGAL::AABB_traits<AABBGeomTraits,AABBPrimitive>
Refines:
SearchGeomTraits_3
See Also
CGAL::AABB_traits<AABBGeomTraits,AABBPrimitive>
CGAL::AABB_tree<AABBTraits>
AABBPrimitive

Types

enum  Axis
 
typedef unspecified_type FT
 Value type of the Squared_distance functor.
 
typedef unspecified_type Point_3
 Type of a 3D point.
 
typedef unspecified_type Primitive
 Type of primitive. More...
 
typedef unspecified_type Bounding_box
 Bounding box type.
 
typedef std::pair< Point_3,
Primitive::Id > 		Point_and_primitive_id
 
typedef std::pair< Object,
Primitive::Id > 		Object_and_primitive_id
 
template<typename Query >
using Intersection_and_primitive_id = unspecified_type
 A nested class template providing as a pair the intersection result of a Query object and a Primitive::Datum, together with the Primitive::Id of the primitive intersected. More...
 

Splitting

During the construction of the AABB tree, the primitives are sorted according to some comparison functions related to the \(x\), \( y\) or \( z\) coordinate axis:

typedef unspecified_type Split_primitives_along_x_axis
 A functor object to split a range of primitives into two sub-ranges along the X-axis. More...
 
typedef unspecified_type Split_primitives_along_y_axis
 A functor object to split a range of primitives into two sub-ranges along the Y-axis. More...
 
typedef unspecified_type Split_primitives_along_z_axis
 A functor object to split a range of primitives into two sub-ranges along the Z-axis. More...
 
typedef unspecified_type Compute_bbox
 A functor object to compute the bounding box of a set of primitives. More...
 

Intersections

The following predicates are required for each type Query for which the class CGAL::AABB_tree<AABBTraits> may receive an intersection detection or computation query.

typedef unspecified_type Do_intersect
 A functor object to compute intersection predicates between the query and the nodes of the tree. More...
 
typedef unspecified_type Intersect
 A functor object to compute the intersection of a query and a primitive. More...
 

Distance Queries

The following predicates are required for each type Query for which the class CGAL::AABB_tree<AABBTraits> may receive a distance query.

typedef unspecified_type Compare_distance
 A functor object to compute distance comparisons between the query and the nodes of the tree. More...
 
typedef unspecified_type Closest_point
 A functor object to compute closest point from the query on a primitive. More...
 
typedef unspecified_type Squared_distance
 A functor object to compute the squared distance between two points. More...
 
typedef unspecified_type Equal_3
 A functor object to compare two points. More...
 

Operations

Split_primitives_along_x_axis split_primitives_along_x_axis_object ()
 Returns the primitive splitting functor for the X axis.
 
Split_primitives_along_y_axis split_primitives_along_y_axis_object ()
 Returns the primitive splitting functor for the Y axis.
 
Split_primitives_along_z_axis split_primitives_along_z_axis_object ()
 Returns the primitive splitting functor for the Z axis.
 
Compute_bbox compute_bbox_object ()
 Returns the bounding box constructor.
 
Do_intersect do_intersect_object ()
 Returns the intersection detection functor.
 
Intersect intersect_object ()
 Returns the intersection constructor.
 
Compare_distance compare_distance_object ()
 Returns the distance comparison functor.
 
Closest_point closest_point_object ()
 Returns the closest point constructor.
 
Squared_distance squared_distance_object ()
 Returns the squared distance functor.
 
Equal_3 equal_3_object ()
 Returns the equal functor.
 

Primitive with Shared Data

In addition, if Primitive is a model of the concept AABBPrimitiveWithSharedData, the following functions are part of the concept:

template<class... T>
void set_shared_data (T...t)
 the signature of that function must be the same as the static function Primitive::construct_shared_data. More...
 

Member Typedef Documentation

typedef unspecified_type AABBTraits::Closest_point

A functor object to compute closest point from the query on a primitive.

Provides the operator: Point_3 operator()(const Query& query, const Primitive& primitive, const Point_3 & closest); which returns the closest point to query, among closest and all points of the primitive.

typedef unspecified_type AABBTraits::Compare_distance

A functor object to compute distance comparisons between the query and the nodes of the tree.

Provides the operators:

  • bool operator()(const Query & query, const Bounding_box& box, const Point & closest); which returns true iff the bounding box is closer to query than closest is
  • bool operator()(const Query & query, const Primitive & primitive, const Point & closest); which returns true iff primitive is closer to the query than closest is
typedef unspecified_type AABBTraits::Compute_bbox

A functor object to compute the bounding box of a set of primitives.

Provides the operator: Bounding_box operator()(Input_iterator begin, Input_iterator beyond); Iterator type InputIterator must have Primitive as value type.

typedef unspecified_type AABBTraits::Do_intersect

A functor object to compute intersection predicates between the query and the nodes of the tree.

Provides the operators:

  • bool operator()(const Query & q, const Bounding_box & box); which returns true iff the query intersects the bounding box
  • bool operator()(const Query & q, const Primitive & primitive); which returns true iff the query intersects the primitive
typedef unspecified_type AABBTraits::Equal_3

A functor object to compare two points.

Provides the operator: bool operator()(const Point_3& p, const Point_3& q);} which returns true if p is equal to q.

typedef unspecified_type AABBTraits::Intersect

A functor object to compute the intersection of a query and a primitive.

Provides the operator: boost::optional<Intersection_and_primitive_id<Query>::Type > operator()(const Query & q, const Primitive& primitive); which returns the intersection as a pair composed of an object and a primitive id, iff the query intersects the primitive.

Note on Backward Compatibility
Before the release 4.3 of CGAL, the return type of this function used to be boost::optional<Object_and_primitive_id>.

template<typename Query >
using AABBTraits::Intersection_and_primitive_id = unspecified_type

A nested class template providing as a pair the intersection result of a Query object and a Primitive::Datum, together with the Primitive::Id of the primitive intersected.

The type of the pair is Intersection_and_primitive_id<Query>::Type.

typedef std::pair<Object, Primitive::Id> AABBTraits::Object_and_primitive_id
Deprecated:
This requirement is deprecated and is no longer needed.
typedef unspecified_type AABBTraits::Primitive

Type of primitive.

Must be a model of the concepts AABBPrimitive or AABBPrimitiveWithSharedData.

typedef unspecified_type AABBTraits::Split_primitives_along_x_axis

A functor object to split a range of primitives into two sub-ranges along the X-axis.

Provides the operator: void operator()(InputIterator first, InputIterator beyond); Iterator type InputIterator must be a model of RandomAccessIterator and have Primitive as value type. The operator is used for determining the primitives assigned to the two children nodes of a given node, assuming that the goal is to split the X-dimension of the bounding box of the node. The primitives assigned to this node are passed as argument to the operator. It should modify the iterator range in such a way that its first half and its second half correspond to the two children nodes.

typedef unspecified_type AABBTraits::Split_primitives_along_y_axis

A functor object to split a range of primitives into two sub-ranges along the Y-axis.

See Split_primitives_along_x_axis for the detailed description.

typedef unspecified_type AABBTraits::Split_primitives_along_z_axis

A functor object to split a range of primitives into two sub-ranges along the Z-axis.

See Split_primitives_along_x_axis for the detailed description.

typedef unspecified_type AABBTraits::Squared_distance

A functor object to compute the squared distance between two points.

Provides the operator: FT operator()(const Point& query, const Point_3 & p); which returns the squared distance between p and q.

Member Function Documentation

template<class... T>
void AABBTraits::set_shared_data ( T...  t)

the signature of that function must be the same as the static function Primitive::construct_shared_data.

The type Primitive expects that the data constructed by a call to Primitive::construct_shared_data(t...) is the one given back when accessing the reference point and the datum of a primitive.