Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!adobe!hawley
From: hawley@adobe.COM (Steve Hawley)
Newsgroups: comp.sys.mac.programmer
Subject: Better Quality Spline Code
Message-ID: <11332@adobe.UUCP>
Date: 20 Feb 91 17:36:02 GMT
Organization: Adobe Systems Incorporated, Mountain View
Lines: 80


Here is the spline code (originally written by Theo Pavlidis at Bell Labs)
optimized to a degree, but with a reasonable amount of readability (read:
it can still be better).

/*
 * spline(p, n)
 * draws an approximate bicubic spline through the control points in the
 * array p.  Don't use the first and last slots -- they're used to weight
 * the endpoints.
 * The previous version called for an offset.  None has been included here.
 * Also, the previous version had a kind of screwy notion as to what n was.
 * Here, n refers to the total number of control points.  If n is 4, the
 * array p must have 6 entries in it.  This 0th and 5th slots are used to
 * weight control points, slots 1-4 inclusive are the 4 control points.
 */

/*
 * Scaling factor and the number of subdivisions per curve.  For best
 * performance, SCALE should be power of 2 and STEPS should evenly
 * divide SCALE.  Also SCALE should always be greater than STEPS.
 */

#define SCALE 1024L
#define STEPS 8

spline(p, n)
register Point *p;
short n;
{
	register long w, t1, t2, t3;
	register short i, j;

	p[0] = p[1];
	MoveTo(p->h, p->v);
	p[n+1] = p[n];

	for (i=0; i < n; i++, p++) {
		for (j=0; j < STEPS; j++) {
		/*
		 * calculate the three terms for the polynomial
		 */
			w = (SCALE/STEPS) * j;
			t1 = w*w / (2 * SCALE);
			w -= SCALE/2;
			t2 = 3*SCALE/4 - w*w / SCALE;
			w -= SCALE/2;
			t3 = w*w / (2 * SCALE);
			LineTo((t1 * (p+2)->h + t2 * (p+1)->h +
				t3 * p->h + SCALE/2) / SCALE,
				(t1 * (p+2)->v + t2 * (p+1)->v +
				t3 * p->v + SCALE/2) / SCALE);
			/* The following call to Line() will redraw the
			 * last point in the line segment.  This allows
			 * spline() to be used with patXor modes.  If you're
			 * not going to use xor drawing modes, take this
			 * call out.
			 */
			Line(0, 0);
		}
	}
}

typical usage:

static Point k[7] = {
	{0, 0}, {50, 50}, {75, 100}, {75, 120}, {200, 30}, {85, 150},
	{0, 0} };

...
	PenMode(patXor);
	spline(k, 5);
...

Steve Hawley
hawley@adobe.com
-- 
"Did you know that a cow was *MURDERED* to make that jacket?"
"Yes.    I didn't think there were any witnesses, so I guess I'll have to kill
 you too." -Jake Johansen