Graphics Reference
In-Depth Information
1. Parallel Solve
1. Parallel Sol
v
e
e
C
2. Parallel Solve
2. Parallel Solv
Solve
e
B
D
A
3. Parallel Solve
3. Parallel Solve
Figure 4.1.
Batched constraints (left) and how they are solved in three steps (right).
4.2 Rigid Body Simulation
4.2.1 Simulation Pipeline
Rigid body simulation has been studied for decades. To realize interaction be-
tween bodies, colliding pairs must be detected dynamically, and a collision must
be resolved for each of the detected pairs. Studies of implementing collision de-
tection on GPUs include [Harada 07,Grand 07,Liu et al. 10].
After colliding pairs are detected, the normal directional component of rela-
tive velocity at each contact point must be greater than zero to prevent further
penetration [Ericson 04]. This is a condition called velocity constraint and must
be satisfied at all the contact points. Because the velocity constraint is not an
equality, this is a linear complementarity problem (LCP) [Eberly 03]. LCPs can
be solved using the projected Gauss-Seidel method, which is gaining popularity
in a real-time application [Catto 05]. The Gauss-Seidel method can solve only
a linear system, but the projected Gauss-Seidel method can solve LCP; it adds
clamping a solution after solving a row of the system to the Gauss-Seidel method.
However, the serial nature of the algorithm makes it dicult to implement in par-
allel.
4.2.2 Constraint Solver
Batched constraint solver.
To solve constraints in parallel, dependency must be
checked among the constraints. If we look at the constraints connecting A,B
and C,D of the example shown in Figure 4.1, we see that they are independent
constraints (i.e., they do not share any body), thus they can be solved in parallel.
We can collect those independent constraints and define a group of constraints,
which is called a batch. These constraints in a batch can be solved in parallel be-
cause they are independent. After a batch is created, independent constraints are
collected from the remaining constraints to create another batch. This operation
