/*
 * File:      wxspline.cc
 * Purpose:     
 * Author:      Julian Smart
 * Created:     1993
 * Updated:	August 1994
 * RCS_ID:      $Id: wxspline.cc,v 1.2 1994/08/14 21:34:01 edz Exp $
 * Copyright:   (c) 1993, AIAI, University of Edinburgh
 */

// Has to be a comment as this file is #include\'d from wb_dc.cc
/* static const char sccsid[] = "@(#)wxspline.cc        1.3 5/9/94"; */

/*
 * Artificial Intelligence Applications Institute,                     
 * The University of Edinburgh
 */


/*
 *  Cubic B spline drawing code based on:
 *  Computer Graphics - A Programming Approach
 *  Steven Harrington (2nd edition)
 *  Published by McGraw-Hill
 *  Chapter 11 p400 - 417

 *  A B-spline is an interpolation curve that does not necessarily pass
 *  through all the sample points. This code implements a cubic B-spline
 *  function. The cubic B-spline functions interpolate over 4 sample
 *  points.

 *  The mathematical function that defines the curve can be expressed in
 *  parametric form as:
 * 
 *            X = fX(u) = sum(i to n) XiBi(u)
 *            Y = fY(u) = sum(i to n) YiBi(u)
 *
 *  where Bi(u) is called a blending function.
 *
 *  The function DrawSpline defines the blending functions for 
 *  a cubic B-spline, which are cubic polynomials in u. Special blending
 *  functions are required for the first, second, next to last and last
 *  section of the curve (a section is defined by 2 of the sample points),
 *  as well as the standard blending function. These special blending 
 *  functions are needed because of the requirement that the spline 
 *  must pass through the first and last sample points.
 *
 *  DrawSpline works by calculating points on the spline
 *  (at various values of u) and then drawing straight lines
 *  between the points to approximate the spline. Points on the spline 
 *  are calculated for each section of the curve, moving along one 
 *  section at a time until we reach the end of the sample points.
 */

static wxPoint *startPoint = NULL;
static wxPoint *samplePoints = NULL;

// function prototype
static void allocBlendArrays (double **mainBlend[],
			      double **firstBlend[],
			      double **secondBlend[],
			      double **penultimateBlend[],
			      double **lastBlend[],
			      int nSegments,
			      int numberOfLines);

// function prototype
static void initBSpline (int numberOfLines,
			 double *mainBlend[],
			 double *firstBlend[],
			 double *secondBlend[],
			 double *penultimateBlend[],
			 double *lastBlend[]);

// function prototype
static void MakeCurve (wxbDC * dc, wxPoint samplePoints[],
		       int numberOfLines,
		       double *blendFunction[],
		       wxPoint startPoint[]);

// function prototype
static void nextSection (wxPoint samplePoints[]);

// function prototype
static void nextSamplePoint (int &currentPoint,
			     wxPoint samplePoints[],
			     wxPoint points[]);

/*************************************************************************
 * This is the main function that draws the spline for a given set of
 * sample points. It's arguments are:
 *
 *   1) dc -- the device on which to draw the spline,
 *   2) nPoints -- the number of sample points
 *   3) an array of structures, each structure containing a x and y coordinate
 *      of a sample point. The array is of size nPoints -- this is
 *      guaranteed by the calling function -- so no checking is done.
 */

void wxbDC::DrawSpline (wxList * list)
{
  wxPoint *points = new wxPoint[list->Number ()];
  int i = 0;

  for(wxNode *node = list->First (); node; node = node->Next())
    {
      wxPoint *point = (wxPoint *) node->Data ();
      points[i].x = point->x;
      points[i++].y = point->y;
    }
  DrawSpline (i, points);
  delete[]points;
}

