# Geometric representations§

Different representations of geometric objects will lead to different
algorithms. Currently, **ncollide** relies a lot on convex shapes described by
a support mapping. However, working exclusively with
convex shapes is too restrictive so **ncollide** provides composite
shapes that allows the construction of a concave shape from
its convex parts.

Geometric primitives supported by **ncollide** are defined on the `shape`

module. They all share a common dynamic
representation. Note that all geometric
primitives have a predefined constant local frame equal to the identity matrix.
Thus, one usually has to store a transformation matrix separately from
the shape itself in order to reach any location and orientation.

# Support mappings§

**ncollide** supports generic algorithms that work for any (possibly
user-defined) shape defined by a support map. The support map (argument) of a
shape is a function that returns the point that
maximises its dot product with a given direction . Such a point
point is called a *support point*:

This can be seen as a function that returns a point of the support mapped
shape which is *the furthest on the given direction*. Such a function is
enough to describe completely a convex object. If several points are eligible
to be support points for a given direction , any one of them can
be returned (preferably a corner). The following shows support points for the
shapes and , given two directions
and :

The support mapping function is exposed by the `SupportMap`

trait.

Method | Description |
---|---|

`.support_point(m, v)` |
Computes the support point (in the direction `v` ) of the caller transformed by the transformation matrix `m` . |

`.support_point_toward(m, v)` |
Same as `.support_point(...)` except that `v` is already a unit vector. |

Most basic geometric primitives like balls, cubes, cones, and even more complex
ones like a Minkowski Sum of convex shapes can be described by their support
mappings. This allows a useful level of genericity for several geometric
queries on **ncollide**. Moreover, allogithms based on support algorithms can
usually general enough to be able to operate on shapes embedded on a space of
finite dimension higher than 3.

### Ball§

Mathematically speaking, the `Ball`

structure describes a closed ball on the
*n*-dimensional euclidean space. In two dimensions this is a disk, and in three
dimensions a sphere, both centered at the origin.

Method | Description |
---|---|

`.radius()` |
The radius of the ball. |

```
let ball = Ball::new(1.0f32);
assert!(ball.radius() == 1.0);
```

### Cuboid§

The `Cuboid`

structure describes a rectangle in two dimensions or a cuboid in
three dimensions. A cuboid is defined by its *half extents*, i.e., its
half length along each coordinate axis.

Method | Description |
---|---|

`.half_extents()` |
The half extents of the cuboid. |

```
let cuboid = Cuboid::new(Vector2::new(2.0f32, 1.0));
assert!(cuboid.half_extents().x == 2.0);
assert!(cuboid.half_extents().y == 1.0);
```

```
let cuboid = Cuboid::new(Vector3::new(2.0f32, 1.0, 3.0));
assert!(cuboid.half_extents().x == 2.0);
assert!(cuboid.half_extents().y == 1.0);
assert!(cuboid.half_extents().z == 3.0);
```

### Cylinder§

The `Cylinder`

structure describes a 3D cylinder with as its principal axis.

Method | Description |
---|---|

`.half_height()` |
The half height of the cylinder. |

`.radius()` |
The radius of the cylinder basis. |

```
let cylinder = Cylinder::new(0.5f32, 1.0);
assert!(cylinder.half_height() == 0.5);
assert!(cylinder.radius() == 1.0);
```

### Cone§

The `Cone`

structure describes a cone of revolution in three dimensions.
A cone is defined by the *radius* of its basis and its *half height* − the
half distance between the basis and the apex. It points upward, its principal
axis is the axis, and its apex has coordinates .

Method | Description |
---|---|

`.half_height()` |
The half height of the cone. |

`.radius()` |
The radius of the cone basis. |

```
let cone = Cone::new(0.5f32, 0.75);
assert!(cone.half_height() == 0.5);
assert!(cone.radius() == 0.75);
```

### Capsule§

The `Capsule`

