Graphics Reference
In-Depth Information
Inputs:
Contour curves p
i
(u), real numbers u and v
Output:
p(u,v)
Step 1:
Because one no longer requires the same v knot vector for all u, one computes a knot
vector v
0
(u), v
1
(u), º , v
k
(u) as follows:
v
0
(u) = 0 , v
1
(u) = 1 , for all u
L
L
v
i
(u) =
i
Œ [0,1] , 1 < i < k ,
k
where L
j
is the length of the polygonal curve with vertices p
0
(u), p
1
(u), º , p
j
(u).
Step 2:
Determine s so that v
s
(u) £ v < v
s+1
(u).
Step 3:
Evaluate p
s-1
(u), p
s
(u), p
s+1
(u), and p
s+2
(u).
Step 4:
Determine the cubic curve D(w), 0 £ w £ 1, which starts at p
s
(u), ends at p
s+1
(u), and
has tangent vectors at its endpoints that match the tangent vector to the parabolas
defined by p
s
-
1
(u), p
s
(u), p
s
+
1
(u) and p
s
(u), p
s
+
1
(u), p
s
+
2
(u), respectively.
Step 5:
Let p (u,v) = D (
vv
-
s
)
v
-
v
s1
+
s
Algorithm 14.7.2.
A procedural skinning algorithm.
The Arc length problem:
Compute the length L of p.
The Arc-length parameterization problem:
Given s Œ [0,L], find the point
q
on the curve
so that the part of the curve from p(a) to
q
has length s. In practice, the problem is one of
finding u Œ [a,b], so that p(u) is that point.
By definition, the length L of the curve p in (14.21) is the limit of sums of the form
n
Â
{}
(
)
=
(
) (
)
Lu
pu pu
,
(14.22)
i
i
-
1
i
i
=
1
where the limit is taken over all partitions {u
i
} of [a,b], a = u
0
< u
1
< ...< u
n
= b, whose
norms go to zero. It follows that L({u
i
}) will be a good approximation to L provided
that the polygonal curve p(u
0
), p(u
1
),..., p(u
n
) is a good approximation to the curve
p. Therefore, a quick and dirty way to estimating arc length is just to make a guess
as to a reasonable subdivision {u
i
} and then to use the value L({u
i
}). We can also get
a quick estimate for
q
in the arc-length parameterization problem as follows:
(1) Make a table of the lengths s
i
of the polygonal curve defined by the points
p(u
0
), p(u
1
),..., p(u
i
).
(2) Given s, find j so that s
j
£ s £ s
j+1
.
(3) Set
q
= p(u), where u is the corresponding interpolated value in [u
j
,u
j+1
], that
is,