void wxbDC::DrawSpline (int nPoints, wxPoint points[])
{
/*
   First declare the number of line segments per section, to make
   it easy to change this value if more line segments are required
   to better draw the spline. When numberOfLines = 3, you can see that
   the spline is made up of straight line segments, but when 
   numberOfLines = 30, the spline looks smooth.
 */

  const int numberOfLines = 30;

/* declare the array to hold the x and y coordinates for the start of
   each spline segment that is drawn. startPoint[0].x and startPoint[0].y
   are constantly updated, after the spline segment is drawn, to be the 
   end of the last drawn spline segment -- see function MakeCurve.
 */

  startPoint = new wxPoint[1];

/* declare the array to hold the sample points that are used to calculate
   the x and y coordinates for the spline segments. To draw a spline between
   any 2 sample points actually requires taking into account 4 sample points
 */

  samplePoints = new wxPoint[4];

// declare the arrays to hold the blending functions

  double **mainBlend = NULL;
  double **firstBlend = NULL;
  double **secondBlend = NULL;
  double **penultimateBlend = NULL;
  double **lastBlend = NULL;

// declare the second dimension of the array, which is due to the number
  // of sample points taken into account when drawing a spline

  const int nSegments = 4;

// Allocate memory for the blending function arrays

  allocBlendArrays (&mainBlend, &firstBlend, &secondBlend,
		    &penultimateBlend, &lastBlend,
		    nSegments, numberOfLines);

// instantiate the blending function arrays with the appropriate values

  initBSpline (numberOfLines, mainBlend, firstBlend,
	       secondBlend, penultimateBlend, lastBlend);

/* 0, 1 and 2 sample points are special cases and are handled separately */

  int currentPoint = 0;

  if (nPoints <= 1)
    {
      return;
    }
  if (nPoints == 2)
    {
      startPoint[0].x = points[0].x;
      startPoint[0].y = points[0].y;
      float x = points[1].x;
      float y = points[1].y;
      DrawLine (startPoint[0].x, startPoint[0].y, x, y);
    }

/* 3 - 7 sample points are handled by repeating the first and last point
 * an equal number of times, such that the number of sample points becomes 
 * >= 8. The reason for this is that the algorithm really expects a minimum
 * of 8 sample points.
 * 
 * Hence the array samplePoints will contain repetitions of points in the
 * array called points (which are the actual sample points that the function
 * is called with.
 */

  if (nPoints == 3)
    {
      currentPoint = 0;
      startPoint[0].x = points[0].x;
      startPoint[0].y = points[0].y;
      int i;
      for (i = 0; i < 4; i++)
	{
	  samplePoints[i].x = points[0].x;
	  samplePoints[i].y = points[0].y;
	}
      MakeCurve (this, samplePoints, numberOfLines, firstBlend, startPoint);
      nextSection (samplePoints);
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 secondBlend, startPoint);
      nextSection (samplePoints);
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 mainBlend, startPoint);
      nextSection (samplePoints);
// reached the last sample point, so compensate for the fact that
      // currentPoint will be incremented by 1 in the function nextSamplePoint
      currentPoint = currentPoint - 1;
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 mainBlend, startPoint);
      nextSection (samplePoints);
      currentPoint = currentPoint - 1;
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 penultimateBlend, startPoint);
      nextSection (samplePoints);
      currentPoint = currentPoint - 1;
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 lastBlend, startPoint);
    }

  if (nPoints >= 4 && nPoints < 8)
    {
      currentPoint = 0;
      startPoint[0].x = points[0].x;
      startPoint[0].y = points[0].y;
      int i;
      for (i = 0; i < 3; i++)
	{
	  samplePoints[i].x = points[0].x;
	  samplePoints[i].y = points[0].y;
	}
      samplePoints[3].x = points[1].x;
      samplePoints[3].y = points[1].y;
      currentPoint = currentPoint + 1;
      MakeCurve (this, samplePoints, numberOfLines, firstBlend, startPoint);
      nextSection (samplePoints);
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 secondBlend, startPoint);
      nextSection (samplePoints);
      int j;
      for (j = 0; j < (nPoints - 3); j++)
	{
	  nextSamplePoint (currentPoint, samplePoints, points);
	  MakeCurve (this, samplePoints, numberOfLines,
		     mainBlend, startPoint);
	  nextSection (samplePoints);
	}
// reached the last sample point, so compensate for the fact that
      // currentPoint will be incremented by 1 in the function nextSamplePoint
      currentPoint = currentPoint - 1;
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 penultimateBlend, startPoint);
      nextSection (samplePoints);
      currentPoint = currentPoint - 1;
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 lastBlend, startPoint);
    }
  if (nPoints >= 8)
    {
      currentPoint = 0;
      startPoint[0].x = points[0].x;
      startPoint[0].y = points[0].y;
      int i;
      for (i = 0; i < 4; i++)
	{
	  samplePoints[i].x = points[i].x;
	  samplePoints[i].y = points[i].y;
	}
      currentPoint = currentPoint + 3;
      MakeCurve (this, samplePoints, numberOfLines, firstBlend, startPoint);
      nextSection (samplePoints);
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 secondBlend, startPoint);
      nextSection (samplePoints);
      while (currentPoint < (nPoints - 3))
	{
	  nextSamplePoint (currentPoint, samplePoints, points);
	  MakeCurve (this, samplePoints, numberOfLines,
		     mainBlend, startPoint);
	  nextSection (samplePoints);
	}
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 penultimateBlend, startPoint);
      nextSection (samplePoints);
      nextSamplePoint (currentPoint, samplePoints, points);
      MakeCurve (this, samplePoints, numberOfLines,
		 lastBlend, startPoint);
    }
}