structure describes either a rectangle with extremitis replaced by half-discs (in 2D),
or a cylinder with extremities replaced by half-balls (in 3D). A capsule is defined by the *half height*
of its rectangular/cylindrical part and the *radius* of its extremities. It is centered at the origin and
its principal axis is the axis.

Method | Description |
---|---|

`.half_height()` |
The half height of the capsule cylindrical part. |

`.radius()` |
The radius of the capsule extremities. |

```
let capsule = Capsule::new(0.5f32, 0.75);
assert!(capsule.half_height() == 0.5);
assert!(capsule.radius() == 0.75);
```

### Convex hull§

The `ConvexPolygon`

(in 2D) and `ConvexHull`

(in 3D) structures represent the smallest convex envelope of a set of
point. Remember that an object is said to be convex if it is not self-crossing,
and if it contains any segment joining two of its points:

The `ConvexPolygon`

(in 2D) and `ConvexHull`

shape (in 3D) are created from a set of points using the `::try_from_points(points)`

constructor. Note that this explicitly computes the convex hull of the input point cloud. If you already computed the convex hull on your side, you may use `::try_new(...)`

instead (described later in this section).

Method | Description |
---|---|

`.points()` |
The points used to create the `ConvexHull` shape. |

```
let points = [
Point2::new(-1.0f32, 1.0),
Point2::new(-0.5, -0.5),
Point2::new(0.0, 0.5),
Point2::new(0.5, -0.5),
Point2::new(1.0, 1.0),
];
let convex = ConvexPolygon::try_from_points(&points).expect("Convex hull computation failed.");
assert!(convex.points().len() == 4); // The convex hull has only 4 vertices.
```

```
let points = [
Point3::new(0.0f32, 0.0, 1.0),
Point3::new(0.0, 0.0, -1.0),
Point3::new(0.0, 1.0, 0.0),
Point3::new(0.0, -1.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(-1.0, 0.0, 0.0),
Point3::new(0.0, 0.0, 0.0)
];
let convex = ConvexHull::try_from_points(&points).expect("Convex hull computation failed.");
assert!(convex.points().len() == 6); // The convex hull has only 6 vertices.
```

If you have the ability to provide the convex hull directly, you may use `::try_new(...)`

instead. It won’t compute explicitly the convex hull of the points but expect the input to describe one. In 2D, the given vertices are expected to be ordered such that they appear counterclockwise on the convex polygon boundary. In 3D, the provided index buffer must be such that each triangle is properly connected to its neighbors and is oriented counterclockwise, i.e., given a triangle `ABC`

, the cross product should result in a vector pointing toward the exterior of the convex polyhedron.

```
let points = vec![
Point2::new(-1.0f32, 1.0),
Point2::new(-0.5, -0.5),
Point2::new(0.5, -0.5),
Point2::new(1.0, 1.0),
];
let convex = ConvexPolygon::try_new(points).expect("Invalid convex polygon.");
assert!(convex.points().len() == 4);
```

```
let points = vec![
Point3::new(0.0f32, 0.0, 1.0),
Point3::new(0.0, 0.0, -1.0),
Point3::new(0.0, 1.0, 0.0),
Point3::new(0.0, -1.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(-1.0, 0.0, 0.0),
];
let indices = vec![
0, 4, 2,
0, 3, 4,
5, 0, 2,
5, 3, 0,
1, 5, 2,
1, 3, 5,
4, 1, 2,
4, 3, 1,
];
let convex = ConvexHull::try_new(points, &indices).expect("Invalid convex shape.");
assert!(convex.points().len() == 6);
```

Keep in mind that while those constructors will fail if the topology of the convex hull is invalid, or if it contains degenate faces, it does not check the convexity of the input. Therefore, `::try_new(...)`

may succeed even if your input is not actually convex. In that case, you may experience odd results for various geometric queries.

# Composite shapes§

**ncollide** supports shapes that are defined as aggregations of others. Every
composite shape must implement the `CompositeShape`

trait which defines methods
for accessing their individual parts using indices. The composite is assumed to
be immutable, i.e., an index must always map to a shape and local
transformation that both remain constant over time. However, the actual range
of index values is implementation-defined and does not even have to be
contiguous nor finite.

