\documentclass[12pt]{article}

\usepackage{amsmath,amsthm,amssymb}
\usepackage[dvips]{graphicx}
\usepackage[dvips]{epsfig}

\newcommand{\single}{\def\baselinestretch{1.0}\large\normalsize}
\newcommand{\double}{\def\baselinestretch{1.5}\large\normalsize}
\newcommand{\triple}{\def\baselinestretch{2.2}\large\normalsize}
\newcommand{\wider }{\def\baselinestretch{1.2}\large\normalsize}

\newcommand{\openN}{{{\rm I}\kern-.16em {\rm N}}}
\newcommand{\openZ}{{{\rm Z}\kern-.28em{\rm Z}}}
\newcommand{\openR}{{{\rm I}\kern-.16em {\rm R}}}
\newcommand{\lsim}{\mbox{ \raisebox{-1.0ex}{\mbox{$\stackrel{\textstyle < }{\sim}$}} }}
\newcommand{\gsim}{\mbox{ \raisebox{-1.0ex}{\mbox{$\stackrel{\textstyle > }{\sim}$}} }}

\def\rd{{\rm d}}
\def\re{{\rm e}}
\def\ri{{\rm i}}
\def\Re{{\rm Re}\;\!}
\def\Im{{\rm Im}\;\!}
\def\sign{{\rm sign}\,\!}
\def\cross{\!\times\!}
\def\dotpr{\!\cdot\!}
\def\sp{\qquad\quad}
\def\rp{{\bf r}'}
\def\c{{\bf c}}
\def\a{{\bf a}}
\def\b{{\bf b}}
\def\ac{\overline{\bf a}}
\def\bc{\overline{\bf b}}
\def\d{{\bf d}}
\def\f{{\bf f}}
\def\g{{\bf g}}
\def\h{{\bf h}}
\def\k{{\bf k}}
\def\n{{\bf n}}
\def\p{{\bf p}}
\def\r{{\bf r}}
\def\t{{\bf t}}
\def\z{{\bf z}}
\def\w{{\bf w}}
\def\G{{\bf G}}
\def\H{{\bf H}}
\def\R{{\bf R}}
\def\M{{\bf M}}
\def\q{{\bf q}}
\def\l{{\bf l}}
\def\x{{\bf x}}
\def\y{{\bf y}}
\def\u{{\bf u}}

\newcommand{\wc}{\overline{\w}}
\def\hz{{\widehat {\bf z}}}
\def\hw{{\widehat {\bf w}}}
\def\dz{\Delta{\bf z}}
\newcommand{\bftau}{{\mbox{\boldmath $\tau$}}}
\newcommand{\bfzeta}{{\mbox{\boldmath $\zeta$}}}
\newcommand{\bfsigma}{{\mbox{\boldmath $\sigma$}}}
\newcommand{\bfphi}{{\mbox{\boldmath $\phi$}}}
\newcommand{\bfxi}{{\mbox{\boldmath $\xi$}}}

\def\half{\textstyle\frac{1}{2}\displaystyle}
\def\third{\textstyle\frac{1}{3}\displaystyle}
\def\fifth{\textstyle\frac{1}{5}\displaystyle}

\def\ldash{\vrule height 3pt width 0.35in depth -2.5pt}

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\ba}{\begin{eqnarray}}
\newcommand{\ea}{\end{eqnarray}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}

\newtheorem{dfn}{Definition}
\newtheorem{rmk}{Remark}
\newtheorem{lma}{Lemma}
\newtheorem{crl}{Corollary}
\newtheorem{thm}{Theorem}
\newtheorem{prn}{Proposition}
\newtheorem{prb}{Problem}
\newtheorem{exm}{Example}
\newcommand{\prf}{\noindent{{\bf Proof} :\ }}
\newcommand{\QED}{\vrule height 1.4ex width 1.0ex depth -.1ex\ \medskip}

\begin{document}

\title{{\tt PHquintic} Software Library: User Manual}

\author{
Bohan Dong and Rida~T.~Farouki \\
Department of Mechanical and Aerospace Engineering, \\
University of California, Davis, CA 95616, USA
}

\date{}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}

\section{Software packages}

Two software packages have been prepared. The first package, found in the 
file {\tt PHquintic.c}, is written in plain {\tt C} language and offers a 
set of modular functions that execute each of the basic PH curve construction 
and analysis computations described in the paper. The function prototypes 
are specified below. This package allows a software developer to ``pick and 
choose'' those functions of primary interest in a specific application 
context, and incorporate them in an existing software system with minimum 
effort. The main program accompanying these functions provides some sample 
data and function calls to test the various functions, but no graphics 
capability.

