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:

$$s_{\mathcal{A}}(\mathbf{v}) = \arg \max\limits_{\mathbf{p} \in \mathcal{A}} \left< \mathbf{p}, \mathbf{v} \right>$$

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.

Most basic geometric primitives like balls, cubes, cones, can be described by their support mappings. This allows a useful level of genericity for several geometric queries on ncollide.

Ball§

The Ball designs a disk in 2D, or a sphere in 3D, both centered at the origin.

• Example

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.

• 2D example
• 3D example

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 $\mathbf{y}$ as its principal axis.

• Example

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 $\mathbf{y}$ axis, and its apex has coordinates $(0, \text{cone.half_height()}, 0)$.

• Example

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 $\mathbf{y}$ axis.

• Example

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

• 2D example
• 3D example

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 $(B - A) × (C - A)$ should result in a vector pointing toward the exterior of the convex polyhedron.

• 2D example
• 3D example

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 degenerate 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 shape is assumed to be immutable, i.e., an index must always map to a shape and local transformation that both remain constant over time. The indices must be contiguous and on the range $[0, shape.nparts()[$

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.

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.

• 2D example
• 3D example

// 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§

The Polyline structure describes a set of contiguous segments. It is constructed from arrays of vertices, each vertex being linked to its adjacent elements on this array.

• 2D example
• 3D example

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),
    Point2::new(0.0, 1.0), // This forms a loop.
];

// Build the polyline.
let polyline = Polyline::new(points);

assert!(polyline.vertices().len() == 4);

let points = vec![
    Point3::new(0.0, 1.0, 0.0),
    Point3::new(-1.0, -1.0, 1.0),
    Point3::new(0.0, -0.5, 0.0),
    Point3::new(1.0, -1.0, -1.0),
    Point3::new(0.0, 1.0, 0.0), // This forms a loop.
];

// Build the polyline.
let polyline = Polyline::new(points);

assert!(polyline.vertices().len() == 5);

TriMesh§

The TriMesh structure is only available in 3D and describes a mesh of triangles. It is constructed from arrays of vertices and indices describing its triangles. It is also possible to provide one texture coordinate per vertex; those are not used for contact determination but are useful for, e.g., ray-tracing applications.

• 3D example

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(points, indices, 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.

• 2D example
• 3D example

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.

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:

$$\left\{ \begin{array}{lcl} \frac{x_v y^*}{b^2} - \frac{y_vx^*}{a^2} & = & 0\\ \left(\frac{x^*}{a}\right)^2 + \left(\frac{y^*}{b}\right)^2 - 1 & = & 0 \end{array} \right.$$

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<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<f32> for Ellipse {
    fn aabb(&self, m: &Isometry2<f32>) -> AABB<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<&SupportMap<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!(relative_eq!(dist, 1.0, epsilon = 1.0e-6));
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, AABB<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) -> AABB<f32> {
        if i == 0 {
            // The AABB for the horizontal cuboid.
            AABB::new(Point2::new(-1.0, 0.0), Point2::new(3.0, 2.0))
        } else {
            // The AABB for the vertical cuboid.
            AABB::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) -> Cuboid<f32> {
        if i == 0 {
            // Create a 4x2 cuboid. Remember that we must provide the
            // half-lengths.
            Cuboid::new(Vector2::new(2.0, 1.0))
        } else {
            // Create a 2x4 cuboid. Remember that we must provide the
            // half-lengths.
            Cuboid::new(Vector2::new(1.0, 2.0))
        }
    }
}

Now we have to implement the CompositeShape trait.

impl CompositeShape<f32> for CrossedCuboids {
    fn nparts(&self) -> usize {
        2
    }

    fn map_part_at(&self, i: usize, f: &mut FnMut(usize, &Isometry2<f32>, &Shape<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(i, &transform, &cuboid)
    }

    fn map_transformed_part_at(
        &self,
        i: usize,
        m: &Isometry2<f32>,
        f: &mut FnMut(usize, &Isometry2<f32>, &Shape<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(i, &transform, &cuboid)
    }

    fn aabb_at(&self, i: usize) -> AABB<f32> {
        // Compute the i-th AABB.
        CrossedCuboids::generate_aabb(i)
    }

    fn bvt(&self) -> &BVT<usize, AABB<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<f32> for CrossedCuboids {
    fn aabb(&self, m: &Isometry2<f32>) -> AABB<f32> {
        // This is far from an optimal AABB.
        AABB::new(
            m.translation * Point2::new(-10.0, -10.0),
            m.translation * Point2::new(10.0, 10.0),
        )
    }

    fn as_composite_shape(&self) -> Option<&CompositeShape<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 cross = CrossedCuboids::new();
let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));

let cross_pos = na::one();
let cuboid_pos = Isometry2::new(Vector2::new(6.0, 0.0), na::zero());

let dist = query::distance(&cross_pos, &cross, &cuboid_pos, &cuboid);
let prox = query::proximity(&cross_pos, &cross, &cuboid_pos, &cuboid, 0.0);
let ctct = query::contact(&cross_pos, &cross, &cuboid_pos, &cuboid, 0.0);

assert!(relative_eq!(dist, 2.0));
assert_eq!(prox, Proximity::Disjoint);
assert!(ctct.is_none());