Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!ncar!tank!eecae!abaa!itivax!umich!zip!spencer From: spencer@eecs.umich.edu (Spencer W. Thomas) Newsgroups: comp.graphics Subject: Re: Bezier Curves (really adding knots) Message-ID: Date: 12 Sep 89 21:43:40 GMT References: <34676@apple.Apple.COM> Sender: news@zippy.eecs.umich.edu Organization: University of Michigan EECS Dept Lines: 34 In-reply-to: jp@Apple.COM's message of 12 Sep 89 19:02:23 GMT In article <34676@apple.Apple.COM> jp@Apple.COM (John Peterson) writes: For doing knot inseration on curves, Boehm's method is much faster than the Oslo algorithm. (Boehm, "Inserting new knots into B-Spline Curves," CAD, July 1980). Actually, John, Lyche and Moerken ("Making the Oslo Algorithm more Efficient", SIAM J. Numer. Anal. 23, 1986, 663-675.) show that, properly tuned, the Oslo algorithm is equivalent to Boehm's method for single knot insertions, and more efficient for simultaneous insertion of multiple knots. "Our Algorithm 2 reduces to Boehm's method when t is obtained from r by adding one knot." Some operation count data is found in (Lyche et al, "Knot line refinement algorithms for tensor product B-spline surfaces", CAGD 2, 1985, 133-139.) The original Oslo 1 slightly outperforms Boehm when dealing with (3-D) tensor product surfaces, and the improved algorithm is significantly faster. Their table (for an n x m tensor product surface, n >= m): Algorithm = flops n = m = 10 Oslo 1 72(m-3/2)(n-1) + 36(n+m-3) 6120 Oslo 2 324(m-3/2)(n-1) 24786 Improved Oslo 1 45(m-3/2)(n-1) + 12(n+m-3) 3647 Improved Oslo 2 108(m-3/2)(n-1) 8262 Boehm 81((m-2)(n-2)-1) 5103 (Note that the asymptotic behaviour is well characterized by the leading coefficient, so that the advantage that Boehm has over Oslo 1 initially will disappear with larger values of n and m. -- =Spencer (spencer@eecs.umich.edu)