The second package, contained in the zip file {\tt InteractivePHquintic}, 
is implemented in {\tt C++} for compatibility with the MFC and OpenGL 
libraries, and provides interactive graphical construction, manipulation, 
and analysis capabilities (these libraries are required to compile and run 
the package). The unzipped package can be compiled and run by opening a 
{\tt VC++} project file in Microsoft Visual Studio. The basic functions 
in {\tt PHquintic.c} are included in this package, but the interfaces are 
modified to meet the requirements of {\tt C++} and the MFC and OpenGL 
libraries. This package offers a more visual and intuitive user interface, 
but is perhaps less well--suited to the purpose of porting individual 
functions to an existing software system.

\section{Function prototypes}

The prototype for each function in {\tt PHquintic.c} is described below.

\subsection{PH quintic representation}

The data defining a single PH quintic segment is encapsulated in the 
following {\tt C} struct.

\medskip

{\tt
\smallskip\noindent
struct PHquintic \{ 

\smallskip\noindent
complex double p[6] ; /* Bezier control points of PH quintic */

\smallskip\noindent
complex double w[3] ; /* Bernstein coefficients of w polynomial */ 

\smallskip\noindent
double sigma[5] ; /* parametric speed Bernstein coefficients */ 

\smallskip\noindent
double s[6] ; /* arc length Bernstein coefficients */ 

\smallskip\noindent
\} ; 
}

\bigskip\noindent
The complex arrays {\tt p[6]} and {\tt w[3]} store the B\'ezier control 
points $\p_0,\ldots,\p_5$ of the curve, and coefficients $\w_0,\w_1,\w_2$ 
of the quadratic polynomial $\w(t)$. The real arrays {\tt sigma[5]} and 
{\tt s[6]} store the coefficients of the parametric speed and arc length 
polynomials, $\sigma(t)$ and $s(t)$. Note that this specification is 
redundant, since $\p_1,\ldots,\p_5$, $\sigma_0,\ldots,\sigma_4$, and 
$s_0,\ldots,s_5$ can be determined from $\p_0$ and $\w_0,\w_1,\w_2$ alone. 
However, pre--computing the entire contents of a {\tt PHquintic} struct 
can save considerable effort in subsequent usage of the PH quintic segment 
it defines.

\subsection{PH quintic offset curve}

The prototype for the function that computes the offset to a PH quintic 
segment is as follows. The struct {\tt curve} passes the data that 
defines the PH quintic to the function, the value {\tt d} defines the 
signed\footnote{The offset distance is positive to the {\it right\/} 
of the curve $\r(t)$, relative to the sense of increasing parameter $t$.}
offset distance, and the homogeneous coordinates of the control points 
for the degree 9 rational offset curve are returned in the arrays 
{\tt W[]}, {\tt X[]}, {\tt Y[]}.

{\tt 
\begin{tabbing}
void PHquintic\underline{$\hphantom{x}$}offset( \= double d , \\
		       \> struct PHquintic *curve , \\
		       \> double W[] , double X[] , double Y[] )
\end{tabbing}
}

\subsection{PH quintic elastic bending energy}

The prototype for the function that computes the bending energy of a PH 
quintic segment is as follows. The struct {\tt curve} passes the data 
defining the PH quintic to the function, and the computed bending energy 
is returned as the value of the function.

\begin{quote}
{\tt 
\begin{tabbing}
double PHquintic\underline{$\hphantom{x}$}energy( struct PHquintic *curve )
\end{tabbing}
}
\end{quote}

\subsection{First--order Hermite interpolants}

The prototype for the function that constructs a PH quintic segment is 
as follows. The complex variables {\tt p0}, {\tt p1}, {\tt p4}, {\tt p5} 
pass the initial and final pairs of control points to the function, and 
the data defining the constructed PH quintic are returned in the struct 
{\tt curve}.

\bigskip

\begin{quote}
{\tt 
\begin{tabbing}
void construct\underline{$\hphantom{x}$}PHquintic( \= complex double p0 , \\
\> complex double p1 , \\
\> complex double p4 , \\
\> complex double p5 , \\
\> struct PHquintic *curve )
\end{tabbing}
}
\end{quote}

\subsection{$C^2$ PH quintic spline curves}

Although the algorithms to compute open and closed $C^2$ PH quintic splines 
have much in common, they also differ in numerous details. To avoid the use 
of many conditional statements accommodating the end conditions, they are 
implemented in separate functions. The prototypes are as follows. 

