Graphics Reference
In-Depth Information
p
k
+1
p
k
g
g
g
┴
p
k
Figure 8.71
The fiber-growing algorithm estimates the direction
g
of the hair fiber, which lies at the
intersection of the ribbons from
p
k
. The next point
p
k
+
1
is found in the cross section of
the plane
g
⊥
perpendicular to
g
. (From [Jakob et al. 09]
c
2009 ACM, Inc. Included here
by permission.)
a “fiber-growing” algorithm (but the algorithm does not simulate the growth of
the hair as it developed from the hair follicle). The fiber-growing algorithm is
a standard predictor/corrector method: at each iteration, the direction to the next
point is predicted from the local geometry and then corrected to a better match for
use in the next iteration. Without the correction step, the prediction error would
likely increase with each iteration, causing the computed segments to drift away
from the actual fiber curve.
The prediction step starts with a point in space and estimates the direction of
the next point on the fiber. Just as the 3D curve can be locally approximated by
a line, each ribbon can be locally approximated by a plane. The intersection of
all the ribbon planes provides the direction of the fiber segment. However, due
to measurement errors, it is not possible to determine this direction exactly. De-
termining this information from the intersection of the planes is a overdetermined
problem. A least squares solution is extracted using the
singular value decomposi-
tion
(SVD), which is described more fully in Section 9.3.2. In a nutshell, the SVD
factors a matrix into a product
U
is a diagonal matrix of
singular val-
ues
. The SVD is applied to the matrix having the normal vectors
Σ
V
where
Σ
n
i
of the ribbons
as its rows, and the vector in the third row of the
V
matrix is the estimated direction
(
Figure 8.72
)
. This vector is the “most orthogonal” to the set of planes and thus
is the best direction estimate. Denoting the predicted direction vector by
g
,the
next predicted point is the current point
p
k
plus
h
g
,where
h
is the
step size
of the
iteration.
Because it is just an estimate, the computed next point is likely to be slightly
off the intersection of the ribbons (see
Figure 8.71
). The correction step “recen-