Method | Description |
---|---|

`.map_part_at(i, f)` |
Applies the closure `f` to the `i` -th part and its local transformation matrix. |

`.map_transformed_part_at(i, m, f)` |
Applies the closure `f` to the `i` -th part and its local transformation matrix with `m` appended to it. |

`.aabb_at(i)` |
The `AABB` of the `i` -th part of the composite shape. |

`.bvt()` |
The space-partitioning acceleration structure used by the composite shape. |

The requirement to use a `BVT`

for space-partitioning is extremely restrictive
and will be replaced by a more flexible system in the future. Currently, three
composite shapes are available on **ncollide**. The `Compound`

describes the
union of any shape supported by **ncollide**. The `TriMesh`

and the `Polyline`

are dedicated to assemblies of triangles and segments.

### Compound§

The `Compound`

structure is the main way of describing concave shapes from
convex ones. It is a set of any shape handle.

Method | Description |
---|---|

`.shapes()` |
The shapes composing the compound. |

`.bounding_volumes()` |
The `AABB` of the shapes composing the compound. |

`.bvt()` |
The space-partitioning acceleration structure used by the compound. |

Two steps are necessary to create a `Compound`

:

- Initialize a vector of shape handles with their positions and orientations relative to the origin.
- Call
`Compound::new`

with this vector.

```
// Delta transformation matrices.
let delta1 = Isometry2::new(Vector2::new(0.0f32, -1.5), na::zero());
let delta2 = Isometry2::new(Vector2::new(-1.5f32, 0.0), na::zero());
let delta3 = Isometry2::new(Vector2::new(1.5f32, 0.0), na::zero());
// 1) Initialize the shape list.
let mut shapes = Vec::new();
let horizontal_box = ShapeHandle::new(Cuboid::new(Vector2::new(1.5f32, 0.25)));
let vertical_box = ShapeHandle::new(Cuboid::new(Vector2::new(0.25f32, 1.5)));
shapes.push((delta1, horizontal_box));
shapes.push((delta2, vertical_box.clone()));
shapes.push((delta3, vertical_box));
// 2) Create the compound shape.
let compound = Compound::new(shapes);
assert!(compound.shapes().len() == 3)
```

```
// Delta transformation matrices.
let delta1 = Isometry3::new(Vector3::new(0.0f32, -1.5, 0.0), na::zero());
let delta2 = Isometry3::new(Vector3::new(-1.5f32, 0.0, 0.0), na::zero());
let delta3 = Isometry3::new(Vector3::new(1.5f32, 0.0, 0.0), na::zero());
// 1) Initialize the shape list.
let mut shapes = Vec::new();
let horizontal_box = ShapeHandle::new(Cuboid::new(Vector3::new(1.5f32, 0.25, 0.25)));
let vertical_box = ShapeHandle::new(Cuboid::new(Vector3::new(0.25f32, 1.5, 0.25)));
shapes.push((delta1, horizontal_box));
shapes.push((delta2, vertical_box.clone()));
shapes.push((delta3, vertical_box));
// 2) Create the compound shape.
let compound = Compound::new(shapes);
assert!(compound.shapes().len() == 3)
```

### Polyline and TriMesh§

The `Polyline`

and `TriMesh`

structures describe a set of segments and a mesh
of triangles. They are constructed from shared arrays of vertices and indices.
Each segment (resp. triangle) is identified by two (resp. three) indices. It is
also possible to provide one normal and one texture coordinate per vertex;
those are not used for contact determination but are useful for, e.g.,
ray-tracing applications.

Method | Description |
---|---|

`.vertices()` |
The vertex buffer. |

`.indices()` |
The index buffer. |

`.normals()` |
The normal buffer. |

`.uvs()` |
The texture coordinates buffer. |

`.bounding_volumes()` |
The bounding volume of each primitive (segment or triangle). |

`.bvt()` |
The space-partitioning acceleration structure used by the mesh. |