\begin{quote}
{\tt
\begin{tabbing}
void open\underline{\hphantom{x}}PHquintic\underline{\hphantom{x}}spline( 
\= int n , \\
\> complex double q[] , \\
\> struct PHquintic spline[] )
\end{tabbing}
}

{\tt
\begin{tabbing}
void closed\underline{\hphantom{x}}PHquintic\underline{\hphantom{x}}spline( 
\= int n , \\
\> complex double q[] , \\
\> struct PHquintic spline[] )
\end{tabbing}
}
\end{quote}

\noindent
Here the integer {\tt n} defines the number of interpolation points 
(namely, {\tt n}+1), passed to the function through the array of complex 
values {\tt q[]} --- these points are labelled {\tt q[0]},$\ldots$,
{\tt q[n]}. The {\tt n} PH quintic segments defining the constructed 
spline curve are returned through the struct array {\tt spline[]} --- 
these segments are labelled {\tt spline[1]},$\ldots$,{\tt spline[n]}.

\bigskip\noindent
The functions {\tt tridiag\underline{\hphantom{x}}open()} and
{\tt tridiag\underline{\hphantom{x}}closed()} are called to solve 
the tridiagonal system arising in each Newton--Raphson iteration. 
The inputs to these functions are the dimension {\tt n} of the system, 
arrays {\tt a[]}, {\tt b[]}, {\tt c[]} defining the lower, main, and 
upper diagonal matrix elements, and the array {\tt d[]} of right--hand 
side values. The solutions are returned in the array {\tt x[]}. 

\bigskip\noindent
The function {\tt beval()} is another basic utility, that receives as
input the degree {\tt n} and array of Bernstein coefficients {\tt b[]} of 
a polynomial, and an independent variable value {\tt t}, and returns the 
polynomial value computed by the de Casteljau algorithm. The parameter
{\tt MAXDEGREE} sets that maximum polynomial degree that {\tt beval()}
can accommodate.

\section{Interactive implementation}

The interactive implementation allows the user to input the point data 
that defines a single PH quintic segment or a $C^2$ PH quintic interpolating 
spline by mouse, and to modify the resulting curve in real time by using 
the mouse to move these points. Key properties of the resulting PH curves 
(arc length, bending energy, etc.) are reported, and offset curves can 
also be constructed. For applications in which the point data must be 
precisely specified, the user can type in the point coordinates.

Individual PH quintic curve segments are defined by the {\tt PHquintic} 
struct, and PH quintic splines are defined as arrays of these structs. 
Class {\tt PlanarPH} defines basic functions for computing and analyzing 
these curves. To ensure a high level of precision, all complex variables 
in the class are type double.

\begin{quote}
{\tt
PlanarPH(const CPointPH m\underline{\hphantom{x}}pt[]); \\
PlanarPH(const CPointPH m\underline{\hphantom{x}}pt[], int index);
}
\end{quote}

\noindent
The overloading constructors (for a single PH quintic Hermite interpolant
and a PH quintic spline, respectively) convert the point coordinates 
specified by the user from type {\tt CPointPH} to complex double. The 
{\tt CPoint} type captured in the window display is long int, so the point 
type is redefined as {\tt CPointPH}, which gives a representation of plane 
coordinates in type double.

The {\tt beval()} function is used to plot PH curves. This function 
is over--loaded to evaluate polynomials with {\it complex\/} Bernstein 
coefficients, to obtain the curve points directly. The friend function is 
a non--member function, but can access the private and protected members. 
Friend utility functions are typically used to allow mutual access to 
private or protected members of different classes. It also allows other 
classes to invoke functions using a concise syntax --- e.g., {\tt iter 
= getIter(pph)}, rather than {\tt iter = pph.getIter()}.

\bigskip\noindent
{\tt
friend double beval(int n, const double b[], double t); \\
friend complex<double> beval(int n, const complex<double> b[], \\
\mbox{} \hfill double t);
}

\bigskip\noindent
The function {\tt Spline()} computes a $C^2$ PH quintic spline 
interpolating {\tt num}+1 points labelled $0,\ldots,{\tt num}$ under 
specified end conditions. The coordinates of these points are stored in 
the complex array {\tt q[]}. The data that defines the {\tt num} PH quintic 
segments of the constructed spline curve are returned in the {\tt PHquintic} 
struct array {\tt spline[]}. The Boolean parameter {\tt closed} specifies 
the end conditions (cubic end spans or periodic end conditions, for open 
and closed curves, respectively). To obtain a closed $C^2$ spline, the 
user types ``{\tt c}'' after entering the last point with the mouse. 
The functions {\tt tridiag\underline{\hphantom{x}}open()} and 
{\tt tridiag\underline{\hphantom{x}}closed()} solve the tridiagonal 
systems for these two cases.

