Graphics Reference
In-Depth Information
Combining this with the derivation of the fluid kinetic energy from the
end of Chapter 4, and rescaling as was done there (dividing by Δ
t
and
replacing actual volumes by dimensionless volume fractions) we see we just
add Δ
tJ
T
M
−
1
J
to the matrix and
J
T
U
to the right-hand side.
This is precisely where we need more general sparse matrices:
Δ
tJ
T
M
−
1
J
doesn't correspond to a simple grid structure. In fact, it forms
a dense submatrix, connecting up all the cells near the boundary of the ob-
ject. If you're interested in the linear algebra, it's also simple to see that
it is (at most) rank six and must be symmetric positive semi-definite—so
PCG still works! The density may, however, cause memory and perfor-
mance problems: these can mostly be overcome by keeping the extra terms
separate in factored form. The matrix-vector multiplies in PCG can be
significantly accelerated then by multiplying
J
T
M
−
1
Js
as
J
T
(
M
−
1
(
J
T
s
)),
and since they are only rank six can be ignored in constructing the precon-
ditioner without too big a penalty.
For large objects, which overlap many grid cells, this is actually a con-
siderable problem: a large amount of memory will be required to store it,
and PCG will run slowly due to all the work multiplying with this dense
submatrix. One possibility for improvement is to add the new rigid body
velocity
U
n
+1
as an auxiliary variable in the pressure solve, giving the
following slightly larger but much sparser system:
−
A
p
U
n
+1
=
.
T
−
d
Δ
t
M U
1
J
−
Δ
t
M
1
−
While this still leads to a symmetric matrix, it is unfortunately now in-
definite, which means PCG no longer can work. Nevertheless, this is in a
well-studied class of matrices, sometimes termed “saddle-point” matrices
(in fact, apart from the constant pressure null-space, it would be a “sym-
metric quasi-definite” matrix), and it seems promising to solve it as such.
For example, it would be worthwhile trying an iterative method such as
MINRES in conjunction with an incomplete Cholesky preconditioner in
LDL
T
form (where
L
has unit diagonal, and
D
is a diagonal matrix with
positive entries for the pressure unknowns and negative entries for the rigid
body unknowns). For more on solving this class of matrix problems, see
the review article by Benzi et al. [Benzi et al. 05] for example.
Another interesting direction to consider is to generalize this approach
to include strong coupling of articulated rigid bodies: for example, the
Lagrange multiplier approach to constraints can also be phrased as a min-
imization of kinetic energy. Frictional contact forces fall in the same cat-
