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)