\begin{quote}
{\tt
void Spline(BOOL closed); \\
friend void tridiag\underline{\hphantom{x}}open($\ldots$); \\
friend void tridiag\underline{\hphantom{x}}closed($\ldots$);
}
\end{quote}

\noindent
The following functions define various interfaces for passing data. 
External functions must call {\tt getCtrlPt} to obtain the complex 
values that define the control points. {\tt getIter} returns the number of 
Newton--Raphson iterations employed in the spline construction, stored in 
the variable {\tt iter}. Similarly, the functions {\tt getParaSpeed}, 
{\tt getArcLength}, and {\tt getEnergy} compute the parametric speed, 
arc length, and bending energy.

\bigskip\noindent
{\tt
friend complex<double> getCtrlPt(const~PlanarPH~\&pph, int~i, int~j); \\
friend int getIter(const PlanarPH \&pph); \\
friend double getParaSpeed(const PlanarPH \&pph, int i, double t); \\
friend double getArcLength(const PlanarPH \&pph, int i, double t); \\
friend double getEnergy(const PlanarPH \&pph, int j);
}

\bigskip\noindent
In order to plot the constructed PH curves on the screen, OpenGL 
must first be initialized in the view class of MFC --- this is named 
{\tt PlanarPH\underline{\hphantom{x}}mfcView}, inherited from the base 
class {\tt CView}. 

\begin{quote}
{\tt
int index, status, pointing; \\
CPointPH o\underline{\hphantom{x}}ActRF, o\underline{\hphantom{x}}ActRFTrans; \\
CPointPH ptActRF[Max+1]; \\
CPointPH getAbsCoord(CPointPH pt); \\
CPointPH getActCoord(CPointPH pt); \\
double Distance(CPointPH p1, CPointPH p2);
}
\end{quote}

\noindent
The variable {\tt index} (={\tt num}+1) records the number of input points, 
and {\tt status} tracks the program mode (plotting, analyzing, translating, 
etc). The variable {\tt pointing} identifies a point selected by the user 
after the curve is plotted, and the selected point is highlighted 
({\tt pointing} = $-1$ if no point is selected).

The program employs two coordinate systems, absolute and relative, to 
solve translation and display problems. For absolute coordinates, the window 
display selects the left upper window corner as the origin, with a downward 
ordinate direction. However, OpenGL selects the left lower corner as origin, 
with an upward ordinate direction. In both cases, the abscissa direction 
is to the right. The origin of the relative coordinates, in the absolute 
coordinate system, is defined by {\tt o\underline{\hphantom{x}}ActRF}. All 
calculations are performed in the relative coordinates, including cursor 
location and PH curve computations. The array {\tt ptActRF[]} stores the 
relative coordinates of the input points. By calling the functions 
{\tt getAbsCoord()} and {\tt getActCoord}, the coordinates of any point 
can be transformed between the relative and absolute systems. The function 
{\tt Distance()} returns the distance between two points.

\begin{quote}
{\tt
PlanarPH pph; \\
void InitPH(); \\
void DrawLine(int nIndex, int flag);
}
\end{quote}

Before rendering, the function {\tt InitPH()} should be called in most 
cases to initialize {\tt pph}, which is an object of class {\tt PlanarPH}. 
The plotting function {\tt DrawLine} is called to plot a single point, a
whole curve, or an offset, according to whether {\tt flag} is equal to 
{\tt plotPoint}, {\tt plotSpline}, or {\tt plotOffset}. {\tt nIndex} 
indicates the number of points to be plotted when {\tt flag} equals 
{\tt plotPoint}. Otherwise, {\tt nIndex} is the number of the last 
point which should be plotted.

\begin{quote}
{\tt
BOOL isMenuPh, isMenuCubic, isMenuPhCtrl, isMenuCubicCtrl; \\
//Status of Menu \\
BOOL isLBDown; \\
CPointPH LBDownPt; \\
GLfloat margin;
}
\end{quote}

The program also offers the ability to compare the $C^2$ PH quintic 
spline and the ``ordinary'' $C^2$ cubic spline with analogous end 
conditions, and the user may control the display status of each spline. 
The variables {\tt isMenuPh}, {\tt isMenuCubic}, {\tt isMenuPhCtrl}, and 
{\tt isMenuCubicCtrl} monitor the status of the menu. They are TRUE if the 
corresponding menu is checked, and the program then calls the {\tt Drawline} 
function to plot the spline curves and their control polygons. {\tt isLBDown} 
and {\tt LBDownPt} specify the status of the left mouse button, and record 
the coordinates of the point where it is pressed down.

