Graphics Reference
In-Depth Information
4.3 Two-Level Constraint Solver
This section presents the two-level constraint solver, which solves constraints in
two stages. The reason for the split is to make the algorithm easy to parallelize
and to localize expensive operations to improve the eciency. This two-level
approach is applicable for GPUs as well as for multi-core CPUs. Because the
two-level constraint solver solves constraints in two steps, the batching, which is
a serial computation, is also split into two steps (global split and local batching),
each of which can be implemented in parallel.
4.3.1 Global Split
Constraints are split into several independent groups during the global split (a
group is similar in concept to a simulation island). The objective of this split is
to process groups in parallel. However, if all the constraints in the simulation are
connected—as often happens—it just creates a single big group and we cannot
split it into groups. Therefore, we first split constraints into groups, allowing
some dependencies. Then independent groups are collected from all the groups
to form a set of constraint groups. This operation is repeated until all the groups
are assigned to one of the sets. After sets are created, constraint groups in a set
can be processed in parallel; however, processing different sets must be serialized
because they may depend on each other.
There are several spatial splits we can use, but we employ a two-dimensional
regular split as shown in Figure 4.2 because the simplicity of the connectivity
of cells of a regular split makes it easy to create sets of constraint groups. Con-
straints in a cell form a constraint group. Although adjacent cells can have a con-
straint sharing a body, one-ring neighbor cells do not have a connected constraint.
Therefore, cells (or groups) are split into four independent sets (Figure 4.2).
Set 0
Group 0
Set 1
Group 0
Set 2
Group 0
Set 3
Group 0
Group 1
Group 1
Group 1
Group 1
Group 2
Group 2
Group 2
Group 2
Group 3
Group 3
Group 3
Group 3
Figure 4.2.
Global split creates sets of constraint groups.
