Path: utzoo!utgpu!watmath!watcgl!rhbartels
From: rhbartels@watcgl.waterloo.edu (Richard Bartels)
Newsgroups: comp.graphics
Subject: Re: Segment polynomials for NURBS
Message-ID: <12086@watcgl.waterloo.edu>
Date: 26 Oct 89 19:14:03 GMT
References: <1139@creare.UUCP>
Reply-To: rhbartels@watcgl.waterloo.edu (Richard Bartels)
Distribution: na
Organization: U. of Waterloo, Ontario
Lines: 26

In article <1139@creare.UUCP> cmm@creare.UUCP (Chris Morley) writes:
>In order to rapidly evaluate a non-uniform rational B-spline,
>I would like to convert from the control vertex format to
>the segment polynomials (ie, the coeficients of the powers of u).

Generally it is better not to convert to powers, for reasons of
numerical stability and accuracy.  At least that is the current,
conventional advice, based upon some work that Rida Farouki is doing
at TJ Watson, IBM.  The nicest conversion is to Bernstein polynomials
(a.k.a. Bezier form) from which a nested multiplication evaluation
is possible.

Also a paper to read (when they ever ship them) is "Rendering Cubic
Curves and Surfaces with Integer Adaptive Forward Differencing"
in this year's SIGGRAPH Proceedings.  Forward differencing is fast,
and can also run from Bernstein/Bezier form.  But it suffers from
error growth and shouldn't be used for high degrees.

As for converting to Bernstein polynomials: knot insertion is
a route to go, look up Boehm's knot insertion algorithm for
a good set of formulas, Computer Aided Design, vol 12, pp 199-201.
(A Butterworth publication, if you library can't locate).
Or see the book "Curves and Surfaces for Computer Aided Geometric
Design", G. Farin, Academic Press.

-Richard