Single-shape queries§

Geometric queries involving only one shape are exposed through traits. Most of them declare several methods that achieve similar goals but with different levels of details: from simple boolean tests to complete geometric descriptions of the results. Of course, a general rule is to assume that the less detailed queries are be the fastest to execute.

Point projection§

It is possible to check whether or not a point is inside of a shape, to project it, or to compute the distance from a point to a shape. Those queries are exposed by the PointQuery trait:

The solid flag indicates whether the projection is solid or not. If solid is set to false then, the point will be projected on the shape border even if it is located on its inside. If solid is set to true then a copy of point to be projected is returned if it is inside of the shape. Note that a solid point projection (or distance computation) is usually much more efficient than a non-solid one.

The result of point projection is given by the PointProjection structure:

The result of the distance computation with .distance_to_point(...) is a signed real number. If the projection is non-solid and the returned distance negative, then the point is located inside of the shape and this number’s absolute value gives the shortest distance between the point and the shape border. It is zero if the projection is solid and the point located inside of the shape.

The following examples attempt to project two points point_inside and point_outside on a cuboid. Because point_inside is located inside of the cuboid, the resulting distance will be zero if the projection is solid, or negative otherwise. The distance from point_outside to the cuboid is not affected by the solid flag because it is outside of it anyway.

• 2D example
• 3D example

let cuboid = Cuboid::new(Vector2::new(1.0, 2.0));
let pt_inside = na::origin::<Point2<f32>>();
let pt_outside = Point2::new(2.0, 2.0);

// Solid projection.
assert_eq!(cuboid.distance_to_point(&Isometry2::identity(), &pt_inside, true), 0.0);

// Non-solid projection.
assert_eq!(
    cuboid.distance_to_point(&Isometry2::identity(), &pt_inside, false),
    -1.0
);

// The other point is outside of the cuboid so the `solid` flag has no effect.
assert_eq!(
    cuboid.distance_to_point(&Isometry2::identity(), &pt_outside, false),
    1.0
);
assert_eq!(cuboid.distance_to_point(&Isometry2::identity(), &pt_outside, true), 1.0);

let cuboid = Cuboid::new(Vector3::new(1.0, 2.0, 2.0));
let pt_inside = na::origin::<Point3<f32>>();
let pt_outside = Point3::new(2.0, 2.0, 2.0);

// Solid projection.
assert_eq!(cuboid.distance_to_point(&Isometry3::identity(), &pt_inside, true), 0.0);

// Non-solid projection.
assert_eq!(
    cuboid.distance_to_point(&Isometry3::identity(), &pt_inside, false),
    -1.0
);

// The other point is outside of the cuboid so the `solid` flag has no effect.
assert_eq!(
    cuboid.distance_to_point(&Isometry3::identity(), &pt_outside, false),
    1.0
);
assert_eq!(cuboid.distance_to_point(&Isometry3::identity(), &pt_outside, true), 1.0);

Ray casting§

Ray casting is also one of the core geometric queries in the field of collision detection. Besides the fact it can be used for rendering (like ray-tracing), it is useful for, e.g., continuous collision detection and navigation on a virtual environment. Therefore ncollide has efficient ray casting algorithms for all the shapes it implements (including functions that are able to cast rays on arbitrary support-mapped convex shapes). The main ray-casting related data structure is the Ray itself:

The result of a successful ray-cast is given by the RayIntersection structure:

Recall that the exact point of intersection may be computed from the time of impact:

let intersection_point = ray.origin + ray.dir * result.toi

Because ray.dir does not need to be normalized, a physical interpretation of the time of impact is the time needed for a point with velocity ray.dir to travel from the position ray.origin to the object.

The RayCast trait is implemented by shapes that can be intersected by a ray:

If you implement this trait for your own shape, only the second method of this list − namely .toi_and_normal_with_ray(...) − is required. The other ones are automatically inferred (but for optimization purpose you might want to specialize them as well).

If the starting point of a ray is inside of a shape, the result depends on the value of the solid flag. A solid ray cast (solid is set to true) will return an intersection with its toi field set to zero and its normal undefined. A non-solid ray cast (solid is set to false) will assume that the shape is hollow and will propagate on its inside until it hits a border:

Of course, if the starting point of the ray is outside of any shape, then the solid flag has no effect. Note that a solid ray cast is usually much faster than a non-solid one.

The following examples attempt to cast two rays ray_inside and ray_miss on a cuboid. Because the starting point of ray_inside is located inside of the cuboid, the resulting time of impact will be zero if the ray cast is solid and non-zero otherwise. Casting ray_miss will fail because it starts and points away from the cuboid.

• 2D example
• 3D example