```
let points = vec!(
Point2::new(0.0, 1.0), Point2::new(-1.0, -1.0),
Point2::new(0.0, -0.5), Point2::new(1.0, -1.0));
let indices = vec!(Point2::new(0usize, 1),
Point2::new(1, 2),
Point2::new(2, 3),
Point2::new(3, 1));
// Build the polyline.
let polyline = Polyline::new(Arc::new(points), Arc::new(indices), None, None);
assert!(polyline.vertices().len() == 4);
```

```
let points = vec!(
Point3::new(0.0, 1.0, 0.0), Point3::new(-1.0, -0.5, 0.0),
Point3::new(0.0, -0.5, -1.0), Point3::new(1.0, -0.5, 0.0));
let indices = vec!(Point3::new(0usize, 1, 2),
Point3::new(0, 2, 3),
Point3::new(0, 3, 1));
// Build the mesh.
let mesh = TriMesh::new(Arc::new(points), Arc::new(indices), None, None);
assert!(mesh.vertices().len() == 4);
```

# Other shapes§

Some shapes do not fall into any of the general categories described above.

### Plane§

The `Plane`

structure describes a solid closed half-space. The border of a
plane contains the origin and is characterized by its *normal*. Every point
that has a negative or null dot product with the plane normal is considered
*inside* of it. Other points are *outside* of the plane.

Method | Description |
---|---|

`.normal()` |
The unit normal of the plane. |

```
let plane = Plane::new(Vector2::<f32>::y_axis());
assert!(plane.normal().as_ref().x == 0.0);
assert!(plane.normal().as_ref().y == 1.0);
```

```
let plane = Plane::new(Vector3::<f32>::y_axis());
assert!(plane.normal().as_ref().x == 0.0);
assert!(plane.normal().as_ref().y == 1.0);
assert!(plane.normal().as_ref().z == 0.0);
```

# Dynamic shape representation§

In order to select the right algorithms for geometric queries on specific
shapes, `ncollide`

has to be able to distinguish at runtime different shapes
from their types and they capabilities. As described by another
chapter of this guide, there are two kinds of geometric
queries: those that operate on a single
shape and those that operate on
two shapes simultaneously. In the
first case, runtime algorithm selection is performed with the help of traits
which can be easily implemented for user-defined shapes and exposed at runtime
by a `Shape`

trait-object. On the other hand, queries involving two shapes
require more complex dispatch mechanisms that are not yet customizable by the
user.

### The shape handle§

Elements to inspect shape representation and capabilities are provided for each
shape by implementing the `Shape`

trait. The `ShapeHandle`

structure is nothing
more than a `Shape`

trait-object wrapped into an `Arc`

.

Method | Description |
---|---|

`.aabb(m: &M)` |
The AABB of the shape transformed by `m` . |

`.bounding_sphere(m: &M)` |
The bounding sphere of the shape transformed by `M` . |

`.as_ray_cast()` |
Converts `self` to a `RayCast` trait-object. |

`.as_point_query()` |
Converts `self` to a `PointQuery` trait-object. |

`.as_support_map()` |
Converts `self` to a `SupportMap` trait-object. |

`.as_composite_shape()` |
Converts `self` to a `CompositeShape` trait-object. |

`.is_support_map()` |
Returns `true` if this shape has a support-mapping. |

`.is_composite_shape()` |
Returns `true` if this shape is a composite shape. |

All the conversion methods have a default implementation returning `None`

.
This allows you to only partially implement the trait if some of those features
are of no interest to you or even not applicable for your specific shape. For
example it is extremely rare to implement both `.as_composite_shape()`

and
`.as_support_map()`

as algorithms applicable to the latter will almost always
be more efficient than for the former.

Methods related to bounding volumes have default implementations as well
except for AABB construction. AABBs are widely used throughout **ncollide** so
their tightness is critical for good performances. Other bounding volumes are
less used so by default they are deduced from the AABB itself. Those default
implementations will unfortunately only result in very loose bounding volumes
so it is advised to provide your own to ensure optimal performances.

