Path: utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!rutgers!njin!princeton!udel!wuarchive!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!hplabs!hp-sdd!ucsdhub!calmasd!bdd
From: bdd@calmasd.Prime.COM (Brian Donahue)
Newsgroups: comp.graphics
Subject: Re: NURBS, interpolating them with lower degree NURBS
Message-ID: <726@calmasd.Prime.COM>
Date: 17 Nov 89 16:57:40 GMT
References: <206@nwnexus.WA.COM>
Reply-To: bdd@calmasd.Prime.COM (Brian Donahue)
Distribution: comp.graphics
Organization: Calma - A Division of Prime
Lines: 34

In article <206@nwnexus.WA.COM> tim@nwnexus.UUCP (Tim Anderson) writes:

>I want to turn big ugly NURB's (with degree <= 20) into lots of nice
>quick-to-draw peicewise cubic rational Bezier's. (What I *really* want
>is to be able to display and compute tangents and normals at blinding
>speed [...]
>
> Do I just cut those into
>little sections and then do a bunch of curve fitting with cubic Bezier's?
>Seems like there would be a 'better' way of doing this than that...

You can do "degree-reduction" without doing a (time-consuming) interpolation
step if you use Hermite approximation.  See:  "Numerical Analysis", 
Burden, Faires & Reynolds. 2nd edi. pg. 101.  The basic idea is :
the error bound on the Hermite polynomial as it approximates a continuous
(C1) curve on [A,B] is given and depends on the maximum magnitude of
the (2n + 2)'th derivative of the curve (where the Hermite polynomial
is of degree 2n + 1).  (Eg. if n = 1 for your resulting cubics, the 
error bound is determined by the max magnitude of the 4th derivative
of the original somewhere on [A,B]).  This lets you calculate a "step-size"
so that you can sample your original curve (position and 1st derivative)
and do some cubic hermite interpolation.  The "hard" / time
consuming part may be estimating/calculating the max magnitude of 
the 4th derivative....


I have implemented this algo here, and its performance is not too bad
if your error bound is "reasonable".

bd

-- 
Brian Donahue	   	Calma San Diego R&D
...{ucbvax|decvax}!sdcsvax!calmasd!bdd        bdd@calmasd.Prime.COM