let cuboid = Cuboid::new(Vector2::new(1.0, 2.0));
let ray_inside = Ray::new(na::origin::<Point2<f32>>(), Vector2::y());
let ray_miss = Ray::new(Point2::new(2.0, 2.0), Vector2::new(1.0, 1.0));

// Solid cast.
assert_eq!(
    cuboid.toi_with_ray(&Isometry2::identity(), &ray_inside, true).unwrap(),
    0.0
);

// Non-solid cast.
assert_eq!(
    cuboid.toi_with_ray(&Isometry2::identity(), &ray_inside, false).unwrap(),
    2.0
);

// The other ray does not intersect this shape.
assert!(cuboid.toi_with_ray(&Isometry2::identity(), &ray_miss, false).is_none());
assert!(cuboid.toi_with_ray(&Isometry2::identity(), &ray_miss, true).is_none());

let cuboid = Cuboid::new(Vector3::new(1.0, 2.0, 1.0));
let ray_inside = Ray::new(na::origin::<Point3<f32>>(), Vector3::y());
let ray_miss = Ray::new(Point3::new(2.0, 2.0, 2.0), Vector3::new(1.0, 1.0, 1.0));

// Solid cast.
assert!(cuboid.toi_with_ray(&Isometry3::identity(), &ray_inside, true).unwrap() == 0.0);

// Non-solid cast.
assert!(cuboid.toi_with_ray(&Isometry3::identity(), &ray_inside, false).unwrap() == 2.0);

// The other ray does not intersect this shape.
assert!(cuboid.toi_with_ray(&Isometry3::identity(), &ray_miss, false).is_none());
assert!(cuboid.toi_with_ray(&Isometry3::identity(), &ray_miss, true).is_none());

Pairwise queries§

Instead of being exposed by traits, pairwise geometric queries for shapes having a dynamic representation are defined by free-functions on the query module. Those functions will inspect the shape representation in order to select the right algorithm for the query. To avoid this dynamic dispatch when you already know at compile-time which types of shapes are involved, the internal submodules, e.g., query::distance_internal, contain functions dedicated to specific shape types or representations.

Proximity§

The proximity query query::proximity(m1, g1, m2, g2, margin) tests if the shapes g1 and g2, respectively transformed by m1 and m2, are intersecting. It will not provide any specific detail regarding the exact distance separating them. Its result is described by the Proximity enumeration:

Because it might be useful to know when two objects are not intersecting but close to each another, the user may specifies a margin which must be positive or zero. If the two objects are separated by a distance smaller than this margin, the proximity is said to be within the margin.

In the following example, the margin is depicted as a red curve around the rectangle. The sphere being closer than the margin is equivalent to it intersecting the red curve:

• 2D example
• 3D example

let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));
let ball   = Ball::new(1.0);
let margin = 1.0;

let cuboid_pos             = na::one();
let ball_pos_intersecting  = Isometry2::new(Vector2::new(1.0, 1.0), na::zero());
let ball_pos_within_margin = Isometry2::new(Vector2::new(2.0, 2.0), na::zero());
let ball_pos_disjoint      = Isometry2::new(Vector2::new(3.0, 3.0), na::zero());

let prox_intersecting = query::proximity(&ball_pos_intersecting, &ball,
                                         &cuboid_pos,            &cuboid,
                                         margin);
let prox_within_margin = query::proximity(&ball_pos_within_margin, &ball,
                                          &cuboid_pos,             &cuboid,
                                          margin);
let prox_disjoint = query::proximity(&ball_pos_disjoint, &ball,
                                     &cuboid_pos,        &cuboid,
                                     margin);

assert_eq!(prox_intersecting, Proximity::Intersecting);
assert_eq!(prox_within_margin, Proximity::WithinMargin);
assert_eq!(prox_disjoint, Proximity::Disjoint);

let cuboid = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let ball   = Ball::new(1.0);
let margin = 1.0;

let cuboid_pos             = na::one();
let ball_pos_intersecting  = Isometry3::new(Vector3::new(1.0, 1.0, 1.0), na::zero());
let ball_pos_within_margin = Isometry3::new(Vector3::new(2.0, 2.0, 2.0), na::zero());
let ball_pos_disjoint      = Isometry3::new(Vector3::new(3.0, 3.0, 3.0), na::zero());

let prox_intersecting = query::proximity(&ball_pos_intersecting, &ball,
                                         &cuboid_pos,            &cuboid,
                                         margin);
let prox_within_margin = query::proximity(&ball_pos_within_margin, &ball,
                                          &cuboid_pos,             &cuboid,
                                          margin);
let prox_disjoint = query::proximity(&ball_pos_disjoint, &ball,
                                     &cuboid_pos,        &cuboid,
                                     margin);

