Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sdd.hp.com!news.cs.indiana.edu!msi.umn.edu!umeecs!zip!spencer
From: spencer@eecs.umich.edu (Spencer W. Thomas)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Better Quality Spline Code
Message-ID: <SPENCER.91Feb22142101@spline.eecs.umich.edu>
Date: 22 Feb 91 20:21:01 GMT
References: <11332@adobe.UUCP> <1991Feb22.103752.23459@lth.se>
Sender: news@zip.eecs.umich.edu
Organization: University of Michigan EECS Dept
Lines: 72
In-Reply-To: sund@tde.lth.se's message of 22 Feb 91 10:37:52 GMT

Yes, you can do this, but it's more expensive than just computing a
priori how many points you need for a given spline segment and then
just blasting them out.  A sketch of the code appears below.

The second method involves looking at the curvature (second
derivative) and using that to estimate the number of segments needed.
Sederberg and Parry ("Comparison of three curve intersection
algorithms," CAD, 1986 (sorry, I don't have vol/no reference), pp
58-63) attribute the following method to G Wang (published in Zhejiang
U Journal). Given a Bezier curve (you can always convert a polynomial
spline to a collection of Bezier curves by subdividing at the knots)
with control points (x[i],y[i]) i=0..n, compute
	L0 = max( | x[i] - 2x[i+1]+ x[i+2] |, | y[i] - 2y[i+1] + y[i+2] | )
	i = 0 .. n-2
then
	r0 = log4(sqrt(2)*n*(n-1)*L0 / 8*epsilon)
is the number of segments to draw to stay within epsilon distance of
the curve.

/* Draw a spline (or Bezier curve) with recursive adaptive subdivision. */
draw_spline(s)
spline *s;
{
	spline *s1, *s2;

	if ( is_straight(s) )
		draw_seg( first_pt(s), last_pt(s) );
	else
	{
		subdivide( s, &s1, &s2 )
		draw_spline( s1 );
		draw_spline( s2 );
	}
}

is_straight(s)
spline *s;
{
	l = line( first_pt(s), last_pt(s) );
	for (p = each control point in s)
	{
		/* Actually, you want to make sure the curve doesn't
		   "double back", either.  The usual method is to 
		   project each of the control points onto the line,
		   and make sure that they appear monotonically.
		   (I.e., the 't' values for the projections should
		   be in increasing or decreasing sequence.)  I leave
		   this as an exercise.
		*/
		if ( distance( p, l ) > EPSILON )
			return FALSE;
	}
	return TRUE;
}

subdivide( s, s1, s2 )
spline *s;
spline **s1, **s2;
{
	/* Use a spline subdivision algorithm to split s into two
	   halves, usually at the midpoint of its parametric range.
	   If using Bezier curves instead of splines, just split it
	   in the middle.  The first half is returned via s1 and the
	   second half via s2 (the storage is dynamically allocated
	   in this "implementation".)
	*/
}


--
=Spencer W. Thomas 		EECS Dept, U of Michigan, Ann Arbor, MI 48109
spencer@eecs.umich.edu		313-936-2616 (8-6 E[SD]T M-F)