Graphics Reference
In-Depth Information
is repeated until all the constraints are assigned to a batch. Once constraints are
divided into batches, we can solve constraints within a batch in parallel, although
synchronization is necessary among solving different batches because they have
dependency. Figure 4.1 illustrates batched constraints in which constraints in the
same batch are drawn using the same color.
Global batching.
Batching classifies all the constraints into independent batches.
An algorithm for batching is shown in Algorithm 4.1. It iterates through all the
constraints in the simulation and checks the dependency of a constraint against
the constraints stored in a batch. If a constraint does not have dependency to
the constraints in the batch (line 7), the constraint is added to the batch (line 8);
otherwise, the constraint is stored in another buffer as a remaining constraint
(line 13).
Once all the constraints are checked, the batch is closed (line 16). Then the
next batch is opened, the remaining constraints from the previous iteration are
processed one by one, and dependency is checked against the current batch as for
the first batch. This operation is repeated until all the constraints are assigned to
a batch. We call this batching algorithm
global batching
, and a constraint solver
that solves constraints using it a
global batch global constraint solver
.
1:
pairsSrc
←
pairs
2:
pairsDst
3:
while
pairsSrc.getSize()
do
4:
nConsumed = 0
// pair count scheduled in the batch
for
pairsSrc.getSize()
do
5:
iPair = pairsSrc[i]
6:
if
!locked(iPair.x) and !locked(iPair.y)
then
7:
batch.add( iPair )
8:
lock( iPair.x )
9:
lock( iPair.y )
11:
nConsumed++
12:
else
13:
pairsDst.add( iPair )
14:
end if
15:
end for
16:
if
nConsumed = 0
then
17:
batch.close()
18:
clear( lockStatus )
19:
end if
20:
swap( pairSrc, pairsDst )
21:
end while
22:
batch.close()
10:
Algorithm 4.1.
Batch creation.
