CGAL 4.12.1 - 3D Fast Intersection and Distance Computation (AABB Tree)
AABBTraits Concept Reference

## 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
CGAL::AABB_traits<AABBGeomTraits,AABBPrimitive>
CGAL::AABB_tree<AABBTraits>
AABBPrimitive

## Types

enum  Axis
enum required for axis selection

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
3D Point and Primitive Id type

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

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

## ◆ 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

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

## ◆ 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

## ◆ Equal_3

 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.

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

## ◆ Intersection_and_primitive_id

template<typename Query >

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.

## ◆ Object_and_primitive_id

 typedef std::pair AABBTraits::Object_and_primitive_id
Deprecated:
This requirement is deprecated and is no longer needed.

## ◆ Primitive

Type of primitive.

Must be a model of the concepts AABBPrimitive or AABBPrimitiveWithSharedData.

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

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

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

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

## ◆ set_shared_data()

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.