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)