/*************************************************************************
 * This function alocates memory for a blending function array
 */

static void 
allocArray (double ***ar, int nSegments, int numberOfLines)
{
  *ar = new double *[nSegments];
  int i;
  for (i = 0; i < nSegments; i++)
    (*ar)[i] = new double[numberOfLines];
}

/*************************************************************************
 * This function alocates memory for all the blending function arrays
 */

static void 
allocBlendArrays (double **mainBlend[],
		  double **firstBlend[],
		  double **secondBlend[],
		  double **penultimateBlend[],
		  double **lastBlend[],
		  int nSegments,
		  int numberOfLines)
{
  allocArray (mainBlend, nSegments, numberOfLines);
  allocArray (firstBlend, nSegments, numberOfLines);
  allocArray (secondBlend, nSegments, numberOfLines);
  allocArray (penultimateBlend, nSegments, numberOfLines);
  allocArray (lastBlend, nSegments, numberOfLines);
}

/*************************************************************************
 * This function initialise the spline blending function arrays.
 * It's arguments are:
 *
 * 1) numberOfLines -- the number of segment lines to use to draw
 *                     the spline between two sample points.
 *	               This is a set at the top of the file.
 * 2) - 6) Blending function arrays of size 4 by numberOfLines.
 *         The reason the first array dimension is 4 is that 4 sample
 *         points are required by this algorithm to calculate
 *         the x and y coordinates of points on the spline to be drawn.
 *	   
 *         The values in these arrays are constant, irrespective of
 *	   the sample points.
 */

static void 
initBSpline (int numberOfLines,
	     double *mainBlend[],
	     double *firstBlend[],
	     double *secondBlend[],
	     double *penultimateBlend[],
	     double *lastBlend[])

/*
 * The cubic B-spline blending function interpolates over 4 sample points
 * Thus in the code below the first index of the the Blending function array,
 * is either 0,1,2,3. The second index of the blending function is related 
 * to how many line segments are used to draw the spline for two sample
 * points (that is in a section of the spline).
 */

{
  int i;
  for (i = 0; i < numberOfLines; i++)
    {
      double u = (double) (i + 1) / numberOfLines;
      firstBlend[0][i] = pow (1.0 - u, 3);
      firstBlend[3][i] = pow (u, 3) / 6.0;
      firstBlend[2][i] = ((3.0 / 2.0) - (11.0 * u / 12.0))
	* pow (u, 2);
      firstBlend[1][i] = 1.0 - firstBlend[0][i]
	- firstBlend[2][i]
	- firstBlend[3][i];

      secondBlend[0][i] = firstBlend[0][i] / 4.0;
      secondBlend[3][i] = firstBlend[3][i];
      secondBlend[2][i] = (((1 - u) * u + 1.0) * u + 1.0 / 3.0) / 2.0;
      secondBlend[1][i] = 1.0 - secondBlend[0][i]
	- secondBlend[2][i]
	- secondBlend[3][i];

      mainBlend[0][i] = firstBlend[0][i] / 6.0;
      mainBlend[3][i] = firstBlend[3][i];
      mainBlend[2][i] = secondBlend[2][i];
      mainBlend[1][i] = 1.0 - mainBlend[0][i]
	- mainBlend[2][i]
	- mainBlend[3][i];

      int j = numberOfLines - i - 2;
/*  -2 because both i and j are array subscripts and go from 0 rather than 
 *  from 1, as they do in the algorithm. 
 *
 *  Having j >= 0 lets through all values of j except the last, which
 *  is the (numberOfLines - 1)th index, like the algorithm does.
 */
      if (j >= 0)
	{
	  penultimateBlend[0][j] = secondBlend[3][i];
	  penultimateBlend[1][j] = secondBlend[2][i];
	  penultimateBlend[2][j] = secondBlend[1][i];
	  penultimateBlend[3][j] = secondBlend[0][i];

	  lastBlend[0][j] = firstBlend[3][i];
	  lastBlend[1][j] = firstBlend[2][i];
	  lastBlend[2][j] = firstBlend[1][i];
	  lastBlend[3][j] = firstBlend[0][i];
	}
    }

  penultimateBlend[0][numberOfLines - 1] = 0.0;
  penultimateBlend[1][numberOfLines - 1] = 1.0 / 6.0;
  penultimateBlend[2][numberOfLines - 1] = 7.0 / 12.0;
  penultimateBlend[3][numberOfLines - 1] = 1.0 / 4.0;

  lastBlend[0][numberOfLines - 1] = 0.0;
  lastBlend[1][numberOfLines - 1] = 0.0;
  lastBlend[2][numberOfLines - 1] = 0.0;
  lastBlend[3][numberOfLines - 1] = 1.0;
}

