First working version of non-linear CCD based on single-substep motion-clamping.

29 files changed, 695 insertions, 108 deletions

diff --git a/Cargo.toml b/Cargo.toml
index b6ae4da..cfdb3ba 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -19,10 +19,10 @@ members = [ "build/rapier2d", "build/rapier2d-f64", "build/rapier_testbed2d", "e
 
 #kiss3d = { git = "https://github.com/sebcrozet/kiss3d" }
 #nalgebra = { git = "https://github.com/dimforge/nalgebra", branch = "dev" }
-#parry2d = { git = "https://github.com/dimforge/parry" }
-#parry3d = { git = "https://github.com/dimforge/parry" }
-#parry2d-f64 = { git = "https://github.com/dimforge/parry" }
-#parry3d-f64 = { git = "https://github.com/dimforge/parry" }
+parry2d = { git = "https://github.com/dimforge/parry", branch = "special_cases" }
+parry3d = { git = "https://github.com/dimforge/parry", branch = "special_cases" }
+parry2d-f64 = { git = "https://github.com/dimforge/parry", branch = "special_cases" }
+parry3d-f64 = { git = "https://github.com/dimforge/parry", branch = "special_cases" }
 #ncollide2d = { git = "https://github.com/dimforge/ncollide" }
 #ncollide3d = { git = "https://github.com/dimforge/ncollide" }
 #nphysics2d = { git = "https://github.com/dimforge/nphysics" }
diff --git a/benchmarks3d/all_benchmarks3.rs b/benchmarks3d/all_benchmarks3.rs
index f35cb8e..38d71cd 100644
--- a/benchmarks3d/all_benchmarks3.rs
+++ b/benchmarks3d/all_benchmarks3.rs
@@ -13,6 +13,7 @@ use std::cmp::Ordering;
 mod balls3;
 mod boxes3;
 mod capsules3;
+mod ccd3;
 mod compound3;
 mod convex_polyhedron3;
 mod heightfield3;
@@ -52,6 +53,7 @@ pub fn main() {
         ("Balls", balls3::init_world),
         ("Boxes", boxes3::init_world),
         ("Capsules", capsules3::init_world),
+        ("CCD", ccd3::init_world),
         ("Compound", compound3::init_world),
         ("Convex polyhedron", convex_polyhedron3::init_world),
         ("Heightfield", heightfield3::init_world),
diff --git a/benchmarks3d/ccd3.rs b/benchmarks3d/ccd3.rs
new file mode 100644
index 0000000..f1831e7
--- /dev/null
+++ b/benchmarks3d/ccd3.rs
@@ -0,0 +1,85 @@
+use na::Point3;
+use rapier3d::dynamics::{JointSet, RigidBodyBuilder, RigidBodySet};
+use rapier3d::geometry::{ColliderBuilder, ColliderSet};
+use rapier_testbed3d::Testbed;
+
+pub fn init_world(testbed: &mut Testbed) {
+    /*
+     * World
+     */
+    let mut bodies = RigidBodySet::new();
+    let mut colliders = ColliderSet::new();
+    let joints = JointSet::new();
+
+    /*
+     * Ground
+     */
+    let ground_size = 100.1;
+    let ground_height = 0.1;
+
+    let rigid_body = RigidBodyBuilder::new_static()
+        .translation(0.0, -ground_height, 0.0)
+        .build();
+    let handle = bodies.insert(rigid_body);
+    let collider = ColliderBuilder::cuboid(ground_size, ground_height, ground_size).build();
+    colliders.insert(collider, handle, &mut bodies);
+
+    /*
+     * Create the cubes
+     */
+    let num = 4;
+    let numj = 20;
+    let rad = 1.0;
+
+    let shiftx = rad * 2.0 + rad;
+    let shifty = rad * 2.0 + rad;
+    let shiftz = rad * 2.0 + rad;
+    let centerx = shiftx * (num / 2) as f32;
+    let centery = shifty / 2.0;
+    let centerz = shiftz * (num / 2) as f32;
+
+    let mut offset = -(num as f32) * (rad * 2.0 + rad) * 0.5;
+
+    for j in 0usize..numj {
+        for i in 0..num {
+            for k in 0usize..num {
+                let x = i as f32 * shiftx - centerx + offset;
+                let y = j as f32 * shifty + centery + 3.0;
+                let z = k as f32 * shiftz - centerz + offset;
+
+                // Build the rigid body.
+                let rigid_body = RigidBodyBuilder::new_dynamic()
+                    .translation(x, y, z)
+                    .linvel(0.0, -1000.0, 0.0)
+                    .ccd_enabled(true)
+                    .build();
+                let handle = bodies.insert(rigid_body);
+
+                let collider = match j % 5 {
+                    0 => ColliderBuilder::cuboid(rad, rad, rad),
+                    1 => ColliderBuilder::ball(rad),
+                    // Rounded cylinders are much more efficient that cylinder, even if the
+                    // rounding margin is small.
+                    // 2 => ColliderBuilder::round_cylinder(rad, rad, rad / 10.0),
+                    // 3 => ColliderBuilder::cone(rad, rad),
+                    _ => ColliderBuilder::capsule_y(rad, rad),
+                };
+
+                colliders.insert(collider.build(), handle, &mut bodies);
+            }
+        }
+
+        offset -= 0.05 * rad * (num as f32 - 1.0);
+    }
+
+    /*
+     * Set up the testbed.
+     */
+    testbed.set_world(bodies, colliders, joints);
+    testbed.look_at(Point3::new(100.0, 100.0, 100.0), Point3::origin());
+}
+
+fn main() {
+    let testbed = Testbed::from_builders(0, vec![("Boxes", init_world)]);
+    testbed.run()
+}
diff --git a/examples2d/all_examples2.rs b/examples2d/all_examples2.rs
index f4430aa..8f38ced 100644
--- a/examples2d/all_examples2.rs
+++ b/examples2d/all_examples2.rs
@@ -11,6 +11,7 @@ use rapier_testbed2d::Testbed;
 use std::cmp::Ordering;
 
 mod add_remove2;
+mod ccd2;
 mod collision_groups2;
 mod convex_polygons2;
 mod damping2;
@@ -60,6 +61,7 @@ pub fn main() {
 
     let mut builders: Vec<(_, fn(&mut Testbed))> = vec![
         ("Add remove", add_remove2::init_world),
+        ("CCD", ccd2::init_world),
         ("Collision groups", collision_groups2::init_world),
         ("Convex polygons", convex_polygons2::init_world),
         ("Damping", damping2::init_world),
diff --git a/examples3d/all_examples3.rs b/examples3d/all_examples3.rs
index a8c38c6..8122583 100644
--- a/examples3d/all_examples3.rs
+++ b/examples3d/all_examples3.rs
@@ -10,6 +10,7 @@ use inflector::Inflector;
 use rapier_testbed3d::Testbed;
 use std::cmp::Ordering;
 
+mod ccd3;
 mod collision_groups3;
 mod compound3;
 mod convex_decomposition3;
@@ -77,6 +78,7 @@ pub fn main() {
     let mut builders: Vec<(_, fn(&mut Testbed))> = vec![
         ("Fountain", fountain3::init_world),
         ("Primitives", primitives3::init_world),
+        ("CCD", ccd3::init_world),
         ("Collision groups", collision_groups3::init_world),
         ("Compound", compound3::init_world),
         ("Convex decomposition", convex_decomposition3::init_world),
diff --git a/examples3d/ccd3.rs b/examples3d/ccd3.rs
new file mode 100644
index 0000000..b62427f
--- /dev/null
+++ b/examples3d/ccd3.rs
@@ -0,0 +1,145 @@
+use na::{Isometry3, Point3, Vector3};
+use rapier3d::dynamics::{JointSet, RigidBodyBuilder, RigidBodySet};
+use rapier3d::geometry::{ColliderBuilder, ColliderSet};
+use rapier_testbed3d::Testbed;
+
+fn create_wall(
+    testbed: &mut Testbed,
+    bodies: &mut RigidBodySet,
+    colliders: &mut ColliderSet,
+    offset: Vector3<f32>,
+    stack_height: usize,
+    half_extents: Vector3<f32>,
+) {
+    let shift = half_extents * 2.0;
+    for i in 0usize..stack_height {
+        for j in i..stack_height {
+            let fj = j as f32;
+            let fi = i as f32;
+            let x = offset.x;
+            let y = fi * shift.y + offset.y;
+            let z = (fi * shift.z / 2.0) + (fj - fi) * shift.z + offset.z
+                - stack_height as f32 * half_extents.z;
+
+            // Build the rigid body.
+            let rigid_body = RigidBodyBuilder::new_dynamic().translation(x, y, z).build();
+            let handle = bodies.insert(rigid_body);
+            let collider =
+                ColliderBuilder::cuboid(half_extents.x, half_extents.y, half_extents.z).build();
+            colliders.insert(collider, handle, bodies);
+            testbed.set_body_color(handle, Point3::new(218. / 255., 201. / 255., 1.0));
+        }
+    }
+}
+
+pub fn init_world(testbed: &mut Testbed) {
+    /*
+     * World
+     */
+    let mut bodies = RigidBodySet::new();
+    let mut colliders = ColliderSet::new();
+    let joints = JointSet::new();
+
+    /*
+     * Ground
+     */
+    let ground_size = 50.0;
+    let ground_height = 0.1;
+
+    let rigid_body = RigidBodyBuilder::new_static()
+        .translation(0.0, -ground_height, 0.0)
+        .build();
+    let ground_handle = bodies.insert(rigid_body);
+    let collider = ColliderBuilder::cuboid(ground_size, ground_height, ground_size).build();
+    colliders.insert(collider, ground_handle, &mut bodies);
+
+    /*
+     * Create the pyramids.
+     */
+    let num_z = 8;
+    let num_x = 5;
+    let shift_y = ground_height + 0.5;
+    let shift_z = (num_z as f32 + 2.0) * 2.0;
+
+    for i in 0..num_x {
+        let x = i as f32 * 6.0;
+        create_wall(
+            testbed,
+            &mut bodies,
+            &mut colliders,
+            Vector3::new(x, shift_y, 0.0),
+            num_z,
+            Vector3::new(0.5, 0.5, 1.0),
+        );
+
+        create_wall(
+            testbed,
+            &mut bodies,
+            &mut colliders,
+            Vector3::new(x, shift_y, shift_z),
+            num_z,
+            Vector3::new(0.5, 0.5, 1.0),
+        );
+    }
+
+    /*
+     * Create two very fast rigid-bodies.
+     * The first one has CCD enabled and a sensor collider attached to it.
+     * The second one has CCD enabled and a collider attached to it.
+     */
+    let collider = ColliderBuilder::ball(1.0)
+        .density(10.0)
+        .sensor(true)
+        .build();
+    let mut rigid_body = RigidBodyBuilder::new_dynamic()
+        .linvel(1000.0, 0.0, 0.0)
+        .translation(-20.0, shift_y + 2.0, 0.0)
+        .ccd_enabled(true)
+        .build();
+    let sensor_handle = bodies.insert(rigid_body);
+    colliders.insert(collider, sensor_handle, &mut bodies);
+
+    // Second rigid-body with CCD enabled.
+    let collider = ColliderBuilder::ball(1.0).density(10.0).build();
+    let mut rigid_body = RigidBodyBuilder::new_dynamic()
+        .linvel(1000.0, 0.0, 0.0)
+        .translation(-20.0, shift_y + 2.0, shift_z)
+        .ccd_enabled(true)
+        .build();
+    let handle = bodies.insert(rigid_body);
+    colliders.insert(collider.clone(), handle, &mut bodies);
+
+    // Callback that will be executed on the main loop to handle proximities.
+    testbed.add_callback(move |_, mut graphics, physics, events, _| {
+        while let Ok(prox) = events.intersection_events.try_recv() {
+            let color = if prox.intersecting {
+                Point3::new(1.0, 1.0, 0.0)
+            } else {
+                Point3::new(0.5, 0.5, 1.0)
+            };
+
+            let parent_handle1 = physics.colliders.get(prox.collider1).unwrap().parent();
+            let parent_handle2 = physics.colliders.get(prox.collider2).unwrap().parent();
+
+            if let Some(graphics) = &mut graphics {
+                if parent_handle1 != ground_handle && parent_handle1 != sensor_handle {
+                    graphics.set_body_color(parent_handle1, color);
+                }
+                if parent_handle2 != ground_handle && parent_handle2 != sensor_handle {
+                    graphics.set_body_color(parent_handle2, color);
+                }
+            }
+        }
+    });
+
+    /*
+     * Set up the testbed.
+     */
+    testbed.set_world(bodies, colliders, joints);
+    testbed.look_at(Point3::new(100.0, 100.0, 100.0), Point3::origin());
+}
+
+fn main() {
+    let testbed = Testbed::from_builders(0, vec![("Boxes", init_world)]);
+    testbed.run()
+}
diff --git a/src/data/coarena.rs b/src/data/coarena.rs
index 78cbfa7..c25cc55 100644
--- a/src/data/coarena.rs
+++ b/src/data/coarena.rs
@@ -29,6 +29,20 @@ impl<T> Coarena<T> {
             .and_then(|(gg, t)| if g == *gg { Some(t) } else { None })
     }
 
+    /// Inserts an element into this coarena.
+    pub fn insert(&mut self, a: Index, value: T)
+    where
+        T: Clone + Default,
+    {
+        let (i1, g1) = a.into_raw_parts();
+
+        if self.data.len() <= i1 {
+            self.data.resize(i1 + 1, (u32::MAX as u64, T::default()));
+        }
+
+        self.data[i1] = (g1, value);
+    }
+
     /// Ensure that elements at the two given indices exist in this coarena, and return their reference.
     ///
     /// Missing elements are created automatically and initialized with the `default` value.
diff --git a/src/dynamics/ccd/toi_entry.rs b/src/dynamics/ccd/toi_entry.rs
new file mode 100644
index 0000000..20f5268
--- /dev/null
+++ b/src/dynamics/ccd/toi_entry.rs
@@ -0,0 +1,147 @@
+use crate::data::Coarena;
+use crate::dynamics::ccd::ccd_solver::CCDContact;
+use crate::dynamics::ccd::CCDData;
+use crate::dynamics::{IntegrationParameters, RigidBody, RigidBodyHandle};
+use crate::geometry::{Collider, ColliderHandle};
+use crate::math::{Isometry, Real};
+use crate::parry::query::PersistentQueryDispatcher;
+use crate::utils::WCross;
+use na::{RealField, Unit};
+use parry::query::{NonlinearRigidMotion, QueryDispatcher, TOI};
+
+#[derive(Copy, Clone, Debug)]
+pub struct TOIEntry {
+    pub toi: Real,
+    pub c1: ColliderHandle,
+    pub b1: RigidBodyHandle,
+    pub c2: ColliderHandle,
+    pub b2: RigidBodyHandle,
+    pub is_intersection_test: bool,
+    pub timestamp: usize,
+}
+
+impl TOIEntry {
+    fn new(
+        toi: Real,
+        c1: ColliderHandle,
+        b1: RigidBodyHandle,
+        c2: ColliderHandle,
+        b2: RigidBodyHandle,
+        is_intersection_test: bool,
+        timestamp: usize,
+    ) -> Self {
+        Self {
+            toi,
+            c1,
+            b1,
+            c2,
+            b2,
+            is_intersection_test,
+            timestamp,
+        }
+    }
+
+    pub fn try_from_colliders<QD: ?Sized + PersistentQueryDispatcher<(), ()>>(
+        params: &IntegrationParameters,
+        query_dispatcher: &QD,
+        ch1: ColliderHandle,
+        ch2: ColliderHandle,
+        c1: &Collider,
+        c2: &Collider,
+        b1: &RigidBody,
+        b2: &RigidBody,
+        frozen1: Option<Real>,
+        frozen2: Option<Real>,
+        start_time: Real,
+        end_time: Real,
+        body_params: &Coarena<CCDData>,
+    ) -> Option<Self> {
+        assert!(start_time <= end_time);
+
+        let linvel1 = frozen1.is_none() as u32 as Real * b1.linvel;
+        let linvel2 = frozen2.is_none() as u32 as Real * b2.linvel;
+
+        let vel12 = linvel2 - linvel1;
+        let thickness = (c1.shape().ccd_thickness() + c2.shape().ccd_thickness());
+
+        if params.dt * vel12.norm() < thickness {
+            return None;
+        }
+
+        let is_intersection_test = c1.is_sensor() || c2.is_sensor();
+
+        let body_params1 = body_params.get(c1.parent.0)?;
+        let body_params2 = body_params.get(c2.parent.0)?;
+
+        // Compute the TOI.
+        let mut motion1 = body_params1.motion(params.dt, b1, 0.0);
+        let mut motion2 = body_params2.motion(params.dt, b2, 0.0);
+
+        if let Some(t) = frozen1 {
+            motion1.freeze(t);
+        }
+
+        if let Some(t) = frozen2 {
+            motion2.freeze(t);
+        }
+
+        let mut toi;
+        let motion_c1 = motion1.prepend(*c1.position_wrt_parent());
+        let motion_c2 = motion2.prepend(*c2.position_wrt_parent());
+
+        // println!("start_time: {}", start_time);
+
+        // If this is just an intersection test (i.e. with sensors)
+        // then we can stop the TOI search immediately if it starts with
+        // a penetration because we don't care about the whether the velocity
+        // at the impact is a separating velocity or not.
+        // If the TOI search involves two non-sensor colliders then
+        // we don't want to stop the TOI search at the first penetration
+        // because the colliders may be in a separating trajectory.
+        let stop_at_penetration = is_intersection_test;
+
+        let res_toi = query_dispatcher
+            .nonlinear_time_of_impact(
+                &motion_c1,
+                c1.shape(),
+                &motion_c2,
+                c2.shape(),
+                start_time,
+                end_time,
+                stop_at_penetration,
+            )
+            .ok();
+
+        toi = res_toi??;
+
+        Some(Self::new(
+            toi.toi,
+            ch1,
+            c1.parent(),
+            ch2,
+            c2.parent(),
+            is_intersection_test,
+            0,
+        ))
+    }
+}
+
+impl PartialOrd for TOIEntry {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        (-self.toi).partial_cmp(&(-other.toi))
+    }
+}
+
+impl Ord for TOIEntry {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.partial_cmp(other).unwrap()
+    }
+}
+
+impl PartialEq for TOIEntry {
+    fn eq(&self, other: &Self) -> bool {
+        self.toi == other.toi
+    }
+}
+
+impl Eq for TOIEntry {}
diff --git a/src/dynamics/mod.rs b/src/dynamics/mod.rs
index eab6916..751f6f9 100644
--- a/src/dynamics/mod.rs
+++ b/src/dynamics/mod.rs
@@ -18,6 +18,7 @@ pub use self::rigid_body::{ActivationStatus, BodyStatus, RigidBody, RigidBodyBui
 pub use self::rigid_body_set::{BodyPair, RigidBodyHandle, RigidBodySet};
 pub use parry::mass_properties::MassProperties;
 // #[cfg(not(feature = "parallel"))]
+pub use self::ccd::CCDSolver;
 pub use self::coefficient_combine_rule::CoefficientCombineRule;
 pub(crate) use self::joint::JointGraphEdge;
 pub(crate) use self::rigid_body::RigidBodyChanges;
@@ -26,6 +27,7 @@ pub(crate) use self::solver::IslandSolver;
 #[cfg(feature = "parallel")]
 pub(crate) use self::solver::ParallelIslandSolver;
 
+mod ccd;
 mod coefficient_combine_rule;
 mod integration_parameters;
 mod joint;
diff --git a/src/dynamics/rigid_body.rs b/src/dynamics/rigid_body.rs
index 7cc7a99..9ac4763 100644
--- a/src/dynamics/rigid_body.rs
+++ b/src/dynamics/rigid_body.rs
@@ -36,6 +36,7 @@ bitflags::bitflags! {
         const ROTATION_LOCKED_X = 1 << 1;
         const ROTATION_LOCKED_Y = 1 << 2;
         const ROTATION_LOCKED_Z = 1 << 3;
+        const CCD_ENABLED = 1 << 4;
     }
 }
 
@@ -58,7 +59,16 @@ bitflags::bitflags! {
 pub struct RigidBody {
     /// The world-space position of the rigid-body.
     pub(crate) position: Isometry<Real>,
-    pub(crate) predicted_position: Isometry<Real>,
+    /// The next position of the rigid-body.
+    ///
+    /// At the beginning of the timestep, and when the
+    /// timestep is complete we must have position == next_position
+    /// except for kinematic bodies.
+    ///
+    /// The next_position is updated after the velocity and position
+    /// resolution. Then it is either validated (ie. we set position := set_position)
+    /// or clamped by CCD.
+    pub(crate) next_position: Isometry<Real>,
     /// The local mass properties of the rigid-body.
     pub(crate) mass_properties: MassProperties,
     /// The world-space center of mass of the rigid-body.
@@ -76,6 +86,10 @@ pub struct RigidBody {
     pub linear_damping: Real,
     /// Damping factor for gradually slowing down the angular motion of the rigid-body.
     pub angular_damping: Real,
+    /// The maximum linear velocity this rigid-body can reach.
+    pub max_linear_velocity: Real,
+    /// The maximum angular velocity this rigid-body can reach.
+    pub max_angular_velocity: Real,
     /// Accumulation of external forces (only for dynamic bodies).
     pub(crate) force: Vector<Real>,
     /// Accumulation of external torques (only for dynamic bodies).
@@ -97,13 +111,14 @@ pub struct RigidBody {
     dominance_group: i8,
     /// User-defined data associated to this rigid-body.
     pub user_data: u128,
+    pub(crate) ccd_thickness: Real,
 }
 
 impl RigidBody {
     fn new() -> Self {
         Self {
             position: Isometry::identity(),
-            predicted_position: Isometry::identity(),
+            next_position: Isometry::identity(),
             mass_properties: MassProperties::zero(),
             world_com: Point::origin(),
             effective_inv_mass: 0.0,
@@ -115,6 +130,8 @@ impl RigidBody {
             gravity_scale: 1.0,
             linear_damping: 0.0,
             angular_damping: 0.0,
+            max_linear_velocity: Real::MAX,
+            max_angular_velocity: 100.0,
             colliders: Vec::new(),
             activation: ActivationStatus::new_active(),
             joint_graph_index: InteractionGraph::<(), ()>::invalid_graph_index(),
@@ -127,6 +144,7 @@ impl RigidBody {
             body_status: BodyStatus::Dynamic,
             dominance_group: 0,
             user_data: 0,
+            ccd_thickness: Real::MAX,
         }
     }
 
@@ -176,6 +194,20 @@ impl RigidBody {
         }
     }
 
+    /// Enables of disable CCD (continuous collision-detection) for this rigid-body.
+    pub fn enable_ccd(&mut self, enabled: bool) {
+        self.flags.set(RigidBodyFlags::CCD_ENABLED, enabled)
+    }
+
+    /// Is CCD (continous collision-detection) enabled for this rigid-body?
+    pub fn is_ccd_enabled(&self) -> bool {
+        self.flags.contains(RigidBodyFlags::CCD_ENABLED)
+    }
+
+    pub(crate) fn should_resolve_ccd(&self, dt: Real) -> bool {
+        self.is_ccd_enabled() && self.is_dynamic() && self.linvel.norm() * dt > self.ccd_thickness
+    }
+
     /// Sets the rigid-body's mass properties.
     ///
     /// If `wake_up` is `true` then the rigid-body will be woken up if it was
@@ -228,8 +260,8 @@ impl RigidBody {
     /// If this rigid-body is kinematic this value is set by the `set_next_kinematic_position`
     /// method and is used for estimating the kinematic body velocity at the next timestep.
     /// For non-kinematic bodies, this value is currently unspecified.
-    pub fn predicted_position(&self) -> &Isometry<Real> {
-        &self.predicted_position
+    pub fn next_position(&self) -> &Isometry<Real> {
+        &self.next_position
     }
 
     /// The scale factor applied to the gravity affecting this rigid-body.
@@ -254,6 +286,8 @@ impl RigidBody {
             true,
         );
 
+        self.ccd_thickness = self.ccd_thickness.min(coll.shape().ccd_thickness());
+
         let mass_properties = coll
             .mass_properties()
             .transform_by(coll.position_wrt_parent());
@@ -265,8 +299,8 @@ impl RigidBody {
     pub(crate) fn update_colliders_positions(&mut self, colliders: &mut ColliderSet) {
         for handle in &self.colliders {
             let collider = &mut colliders[*handle];
+            collider.prev_position = self.position;
             collider.position = self.position * collider.delta;
-            collider.predicted_position = self.predicted_position * collider.delta;
         }
     }
 
@@ -331,18 +365,39 @@ impl RigidBody {
         !self.linvel.is_zero() || !self.angvel.is_zero()
     }
 
-    fn integrate_velocity(&self, dt: Real) -> Isometry<Real> {
+    pub(crate) fn integrate_velocity(&self, dt: Real) -> Isometry<Real> {
         let com = self.position * self.mass_properties.local_com;
         let shift = Translation::from(com.coords);
         shift * Isometry::new(self.linvel * dt, self.angvel * dt) * shift.inverse()
     }
 
-    pub(crate) fn integrate(&mut self, dt: Real) {
+    pub(crate) fn position_at_time(&self, dt: Real) -> Isometry<Real> {
+        self.integrate_velocity(dt) * self.position
+    }
+
+    pub(crate) fn integrate_next_position(&mut self, dt: Real, apply_damping: bool) {
         // TODO: do we want to apply damping before or after the velocity integration?
-        self.linvel *= 1.0 / (1.0 + dt * self.linear_damping);
-        self.angvel *= 1.0 / (1.0 + dt * self.angular_damping);
+        if apply_damping {
+            self.linvel *= 1.0 / (1.0 + dt * self.linear_damping);
+            self.angvel *= 1.0 / (1.0 + dt * self.angular_damping);
+
+            // self.linvel = self.linvel.cap_magnitude(self.max_linear_velocity);
+            // #[cfg(feature = "dim2")]
+            // {
+            //     self.angvel = na::clamp(
+            //         self.angvel,
+            //         -self.max_angular_velocity,
+            //         self.max_angular_velocity,
+            //     );
+            // }
+            // #[cfg(feature = "dim3")]
+            // {
+            //     self.angvel = self.angvel.cap_magnitude(self.max_angular_velocity);
+            // }
+        }
 
-        self.position = self.integrate_velocity(dt) * self.position;
+        self.next_position = self.integrate_velocity(dt) * self.position;
+        let _ = self.next_position.rotation.renormalize();
     }
 
     /// The linear velocity of this rigid-body.
@@ -416,7 +471,8 @@ impl RigidBody {
     /// put to sleep because it did not move for a while.
     pub fn set_position(&mut self, pos: Isometry<Real>, wake_up: bool) {
         self.changes.insert(RigidBodyChanges::POSITION);
-        self.set_position_internal(pos);
+        self.position = pos;
+        self.next_position = pos;
 
         // TODO: Do we really need to check that the body isn't dynamic?
         if wake_up && self.is_dynamic() {
@@ -424,24 +480,19 @@ impl RigidBody {
         }
     }
 
-    pub(crate) fn set_position_internal(&mut self, pos: Isometry<Real>) {
-        self.position = pos;
-
-        // TODO: update the predicted position for dynamic bodies too?
-        if self.is_static() || self.is_kinematic() {
-            self.predicted_position = pos;
-        }
+    pub(crate) fn set_next_position(&mut self, pos: Isometry<Real>) {
+        self.next_position = pos;
     }
 
     /// If this rigid body is kinematic, sets its future position after the next timestep integration.
     pub fn set_next_kinematic_position(&mut self, pos: Isometry<Real>) {
         if self.is_kinematic() {
-            self.predicted_position = pos;
+            self.next_position = pos;
         }
     }
 
-    pub(crate) fn compute_velocity_from_predicted_position(&mut self, inv_dt: Real) {
-        let dpos = self.predicted_position * self.position.inverse();
+    pub(crate) fn compute_velocity_from_next_position(&mut self, inv_dt: Real) {
+        let dpos = self.next_position * self.position.inverse();
         #[cfg(feature = "dim2")]
         {
             self.angvel = dpos.rotation.angle() * inv_dt;
@@ -453,8 +504,8 @@ impl RigidBody {
         self.linvel = dpos.translation.vector * inv_dt;
     }
 
-    pub(crate) fn update_predicted_position(&mut self, dt: Real) {
-        self.predicted_position = self.integrate_velocity(dt) * self.position;
+    pub(crate) fn update_next_position(&mut self, dt: Real) {
+        self.next_position = self.integrate_velocity(dt) * self.position;
     }
 
     pub(crate) fn update_world_mass_properties(&mut self) {
@@ -666,6 +717,7 @@ pub struct RigidBodyBuilder {
     mass_properties: MassProperties,
     can_sleep: bool,
     sleeping: bool,
+    ccd_enabled: bool,
     dominance_group: i8,
     user_data: u128,
 }
@@ -685,6 +737,7 @@ impl RigidBodyBuilder {
             mass_properties: MassProperties::zero(),
             can_sleep: true,
             sleeping: false,
+            ccd_enabled: false,
             dominance_group: 0,
             user_data: 0,
         }
@@ -888,6 +941,12 @@ impl RigidBodyBuilder {
         self
     }
 
+    /// Enabled continuous collision-detection for this rigid-body.
+    pub fn ccd_enabled(mut self, enabled: bool) -> Self {
+        self.ccd_enabled = enabled;
+        self
+    }
+
     /// Sets whether or not the rigid-body is to be created asleep.
     pub fn sleeping(mut self, sleeping: bool) -> Self {
         self.sleeping = sleeping;
@@ -897,8 +956,8 @@ impl RigidBodyBuilder {
     /// Build a new rigid-body with the parameters configured with this builder.
     pub fn build(&self) -> RigidBody {
         let mut rb = RigidBody::new();
-        rb.predicted_position = self.position; // FIXME: compute the co