Graphics Reference
In-Depth Information
Figure 14.7.
Chordal deviation.
A curve p : [a,b] Æ R n
A function Flat( p 1 , p 2 , p 3 ) that returns true or false depending on whether the
three consecutive points p 1 , p 2 , and p 3 pass some flatness test
Inputs:
Output:
A sequence of points p i that define a polygonal approximation to the curve p(u)
begin
Output (p(a));
Sample (p,a,b,p(a),p(b));
end ;
procedure Sample ( 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
Output (p d )
else
begin
Sample (p,c,s,p c ,p s );
Sample (p,s,d,p s ,p d );
end
end ;
Algorithm 14.3.1.
Adaptive curve subdivision algorithm.
terion for flatness should be based on the curvature function for the curve, but to
compute that would involve computing the first and second derivatives. De Figueiredo
([Figu95]) describes a recursive algorithm, Algorithm 14.3.1, that generates a good
adaptively sampled polygonal approximation to the curve p(u) but takes less work.
What the algorithm does is check to see if the curve is flat over the input domain by
calling a function Flat. If so, then it approximates the curve with the segment defined
by the endpoints of the curve segment; otherwise, it divides the domain into two and
recursively calls itself over the two subdomains.
Search WWH ::




Custom Search