Simulating the World Faster
Used with permission from CM Labs Simulations. Copyright.
One of the most valuable applications of virtual reality (VR) technology is training users to perform skilled tasks that are costly or difficult to perform in a real-world setting. For example, training a surgeon to perform a delicate procedure, or a crane operator to control construction equipment. This last example is precisely the type of scenario targeted by our recent work done in collaboration with Montreal-based company CM Labs Simulations. They develop physics-based training simulators for heavy vehicles, construction equipment, and robotics that are all simulated using their in-house physics engine called Vortex. Performance, stability, and accuracy are key requirements for their simulations, so typical solutions developed for video games and other interactive applications are not well suited to meet all of these criteria; therefore, specialized algorithms are required.
Simulating Physics in Smaller Pieces
During a previous collaboration with CM Labs (Peiret et al., 2019), we developed a novel technique to parallelize the simulation of complex mechanical systems based on a domain decomposition approach called the Schur complement method. The approach decomposes the simulation into smaller contiguous sub-systems and makes effective use of modern multi-processor hardware found in most computers. This resulted in a nearly 14x speed increase in computational performance of certain training scenarios (see Figure 1), and this, without sacrificing the accuracy of the simulation.
Figure 1 – The Schur complement method (bottom-left) achieves a near-14 times speed increase in simulating this training scenario involving tandem cranes lifting objects compared to the baseline solver.
Simulations as a Graph
Although the proposed parallelization technique significantly improved performance, it varied depending on how the global simulation was decomposed into smaller sub-systems. This is where our most recent work plays an important role. We analyzed the model of the mechanical system as a graph, where physical bodies are vertices in the graph, and kinematic constraints that couple the motion of bodies (e.g., mechanical joints and contacts) are the edges.
Figure 2 – Graph representation of different simulation examples: a chain falling on the ground (left), a dense pile of rocks (centre), and a log tower collapsing (right).
Graph Partitioning Algorithms
The constraint-body graph lays the foundation for decomposing a simulation, and this naturally leads to the question: What is the best way to decompose the simulation? Our recent paper examines the efficacy of several graph partitioning algorithms that are suitable for real-time applications, meaning that the algorithms must be able to produce partitions (or sub-systems) in only a few milliseconds. We found that a greedy algorithm that expands each sub-system by alternating between minimizing and then maximizing the degree of added vertices produces decomposition, yielding improved performance compared to baseline techniques.
However, our earlier work observed that increased coupling between subsystems leads to reduced solver performance. We therefore consider—once an initial partitioning is computed—how the graph may be refined to further reduce the edges between each sub-system.
Refinement Algorithms
A refinement step reduces connections between sub-systems by applying graph refinement algorithms, namely the Kernighan–Lin (KL) and Fiduccia–Mattheyses (FM) algorithms. These algorithms have seen extensive use in other fields, such as circuit design, but to our knowledge this is the first application in the context of physics simulation. Briefly, the KL algorithm focuses on finding a pair of bodies in two different subsystems and swaps them if it reduces the total number of edges between the subsystems, whereas the FM algorithm plays “tennis” by finding a single body to move from one partition to an adjacent one. However, analyzing all bodies and constraints in the simulation is time-consuming, especially for large and complex rigid body simulations. Therefore, we improve the efficiency of the refinement algorithms by tracking peripheral bodies of each partition and apply the refinement algorithms only to bodies at the interface between partitions.
Figure 3 – Wall-clock time to solve the dynamics of the rock pile example. Our proposed partitioning strategy (MIX) with either KL (grey bar) or FM (white bar) refinement gives the best performance.
Conclusion
The newly proposed partitioning method outperforms other algorithms we compared in our study. Furthermore, refinement using the KL and FM algorithms gives an additional performance boost by reducing the number of graph edges between subsystems. From our experiments, we observed that our proposed partitioning algorithm can achieve performance improvements by reducing solver computation time by up to 50%.
Additional information
Further details can be found in the following papers:
Peiret, A., Andrews, S., Kövecses, J., Kry, P. G. and Teichmann, M. (2019). “Schur Complement-based Substructuring of Stiff Multibody Systems with Contact”. ACM Transactions on Graphics (TOG), 38(5), 1-17.
Liu, Y. and Andrews, S. (2022). “Graph Partitioning Algorithms for Rigid Body Simulations”. Eurographics 2022 (Short Papers).
