# 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 $\mathcal{A}$ is a function that returns the point $\mathbf{p}$ that maximises its dot product with a given direction $\mathbf{v}$. Such a point point $s_{\mathcal{A}}(\mathbf{v})$ 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 $\mathbf{v}$, any one of them can be returned (preferably a corner). The following shows support points for the shapes $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$, given two directions $\mathbf u$ and $\mathbf v$:

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.

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 rectangle in two dimensions or a cylinder in three dimensions. Its principal axis is the $\mathbf{y}$ 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 an isosceles triangle in two dimensions or 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 $\mathbf{y}$ axis, and its apex has coordinates $(0, \text{cone.half_height()}, 0)$.

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 the Minkowski sum of a segment and a ball. In other words, this is a cylinder with extremities replaced by half-balls. A capsule is defined by the half height of its cylindrical part and the radius of its extremities. It is centered at the origin and its principal axis is the $\mathbf{y}$ 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 ConvexHull structure represents 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 ConvexHull shape is created from a set of points. Note that it does not compute explicitly the convex hull of the points so its creation takes $\mathcal{O}(1)$ time.

Method Description
.points() The points used to create the ConvexHull shape.
let points = vec![
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 = ConvexHull::new(points);

// ConvexHull does not compute explicitly the convex hull (which has 4 vertices)!
assert!(convex.points().len() == 5);
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),
Point3::new(0.0, 0.0, 0.0)
];

let convex = ConvexHull::new(points);

// ConvexHull does not compute explicitly the convex hull (which has 6 vertices)!
assert!(convex.points().len() == 7);

### Reflection§

The Reflection structure describes the reflection of a shape $\mathcal{A}$ with regard to the origin:

The reflected shape and the reflection itself are lifetime-bound so it cannot be used to create a shape handle.

Method Description
.shape() The shape affected by the reflection.
let cone = Cone::new(0.5f32, 0.75);

// Build the reflection.
let _ = Reflection::new(&cone);

### Minkowski sum§

The MinkowskiSum structure describes the Minkoswki sum of two shapes implementing the SupportMap trait. If $\mathcal{A}$ and $\mathcal{B}$ are two (possibly infinite) sets of points, their Minkowski sum is given by the set:

In other words, this is the union of all points of one shape successively translated by each point of the other one. This is extremely useful for discrete and continuous collision detection. Note that MinkowskiSum does not compute the sum explicitly so its construction is $\mathcal{O}(1)$. It is lifetime-bound to the shapes involved in the sum so it cannot be used to create a shape handle.

Method Description
.m1() The local transformation of the first shape involved in the sum.
.m2() The local transformation of the second shape involved in the sum.
.g1() The first shape involved in the sum.
.g2() The second shape involved in the sum.
let cylinder = Cylinder::new(0.5f32, 0.75);
let cone     = Cone::new(0.75f32, 0.75);

let delta_cylinder = na::one::<Isometry2<f32>>(); // Identity matrix.
let delta_cone     = na::one::<Isometry2<f32>>(); // Identity matrix.

let _ = MinkowskiSum::new(&delta_cylinder, &cylinder, &delta_cone, &cone);
let cylinder = Cylinder::new(0.5f32, 0.75);
let cone     = Cone::new(0.75f32, 0.75);

let delta_cylinder = na::one::<Isometry3<f32>>(); // Identity matrix.
let delta_cone     = na::one::<Isometry3<f32>>(); // Identity matrix.

let _ = MinkowskiSum::new(&delta_cylinder, &cylinder, &delta_cone, &cone);

#### Configuration Space Obstacle construction example §

The Configuration Space Obstacle (CSO) is the same as the Minkowski sum of the first shape with the reflection of the second one:

This concept is extensively used, e.g., in robotics and interference detection to compute all the impossible positions of the center of mass of an object that evolves in a complex environment. This is obviously not a commutative operator. It can be constructed using the MinkowskiSum and Reflection shapes:

let cylinder   = Cylinder::new(0.5f32, 0.75);
let cone       = Cone::new(0.75f32, 0.75);
let reflection = Reflection::new(&cone); // Take the reflection of the cone.

let delta_cylinder = na::one::<Isometry3<f32>>(); // Identity matrix.
let delta_cone     = na::one::<Isometry3<f32>>(); // Identity matrix.

// Build the Configuration Space Obstacle.
let _ = MinkowskiSum::new(&delta_cylinder, &cylinder, &delta_cone, &reflection);

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

1. Initialize a vector of shape handles with their positions and orientations relative to the origin.
2. 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 normal of the plane.
let plane = Plane::new(Vector2::new(0.0f32, 1.0));

assert!(plane.normal().x == 0.0);
assert!(plane.normal().y == 1.0);
let plane = Plane::new(Vector3::new(0.0f32, 1.0, 0.0));

assert!(plane.normal().x == 0.0);
assert!(plane.normal().y == 1.0);
assert!(plane.normal().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 ComposteShape 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 $a$ and $b$:

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

We first have to define its support mapping. Let $\mathcal{F}$ be an ellipse. The implicit equation of the border of an ellipse centered at the origin is given by $f(x, y) = \left(\frac{x}{a}\right)^2 + \left(\frac{y}{b}\right)^2 - 1 = 0$. Therefore its gradient is simply $\nabla{}f(x, y) = \left[ \frac{2x}{a^2}, \frac{2y}{b^2} \right]^\intercal$. Then, for some direction $\mathbf{v} = [ x_v, y_v ]^\intercal \in \mathbb{R}^2$, convex analysis tells us that the point $[ x^*, y^* ]^\intercal \in \mathcal{F}$ that maximizes or minimizes the dot product with $\mathbf{v}$ is such that $v \times \nabla{}f(x^*, y^*) = \frac{x_vy^*}{b^2} - \frac{y_vx^*}{a^2} = 0$. Thus, we have to solve the quadratic algebraic system:

The solutions of this system are $[ x^*, y^* ]^\intercal = \pm{}\left[ \frac{x_v a^2}{\sqrt{x_v^2 a^2 + y_v^2 b^2}}, \frac{y_vb^2}{\sqrt{x_v^2 a^2 + y_v^2 b^2}} \right]^\intercal$. 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:

1. A Cuboid of width 4 and height 2.
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());