assert_eq!(prox_intersecting, Proximity::Intersecting);
assert_eq!(prox_within_margin, Proximity::WithinMargin);
assert_eq!(prox_disjoint, Proximity::Disjoint);

Distance§

The minimal distance between two shapes g1 and g2, respectively transformed by m1 and m2, can be computed by query::distance(m1, g1, m2, g2). This will return a positive value if the objects are not intersecting and zero otherwise. The following example computes the distance between a cube and a sphere.

• 2D example
• 3D example

let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));
let ball   = Ball::new(1.0);

let cuboid_pos             = na::one();
let ball_pos_intersecting  = Isometry2::new(Vector2::y(), na::zero());
let ball_pos_disjoint      = Isometry2::new(Vector2::y() * 3.0, na::zero());

let dist_intersecting = query::distance(&ball_pos_intersecting, &ball,
                                        &cuboid_pos,            &cuboid);
let dist_disjoint     = query::distance(&ball_pos_disjoint, &ball,
                                        &cuboid_pos,        &cuboid);

assert_eq!(dist_intersecting, 0.0);
assert!(relative_eq!(dist_disjoint, 1.0, epsilon = 1.0e-7));

let cuboid = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let ball   = Ball::new(1.0);

let cuboid_pos             = na::one();
let ball_pos_intersecting  = Isometry3::new(Vector3::y(), na::zero());
let ball_pos_disjoint      = Isometry3::new(Vector3::y() * 3.0, na::zero());

let dist_intersecting = query::distance(&ball_pos_intersecting, &ball,
                                        &cuboid_pos,            &cuboid);
let dist_disjoint     = query::distance(&ball_pos_disjoint, &ball,
                                        &cuboid_pos,        &cuboid);

assert_eq!(dist_intersecting, 0.0);
assert!(relative_eq!(dist_disjoint, 1.0, epsilon = 1.0e-7));

Contact§

Contact determination is the core feature of any collision detection library. The function query::contact(m1, g1, m2, g2, prediction) will compute one pair of closest points between two objects if they are penetrating, touching, or separated by a distance smaller than prediction. If the shapes are concave or in conforming contact, you may need multiple contact points instead. This can be achieved by persistent contact generation structures. In any cases, a contact is described by the Contact structure:

Here, absolute coordinate system is the set of axises that are not relative to any object. The last depth field requires some details. Sometimes, the objects in contact are penetrating each other. Notably, if you are using ncollide within the context of physics simulation, penetrations are unrealistic configurations where the inside of the two objects are overlapping. This can be described geometrically in several forms including the penetration volume (left) or the minimal translational distance (right):

ncollide implements the latter: the minimal translational distance, also known as the penetration depth. This is the smallest translation along the contact normal needed to make both shapes touch each other without overlap. Therefore, the contact depth field is set to a positive value if the objects are penetrating. If they are disjoint but closer than prediction, the depth field is set to a negative value corresponding to the signed distance separating both objects along the contact normal.

The following example depicts three configurations where the shapes are either penetrating, separated by a distance smaller, or larger, than the prediction parameter set to 1.0.

• 2D example
• 3D example

let cuboid     = Cuboid::new(Vector2::new(1.0, 1.0));
let ball       = Ball::new(1.0);
let prediction = 1.0;

let cuboid_pos             = na::one();
let ball_pos_penetrating   = Isometry2::new(Vector2::new(1.0, 1.0), na::zero());
let ball_pos_in_prediction = Isometry2::new(Vector2::new(2.0, 2.0), na::zero());
let ball_pos_too_far       = Isometry2::new(Vector2::new(3.0, 3.0), na::zero());

let ctct_penetrating = query::contact(&ball_pos_penetrating, &ball,
                                      &cuboid_pos,           &cuboid,
                                      prediction);
let ctct_in_prediction = query::contact(&ball_pos_in_prediction, &ball,
                                        &cuboid_pos,             &cuboid,
                                        prediction);
let ctct_too_far = query::contact(&ball_pos_too_far, &ball,
                                  &cuboid_pos,       &cuboid,
                                  prediction);

assert!(ctct_penetrating.unwrap().depth > 0.0);
assert!(ctct_in_prediction.unwrap().depth < 0.0);
assert_eq!(ctct_too_far, None);

let cuboid     = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let ball       = Ball::new(1.0);
let prediction = 1.0;

let cuboid_pos             = na::one();
let ball_pos_penetrating   = Isometry3::new(Vector3::new(1.0, 1.0, 1.0), na::zero());
let ball_pos_in_prediction = Isometry3::new(Vector3::new(2.0, 2.0, 2.0), na::zero());
let ball_pos_too_far       = Isometry3::new(Vector3::new(3.0, 3.0, 3.0), na::zero());

