Lisp is an excellent language for developing high-level AI programs. In particular Allegro Common Lisp (Allegro CL) has made the Macintosh an excellent platform for developing AI software. All implementations of Common Lisp including Allegro CL, are limited by some serious drawbacks. Communications to graphics and audio devices are not specified and Common Lisp does not even define access to physical devices. (A trap mechanism in Allegro CL does permit communication to the Macintosh Toolbox, but this mechanism is very limited.) Additionally, complex mathematical computations, such as geometric transforms or statistical analysis, are extremely slow in any implementation of Lisp.
To overcome these problems, you can write C functions that are called from Lisp. Allegro CL provides a Foreign Function Interface to facilitate inter-language communication. The use of this interface allows C to access physical devices and perform complex computations on behalf of higher-level Lisp operations. This allows the Lisp program to be concerned with high-level problems such as rule-base management, while the C routines handle all of the "dirty work" such as drawing pictures on the screen.
In this article, we present a spline function that uses the Macintosh Toolbox to draw a smooth curve. This spline function is one of 18 graphic primitives in Artifex, a design-rule system based on shape grammars. (Source code for the system is available from the authors of this article.) In order to calculate the points along the curve of a bicubic equation must be solved. Calculations of this sort are miserably slow in Lisp. However, the solution presented here is quick enough to reasonably support user interaction, such as "rubber-splining," in which the user dynamically instances splines.
The Bicubic Spline
"Splines" are graphic elements that are used for drawing objects that contain curves. A spline is composed of one or more "spline segments." Figure 1 illustrates a spline segment defined by the four points P0 though P3. Points P1 and P2 are the end points of the spline segment and the curve is drawn between these two points. Points P0 and P3 are called the "control points." During the process of calculating the spline, the two points are interpreted as vectors.
The magnitude of the vector modulates the tension of the curve. In other words, the greater the distance between P0 and P1, the more the curve will bend. As Figure 2 shows, when P0 and P1 are coincident, the beginning of the curve is parallel to the line P1 - P2.
As P0 approaches infinity, moving further away from P1, the curve tends toward the line P0 - P1. Similarly, the spline may be bent to one side or the other as illustrated in Figure 3, by modulating the vector angle. In this manner, a user can interactively describe a curve by moving its control points in order to perform the rubber-splining mentioned earlier.
The spline presented here uses a kind of interpolation known as "bicubic" to create a particular class of curves. The coordinates for the points, (i, j), along this curve are found by solving the cubic equations shown in Example 1.
j = j<sub>1</sub>t + j<sub>2</sub>(1 - t) + W(j<sub>2</sub> - j<sub>3</sub>)(1 - t)<sup>2</sup>t + W(j1 - j0)(1 - t)t<sup>2</sup> i = i<sub>1</sub>t + i<sub>2</sub> (1 - t) + W(i<sub>2</sub> - i<sub>3</sub>)(1 - t) <sup>2</sup>t + W(i<sub>1</sub> - i<sub>0</sub>)(1 - t)t<sup>2</sup>
To draw a curve, you must solve this pair of equations for every point at some regular sampling interval. The number of samples determines the coarseness or the smoothness of the curve. Figure 4 illustrates a spline segment that results from sampling the equation four times. If you sample the equation more frequently, your curve will be smoother. The production of a reasonably smooth curve requires a fairly short interval with a width of 2 - 3 pixels and a significant amount of computation.
The free cubic variable t has a range from 0 to 1 in real numbers. To find a point in the middle of the curve, you solve the equations for t=0.5. In this way, the degree of smoothness of a curve can be varied, depending on the frequency at which t is sampled.
The other free variable, W, is a weighting factor that controls the tension of the curve. A value of 0.9 produces reasonable curves on the Macintosh. If W is 0, then a straight line is drawn between P1 and P2. As W increases, the end of the curve tends toward tangency with the lines P0 - P1 and P2 - P3. Figure 5 illustrates the effect of varying this weighting factor.
It is important to remember that an infinite number of curves can be drawn between any two points. Bicubic interpolation produces curves with continuities at the end points. These continuities facilitate the process of combining spline segments into an infinite class of curves.
More Details
Figure 6 illustrates two bicubic spline segments. The first spline segment is defined on the line P0-P3 and the second defined on the line P1-P4. Together the two segments form a spline that is continuous in the second derivative at P2. In other words, the two spline segments change at the same rate and have the same slope at P2, so they connect smoothly. This special property of bicubic splines makes them ideal for use with graphics software because a smooth curve can be drawn through any arbitrary set of points. Another advantage of bicubic splines is that the points that define the curve of the splines lie on the curve. Other curve-defining functions, such as the B-spline, are defined by points that are not located on the curve.
You could write a Lisp routine to calculate the points along the curve, but such a routine would be very slow. In any case, you would still need to access a physical line-drawing function in order to connect the points into a curve. The faster and better way to handle this calculation is to call the C routine, _Spline, which is found in Listing One. This routine is accessed through three Lisp functions: Mac_Spline, Do_Spline and, at the highest level, Spline, found in Listing Two.
/* include all of the files that you might need. */
#include <ctype.h>
#include <memory.h>
#include <math.h>
#include <types.h>
#include <quickdraw.h>
#include <palette.h>
#include <toolutils.h>
#include <fonts.h>
#include <events.h>
#include <windows.h>
#include <dialogs.h>
#include <stdio.h>
#include <menus.h>
#include <desk.h>
#include <textedit.h>
#include <scrap.h>
#include <segload.h>
#include <controls.h>
#include <packages.h>
#include <slots.h>
#include <ShutDown.h>
#include <errors.h>
#include <files.h>
/* --------------------------------------------------------------------- */
/* The low-level help functions for graphics. */
/* Mean-squared distance between to coordinate pairs. */
int distance(i0, j0, i1, j1)
int i0, j0, i1, j1;
{ int res;
double x1, x2, y1, y2;
x1 = i0; x2 = i1; y1 = j0; y2 = j1;
res = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
return(res);
}
/* --------------------------------------------------------------------- */
/* The low-level SPLINE function. This function calculates and draws a
curved line along the path of a bi-cubic spline the equation for a coordinate
of the points on the spline is:
j = j1*t + j2*(1 - t) + W*(j2-j3)*t*(1 - t)*(1 - t) + W*(j1-j0)*t*t*(1 - t);
where: j : the coordinate being calculated.
t : the cubic variable.
W : a weighting factor.
(j1, j2) : the end-coordinates of the spline.
(j0, j3) : The control coordinates.
*/
_Spline (i0, j0, i1, j1, i2, j2, i3, j3)
int i0, j0, i1, j1, i2, j2, i3, j3;
{ float dt, t0, t1, t2, t3, t5, inc, dist, W;
int i, j, i5, j5, count;
inc = 2.5; /* Two pixel wide sampling rate */
W = 0.9; /* Set the weighting factor. */
MoveTo(j1, i1); /* Move to P1 */
dist = distance(i1, j1, i2, j2); /* The distance between the two points*/
if (inc < dist)
{ j5 = j1-j0;
i5 = i1-i0;
j3 = j2-j3;
i3 = i2-i3;
dt = inc/dist; /* Transform the sampling rate to a function of T */
count = 1.0/dt; /* Number of samples to be taken in a unit interval */
while (count-- > 0)
{ t1 = dt*count; /* calculate I and J as a function of T */
t2 = 1.0 - t1; /* (1 - t) */
t5 = W*t1*t1*t2; /* W*t*t*(1 - t) */
t3 = W*t1*t2*t2; /* W*t*(1 - t)*(1 - t) */
j = j1*t1 + j2*t2 + t3*j3 + j5*t5;
i = i1*t1 + i2*t2 + t3*i3 + i5*t5;
LineTo(j, i);
} }
else LineTo(i2, j2);
}
;; ----------------------------------------------------------------------
;; You need to change this to the directory where you have stored FF.fasl
(load "Lauzzana:Ray:Projects:Artifex:LLIB:FF")
;; ----------------------------------------------------------------------
;; You need to change this to the directory where C libraries is stored
(def-logical-pathname "CLIB;" "Lauzzana:Ray:Projects:Artifex:CLIB")
;; ----------------------------------------------------------------------
;; The high-level SPLINE function
(defun SPLINE (&rest p)
"
SPLINE (&rest point-list)
Sets up the front window as a graphics port to draw in, and calls
DO-SPLINE to do the actual work of drawing a spline.
"
(with-port (ask (front-window) wptr) (do-spline p)))
(defun DO-SPLINE (p)
"
D0-SPLINE (point-list)
A smooth curve coonecting the points.
"
(let ((p1 (car p))
(p2 (cadr p))
(p3 (caddr p))
(p4 (cadr (cddr p)))
(p5 (cadr (cdddr p))))
(cond ((or (null (pointp p1)) (null (pointp p4))) nil)
((and (pointp p1) (pointp p2) (pointp p3) (pointp p4))
(_Spline (I-coord p1)
(J-coord p1)
(I-coord p2)
(J-coord p2)
(I-coord p3)
(J-coord p3)
(I-coord p4)
(J-coord p4))
(if (pointp p5)
(append (list 'SPLINE p1) (cdr (DO-SPLINE (cdr p))))
(cons 'SPLINE p))))))
;; ----------------------------------------------------------------------
;; The high-level help functions for graphics
;; @@, representation for a point.
(defun @@ (a &optional b)
"
@@ () or (I-coordinate J-coordinate) or (integer)
A single user point or a point.
A screen location, in physical coordinates. (@@ 0 0) is the upper-left
corner. If single integer is recieved it is interpretted as a packed point,
and it is unpacked into a coordinate pair.
"
(cond ((and (numberp a) (numberp b)) (list '@@ (round a) (round b)))
((numberp a) (let ((i (floor (/ a 65536))))
(list '@@ i (- a (* 65536 i)))))))
;; The type test for a POINT.
(defun POINTP (p)
"
POINTP (item)
If the item is a point represented in in coordinates, ie. (@@ I J)
then TRUE, else NIL.
"
(and (listp p)
(or (= 3 (length p)) (= 2 (length p))) (equal (car p) '@@)))
;; I-COORDINATE
(defun I-COORD (p)
"
I-COORD (point)
Returns the vertical screen coordinate of a point.
"
(if (pointp p) (cadr p)))
;; J-COORDINATE
(defun J-COORD (p)
"
J-COORD (point)
Returns the horizontal screen coordinate of a point.
"
(if (pointp p) (caddr p)))
;; ----------------------------------------------------------------------
;; The binding to the low-level SPLINE function
;; There are two methods to bind a C function to Allegro.
;; The first method uses DEFFCFUN. Though this is a simpler function,
;; The binding will be lost if you build a stand-alone application.
;; Using DEFFCFUN the code would be:
;; (deffcfun (Mac_Spline "_Spline")
;; (integer integer integer integer integer integer integer integer) :novalue)
;; The second and preferred method uses MULTIPLE-VALUE-BIND and FF-CALL
;; to bind a physical entry-point to a symbol. This is a hardware dependent
;; solution, in that you need to represent the binding in terms of the
;; physical size and ordering of the machines stack. In the case of the
;; Mac II, parameters are stored in reverse order on the stack. Therefore,
;; the foreign function call must reverse the order of the parameters.
;; MULTIPLE-VALUE-BIND is used to perform the mapping of parametes.
;; FF-LOOKUP-ENTRY find the physical address of the entry-point for function.
;; FF-CALL executes the coda stored at a physical address.
(defun _Spline (a b c d e f g h)
"
_Spline (i0 j0 i1 j1 i2 j2 i3 j3)
Draws a spline between p1 and p2 to the control points p0 and p3.
"
(multiple-value-bind (entry a5) (ff-lookup-entry "_Spline")
(ff-call entry
:a5 a5 :long h :long g :long f :long e :long d :long c :long b :long a
:novalue)))
;; ----------------------------------------------------------------------
;; The loading the low-level SPLINE function
;; FF-LOAD is used to load binary files and their associated libraries.
;; In this case the object module for the function _Spline is stored in
;; the file <spline.c.o>. FF-LOAD searches this file for the symbolic name
;; _Spline and load the binary code associated with it.
;; In addition, it searches the libraries for unsatisfied symbolic references
;; which which may have occurred within the code and loads them as well.
;; In otherwords, it links and loads.
;; You need to change this to the directory where you have stored your C spline
(ff-load "Lauzzana:Ray:Papers:Spline:spline.c.o"
:entry-names
(list "_Spline" )
:libraries
(list "CLIB;StdCLib.o" "CLIB;CRuntime.o" "CLIB;CInterface.o"
"CLIB;math.o" "CLIB;CSANElib.o"))
Help Functions
One C routine (shown in Listing One) and four Lisp Help functions (presented in Listing Two) are required to calculate and display the spline.
The C routine distance calculates the mean-squared distance between two coordinate pairs. This calculation is used in _Spline to determine the distance between the end points.
A higher-level Lisp representation for a point @@ replaces the intrinsic #@ provided with Allegro CL. This representation establishes device-independence for high-level functions, such as SPLINE. The function @@ describes a screen location in physical coordinates. (@@ 0 0) is the upperleft corner. If a single integer is received, the integer is interpreted as a packed point, and it is unpacked into a coordinate pair.
The Lisp predicate POINTPtests for the pointness of its argument. If the argument is a point represented in coordinates (@@ 00 ) the argument returns T; otherwise the argument returns NIL. The two functions I-COORD and J-COORD extract the vertical and horizontal coordinates from a point.
-- R.L., D.P.
The C Routine
The routine _Spline calculates and draws a curved line along the path of a bicubic spline. This routine must solve the equations mentioned earlier for each point along the curve. The parameters to _Spline are the coordinates (i,j) of the four points P0, P1, P2, and P3. The routine has two parts: an initialization phase and a loop. Speed is important, so the routine contains the minimum number of repetitive calculations.
The initialization phase sets up a two-pixel-wide sampling rate, and a weighting factor of 0.9. If you wish to create faster but coarser splines, you would increase the value of inc to either 5 or 7. After these values have been established, the Macintosh Toolbox function MoveTo sets the current position to P1. The routine then calculates the distance between P1 and P2. If that distance is less than the sampling interval, _Spline uses LineTo to draw a straight line from P1 to P2.
To increase the speed of the routine, the bicubic equation is partially solved outside of the loop. A straightforward calculation of the coordinates would result in this loop with 18 multiplies and 19 additions, (Example 2).
while (t <1)
{ j = j1*t + j2*(1 - t) + W*(j2-j3)*t*(1 - t)*(1 - t) + W*(j1-j0)*t*t*
(1 - t);
i = i1*t + i2*(1 - t) + W*(i2-i3)*t*(1 - t)*(1 - t) + W*(i1-i0)*t*t*
(1 - t);
t = t + dt;
LineTo(i, j);
}
A more efficient partitioning of the equation produces this loop with 13 multiplies and 8 additions, as shown in Example 3.
while (t1 < 1)
{ t1 = t1 + dt;
t2 = 1.0 - t1;
t5 = W*t1*t1*t2;
t3 = W*t1*t2*t2;
j = j1*t1 + j2*t2 + t3*j3 + j5*t5;
i = i1*t1 + i2*t2 + t3*i3 + i5*t5;
LineTo (j, i);
}
The reduction in additions results from precalculating the factors, i3, j3, i5, and j5. The reduction in multiplication results from calculating the cubic factors t2, t3, and t5 only once for both coordinates. This may seem like a relatively minor improvement, but the calculation must be performed 100 or more times while the user is trying to instance a curve. In this sort of situation, every nanosecond counts.
The cubic variable t has a range from 0 to 1. The increment on this unit interval, dt, describes the rate of sampling of points on the spline. dt is the unit increment (t) on the variable t. For example, if you want to sample a point every 2.5 pixels and the distance between P1 and P2 is 100 pixels, the unit increment dt would have the value of 0.025. The reciprocal of dt, count, which is the number of points to be calculated. In this case, 40 points would be sampled along the spline.
In order to improve accuracy, the loop in the actual code is incremented with respect to count rather than t. This step incurs the additional cost of one multiply, but the resulting elimination of round-off errors improves the appearance of the curve.
Substantially worse algorithms that do not factor out the cubic variable t can be used to solve this equation. Better algorithms are also probably available. When working on problems of this sort, reach into your bag of algebraic tricks before you start coding.
Loading the C Routine
Before you can use the C routine from Lisp, you must first compile the routine and then load the Allegro CL Foreign Function Interface into your Lisp environment. Remember that you can only load relocatable object files, not sources or programs. In other words, you may only load compiled subroutines. The Foreign Function Interface will load any MPW C relocatable object files. It will not work with LightSpeed C or other third-party compilers.
Once you have compiled your C routine, start up Allegro CL. The simplest way to load the Foreign Function Interface uses the expression require. In order to use this expression, you must have already moved FF.fasl from the Foreign Function folder to the Library folder, as shown in Example 4(a).
<b> (a)</b>
(require 'FF)
<b>(b)</b>
(load "<pathname>:FF.fasl")
<b>(c)</b>
(def-logical-pathname "CLIB;" "<pathname>:MPW:CLibrary")
<b>(d)</b>
(ff-load "<pathname>:spline.c.o"
:entry-names
(list "_Spline")
:libraries
(list "CLIB;StdCLib.o" "CLIB;CRuntime.o" "CLIB;CInterface.o"
"CLIB;math.o" "CLIB;CSANElib.o"))
Another way to load the Foreign Function Interface uses load. In this case, you'll need to specify the exact <pathname7gt; to the folder where you have stored FF.fasl. See Example 4(b). You will also need to specify the folder that stores the C library functions that are provided with MPW C. To do so, create a logical pathname CLIB using deflogical-pathname, as demonstrated in Example 4(c).
You are now ready to load the _Spline function into your Lisp environment. The Foreign Function Utility ff-load loads binary files and their associated libraries. See Example 4(d).
In this case, the object module for the function _Spline is stored in the file called "spline.c.o." ff-load searches this file for the symbolic name _Spline. If it finds the name, it loads the associated binary code. ff-load then searches the libraries for any unsatisfied symbolic references, which may have occurred within the code, and loads them as well. For example, if you use the C sqrt function, you must tell Allegro CL which library to look in for the function. In other words, ff-load links and loads the routines identified in the :entry-names list, using the libraries in the :libraries list. If you wish to load more C functions, add them to the :entry-names list. ff-load is a time-consuming function, so you should call it as infrequently as possible.
Binding the C to Lisp
Once you've loaded _Spline into your environment, the function's code resides in the dynamic memory of your machine. To use the function, you must establish a symbolic reference to its code by binding it. In this case, the symbolic reference Mac_Spline is bound to the C symbol _Spline.
In Allegro Lisp you can bind a C function in two ways. The first method uses deffcfun. _Spline has eight parameters: i0, j0, and so forth. Each of the parameters is an integer and must be declared as such. The flag :novalue indicates that the routine produces only a side effect; the routine does not return a value. Types for both input and output variables are declared in this manner. Example 5(a) demonstrates this method.
<b>(a) </b>
(deffcfun (Mac_Spline "_Spline")
(integer integer integer integer integer integer integer integer)
:novalue)
<b>(b) </b>
(defun Mac_Spline (a b c d e f g h)
(multiple-value-bind (entry a5) (ff-lookup-entry "_Spline")
(ff-call entry
:a5 a5 :long h :long g :long f :long e :long d :long c :long
b :long a :novalue)))
<b>(c) </b>
(Mac_Spline 3 4 120 140 300 260 490 600)
Though deffcfun is a more simple function, the binding is lost if you build a stand-alone application. Most of the C variable types, such as long, char, integer, and word are available using deffcfun, but if you want to pass a list from Lisp or a structure from C, you are on your own. Good luck!
The second and preferred method of binding a C function uses ff-look-up-entry, ff-call, and multiple-value-bind to bind the physical entry point to a Lisp symbol. This method can be used for any MPW C relocatable object code, not just for C functions. In other words, you could even bind assembly language or Pascal code by using this method. This method is a hardware-dependent solution, because you must represent the binding in terms of the physical size and order of the machine's stack. In the case of the Mac II, parameters are stored in reverse order on the stack. The foreign function call must push the parameters onto the stack in reverse order.
The function ff-lookup-entry finds the physical address of the entry point for the _Spline routine and the location of the register to be used when the routine runs. Because this function returns two values, you must use the somewhat esoteric Common Lisp function multiple-value-bind to assign these values to the local variables entry and a5. The function ff-call then executes the code stored at the physical address specified by entry, using register a5. Notice that the parameters in ff-call are reversed from the declaration of Mac_Spline, as shown in Example 5(b).
At this point, Lisp can call your C routine, _Spline, through Mac_Spline. If you typed the following example into the Listener window, a curve would be drawn between the points (@@ 120 140) and (@@ 300 260). The control points for the curve are (@@ 3 4) and (@@ 490 350). The result is shown in Example 5(c).
Mac_Spline might serve as an adequate level of representation for some problems, but in the case of the spline, a higher level of representation is needed.
The High-Level Lisp Functions
The Mac_Spline function draws a spline segment in the current window. Because the user probably wants to combine several spline segments into a continuous curve, a high-level function Do-Spline must be used instead. Do-Spline is a tail-recursive function, and its argument is a list that contains an arbitrary number of points. In other words, Do-Spline draws a spline based on the first four points, then the next four points, and so on, until only three points remain in the list.
In this example, Do_Spline draws two spline segments connected at the point (@@ 300 260). See Example 6. The first spline segment is identical to the spline segment drawn in the previous example. The second spline segment is a curve between the points (@@ 300 260) and (@@ 490 350). The two curves are continuous at (@@ 300 260). A few problems still remain. First, Do_Spline draws the curve in your Listener window. You probably don't want to draw the curve over the text in the Listener window. Instead, you'd like to select the window in which the curve will be drawn. It's also preferable to invoke the function by using the points themselves, rather than by using a list that contains the points. The highest-level Lisp function SPLINE provides these capabilities:
(SPLINE window pO.... pN)
SPLINE uses the Allegro CL object function with-port to select the graphics port in which the spline will be drawn. It then calls Do-Spline to actually draw the spline. As a result, the SPLINE function can be called with any number of points and targeted to any window. This function could be instanced in a display list, referenced from a menu, and otherwise integrated into a graphics package.
(Do_Spline (list (@@ 3 4) (@@ 120 140) (@@ 300 260) (@@ 490 350) (@@ 25 30)))
General Usage
This spline function can be modified and used as a template for facilitating general connectivity between Lisp and C, or for writing similar C functions for use by Lisp. The Allegro CL Foreign Function Interface includes six functions to support this effort: ff-load, deffcfun, deffpfun, ff-call, ff-lookup-entry, and dispose-ffenv.
ff-load loads any MPW C object file and can be used to load assembly or Pascal code, as well as C code. It returns a foreign function environment that consists of code segments, a jump table, a static data area, and a set of active entry point names. It also removes dead code so that the environment includes only the code and the data that can be reached from the active entry points.
deffcfun and deffpfun define functions that coerce and type-check arguments before calling the foreign function. deffcfun is used for C and deffpfun for Pascal.
ff-call transfers control to the loaded object code and passes arguments according to the type-keyword/argument pairs. Possible type-keywords are :word, :long, :ptr, the data registers :dO to :d7, and the address registers :aO to :a5. It is a low-level function that is faster than deffcfun and deffpfun, because it does not type-check or coerce arguments. Its return values are indicated by similar keywords :word, :long, :ptr, :d0 to :d7, :a0 to :a4, and the empty value :novalue.
Product Information
MPW C Apple Programmers and Developers Association (APDA) 20525 Mariani Avenue, M/S 33G Cupertino, CA 95014 AppleLink: APDA 408-562-3910 800-282-2732 (U.S.) or 800-637-0029 (Canada) Suggested Retail price: $150 (Fall 1989) Requirements: MPW Development Environment, at least 2-Mbyte RAM, 128K ROM, a hard disk Macintosh System Software 6,02 or higher
Macintosh Allegro Common Lisp (Allegro CL) APDA (see MPW C above) Suggested Retail Price: $495 (Fall 1989) Requirements: Macintosh Plus SE, SE/30, II or IIx A second 800K disk drive At least 1-Mbyte RAM
Artifex Oudegracht 317 3511 PB Utrecht The Netherlands +31-(30)-340-866 Price: $300 for source code Requirements: Macintosh Plus SE, SE/30, II or IIx, Allegro CL A second 800K disk drive At least 2-Mbyte RAM
ff-lookup-entry returns two values that describe the entry point. The first value is a pointer to the entry point. The second value is the :a5 address register pointer for the environment where the entry point was found. ff-look-up returns NIL if the specified entry-point name doesn't exist. If the entry-point name exists in more than one environment, the function returns an undefined environment.
dispose-ffenv unloads the foreign function and frees up the memory space that was allocated for your functions.
These six functions are the tools that allow you to link C with Lisp. Together they provide a mechanism for accessing physical devices and for improving the computational performance of your Lisp environment.
References
D. Hearn and M.P. Baker. Computer Graphics. Englewood Cliffs, N.J.: Prentice-Hall International Editions, 1986. A good general graphics text with a clean description of a spline function.
Bartels, Beatty, and Barsky. An Introduction to the Use of Splines in Computer Graphics. Menlo Park, Calif.: Morgan Kaufman, 1988. A survey text that describes many types of splines.
Y. Fletcher and D.F. McAllister. "Automatic Tension Adjustment for Interpolatory Splines." IEEE Computer Graphics and Applications. 10, no. 1 (1990). A recent article that describes how to naturally smooth sections of the curve.
Ian E. Ashdown, "Curve Fitting with Cubic Splines," DDJ, September 1986.