### Custom support mapping §

In this section we detail an example to define your own support-mapped shape
suitable to be wrapped into a `ShapeHandle`

. Too keep the maths simple, we will
define a 2-dimensional ellipse centered at the origin with radii and :

```
struct Ellipse {
a: f32, // The first radius.
b: f32 // The second radius.
}
```

We first have to define its support mapping. Let be an ellipse. The implicit equation of the border of an ellipse centered at the origin is given by . Therefore its gradient is simply . Then, for some direction , convex analysis tells us that the point that maximizes or minimizes the dot product with is such that . Thus, we have to solve the quadratic algebraic system:

The solutions of this system are .
Among those two solutions, the maximizer is the first one (with the leading sign).
Now, we only have to code this into a `SupportMap`

implementation for our
`Ellipse`

.

```
impl SupportMap<Point2<f32>, Isometry2<f32>> for Ellipse {
fn support_point(&self, transform: &Isometry2<f32>, dir: &Vector2<f32>) -> Point2<f32> {
// Bring `dir` into the ellipse's local frame.
let local_dir = transform.inverse_transform_vector(dir);
// Compute the denominator.
let denom = f32::sqrt(local_dir.x * local_dir.x * self.a * self.a +
local_dir.y * local_dir.y * self.b * self.b);
// Compute the support point into the ellipse's local frame.
let local_support_point = Point2::new(self.a * self.a * local_dir.x / denom,
self.b * self.b * local_dir.y / denom);
// Return the support point transformed back into the global frame.
*transform * local_support_point
}
}
```

With this, we will be able to pass an instance of `Ellipse`

to many geometric
queries from the `query::algorithms`

module and all the functions with names
that contain `support_map`

on the other submodules of the `query`

module.
If we want to benefit from a higher-level interface based on the dynamic
dispatch mechanism of **ncollide**, we have to implement the `Shape`

trait
providing at least an AABB and a conversion to the `SupportMap`

trait-object:

```
impl Shape<Point2<f32>, Isometry2<f32>> for Ellipse {
fn aabb(&self, m: &Isometry2<f32>) -> AABB2<f32> {
// Generic method to compute the aabb of a support-mapped shape.
bounding_volume::support_map_aabb(m, self)
}
fn as_support_map(&self) -> Option<&SupportMap2<f32>> {
Some(self)
}
}
```

That’s it! You will now be able to pass an ellipse to various functions of
the `query`

module, and even wrap it on a `ShapeHandle`

to use it in a
collision object for
complex interactions with a `CollisionWorld`

using the collision detection
pipeline. The following is an example of some
pairwise geometric queries involving
our own ellipse:

```
let ellipse = Ellipse { a: 2.0f32, b: 1.0 };
let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));
let ellipse_pos = na::one();
let cuboid_pos = Isometry2::new(Vector2::new(4.0, 0.0), na::zero());
let dist = query::distance(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid);
let prox = query::proximity(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid, 0.0);
let ctct = query::contact(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid, 0.0);
assert!(na::approx_eq(&dist, &1.0));
assert_eq!(prox, Proximity::Disjoint);
assert!(ctct.is_none());
```

### Custom composite shape §

In this section we detail an example to define your own composite shape
suitable to be wrapped into a `ShapeHandle`

. We will define a simple 2D
cross-shaped object with only two part:

- A Cuboid of width 4 and height 2.
- A Cuboid of width 2 and height 4.

Both will be centered at the point (1, 1):

Because the two parts are very simple, we will generate them on-the-fly when needed by the user. Only the acceleration structure will be precomputed.