Color List offers an efficient and flexible means to render the scene 
in the window. With a pointer to an array that contains red, green, and
blue (RGB) values, OpenGL functions such as {\tt glColor3fv} make the 
current brush color as needed. Each color in the Color List should be 
described in RGB format, with three floats between 0 and 1 defining the 
red, green, and blue values. In order to display the points and lines 
smoothly on the screen, the program uses OpenGL functions to enable the 
blending option and smooth option.

As the Graphical User Interface (GUI) for the program, the window has a 
title bar, menu bar, plotting area, and a status bar. The status bar shows 
the cursor coordinates before plotting, the iteration number, the arc 
length and bending energy, and the selected point after plotting. Each
menu option has an accelerator (i.e., an alternative keyboard input:
see Table~1). In the Edit menu, the user can plot a Hermite interpolant or 
spline curve, edit multiple points, translate the curve, and construct an 
offset. The program offers two approaches to editing points: right--clicking 
on a single point to change it, or selecting Edit Multiple Points in the 
menu to change all the points. 

\begin{table}[h]
\centering
\begin{tabular}{|l|r|}
\hline
New Spline & N \\
Edit Multiple Points & ctrl+E \\
Translate Spline & T \\
Offset & O \\
Hermite & H \\
PH & P \\
PH(Ctrl) & ctrl+P \\
Cubic & C \\
Parametric Speed & shift+A \\
Arc Length & A \\
\hline
\end{tabular}
\caption{Accelerator keyboard inputs for menu items.}
\end{table} 

\begin{figure}[htbp]
\centering
\epsfxsize=0.75\textwidth \epsfbox{CaptureHermite.eps}
\caption{A single PH quintic segment, constructed as a Hermite interpolant 
from user mouse input specified as initial and final pairs of control points.}
\label{fig:example1}
\end{figure}

\begin{figure}[htbp]
\centering
\epsfxsize=0.75\textwidth \epsfbox{CaptureCtrl.eps}
\caption{An example of an open $C^2$ PH quintic spline curve interpolating 
a sequence of points (large dots) specified interactively with the mouse.
The control polygons for each of the PH quintic spline segments are also 
shown.}
\label{fig:example2}
\end{figure}

Figures~\ref{fig:example1}--\ref{fig:example5} present examples of the 
program in use. Figure~\ref{fig:example1} illustrates the construction 
of a single PH quintic Hermite interpolant from initial and final pairs
of control points specified by the user. Figure~\ref{fig:example2} shows a 
planar $C^2$ PH quintic spline interpolating a sequence of points freely 
selected by the user with the mouse. For this plot, the View menu options 
PH and PH(Ctrl) have been checked, so the control polygons of each PH 
quintic spline segment are also shown. Figure~\ref{fig:example3} presents
the same $C^2$ PH quintic spline, but in this case the View menu options 
PH and Cubic are checked, to compare the PH spline with the ordinary cubic 
spline --- note the rather poor shape of the latter, as compared to the former. 

\begin{figure}
\centering
\epsfxsize=0.75\textwidth \epsfbox{CaptureCubic.eps}
\caption{Comparison of the $C^2$ PH quintic spline (black curve) 
in Figure~\ref{fig:example2} and the ``ordinary'' $C^2$ cubic spline (red
curve) interpolating the same points with uniform parameterizations,
and equivalent end conditions (quadratic end spans for the cubic 
spline, and cubic end spans for the PH quintic spline).}
\label{fig:example3}
\end{figure}

\begin{figure}[htbp]
\centering
\epsfxsize=0.75\textwidth \epsfbox{CaptureParaSpeed.eps}
\caption{Parametric speed plot for the $C^2$ PH quintic spline in 
Figure~\ref{fig:example2}.} 
\label{fig:example4}
\end{figure}

In Figure~\ref{fig:example4}, the parametric speed variation for the 
$C^2$ PH spline shown in Figure~\ref{fig:example1} is plotted. Finally, 
Figure~\ref{fig:example5} shows the construction of offsets 
to a $C^2$ PH quintic spline, for several (positive and negative) 
values of the offset distance $d$. The offsets can be
cleared from the display by setting $d=0$.

\begin{figure}[htbp]
\centering
\epsfxsize=0.75\textwidth \epsfbox{CaptureOffset.eps}
\caption{Construction of the rational offsets to a planar $C^2$ PH quintic 
spline curve for several --- positive and negative --- values of the offset 
distance $d$.}
\label{fig:example5}
\end{figure}

\end{document}
