Graphics Reference
In-Depth Information
=+
-
ss
j
(
)
uu
uu
-
.
j
j
+
1
j
s
-
s
j
+
1
j
On the other hand, to get a more accurate values we must do more work. We start
with the arc length problem. Our first good approximation to arc length based on
equation (14.22) relies on getting a
good
polygonal approximation to the curve and
then using the length of that polygonal curve. Any good polygonal approximation will
work. One such is the de Figueiredo algorithm (Algorithm 14.3.1) described in Section
14.3, where one subdivides recursively until the curve is relatively flat according to
some criterium. Algorithm 14.8.1 computes arc length based on the polygonal approx-
imation that one gets from this.
Next, note that for smooth functions p(u) the sums L({u
i
}) in equation (14.22) are
Riemann sums which converge to an integral. Specifically,
b
(
)
=¢
Ú
LLab
=
,
p
.
(14.23)
a
Therefore, another way to compute L is to use a known numerical approximation to
integrals. Now sometimes one is in a situation where one has a fixed curve p(u) and
one needs to answer multiple requests for arc lengths of different subarcs p([c,d]) of
p(u). Guenter and Parent ([GueP90]) deal with this situation. The authors decided to
use a Gaussian quadrature method for evaluating integrals because it is a particularly
efficient integration method. They suggested that it is advantageous here to build a
table of a certain number of precomputed arc length values in order to speed up the
computation of other values.
For any c,d Π[a,b], let GQ(c,d) denote the Gaussian quadrature approximation to
the integral
Assume that Flat(
p
1
,
p
2
,
p
3
) is a function that returns
true
or
false
depending on whether
the three consecutive points
p
1
,
p
2
, and
p
3
pass some flatness test.
real function
Length (
curve
p;
real
c, d;
point
p
c
, p
d
)
begin
real
s;
point
p
s
;
s := random number in (c,d);
p
s
:= p(s);
if
Flat (p
c
,p
s
,p
d
)
then
return
|p
c
p
d
|
else
return
( Length (p,c,s,p
c
,p
s
) + Length (p,s,d,p
s
,p
d
) );
end
;
Algorithm 14.8.1.
Arc length based on polygonal approximation.
