Cubic spline packages:
SPLINE1, SPLINE2, SPLINE3, and DRAWSPLINE
This document describes several spline packages: a set of packages for
computing a cubic spline, and a package for displaying such a cubic
spline on the Alto display. The package for computing splines is
available in three versions: SPLINE1.Bcpl, SPLINE2.Bcpl, and
SPLINE3.Bcpl. Each one contains a procedure for fitting cubic splines
to sets of data points, called knots, following algorithms documented
in the report "Spline Curve Techniques" (by Baudelaire, Flegal, &
Sproull), May 1977.
1- Spline computation packages:
The three packages SPLINE1, SPLINE2, and SPLINE3 contain a procedure of
the SAME name, with an IDENTICAL calling sequence:
success_ParametricSpline(N, x, y, p1x, p2x, p3x, p1y, p2y, p3y, type
[0])
N n=|N| is the number of knots. The sign of N tells whether the
knot coordinates are given in integer format (N is negative) or
floating point format (N is positive).
x, y are two tables containing the coordinates of the knots. They
are of length n (integer) or 2*n (floating point).
p1x, p2x, p3x, p1y, p2y, p3y are six tables of length 2*n in which
the coefficients defining the parametric splines are returned
(floating point). These coefficients are, respectively, the
first, second and third derivatives at each knot of the cubic
splines x(t) and y(t), t varying between 0 and 1. Notice that,
although only the first n-1 values of these derivatives are
necessary, the arrays should be of length 2*n.
type is either 0 (for natural end conditions, i.e. open ended curve)
or 1 (for periodicity, i.e. cyclic curve). In the later case, it
is mandatory that the first and last knots be identical. The
type defaults to 0 (natural end conditions).
The implementation of the parametric spline algorithm is different in
each packages: SPLINE1 implements a natural spline with unit step
parametrization (algorithm 1.2.7), SPLINE2 implements a natural spline
with chord length parametrization (algorithm 1.2.5), and SPLINE3
implements local cubic B-splines.
In addition, SPLINE2 contains the procedure CubicSpline which computes
a general non-parametric cubic spline (algorithm 1.2.5). The calling
sequence is:
success_CubicSpline(N, x, y, p1y, p2y, p3y, type [0])
with the same conventions as above.
------------
Copyright Xerox Corporation 1979
Cubic spline packages December 19, 1977 2
All the procedures need free storage, which they get from a zone you
must provide by setting the static PSzone. The amount of storage
needed is as follows: In the basic case (n positive, type=0): enough
for 8 floating point registers (16), plus 4*n. If n is negative, the
coordinates have to be converted to floating point format: so add 4*n.
If type is 1, add 6*n.
The static PSerror points to an error procedure that simply traps to
SWAT. The error routine is called by the statement: "... resultis
PSerror(errorNumber);" You may substitute your own error handling
routine. errorNumber=1 means "not enough storage." Other errors are
probably fatal.
The spline packages use the microcoded floating-point package
MICROFLOAT for all arithmetic calculations. The format of floating
point numbers is consistent with the conventions of that package.
Loading of the microcode in RAM and initialization of floating-point
routines (by calling procedure FPSetup) must be done before using
spline routines.
2- Spline display package:
DRAWSPLINE contains a set of procedures for displaying on an Alto
display bitmap a cubic spline defined by its knot coordinates. It uses
the procedure ParametricSpline defined above: the DRAWSPLINE package
must be loaded with one of the SPLINE packages.
The package must first be initialized: this is done by invoking the
procedure:
InitSpline(zone)
which loads and initializes the floating-point microcode, and provides
a zone to be used by all spline displaying and computation procedures:
the static PSzone will point to this zone. You may prefer to do
initialization yourself.
Splines are displayed on an "area" which is an arbitrary rectangular
window on the plane, mapped onto some arbitrary position inside a
bitmap. An area is defined by a call to the procedure:
area_DefineArea(bitmap, wordWidth, scanCount, Xw [0], Yw [0], Xleft
[0], Ybottom [0], width [16*wordWidth], height [scanCount])
bitmap is a pointer to an Alto display bitmap. You are responsible
for creating and linking the appropriate DCB for this bitmap.
wordWidth and scanCount define the x and y dimension of the bitmap.
Xw and Yw specify the bit position and the scanline position in the
bitmap of the lower-left corner of the window, relatively to the
lower-left corner of the bitmap. For good results, these numbers
should be positive, and respectively less than 16*wordWidth and
scanCount. The default window position is the corner of the
bitmap (Xw=0, Yw=0).
Xleft, Ybottom, width, and height specify a rectangular window on
the plane in which the spline is defined. This defines the
portion of the plane that is visible on the display bitmap: the
Cubic spline packages December 19, 1977 3
spline will be clipped to the limits of this window. The lower-
left corner of the window (plane coordinate Xleft, Ybottom) is
displayed as point (Xw, Yw) of the bitmap. The plane coordinate
system follows standard conventions: Y goes up, and X goes to the
right; one unit represents one display point. The window
defaults to fill the whole bitmap (Xleft=0, Ybottom=0,
width=16*wordWidth, height=scanCount). If the window is too
large when positioned at point (Xw, Yw), it is appropriately
reduced.
The procedure returns an "area", a structure to be used by the spline
drawing routine. Several area may exist simultaneously, on several
bitmaps or on the same bitmap. Areas which are not used any more are
released by the call:
Free(zone, area)
To compute and draw a spline defined by its knots, call:
success_DrawSpline(area, N, x, y, brush [0], drawMode [1], type [0])
area is a structure that has been obtained by a call to DefineArea.
N n=|N| is the number of knots. The sign of N tells whether the
knot coordinates are given in integer format (N is negative) or
floating point format (N is positive).
x, y are two tables containing the coordinates of the knots. They
are of length n (integer) or 2*n (floating point).
brush is a pointer to a small bitmap defining a brush. The brush
bitmap is 1 word wide and H words high. The first word contains
H, and it is followed by H words of bitmap. Standard brushes may
be obtained by calling the routine GetBrush (see below). If the
brush argument is ommitted or equal to zero, a single dot brush
is used.
drawMode is either 1 (the curve is "painted" onto the bitmap using
the brush), 2 (the curve is "xored"), or 3 (the curve is erased).
The procedure uses the microcode function BitBlt to paint, xor,
or erase the brush along the trajectory defined by the spline.
type is either 0 (for natural end conditions, i.e. open ended curve)
or 1 (for periodicity, i.e. cyclic curve). In the later case, it
is mandatory that the first and last knots be identical. The
type defaults to 0 (natural end conditions).
Standard brushes can be obtained by a call to
brush_GetBrush(brushShape, brushSize)
brushShape has one of the following values: 0 (round brush); 1
(square brush); 2 (flat horizontal brush); 3 (flat vertical
brush); 4 (flat diagonal brush).
brushSize is a number between 1 and 16 defining the size of the
brush: it is rounded to one of the values 1, 2, 4, 8 or 16.
The package DrawSpline must be loaded with the following files:
Cubic spline packages December 19, 1977 4
SPLINE1, SPLINE2, or SPLINE3
MICROFLOAT (small resident code for floating point)
MICROFLOATMC (floating point microcode; may be reclaimed after
initialization)
READPRAM (for loading the RAM; may be reclaimed after
initialization)