Graphics Reference
In-Depth Information
3.2.2
Refinements and Extensions
Thenumerical analysis and computer visioncommunities have investigated fastways
to solve Poisson and Laplace equations, which despite their sparsity can become
quite time-consuming to solve when the region
is very large. These equations are
frequently solved using
multigrid
techniques [
413
,
374
]; the basic idea is to iterate
between exactly solving the equation on a coarser grid than the original problem,
and applying a correction step to approximate the solution on the finer, original
grid. Other approaches include early work on orthogonal-transform-based methods
[
452
], and more recently methods based on hierarchical basis preconditioning [
484
],
quadtrees [
6
], exploiting GPUs [
52
,
318
,
218
], and fast multigrid [
177
,
233
].
Farbman et al. [
132
] proposed an extremely efficient approximation to the solution
of Equations (
3.17
)-(
3.18
) using
mean-value coordinates
[
146
] that directly produces
results perceptually indistinguishable from those of the previous section without
solving a large linear system. The interpolating function
E
(
x
,
y
)
is directly computed
from the values of
T
(
x
,
y
)
−
S
(
x
,
y
)
on
∂
as follows.
Let the closed boundary
∂
be specified by a sequence of points, ordered counter-
clockwise and denoted
(
p
1
,
p
2
,
...
,
p
N
)
. Then define
)
j
=
1
w
j
w
i
(
p
λ
i
(
p
)
=
,
i
=
1,
...
,
N
(3.20)
(
p
)
where
tan
(θ
i
−
1
(
p
)/
2
)
+
tan
(θ
i
(
p
)/
2
)
w
i
(
p
)
=
,
i
=
1,
...
,
N
(3.21)
p
i
−
p
and
is the angle formed by
p
i
,
p
, and
p
i
+
1
, as illustrated in Figure
3.11
. (For the
purposes of Equation (
3.21
),
p
0
θ
(
p
)
i
p
N
.)
Then we can obtain an estimate of the harmonic function
E
=
(
p
)
at any point in
as a simple weighted combination of the boundary conditions:
N
E
(
p
)
=
1
λ
i
(
p
)(
T
(
p
i
)
−
S
(
p
i
))
(3.22)
i
=
As previously, we recover
I
(
p
)
=
E
(
p
)
+
S
(
p
)
. Note that we can directly evaluate
I
by computing Equation (
3.22
), which is extremely efficient
and highly parallelizable. While the values of
E
do not precisely solve the Laplace
(
p
)
for any point in
p
i
p
i
1
p
i+1
θ
i
1
θ
i
∂Ω
Ω
p
Figure 3.11.
Mean-value coordinates for fast approximation of Equations (
3.17
)-(
3.18
).
