Graphics Reference
In-Depth Information
Figure 14.6.
Problems with a uniform
subdivision.
(1) The approximation may not be very good at places of high curvature along the
curve. For example, consider the parabola
(
)
[
]
() =-
2
pu
33
u
+
,,
u
u
Œ-
,,
1
in Figure 14.6. The substitution u = v 1/k , k odd, reparameterizes the curve to
(
)
() =-
2
k
1
k
qu
3
v
+
3
,
v
.
Let k = 5 and suppose that we divide [-1,1] into 64 equal parts. Then
1
32
9
4
1
2
1
32
9
4
1
2
Ê
Ë
ˆ
¯
Ê
Ë
ˆ
¯
Ê
Ë
ˆ
¯
= Ê
Ë
ˆ
¯
()
()
q
1
,...,
q
-
=-
,
,
q
,
,...,
q
1
is not a good approximation to the curve even though we have a rather fine
subdivision.
(2) If k is large to get a good fit, then the fact that we generate a lot of data may
become a problem. If the curve has pieces that are essentially flat, then we might
have saved a lot of space and effort by not subdividing those pieces as much. The
extreme case is where the curve is a straight line segment and all we really need
is p(a) and p(b).
These two reasons suggest that an adaptive subdivision would be more appropriate,
where we subdivide highly curved segments more and flat ones less.
This raises the next issue, namely, how to define “flat.” On an intuitive level, flat-
ness over a segment [c,d] is often thought of as a measure of how much the curve
deviates from the chord [p(c),p(d)].
Definition.
The value
[
]
(
()
() ()
)
max
dist p u
,
p c
,
p d
Π[
]
ucd
,
is called the chordal deviation of p(u) over [c,d].
The chordal deviation of the curve in Figure 14.7 is the distance between the points
A and B . On the other hand, if one is interested in preserving shape, then a better cri-
Search WWH ::




Custom Search