```
struct CrossedCuboids {
bvt: BVT<usize, AABB2<f32>>
}
impl CrossedCuboids {
pub fn new() -> CrossedCuboids {
// The shape indices paired with their corresponding AABBs.
// Nedded to initialize the acceleration structure.
let aabbs = vec! [
(0, CrossedCuboids::generate_aabb(0)),
(1, CrossedCuboids::generate_aabb(1))
];
CrossedCuboids {
bvt: BVT::new_balanced(aabbs)
}
}
// Helper function to generate the AABB bounding the i-th cuboid.
fn generate_aabb(i: usize) -> AABB2<f32> {
if i == 0 {
// The AABB for the horizontal cuboid.
AABB2::new(Point2::new(-1.0, 0.0), Point2::new(3.0, 2.0))
}
else {
// The AABB for the vertical cuboid.
AABB2::new(Point2::new(0.0, -1.0), Point2::new(2.0, 3.0))
}
}
// Helper function to generate the i-th cuboid.
fn generate_cuboid(i: usize) -> Cuboid2<f32> {
if i == 0 {
// Create a 4x2 cuboid. Remember that we must provide the
// half-lengths.
Cuboid2::new(Vector2::new(2.0, 1.0))
}
else {
// Create a 2x4 cuboid. Remember that we must provide the
// half-lengths.
Cuboid2::new(Vector2::new(1.0, 2.0))
}
}
}
```

Now we have to implement the `CompositeShape`

trait.

```
impl CompositeShape<Point2<f32>, Isometry2<f32>> for CrossedCuboids {
fn map_part_at(&self, i: usize, f: &mut FnMut(&Isometry2<f32>, &Shape2<f32>)) {
// The translation needed to center the cuboid at the point (1, 1).
let transform = Isometry2::new(Vector2::new(1.0, 1.0), na::zero());
// Create the cuboid on-the-fly.
let cuboid = CrossedCuboids::generate_cuboid(i);
// Call the function.
f(&transform, &cuboid)
}
fn map_transformed_part_at(&self,
i: usize,
m: &Isometry2<f32>,
f: &mut FnMut(&Isometry2<f32>, &Shape2<f32>)) {
// Prepend the translation needed to center the cuboid at the point (1, 1).
let transform = m * Translation2::new(1.0, 1.0);
// Create the cuboid on-the-fly.
let cuboid = CrossedCuboids::generate_cuboid(i);
// Call the function.
f(&transform, &cuboid)
}
fn aabb_at(&self, i: usize) -> AABB2<f32> {
// Compute the i-th AABB.
CrossedCuboids::generate_aabb(i)
}
fn bvt(&self) -> &BVT<usize, AABB2<f32>> {
// Reference to the acceleration structure.
&self.bvt
}
}
```

Just like in the previous section, implementing the `CompositeShape`

trait is
enough to use some pairwise geometric queries, e.g., those from the submodule
of `query`

module with names that contain the word `composite`

. For a more
complete integration, we have to implement the `Shape`

trait providing at least
an AABB and a conversion to the `CompositeShape`

trait-object:

```
impl Shape<Point2<f32>, Isometry2<f32>> for CrossedCuboids {
fn aabb(&self, m: &Isometry2<f32>) -> AABB2<f32> {
// This is far from an optimal AABB.
AABB2::new(m.translation * Point2::new(-10.0, -10.0),
m.translation * Point2::new(10.0, 10.0))
}
fn as_composite_shape(&self) -> Option<&CompositeShape2<f32>> {
Some(self)
}
}
```

That’s it! You will now be able to pass a cross-like shape to various
functions of the `query`

module, and even wrap it on a `ShapeHandle`

to use
it in a collision object
for complex interactions with a `CollisionWorld`

using the collision detection
pipeline. The following is an example of
some pairwise geometric queries
involving our own composite shape:

```
let ellipse = Ellipse { a: 2.0f32, b: 1.0 };
let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));
let ellipse_pos = na::one();
let cuboid_pos = Isometry2::new(Vector2::new(4.0, 0.0), na::zero());
let dist = query::distance(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid);
let prox = query::proximity(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid, 0.0);
let ctct = query::contact(&ellipse_pos, &ellipse, &cuboid_pos, &cuboid, 0.0);
assert!(relative_eq!(dist, 1.0, epsilon = 1.0e-6));
assert_eq!(prox, Proximity::Disjoint);
assert!(ctct.is_none());
```