Game Development Reference
InDepth Information
(a)
(b)
Figure 5.6.
Solution of the Laplace equation. (a) Iterative solution using 100, 1,000,
5,000, and 50,000 Jacobi iterations. (b) Multiscale approach.
This problem is known to be equivalent to solving Laplace's equation Δ
s
=0
with the corresponding Dirichlet boundary condition
s

∂
Ω
. Discretization
of the Laplace operator yields a large sparse linear system of equations

∂
Ω
=
S
Δ
s

i,j
s
i
+1
,j
+
s
i
−
1
,j
+
s
i,j
+1
+
s
i,j
−
1
−
4
s
i,j
=0
,
≈
which may be solved using any technique for solving linear systems. One of the
simplest approaches is to assume that in the
i
th equation only the
i
th parameter
is unknown, leaving the other parameters fixed. Solving each of these equations
independently and iterating the process converges to the solution and is known
as the
Jacobi method
. More specifically, let
s
i,j
denote the
k
th step's structure
tensor at pixel (
i, j
); then a Jacobi relaxation step is given by
⎧
⎨
s
i,j
if (
i, j
)
∈
∂
Ω
,
s
k
+1
i,j
=
s
i
+1
,j
+
s
i
−
1
,j
+
s
i,j
+1
+
s
i,j
−
1
4
⎩
otherwise
.
Since the computation involves a convex combination, the result is again a pos
itive semidefinite matrix and, thus, is welldefined. Unfortunately, a very large
number of iterations is typically required, which is demonstrated in Figure 5.6(a).
Obtaining a sucient approximation of the solution takes approximately 50,000
Jacobi iterations. Even onmodernhighendGPUs,this takes several seconds to
compute. The implementation of a Jacobi step is shown in
Listing 5.2.
Search Nedrilad ::
Custom Search