let ctct_penetrating = query::contact(&ball_pos_penetrating, &ball,
                                      &cuboid_pos,           &cuboid,
                                      prediction);
let ctct_in_prediction = query::contact(&ball_pos_in_prediction, &ball,
                                        &cuboid_pos,             &cuboid,
                                        prediction);
let ctct_too_far = query::contact(&ball_pos_too_far, &ball,
                                  &cuboid_pos,       &cuboid,
                                  prediction);

assert!(ctct_penetrating.unwrap().depth > 0.0);
assert!(ctct_in_prediction.unwrap().depth < 0.0);
assert_eq!(ctct_too_far, None);

Time of impact§

The time of impact − aka. $\mathit{toi}$ − returned by query::time_of_impact(m1, v1, g1, m2, v2, g2) is the time it would take g1 and g2 to touch if they both move with linear velocities v1 and v2 starting with the positions and orientations given by m1 and m2. This is commonly used for, e.g., continuous collision detection to avoid tunnelling effects on physics engines: objects that traverse each other in-between iterations if they are moving too fast or if the simulation time step is too large.

The following example depicts the three possible scenarios:

1. The shapes are already touching at their original positions, i.e., at time $\mathit{toi} = 0$.
2. The shapes start intersecting at some time $\mathit{toi} > 0$. This means that g1 and g2 start touching at the positions m1.append_translation(&(v1 * toi)) and m2.append_translation(&(v2 * toi)).
3. The shapes will never intersect. In this case None is returned.

• 2D example
• 3D example

let cuboid = Cuboid::new(Vector2::new(1.0, 1.0));
let ball   = Ball::new(1.0);

let cuboid_pos            = na::one();
let ball_pos_intersecting = Isometry2::new(Vector2::new(1.0, 1.0), na::zero());
let ball_pos_will_touch   = Isometry2::new(Vector2::new(2.0, 2.0), na::zero());
let ball_pos_wont_touch   = Isometry2::new(Vector2::new(3.0, 3.0), na::zero());

let box_vel1 = Vector2::new(-1.0, 1.0);
let box_vel2 = Vector2::new(1.0, 1.0);

let ball_vel1 = Vector2::new(2.0, 2.0);
let ball_vel2 = Vector2::new(-0.5, -0.5);

let toi_intersecting = query::time_of_impact(&ball_pos_intersecting, &ball_vel1, &ball,
                                             &cuboid_pos,            &box_vel1,  &cuboid);
let toi_will_touch = query::time_of_impact(&ball_pos_will_touch, &ball_vel2, &ball,
                                           &cuboid_pos,          &box_vel2,  &cuboid);
let toi_wont_touch = query::time_of_impact(&ball_pos_wont_touch, &ball_vel1, &ball,
                                           &cuboid_pos,          &box_vel1,  &cuboid);

assert_eq!(toi_intersecting, Some(0.0));
assert!(toi_will_touch.is_some() && toi_will_touch.unwrap() > 0.0);
assert_eq!(toi_wont_touch, None);

let cuboid = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let ball   = Ball::new(1.0);

let cuboid_pos            = na::one();
let ball_pos_intersecting = Isometry3::new(Vector3::new(1.0, 1.0, 1.0), na::zero());
let ball_pos_will_touch   = Isometry3::new(Vector3::new(2.0, 2.0, 2.0), na::zero());
let ball_pos_wont_touch   = Isometry3::new(Vector3::new(3.0, 3.0, 3.0), na::zero());

let box_vel1 = Vector3::new(-1.0, 1.0, 1.0);
let box_vel2 = Vector3::new(1.0, 1.0, 1.0);

let ball_vel1 = Vector3::new(2.0, 2.0, 2.0);
let ball_vel2 = Vector3::new(-0.5, -0.5, -0.5);

let toi_intersecting = query::time_of_impact(&ball_pos_intersecting, &ball_vel1, &ball,
                                             &cuboid_pos,            &box_vel1,  &cuboid);
let toi_will_touch = query::time_of_impact(&ball_pos_will_touch, &ball_vel2, &ball,
                                           &cuboid_pos,          &box_vel2,  &cuboid);
let toi_wont_touch = query::time_of_impact(&ball_pos_wont_touch, &ball_vel1, &ball,
                                           &cuboid_pos,          &box_vel1,  &cuboid);

assert_eq!(toi_intersecting, Some(0.0));
assert!(toi_will_touch.is_some() && toi_will_touch.unwrap() > 0.0);
assert_eq!(toi_wont_touch, None);