/*************************************************************************
 *  This function draws the spline from the startPoint (which will be the
 *  last calculated spline point for the previous sample section), and
 *  draws numberOfLines spline segments.
 *
 *  It's arguments are:
 *
 *  1) dc -- the device on which to draw the spline
 *  2) samplePoints[4] -- the 4 element array of sample points for the
 *                        current spline section
 *  3) numberOfLines -- number of segment lines per spline section
 *  4) blendFunction -- the particular blend function array which applies
 *                      for this section of the spline. There are
 *  		        5 blend function arrays, which are initialised
 * 		        in function initBSpline.
 *  5) startPoint -- the 1 element array which holds the x and y 
 *                   coordinates of the point where this spline is to
 * 		     drawn from -- this is updated in the function such
 *		     that the coordinates are always the end coordinates
 *		     of the spline so far.
 */

static void 
MakeCurve (wxbDC * dc, wxPoint samplePoints[],
	   int numberOfLines,
	   double *blendFunction[],
	   wxPoint startPoint[])
{
  int j;
  for (j = 0; j < numberOfLines; j++)
    {
      double x = 0.0;
      double y = 0.0;
      int i;
      for (i = 0; i < 4; i++)
	{
	  x = x + samplePoints[i].x * blendFunction[i][j];
	  y = y + samplePoints[i].y * blendFunction[i][j];
	}
      dc->DrawLine ((float) startPoint[0].x, (float) startPoint[0].y, (float) x, (float) y);
      startPoint[0].x = (float) x;
      startPoint[0].y = (float) y;
    }
}

/*************************************************************************
 *  This function advances the sample points, being used to determine
 *  the spline curve, by 1. The function nextSamplePoint (below) gets
 *  the new sample point.
 *
 *  It's argument is:
 *
 *  1) samplePoints[4] -- the 4 element array of sample points for the
 *                        current spline section
 */

static void 
nextSection (wxPoint samplePoints[])
{
  int i;
  for (i = 0; i < 3; i++)
    {
      samplePoints[i].x = samplePoints[i + 1].x;
      samplePoints[i].y = samplePoints[i + 1].y;
    }
}

/*************************************************************************
 *  This function gets the next sample point in order to calculate
 *  the next section of the spline curve.
 *
 *  It's arguments are:
 *
 *  1) currentPoint -- a variable which holds the index number to the
 *                     current array element in points (the array in which all
 *		       the sample points are held). The current array element
 *		       is the sample point that we have got to in points[].
 *
 *  2) samplePoints -- the 4 element array of sample points for the
 *                     current spline section
 *   3) points -- the nPoints size array, that hold the sample points
 *	 
 */

static void 
nextSamplePoint (int &currentPoint,
		 wxPoint samplePoints[], wxPoint points[])
{

// move on to next sample point, and put this as the 4th element in
  // the samplePoints array
  currentPoint = currentPoint + 1;
  samplePoints[3].x = points[currentPoint].x;
  samplePoints[3].y = points[currentPoint].y;
}

#if USE_POSTSCRIPT
#include "wx_dcps.h"

void wxPostScriptDC::
DrawSpline (float x1, float y1, float x2, float y2, float x3, float y3)
{
  wxDC::DrawSpline (x1, y1, x2, y2, x3, y3);
}

void wxPostScriptDC::DrawSpline (wxList * points)
{
  wxDC::DrawSpline (points);
}

void wxPostScriptDC::DrawSpline (int n, wxPoint points[])
{
  wxDC::DrawSpline (n, points);
}

#endif
