This month in Dimforge #5 (Feb. 2021 - Mar. 2021)

Sébastien Crozet

Sébastien Crozet

Welcome to the fifth edition of This month in Dimforge! This newsletter provides you with a summary of important updates that occurred within the Dimforge community. This includes in particular updates about the Rapier (physics engine), Salva (fluid simulation), Parry (collision-detection), nalgebra (linear algebra), and Simba (abstract algebra) crates. This fifth edition will contain updates for the months of February and March 2021.

Help us sustain this work by sponsoring us on GitHub sponsors ♥
Join us on discord!

Announcing nalgebra-sparse 0.1 🎊

In February, we silently released a new crate: nalgebra-sparse. This new crate is a complete rewrite of sparse-matrix computations with nalgebra. It aims to completely replace the sparse module from the nalgebra crate. Here are the most significant features of that new crate:

  • CSR, CSC and COO formats, and conversions between them.
  • Common arithmetic operations are implemented: sparse addition, multiplication, and triangular solve.
  • Sparse Cholesky decomposition for CDC sparse matrices.

We thank Andreas Longva for his amazing work in this crate!

Announcing Rapier 0.7 ⚔️

The versions 0.6 (which we didn't communicate about) and 0.7 of Rapier come with very exciting new features! Here is a summary:

Joint motors

Joint motors allow you to make a joint move the rigid-bodies it is attached to by:

  • Choosing the relative velocity of the rigid-bodies along the joint's free degrees of freedoms.
  • Or choosing a desired relative position of the rigid-bodies, along the joints's free degrees of freedoms.

For example, you can set the target angular velocity, or the target angle of a RevoluteJoint. One typical use-case is to make a simulated car move by making the joint rotate its wheels.

The following illustrates examples of motorized ball joints, revolute joints, and prismatic joints:

joint motors

Dominance groups

Dominance groups is a non-physical feature that allows you to ignore Newton's third law of motion (force reciprocity) for chosen pairs of rigid-bodies.

Each dynamic rigid-body can be given a dominance group number in [-127; 127] (the default is 0). If two dynamic rigid-bodies are in contact, the one with the highest dominance group number will act as if it has an infinite mass, making it immune to the forces the other body would apply on it. If both bodies are have the same dominance group number, then their contacts will work in the usual way (both are affected by opposite forces with equal magnitude).

Dominance is a completely unrealistic feature. But it can be used to simulate specific effects in games. An example is the simulation of a player represented as a dynamic rigid-body that cannot be "pushed back" by some other dynamic rigid-bodies part of the environment.

Contact modification

Contact modification allows you to modify the properties of a contact (or completely delete a contact) after it has been computed by the narrow-phase, but before it reaches the constraints solver. Typical use-cases of contact modification are:

  • The simulation of conveyor belts by modifying the tangent_velocity field of a contact.
  • The simulation of one-way platforms by removing some contacts depending on their contact normal.
  • The simulation of materials with smooth friction/restitution coefficient variations by modifying the friction and/or restitution coefficient of a contact, bypassing the CoefficientCombineRule of the colliders involved in the contact.

The one-way platforms example illustrates the first two use-cases enumerated above. Both platforms act as conveyor belts (i.e. they move objects towards predefined directions), and both platforms are one-way platforms:

contact_modification

(Note that the gravity is set to opposite directions on both sides of the simulation to make it more interesting).

These contact modifications are possible thanks to the introduction of a new PhysicsHooks trait that defines methods called during a timestep to filter contact pairs, filter intersection pairs, and modify the contacts to be processed by the constraints solver.

Collider modification

Before Rapier 0.7, it wasn't possible to modify a collider after it was added to the ColliderSet. Therefore, changing a collider's shape, its position relative to the rigid-body it is attached to, or even changing its collision groups, was only possible by removing the collider and inserting a new one. That was both inconvenient and inefficient.

With Rapier 0.7, these modifications are now possible, and will automatically be taken into account by the physics engine.

Continuous collision detection

Fast moving bodies are generally difficult to simulate because the physics engine may not be able to detect some collisions. Indeed, the physics simulation operates by discretizing the motion of rigid-bodies at fixed time intervals (equal to the timestep length dt). Therefore, a fast-moving rigid-body may end up ignoring some contacts that would have happened in-between two discrete positions along this motion. This is known as the tunnelling problem.

The following example illustrates this problem. The blue and green balls are colliders attached to fast-moving rigid-bodies. The simulation is run step-by-step for clarity. It is clear that the blue ball is missing a lot of collisions, resulting in the pyramids not being hit at all! The green ball is a sensor configured in such a way that all the cubes it traverses are recolored in dark-blue. As you can see, only the pyramid at middle of the top row has some of its cubes recolored to dark-blue:

no CCD

Continuous collision detection (CCD) is a technique that aims to eliminate this tunnelling problem. CCD will take into account the actual continuous motion of the rigid-bodies (and their colliders) in order to detect every single contact that must happen in their continuous trajectory. With CCD enabled, the example above behaves as we would expect: the blue collider destroys the pyramids, the green sensor recolors in dark-blue all the cubes it encounters on its continuous path:

CCD

The CCD implementation in Rapier:

  • Is non-linear because it takes into account both the translational and the rotational movements of the rigid-bodies/colliders with CCD enabled. Most other physics engines use linear CCD which is slightly more efficient but yields less realistic results (because rotation are ignored).
  • Works for colliders and sensor colliders (many other physics engines don't support CCD for sensors).
  • Relies on motion clamping. It means that CCD will find the first time of impact between a fast-moving collider and all the other colliders. The fast-moving rigid-body will be advanced to that time of impact, and all the remaining time will be dropped for that rigid-body. In other words, its motion is "clamped" to the first time it hits something.

It is possible to let the CCD resolution run multiple simulation substeps (implying an increased computational cost) in order to reduce the amount of time removed by the clamping procedure.

Currently, our CCD implementation will work with all collider shapes except heightfields and halfspaces. Support for these two shape types will be added soon.

Large colliders support

Before Rapier 0.7, using a collider with a very large shape (for example a 1000x100x1000 3D heightfield) would result in extremely poor performances. This would make Rapier unusable in situations where large terrains were involved.

This is now fixed in Rapier 0.7 thanks to a massive improvement of the way our Broad-Phase algorithm (a variant of Sweep-And-Prune) handles these large shapes. This also means that shapes with virtually infinite bounds (like half-spaces, aka., planes) can now be used as collider shapes without any performance issue.

What's next

At the beginning of this year, we announced our 2021 roadmap for Rapier. So far we implemented and released all the features that were announced to be available in April, with the addition of joint motors. We have two main goals for next month:

  • Const generics (min_const_generics) is now stabilized. Therefore we intend to integrate it to nalgebra. This will allow us to use regular Rust arrays [T; DIM] parametrized by integers instead of GenericArrays parametrized by type-level integers from typenum.
  • Implement joint limits for the revolute joints and ball joints, allowing the user to restrict the range of possible relative orientation of the rigid-bodies attached by these joints. Joint limits are already implemented for prismatic joints.

In addition to this, we would like to:

  • Improve the JS bindings of Rapier by making it possible to read contact information in JS, and by allowing the use of JS closures as PhysicsHooks.
  • Start the implementation of an Inverse Kinematics algorithm (probably the FABRIK method).

We are aware that the user-guides for Rapier really need to be improved now that it has a lot of new advanced features like CCD, dominance, contact modification, etc. Unfortunately we didn't have the time to improve the docs during the past two months. We intend to start addressing this in details in May.

Thanks

We would like to thank the whole community and code contributors. In particular, thanks to the code contributors from the past two months1:

  • Thanks to users reporting spelling mistakes on the documentation. This is always appreciated.
  • Thanks to users joining us on our discord server to provide feedbacks, discuss features, and get assistance!

Finally, thanks to all the former, current and new supporters through GitHub sponsors! This help is greatly appreciated and allows us to continue working on open-source exclusively.

  1. The list of contributors is automatically generated from the past two months' github commit history. Don't hesitate to let us know if your name should have been mentioned here.↩