\documentstyle[verbatim,cgudoc-special,cmacros,psfig]{article}

\title{The NURBS Procedure Library}
\author{W.T. Hewitt and D. Yip}
\docref{CGU 76}

\edition{$1^{st}$}

\makeindex
\begin{document}
\maketitle
\tableofcontents
\bibliographystyle{plain}

\pagebreak

\section{Disclaimer}

This work was originally developed by Mr W. T. Hewitt. This version of the
NURBS procedure library was funded by the Advisory Group On Computer Graphics
(AGOCG).

This library is distributed in the hope that it will be useful,
but {\bf WITHOUT ANY WARRANTY}; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.   

\pagebreak

\section{Introduction}

This document describes a set of Non-Uniform Rational B-Spline (NURB)
procedures. NURBS can be thought of as a superset of the more commonly known
B-spline, they represent the state of the art in curve and surface design and
representation. 

The NURBS procedure library aims to make available a set of functions
specifically for the creation, manipulation and display of NURBS for the
non-expert.

NURBS are well known for their excellent geometric properties and
characteristics~\cite{piegl:onas}.

\begin{itemize}

\item They offer a common mathematical form for representing and designing both
standard analytic shapes and free-form curves and surfaces. 

\item NURBS are able to exactly represent conics.

\item NURBS are invariant under scaling, rotation, translation and shear as
well as parallel and perspective projection.

\item By manipulating the control points as well as the weights, NURBS provide
the flexibility to design a large variety of shapes.

\item Evaluation is reasonably fast and computationally stable

\item NURBS have a clear geometric interpretations, making them particularly
useful for designers.

\item NURBS have a powerful geometric tool kit (knot insertion/refinement/
removal, degree elevation, splitting, etc.) that can be
used through out to design, analyze process and interrogate objects. 

\item NURBS are genuine generalizations of non-rational B-spline forms as well
as rational and non-rational B\'{e}zier curves and surfaces.

\item Provide the ability to model discontinuities.

\end{itemize}

The NURBS library relies on a set of functions TRAN
from the PHIGS Toolkit project, which is also available from NETLIB and also 
{\tt mcchpb.mcc.ac.uk}.
This module provides transformation routines and a number of basic functions
which the library is dependant on.

An example program showing how to use the NURBS procedures is included at the
end of this document.

For any further information please contact Mr. W. T. Hewitt, 
hewitt@uk.ac.mcc.cgu

The authors would like to thank Steve Larkin and Manjula Patel for their
contributions to the library.

I would also like to thank Colin Pinks for Beta testing the library for us.

\section{The Mathematics of NURBS}

\subsection{Curves}\index{Curves}

To define rational B-splines, homogeneous \index{Homogeneous coordinates}
coordinates are used. If $P = (x, y, z)$ is a point in 3D space, the 
corresponding point in 4D homogeneous coordinates is $P^{h} = (wx, wy, wz, w)$,
where $w>0$. $w$ is called the
weight; only positive homogeneous coordinates are considered.

The NURBS curve is defined as the set of points obtained by evaluating
equation~\ref{eqn:curve} for all values of $u$ between some $u_{min}$ and 
$u_{max}$.

\begin{equation}
{\bf C}^h(u) = \left( \begin{array}{c}
x \\ y\\z\\w \end{array}
\right) = \sum_{i=1}^{n} N_{i,k}(u){\bf P}_{i}^{h}\label{eqn:curve}
\end{equation}
\index{Curve definition}

where the ${\bf N}_{i,k}(u)$ are the $k$th-order polynomial B-spline basis
functions, and the ${P}_{i}^{h}$ are the homogeneous control points
${\bf P}_{i}^{h} = (x_{i}w_{i}, y_{i}w_{i}, z_{i}w_{i}, w_{i})$

The 3D point is recovered by dividing the first three coordinates by the fourth:
\begin{equation}
{\bf P}(u) = \left( \begin{array}{c}
x' \\ y'\\z' \end{array}
\right) =\left( \begin{array}{c}
x/w \\ y/w\\z/w \end{array}
\right)
\end{equation}

The $N_{i,k}(u)$'s are the normalized B-spline basis functions of degree 
{\em k} defined recursively using the Cox-de Boor relationship:

\index{Normalized B-spline basis}
\begin{equation}
N_{i}^{0}(u) = 
\left\{\begin{array}{ll}
       1 & {\rm if\ } u_{i}\leq u < u_{i+1}\\
        0 & {\rm otherwise}
       \end{array}
\right. \label{eqn:basis0}
\end{equation}

\begin{equation}
N_{i}^{k}(u) =
\frac{(u-u_{i})*N_{i}^{k-1}(u)}{(u_{i+k}-u_{i})}  +  
\frac{(u_{i+k+1}-u)*N_{i+1}^{k-1}(u)}{(u_{i+k+1}-u_{i+1})}
\label{eqn:basisk}
\end{equation}

(the indeterminate quantity $\frac{0}{0}$ is treated as 0)

where $u_{i}$ are the so-called knots forming a knot vector.  Multiplicity of
knot values enables discontinuities to be represented. The usual form of the
knot vector is:

\begin{equation}
\{u_i\} = \{u_1= \ldots =u_k,u_{k+1}, \ldots,u_n,u_{n+1}= \ldots =u_{n+k}\}\label{eqn:knots}
\end{equation}

\begin{figure}
\centerline{\psfig{figure=example-curve.ps,height=4in}}
\caption{\label{fig:example-curve}A Non-Rational B-spline curve with its 
associated control polygon}
\end{figure}

Note the first and last knot must be repeated k times (e.g., 4 for cubic 
splines). This is a requirement to ensure that the curve starts and ends at the 
first and last control points i.e., the multiplicity ensures that the curve
interpolates its first and last control point.

Thus the curve is specified by its order, a knot vector\index{Knot vector},  and
a list of control points. Figure~\ref{fig:example-curve} shows a NURBS curve
together with its defining control polygon. All the information is encompassed
in the  {\tt PR\_nurb} data structure described in section~\ref{Constants and
Records}.

\subsection{Surfaces}

The NURBS Surface is the tensor product of two curves:
\begin{equation}
{\bf S}(u,v) = \sum_{i=1}^{n}\sum_{j=1}^{m} N_{i,k}(u) N_{j,l}(v){\bf P}_{i,j}
\label{eqn:surface}
\end{equation}\index{Surfaces}

\begin{figure}
\centerline{\psfig{figure=example-surface.ps,height=4in}}
\caption{\label{fig:example-surface}A Non-Rational B-spline surface with 
its associated control polygon}
\end{figure}

The surface is specified by two orders $(k,l)$,  two knot vectors, and an array
of control points. Figure~\ref{fig:example-surface} shows a NURBS surface
together with its defining control polygon. All the information is encompassed
in the  {\tt PR\_nurb} data structure described below. \index{Knot vectors}

In the scheme presented below, curves and surfaces are represented using one
data structure. The data structure represents a curve if $m=1$ and $l=0$
in equation~\ref{eqn:surface}.

\section{Creation Operators}

The above NURBS representations for curves and surfaces are total encompassed
in the {\tt PR\_nurb} data structure used through the procedure
library (see section~\ref{Constants and Records}) to represent NURBS.

The library is equipped with a number of functions to create a series of
common objects. This is achieved inserting values into the {\tt PR\_nurb} 
data structure.

\subsection{2D}

\begin{itemize}

\item Circle and Arc
\index{nrb\_circle}\index{nrb\_arc} 

The circle is defined as a quadratic ($k=3$) NURB, with nine control points, and
twelve knots. The arc is created by splitting (see section~\ref{sec:splitting})
the circle at the appropriate points.

\item Polyline
\index{nrb\_circle} 

A line can be represented as a linear NURBS ($k=2$). If the endpoints are
${\bf P}_1$ and ${\bf P}_2$, then the knot vector will be ${0,0,1,1}$ and the
two control points will be ${\bf P}_1$ and ${\bf P}_2$.
The NURBS representation of the polyline is obtained by making the list of
control points the polyline points, and making the knot vector have a repeated
knots at every point.

\item Square
\index{nrb\_square}

The procedure creates a square with unit sides, centered at the origin (0, 0,
0), using the methodology of the previous section.

\item Triangle
\index{nrb\_triangle}

This creates an equilateral triangle, centered at the origin, (0,0,0).

\end{itemize}

\subsection{3D}

\begin{itemize}

\item Sphere
\index{nrb\_sphere}

This creates a unit sphere, centered at the origin. A semi-circular arc is
created, and then  revolved using {\tt nrb\_revolve}\index{nrb\_revolve} 
(see section~\ref{sec:revolve}). The sphere is centered at (0,0,0).

\item Torus
\index{nrb\_torus}

The procedure creates a torus shape which is centered at (0,0,0). It
is generated by revolving a circle around $360^{\circ}$.

\item Vase
\index{nrb\_vase}

This creates a test object, a vase which is centered at (0,0,0).

\end{itemize}

\section{Using the Curve operations on Surfaces}

Since curves and surfaces are very similar in nature, the operations
on curves can easily be extended to surfaces.

Suppose we have some curve algorithm e.g., {\tt nrb\_refine}
which takes a list of control points (denoted by):

\begin{verbatim}
1 1 1 1 1 1 1 1 1 1 1
\end{verbatim}
\label{fig:hhh}

and produces another NURBS with additional control points {\tt a}:
\begin{verbatim}
1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1
\end{verbatim}
It is relatively easy to extend the algorithm to operate on every row
of an array of control points, so starting with:
\begin{verbatim}
1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4 4
\end{verbatim}
an invocation of {\tt nrb\_refine} produces:
\begin{verbatim}
1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1
2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2
3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3
4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4
\end{verbatim}

Now if we seek also to do the refinement in the `other' direction, another
version of the algorithm must be developed to take the above and do the
refinement on the columns. (In general it just means duplicating 
the code, changing the name, and swapping around the array references).
Thus this version of the algorithm operates on {\tt 1 2 3 4} not {\tt 1 1 1 1},
and introduces new points {\tt A} for column 1, {\tt B} for column 2, etc., 
resulting in:

\begin{verbatim}
1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1
A B C D E F G H I J K L M N O P Q R S T U 
2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2
A B C D E F G H I J K L M N O P Q R S T U
3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3
A B C D E F G H I J K L M N O P Q R S T U
4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4
\end{verbatim}

While this works, the code development is wasteful. de Boor~\cite{boor:pgs}
developed a methodology which enables the `curve' code to be used twice. In
general most of the algorithms described below must operate on $u$ and then on
$v$. The simple curve algorithm is extended as above to operate once one each
row, but rather than write the answers out in rows it writes the answers out in
columns: 

\begin{verbatim} 
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
a b c d
1 2 3 4
\end{verbatim}

Calling the algorithm again but with the `new' surface, it operates on the rows now {\tt 1 2 3 4}
(which were the original columns) producing {\tt A B C} etc.
and writes out the answers in columns, this second transposition putting the
information back in the correct place:

\begin{verbatim}
1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1 a 1
A B C D E F G H I J K L M N O P Q R S T U 
2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2 b 2
A B C D E F G H I J K L M N O P Q R S T U
3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3 c 3
A B C D E F G H I J K L M N O P Q R S T U
4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4 d 4
\end{verbatim}

\section{Other Operations}

\subsection{Degree Elevation}
\index{Degree elevation}
\index{nrb\_elevate}

This elevates the degree of the spline in the $u$ direction, transposing the answer.
So to degree elevate a surface, once in the $u$ and $v$ directions, use:
\begin{verbatim}
   nrb_elevate(TRUE,&nrb1,&temp);
   nrb_elevate(TRUE,&temp,&nrb1);
\end{verbatim}

Most of the uses of degree elevation are for curves, and this could be
achieved using:
\begin{verbatim}
   nrb_elevate(TRUE,&nrb1,&nrb2);  /* Elevate the curve */
   nrb_transpose(&nrb2);           /* Transpose U and V */
\end{verbatim}

Recognizing this {\tt nrb\_elevate}\index{nrb\_elevate} takes a flag, indicating whether
transposition should or should not take place. The previous sequence could then
be written:
\begin{verbatim}
   nrb_elevate(FALSE,&nrb1,&nrb2); /* Elevate the curve */
\end{verbatim}

\subsection{Interpolation}
\index{Interpolation}

The library provides a function which can be used to create a NURBS given a
set of user supplied data. {\tt nrb\_interpolate} interpolates a NURB by
specifying a list of control points. A NURBS surface or curve is generated
depending on whether a set of $v$ control points are specified.

\begin{tabular}{ll}
{\tt nrb\_interpolate}\index{nrb\_interpolate} & Interpolate through a set of data points.\\
\end{tabular}

\section{Evaluation}
\index{Evaluation}

There are a number of different routines that may used to evaluate a NURB
depending on the required evaluation.

The most commonly used is that of {\tt nrb\_evaluate}\index{nrb\_evaluate}.
This routine will evaluate a NURBS at a given $u$. If the NURBS is a surface, 
then the transpose is written out. For example to evaluate the curve at $u$ 
would be:

\index{nrb\_putpoint4}
\index{Curve evaluation}
\begin{verbatim}
   nrb_evaluate(&nrb,u,&temp)
   printf("The point on the curve is: ");
   nrb_putpoint4(stdout,temp.pf_ppp->pts[0])
\end{verbatim}

To evaluate a surface at $(u,v)$ would be:

\index{nrb\_putpoint4}
\index{Surface evaluation}
\begin{verbatim}
   nrb_evaluate(&nrb,u,&temp);
   nrb_evaluate(&temp,v,&temp2);
   printf("The point on the surface is: ");
   nrb_putpoint4(stdout,temp2.pf_ppp->pts[0]);
\end{verbatim}

Thus {\tt temp} contains the isoparametric NURBS curve on the surface specified 
by $u$. 

The other NURBS evaluation routines are {\tt nrb\_bvalue} and {\tt nrb\_du}.

\begin{itemize}
\item {\tt nrb\_bvalue}\index{nrb\_bvalue} is a general purpose routine which allows the 
evaluation of a derivative of a NURBS. 
\item {\tt nrb\_du}\index{nrb\_du} is used to evaluate a NURBS and its first derivative.
\end{itemize}

\subsection{Splitting NURBS}\label{sec:splitting}
\index{Splitting NURBS}
\index{nrb\_split}

This will split a NURBS curve in half, at  some value t. Thus to split a 
surface into four along the isoparametric lines $u$ and $v$ use:
\begin{verbatim}
   PR_nurb nrb, nrbl, nrbr, nrbl1, nrbl2, nrbr1, nrbr2;
   ...
   nrb_split(&nrb ,u,&nrbl ,&nrbr);
   nrb_split(&nrbl,v,&nrbl1,&nrbl2);
   nrb_split(&nrbr,v,&nrbr1,&nrbr2);
\end{verbatim}

The four sections of the subdivided surface are: {\tt nrbl1, nrbl2, nrbr1}, and
{\tt nrbr2}.

\section{Surface Operators}
\index{Surface operators}

The library provides a number of different surface operators.

\subsection{Extrusion}
\index{nrb\_extrude}

\begin{figure}
\centerline{\psfig{figure=cylinder.ps,width=3.5in}}
\caption{\label{fig:cylinder}Cylinder created by extrusion}
\end{figure}

Extruded surfaces are created by defining a profile curve and then extruding
the curve in a certain direction. If the profile curve has the form

\begin{equation}
\label{eqn:extrude-curve}
{\bf C}_{i}(u) = \sum_{i=1}^{n} R_{i,p}(u){\bf Q}_{i}
\end{equation}

then the extruded surface takes the form

\begin{equation}
\label{eqn:extrude-surface}
{\bf S}(u,v) = \sum_{i=1}^{n} \sum_{j=1}^{2} R_{i,p;j,1}(u,v) {\bf P}_{i,j}
\end{equation}

Figure~\ref{fig:cylinder} shows a cylinder created by extruding a circle.

\subsection{Surface of Revolution}\label{sec:revolve}
\index{nrb\_revolve}

A surface of revolution is generated by using a NURBS curve which lies in the
$xz$-plane. A full surface of revolution is obtained by revolving the curve
$360^{\circ}$ about the $z$-axis. The required surface has the form 

\begin{equation}
\label{eqn:revolve-surface}
{\bf S}(u,v) = \sum_{i=1}^{9} \sum_{j=1}^{n} R_{i,2;j,k}(u,v) {\bf P}_{i,j}
\end{equation}

\begin{figure}
\centerline{\psfig{figure=sphere.ps,width=3.5in}}
\caption{\label{fig:sphere}Sphere created by revolution}
\end{figure}

Figure~\ref{fig:sphere} shows a sphere created by revolving an arc of a circle.

\subsection{Ruled Surface}
\index{nrb\_ruled}

This procedure generates a ruled surface between two nurb curves $C_{1}^{h}$ 
and $C_{2}^{h}$. 

\begin{equation}
\label{eqn:ruled-curves}
{\bf C}_{i}^h(u) = \sum_{j=1}^{n_{i}} R_{j,k_{i}}(u){\bf P}_{j}^{i,h}~, i=1,2
\end{equation}

defined over two knots vectors. The required surface, is that of 

\begin{equation}
\label{eqn:ruled-surface}
{\bf S}(u,v) = \sum_{i=1}^{n} \sum_{j=1}^{n} R_{i,p;j,1}(u,v) {\bf P}_{i,j}
\end{equation}

such that ${\bf S}(u,0)={\bf C}_{1}(u)$ and ${\bf S}(u,1)={\bf C}_{2}(u)$.

To create the surface between the two NURBS:
\begin{enumerate}
\item Degree elevate the curve to the same order.
\item Union the knot vectors of the curves.
\item Oslo each curve with the new knot vector. Each curve should now have 
the same knot vector and the same number of control points.
\item Create a surface using the control points and the knot vectors of the 
two curves.
\end{enumerate}

\begin{figure}
\centerline{\psfig{figure=ruled.ps,width=3.5in}}
\caption{\label{fig:ruled}A ruled surface}
\end{figure}

Figure~\ref{fig:ruled} shows a ruled surface between a circle and a square.

\subsection{Transposition}
\index{Transposition}

As a result of some of the functions, the NURBS structure is transposed ready
to be fed back into the same function. This process is usually applied to
surfaces but for curves the function will only usually be called once. 
{\tt nrb\_tranpose} is provided to transpose the NURBS back. 

Transposition also takes place at a lower level, usually within the routines
themselves.
{\tt nrb\_interchange} is provided to interchange the {\tt u} and {\tt v}
components within the NURBS data structure. 

\begin{tabular}{ll}
{\tt nrb\_transpose}\index{nrb\_transpose} & Transpose the whole NURBS structure.\\
{\tt nrb\_interchange}\index{nrb\_interchange} & Interchange only the {\tt u} and {\tt v}
components within the NURBS data structure.\\
\end{tabular}

\subsection{Transformations}
\index{Transformations}
\index{nrb\_xform}

The library provides the function {\tt nrb\_xform} to transform the control
points of a NURBS in euclidean space using a matrix which can be built up using
a number of routines which are provided in the TRAN module.

e.g.,
\begin{verbatim}
   PR_nurb circle, new_nurb;
   Pvector3 point;
   Pmatrix3 matrix;
   ...
   /* Create a circle
   */
   nrb_circle(&circle);
   /* Displacement the circle
   *  - shift in X
   *  - rotate to XZ plane
   */
   point = ptk_vector3(2.0, 0.0, 0.0);
   ptk_shift3(&point, PREPLACE, matrix);
   ptk_rotate3(90.0, 1, PPRECONCATENATE, matrix);
   /* Apply the transformation
   */
   nrb_xform(&circle, matrix);
\end{verbatim}

\subsection{Drawing NURBS}
\index{Drawing NURBS}

Provided within the library are a number of procedures to draw a NURB
structure. These routines rely on the use of DEC PHIGS to produce the output
and thus are provided solely for completeness and as a template for other
systems.

\begin{tabular}{ll}
{\tt nrb\_drawsnet}\index{nrb\_drawsnet} & Draw a control polygon for a given surface.\\
{\tt nrb\_draws}\index{nrb\_draws} & Draw a surface together with the control polygon.\\
{\tt nrb\_drawcnet}\index{nrb\_drawcnet} & Draw the control polygon for a given curve.\\
{\tt nrb\_drawc}\index{nrb\_drawc} & Draw a curve together with the control polygon.\\
{\tt nrb\_phigsplus}\index{nrb\_phigsplus} & Draw the NURBS using PHIGS PLUS primitives.
\end{tabular}

\section{Constants and Records}
\index{Constants and Records}
\label{Constants and Records}

The following constants and record are relevant to NURBS application-level
procedures, and are in the header file \pardesc{nurbtype.h}.

\subsection{Constants}

\begin{verbatim}
   #define PC_MaxNetpts    200  /*Maximum number of points in a net*/
   #define PC_NrbMax       50   /*Pseudo maximum number of control points*/
   #define PC_NrbKmax      20   /*Maximum order of the splines*/
\end{verbatim}

\subsection{Data Structures}
\index{Data structures}

The following are defined in \verb+nurbtype.h+

\begin{verbatim}

typedef struct PR_nurb {          /* tensor product surface       */
  PR_dir                pf_u;     /* U and V knot vectors         */
  PR_dir                pf_v;
  PR_pts                *pf_ppp;  /* Pointer to control points    */
  struct PR_nurb        *pf_next; /* Pointer to next in free list */
  struct PR_nurb        *pf_prev; /* Pointer to prev in free list */
  Pint                  pf_id;    /* Integer ID for user use!     */
} PR_nurb;

typedef struct PR_dir {
  Pint                  pf_k;     /* order in u                   */
  Pint                  pf_n;     /* number of vertices           */
  Pint                  pf_nt;    /* number of knots  n+k         */
  PR_knots              *pf_kk;   /* Pointer to knots             */
} PR_dir;

typedef struct PR_knots {
  struct PR_knots       *pf_next; /* Pointer to next one          */
  Pint                  pf_size;  /* Size of this one             */
  Pfloat                knots[1]; /* Array of the knots           */
} PR_knots;

typedef struct PR_pts {
  struct PR_pts         *pf_next; /* Pointer to next one          */
  Pint                  pf_size;  /* Size of this one             */
  Ppoint4               pts[1];   /* Array of the Points          */
PR_pts;

typedef enum {PVudir, PVvdir} PE_dir;

\end{verbatim}

\pagebreak

\section{Use of the Library}

The {\tt PR\_nurb} data structure can be used either by static or dynamic 
allocation. The following examples serve to show this.

\newcounter{listnum1}
\newcounter{listnum2}

\begin{enumerate}
\item {\large\bf Using static allocation}

\begin{list}%
{(\alph{listnum1})}{\usecounter{listnum1}
 \setlength{\rightmargin}{\leftmargin}}

\item \underline{Define each field in the NURBS data structure individually}

\begin{verbatim}
   PR_nurb any_nurb;
   ...
   nrb_clear(&any_nurb);
   /* Allocate values to each field in the NURBS data structure
   */
   any_nurb.pf_u.pf_k  = order_of_any_nurb;
   any_nurb.pf_u.pf_n  = number_of_control_points_of_any_nurb;
   any_nurb.pf_u.pf_nt = number_of_knots_of_any_nurb;

   /* The knots
   */
   for(i=0;i<any_nurb.pf_x.pf_nt;i++)
      any_nurb.pf_x.pf_kk->knots[i] = knot_values[i];

   /* Set the control points
   */
   nrb_allocatepts(number_of_control_points_of_any_nurb,&any_nurb.pf_ppp);
   for(i=0;i<number_of_control_points_of_any_nurb;i++)
      any_nurb.pf_ppp->pts[i]  = any_data_points[i];

   /* Display the NURBS structure
   */
   nrb_dump(stdout,&any_nurb);
   ...   
\end{verbatim}

\item \underline{Use routines to place values into the NURBS data structure}

\begin{verbatim}
   PR_nurb any_nurb;
   ...
   nrb_clear(&any_nurb);
   /* Allocate values to each field in the NURBS data structure
   */
   nrb_init(order,number_of_control_points+order,0,1,&any_nurb);

   /* The knots
   */
   nrb_makeknots(0.0, 1.0, &any_nurb.pf_u);

   /* Set the control points
   */
   nrb_allocatepts(number_of_control_points,&any_nurb.pf_ppp);
   for(i=0;i<number_of_control_points_of_any_nurb;i++)
      any_nurb.pf_ppp->pts[i]  = any_data_points[i];

   /* Display the NURBS structure
   */
   nrb_dump(stdout,&any_nurb);
   ...   
\end{verbatim}

\item \underline{Use construction operators to build the NURBS data structure}

\begin{verbatim}
   PR_nurb any_nurb;
   ...
   nrb_clear(&any_nurb);

   /* Use a creation operator to fill the NURBS structure
   */
   nrb_sphere(&any_nurb);
   /* Display the NURBS structure
   */
   nrb_dump(stdout,&any_nurb);
   ...   
\end{verbatim}

\end{list}   

\item {\large\bf Using dynamic allocation}

\begin{list}%
{(\alph{listnum2})}{\usecounter{listnum2}
 \setlength{\rightmargin}{\leftmargin}}

\item \underline{Define each field in the NURBS data structure individually}

\begin{verbatim}
   PR_nurb *any_nurb;
   ...
   any_nurb=NULL;
   /* Allocate enough space for the NURB
   */
   nrb_allocatenurb(&any_nurb)
   /* Allocate values to each field in the NURBS data structure
   */
   any_nurb->pf_u.pf_k  = order_of_any_nurb;
   any_nurb->pf_u.pf_n  = number_of_control_points_of_any_nurb;
   any_nurb->pf_u.pf_nt = number_of_knots_of_any_nurb;

   /* The knots
   */
   nrb_makeknots(0.0, 1.0, &any_nurb->pf_u);

   /* Set the control points
   */
   nrb_allocatepts(number_of_control_points_of_any_nurb,&any_nurb->pf_ppp);
   for(i=0;i<number_of_control_points_of_any_nurb;i++)
      any_nurb->pf_ppp->pts[i]  = any_data_points[i];

   /* Display the NURBS structure
   */
   nrb_dump(stdout,any_nurb);
   ...   
   /* Deallocate the space used by the NURB
   */
   nrb_deallocatenurb(&any_nurb)
\end{verbatim}

\item \underline{Use routines to place values into the NURBS data structure}

\begin{verbatim}
   PR_nurb *any_nurb;
   ...
   any_nurb=NULL;
   /* Allocate values to each field in the NURBS data structure
   */
   nrb_init(order,number_of_control_points+order,0,1,any_nurb);

   /* The knots
   */
   nrb_makeknots(0.0, 1.0, any_nurb.pf_u);

   /* Set the control points
   */
   nrb_allocatepts(number_of_control_points_of_any_nurb,&any_nurb->pf_ppp);
   for(i=0;i<number_of_control_points_of_any_nurb;i++)
      any_nurb->pf_ppp->pts[i]  = any_data_points[i];

   /* Display the NURBS structure
   */
   nrb_dump(stdout,any_nurb);
   ...   
   /* Deallocate the space used by the NURB
   */
   nrb_deallocatenurb(&any_nurb)
\end{verbatim}

\item \underline{Use construction operators to build the NURBS data structure}

\begin{verbatim}
   PR_nurb *any_nurb;
   ...
   any_nurb=NULL;

   /* Use a creation operator to fill the NURBS structure
   */
   nrb_sphere(any_nurb);
   /* Display the NURBS structure
   */
   nrb_dump(stdout,any_nurb);
   ...   
   /* Deallocate the space used by the NURB
   */
   nrb_deallocatenurb(&any_nurb)
\end{verbatim}

\end{list}   

\end{enumerate}

\newpage

\section{NURBS Application Level Procedures}

The following procedures are available to the application programmer, and 
are defined in the header file {\tt nurbfns.h} which is currently in the
directory {\tt temp}.

\boxingon

\func{void}{nrb\_allocateknots}\index{nrb\_allocateknots}
\param{PR\_dir}{*kk}
\fend
Allocates space for the knots. It assumes the fields of \pardesc{kk} have been
assigned the appropriate values. If the pointer is not \pardesc{NULL} that knot
vector is added to the free list.

e.g., 
\begin{verbatim}
   PR_nurb *nurb;
   ...
   /* Set the order, number of control points and the number of knots
   */
   nurb->pf_u.pf_k  = 4;
   nurb->pf_u.pf_n  = 5;
   nurb->pf_u.pf_nt = 9;
   ...
   /* Allocate space for the knots in the u direction
   */
   nrb_allocateknots(&nurb->pf_u);
\end{verbatim}

\func{void}{nrb\_allocatenurb}\index{nrb\_allocatenurb}
\param{PR\_nurb}{**nrb}
\fend
Creates a \pardesc{PR\_nurb} on the heap and makes \pardesc{nrb} point to it.

e.g.,
\begin{verbatim}
   PR_nurb *nurb;
   ...
   nrb_clear(nurb);
   ...
   /* Allocate space for the nurb.
   */
   nrb_allocatenurb(nurb);
   \end{verbatim}

\func{void}{nrb\_allocatepts}\index{nrb\_allocatepts}
\param{Pint}{nx}
\param{PR\_pts}{**pp}
\fend

Creates space for {\tt nx} homogeneous points and returns the pointer to them
in {\tt pp}. If the pointer is not \pardesc{NULL} that point
list is added to the free list.

e.g.,
\begin{verbatim}
   PR_nurb *nurb;
   ...
   /* Set the order, number of control points and the number of knots
   */
   nurb->pf_u.pf_k  = 4;
   nurb->pf_u.pf_n  = 5;
   nurb->pf_u.pf_nt = 9;
   ...
   /* Allocate space for the control points in the u direction
   */
   nrb_allocatepts(nurb->pf_u.pf_n,&nurb->pf_ppp);
\end{verbatim}

\func{void}{nrb\_boehmc}\index{nrb\_boehmc}
\param{PR\_nurb}{*nrb1}
\param{PR\_dir}{*tnew}
\param{PR\_nurb}{*nrb2}
\fend

Another knot insertion routine.
Inserts the knots in \pardesc{tnew} into each row (U direction) of
\pardesc{nrb1} returning the answer transposed
in {\tt nrb2}. It uses Boehm's~\cite{boehm:ink} algorithm, and 
\pardesc{nrb1} is unmodified.

e.g.,

\begin{verbatim}
   PR_nurb nurb1,nurb2;
   PR_dir new_knots;
   ...
   /* Create some NURBS
   */
   nrb_circle(&nurb1);
   ...
   nrb_copy(&nurb1,&nurb2);
   nurb2.pf_u.pf_nt = 20;
   nurb2.pf_u.pf_n = nurb2.pf_u.pf_nt - nurb2.pf_u.pf_k;
   ...
   /* Create a new set of knot vectors
   */
   nrb_makeknots(0.0, 1.0, &nurb2.pf_u);
   nrb_unionknots(&nurb1.pf_u, &nurb2.pf_u, &nurb2.pf_u);
   nrb_differenceknots(&nurb1.pf_u,&nurb2.pf_u,&new_knots);
   ...
   nrb_boehmc(&nurb1,&new_knots,&nurb2);
   nrb_transpose(&nurb2);
   ...
   nrb_dump(&nurb1);
\end{verbatim}

\func{void}{nrb\_bvalue}\index{nrb\_bvalue}
\param{PR\_nurb}{*nrb}
\param{Pfloat}{x}
\param{Pint}{jderiv}
\param{PR\_nurb}{*nrb2}
\fend

Evaluate a NURBS at the value {\tt u} of the {\tt jderiv$^{th}$} derivative of
{\tt nrb}.

e.g., 
\begin{verbatim}
   PR_nurb triangle, evaluated_nurb;
   float u=0.5, deriv=2;
   ...
   /* Create a NURBS triangle
   */
   nrb_triangle(&triangle);
   /* Evaluate a NURBS at knot value u of deriv'th derivative of the NURB
   */
   nrb_bvalue(&triangle, u, deriv, &evaluated_nurb);
\end{verbatim}

\func{void}{nrb\_clear}\index{nrb\_clear}
\param{PR\_nurb}{*nrb}
\fend

Assigns all the pointer fields to \pardesc{NULL}. Used mainly by 
\pardesc{nrb\_allocatenurb}\index{nrb\_allocatenurb}, to ensure the fields are properly initialized.

e.g.,
\begin{verbatim}
   PR_nurb *nurb;
   ...
   /* Make sure all the entries in the NURBS structure are pointing to NULL
   */
   nrb_clear(nurb);
\end{verbatim}

\func{void}{nrb\_copy}\index{nrb\_copy}
\param{PR\_nurb}{*nrb1}
\param{PR\_nurb}{*nrb2}
\fend

Makes \pardesc{nrb2} a copy of \pardesc{nrb1}. It allocates space for
the knots and points and copies those as well. 

e.g.,
\begin{verbatim}
   PR_nurb circle1, circle2;
   ...
   /* Create a NURBS representation of a circle
   */
   nrb_circle(&circle1);
   /* Make circle2 a copy of circle1
   */
   nrb_copy(&circle1, &circle2);
\end{verbatim}

\func{void}{nrb\_copyknots}\index{nrb\_copyknots}
\param{PR\_dir}{*k1}
\param{PR\_dir}{*k2}
\fend

Makes a  \pardesc{k2} a copy of \pardesc{k1}. It allocates space for
the knots, and copies them. Mainly used internally within the procedures.

e.g.,
\begin{verbatim}
   PR_nurb *nurb1, *nurb2;
   ...
   /* Set the order, number of control points and the number of knots
   */
   nurb1->pf_u.pf_k  = 3;
   nurb1->pf_u.pf_n  = 5;
   nurb1->pf_u.pf_nt = 8;
   ...
   /* Allocate space for the knots in the u direction
   */
   nrb_allocateknots(&nurb1->pf_u);
   nrb_makeknots(0.0, 1.0, &nurb1->pf_u);
   /* Make nurb2's knots a copy nurb1's knots 
   */
   nrb_copyknots(&nurb1->pf_u, &nurb2->pf_u);
\end{verbatim}
 
\func{void}{nrb\_deallocateknots}\index{nrb\_deallocateknots}
\param{PR\_dir}{*kk}
\fend

Return a knot vector to the free list. Mainly used internally within the 
procedures.

e.g., used in functions such as {\tt nrb\_split}.

\func{void}{nrb\_deallocatenurb}\index{nrb\_deallocatenurb}
\param{PR\_nurb}{**nrb}
\fend

Return a NURBS to the free list. Mainly used internally within the 
procedures.

e.g., used in {\tt nrb\_split}\index{nrb\_split} for instance.

\func{void}{nrb\_deallocatepts}\index{nrb\_deallocatepts}
\param{PR\_pts}{**pp}
\fend

Return a point list to the free list. Mainly used internally within the 
procedures.

e.g., used in {\tt nrb\_elevate}\index{nrb\_elevate} for instance.

\func{void}{nrb\_differenceknots}\index{nrb\_differenceknots}
\param{PR\_dir}{*k1,*k2,*k3}
\fend

Create a knot sequence \pardesc{k3} which contains those knots in
\pardesc{k2} which are NOT in \pardesc{k1}. It assumes \pardesc{k2.pf\_nt}
$>$ \pardesc{k1.pf\_nt}.

e.g.,
\begin{verbatim}
   PR_nurb *nurb1, *nurb2;
   PR_dir *new_knots;
   ...
   nurb1->pf_u.pf_nt = 8;
   nurb2->pf_u.pf_nt = 10;
   ...
   /* Create Knot vectors
   */
   nrb_makeknots(0.0, 0.5, &nurb1->pf_u);
   nrb_makeknots(0.5, 1.0, &nurb2->pf_u);
   ...
   /* Difference the knot sequences from nurb1 and nurb2
   */
   nrb_differenceknots(&nurb1->pf_u, &nurb2->pf_u, new_knots);
\end{verbatim}

\func{void}{nrb\_du}\index{nrb\_du}
\param{PR\_nurb}{*nrb}
\param{Pfloat}{x}
\param{PR\_pts}{**pp}
\fend

Evaluate a NURBS at the value {\tt x}. This function simply calls
\pardesc{nrb\_bvalue}\index{nrb\_bvalue} to evaluate the NURBS at the $1^{st}$ derivative. 

e.g., 
\begin{verbatim}
   PR_nurb triangle;
   PR_pts *set_of_points;
   float u=0.5;
   ...
   /* Create a NURBS triangle
   */
   nrb_triangle(&triangle);
   /* Evaluate a NURBS at knot value u at the first derivative of the NURB
   * returning a set of pts
   */
   nrb_du(&triangle, u, &set_of_points);
\end{verbatim}

\func{void}{nrb\_dump}\index{nrb\_dump}
\param{FILE}{*fp}
\param{PR\_nurb}{*nrb}
\fend

Dump a PR\_nurb representation to file \pardesc{fp}.

e.g.,
\begin{verbatim}
   PR_nurb circle;
   FILE *data_file;
   ...
   /* Create a NURBS representation of a circle
   */
   nrb_circle(&circle);
   /* Dump the values within the NURBS structure
   */
   if(dump_to_file)
   {
      if((data_file=fopen("file.name","w"))==NULL)
         fprintf(stderr,"ERROR: Unable to open file\n");
      else
         nrb_dump(data_file, &circle);            
   }
   else
      /* To the screen
      */
      nrb_dump(stdout, &circle);
\end{verbatim}

\func{void}{nrb\_dumpknots}\index{nrb\_dumpknots}
\param{FILE}{*fp}
\param{Pchar}{*str}
\param{PR\_dir}{kk}
\fend

Dump the knots to file \pardesc{fp}.

e.g., use is similar to that of {\tt nrb\_dump}\index{nrb\_dump}.

\func{void}{nrb\_dumplists}\index{nrb\_dumplists}
\param{FILE}{*fp}
\fend

Dump the freelists of points, knots and NURBS to file \pardesc{fp}.

e.g., Useful for debugging purposes.

\func{void}{nrb\_dumpsummary}\index{nrb\_dumpsummary}
\param{FILE}{*fp}
\param{PR\_nurb}{*nrb}
\fend

Dump a summary of the PR\_nurb representation to file \pardesc{fp}.
It is the equivalent to \pardesc{nrb\_dump}\index{nrb\_dump} without the 
list of points.

e.g., Useful for debugging purposes.

\func{void}{nrb\_elevate}\index{nrb\_elevate}
\param{boolean}{transpose}
\param{PR\_nurb}{*nrb1, *nrb2}
\fend

Elevates the degree of \pardesc{nrb1} returning the answer in \pardesc{nrb2}.
Recognizing that this is more likely to be called for curves rather than
surfaces, \pardesc{transpose} controls whether or not \pardesc{nrb2} is 
transposed.

e.g.,
\begin{verbatim}
   PR_nurb nurb1, nurb2;
   ...
   /*  Check to see if the NURBS is a curve
   */
   if(nurb1.pf_v.pf_nt > 1)
   {
      /* The NURBS is a surface, so elevate both directions of the NURB.
      */
      nrb_elevate(TRUE, &nurb1, &nurb2);
      nrb_elevate(TRUE, &nurb2, &nurb1);
   }
   else
   {
      /* The NURBS is a curve, so only need to elevate the NURBS in 
      * single direction
      */
      nrb_elevate(FALSE, &nurb1, &nurb2);
      nrb_copy(&nurb2, &nurb1);
   }
\end{verbatim}

\func{void}{nrb\_elevateknots}\index{nrb\_elevateknots}
\param{PR\_dir}{*k1, *k2}
\fend

Used by \pardesc{nrb\_elevate}\index{nrb\_elevate} it raises the degree of each of the knots
in \pardesc{k1} by one, but ensures that no knot is repeated more than 
\pardesc{k1.pf\_k+1}. Mainly used internally within the library.

e.g., used within {\tt nrb\_elevate} for instance.

\func{void}{nrb\_evaluate}\index{nrb\_evaluate}
\param{PR\_nurb}{*nrb1}
\param{Pfloat}{x}
\param{PR\_nurb}{*nrb2}
\fend

Evaluate a NURBS at the value {\tt x}. This function simply calls
\pardesc{nrb\_bvalue}\index{nrb\_bvalue} to evaluate the NURBS at the $0^{th}$ derivative.

e.g., 
\begin{verbatim}
   PR_nurb triangle, evaluated_nurb;
   float u=0.5;
   ...
   /* Create a NURBS triangle
   */
   nrb_triangle(&triangle);
   /* Evaluate a NURBS at knot value u of the NURB
   */
   nrb_evaluate(&triangle, u, &evaluated_nurb);
\end{verbatim}

\func{void}{nrb\_extrude}\index{nrb\_extrude}
\param{PR\_nurb}{*nrb1}
\param{Ppoint3}{w}
\param{PR\_nurb}{*nrb2}
\param{Pint}{*error}
\fend

Create \pardesc{nrb2} a linear extrusion of \pardesc{nrb1} along the vector 
\pardesc{w}. Taken from Piegl~\cite{piegl:csc}.

e.g.,
\begin{verbatim}
   PR_nurb circle, nurb;
   int err;
   ...
   nrb_circle(&circle);
   /* Create a cylinder by extruding a circle
   */
   nrb_extrude(&circle, ptk_vector3(0.0,0.0,2.0), &nurb, &err);
\end{verbatim}

\func{void}{nrb\_getpoint4}\index{nrb\_getpoint4}
\param{FILE}{*fp}
\param{Ppoint4} {*pt}
\fend

Input a homogenous point from file pointer.
If successful returns \pardesc{true}, \pardesc{false} otherwise.

e.g., used in {\tt nrb\_read}\index{nrb\_read},

\begin{verbatim}
   PR_nurb nurb;
   FILE *data_file;
   ...
   if((data_file=fopen("file.name","r"))==NULL)
      fprintf(stderr,"ERROR: Unable to open file\n");
   ...
   /* Input a list of control points
   */
   for(i=0;i<number_of_control_points;i++)
      nrb_getpoint4(data_file,nurb.pf_ppp->pts[i]);
\end{verbatim}
                                                                       
\func{Pint}{nrb\_index}\index{nrb\_index}
\param{Pint}{x, y, nx}
\fend
For efficiency reasons, the knots and control points are stored in
1D arrays.  Given \pardesc{nx}  which is the number of knots or control
points in x, this routine calculates the correct index into a
conceptually 2D array. Mainly used internally within the 
procedures.

e.g., used in {\tt nrb\_interpolate}\index{nrb\_interpolate} for instance.

\func{void}{nrb\_init}\index{nrb\_init}
\param{Pint} {kx,ntx,ky,nty}
\param{PR\_nurb}{*nrb}
\fend

Initialize a NURBS using the given order and number of knots in x and y.
Space for the knots and control points is allocated, though the contents of
these arrays is undefined.

e.g.,
\begin{verbatim}
   PR_nurb nurb;
   ...
   nrb_clear(&nurb)
   /* Initialize a nurb with a given set of values
   */
   nrb_init(3, 13, 4, 24, &nurb);
\end{verbatim}

\func{void}{nrb\_initialise}\index{nrb\_initialise}
\fend

Initialize the library. Should be called once at the beginning of your program.

e.g.,
\begin{verbatim}
   main(int argc, char *argv[])
   {
      /* Initialize the NURBS procedure library
      */
      nrb_intialise();
      ...
\end{verbatim}

\func{Pint}{nrb\_inqerrorcount}
\param{Pint}{*i}
\fend

Returns the maximum number of errors that are reported. The default is 10.

Useful for debugging purposes.

\func{void}{nrb\_interchange}\index{nrb\_interchange}
\param{PR\_nurb}{*nrb}
\fend

Interchange the {\tt u} and {\tt v} components of NURBS i.e., the control
points, the knots and the order.

e.g., mainly used within internal routines such as {\tt nrb\_osloc}
\index{nrb\_osloc}.

\func{void}{nrb\_interpolate}\index{nrb\_interpolate}
\param{PR\_nurb}{*nrb1}
\param{Pfloat}{tol}
\param{PR\_nurb}{*nrb2}
\fend

Interpolate a NURBS to a given tolerance through a set of data points.

e.g.,
\begin{verbatim}
   PR_nurb interpolating_nurb, nurb;
   int number_of_points, order;
   float tolerance=0.05;
   ...
   nrb_clear(&interpolating_nurb);
   nrb_clear(&nurb);
   ...
   /* Define the NURBS to be interpolated i.e. order, etc. together
   * with the data points to be interpolated through.
   */
   nrb_init(order,number_of_points+order,0,1,&interpolating_nurb);
   nrb_makeknots(0.0,1.0,&interpolating_nurb.pf_x);
   nrb_allocatepts(number_of_points,&interpolating_nurb.pf_ppp);

   /* Set the data to be interpolating through
   */
   for(i=0;i<number_of_points;i++)
      dummy_path_nurb.pf_ppp->pts[i] = data_points[i];

   /* Interpolate through the data points
   */
   nrb_interpolate(&interpolating_nurb,tolerance,&nurb);
   nrb_transpose(&nurb);
\end{verbatim}

\func{void}{nrb\_interv}\index{nrb\_interv}
\param{PR\_dir}{*kk}
\param{Pfloat}{x}
\param{Pint}{*left, *mflag}
\fend

Mainly used internally within the procedures.

e.g., used in {\tt nrb\_split}\index{nrb\_split} for instance.

\func{void}{nrb\_makeknots}\index{nrb\_makeknots}
\param{Pfloat}{tmin, tmax}
\param{PR\_dir}{*kk}
\fend

This routine produces \pardesc{kk.pf\_nt} knots between \pardesc{tmin} and
\pardesc{tmax}, with \pardesc{tmin} and \pardesc{tmax} repeated 
\pardesc{kk.pf\_k} times, with the rest of the knots distributed
uniformly.

e.g.,
\begin{verbatim}
   PR_nurb *nurb;
   ...
   /* Set the order, number of control points and the number of knots
   */
   nurb->pf_u.pf_k  = 3;
   nurb->pf_u.pf_n  = 5;
   nurb->pf_u.pf_nt = 8;
   ...
   /* Allocate space for the knots in the u direction
   */
   nrb_allocateknots(&nurb->pf_u);
   nrb_makeknots(0.0, 1.0, &nurb->pf_u);
\end{verbatim}
 
\func{Pint}{nrb\_numsubdivs}\index{nrb\_numsubdivs}
\param{PR\_nurb}{*nrb}
\param{PE\_dir}{xory}
\param{Pfloat}{tol}
\fend

This routine determines the level of refinement to be applied to the NURB.

\func{void}{nrb\_osloc}\index{nrb\_osloc}
\param{PR\_nurb}{*nrb1, *nrb2}
\fend

Performs refinement on nrb1 and places the new NURBS in nrb2~\cite{cohen:deg}. 

e.g.,
\begin{verbatim}
   PR_nurb nurb1,nurb2;
   ...
   nurb1.pf_u.pf_k  = 3;
   nurb1.pf_u.pf_n  = 5;
   nurb1.pf_u.pf_nt = 8;
   nurb2.pf_u.pf_k  = 4;
   nurb2.pf_u.pf_n  = 6;
   nurb2.pf_u.pf_nt = 10;
   ...
   nrb_makeknots(0.0, 1.0, &nurb1.pf_u);
   nrb_makeknots(0.0, 1.0, &nurb2.pf_u);
   ...
   /* Create a new knot vector
   */
   nrb_unionknots(&nurb2.pf_u, &nurb1.pf_u, &nurb1.pf_u);
   /* Now insert the new control points corresponding to the
   * new knot vector into the NURB
   */
   nrb_osloc(&nurb2, &nurb1);
   nrb_transpose(&nurb1);
   ...
   nrb_dump(&nurb1);
\end{verbatim}

\func{void}{nrb\_partials}\index{nrb\_partials}
\param{PR\_nurb}{*nrb}
\param{PR\_pts}{**du, **dv, **duv}
\fend

Calculate the partial derivatives of the NURBS in {\tt u}, {\tt v} and {\tt
uv}.

e.g.,
\begin{verbatim}
   PR_nurb *torus, *evaluated_nurb;
   PR_pts *du_values, *dv_values, *duv_values;
   ...
   /* Create a NURBS torus
   */
   nrb_torus(torus);
   /* Evaluate the partial derivatives of a NURBS and retrieve a set of points 
   * for each partial derivative.
   */
   nrb_partials(torus, &du_values, &dv_values, &duv_values);
\end{verbatim}

\func{void}{nrb\_putpoint4}\index{nrb\_putpoint4}
\param{FILE}{*fp}
\param{Ppoint4} {*pt}
\fend

Output a homogenous point to a file pointer.

e.g., used in {\tt nrb\_write}\index{nrb\_write},

\begin{verbatim}
   PR_nurb nurb;
   FILE *data_file;
   ...
   /* Create a NURB
   */
   ...
   /* Output the list of control points
   */
   for(i=0;i<number_of_control_points;i++)
      nrb_putpoint4(data_file,nurb.pf_ppp->pts[i]);
\end{verbatim}

\func{boolean}{nrb\_read}\index{nrb\_read}
\param{FILE}{*fp}
\param{PR\_nurb} {*nrb}
\fend

Read a \pardesc{PR\_nurb} representation from a file, returning the answer in \pardesc{nrb}.
The function returns the value \pardesc{true} if this was successful.

e.g.,
\begin{verbatim}
   PR_nurb nurb;
   FILE *data_file;
   ...
   if((data_file=fopen("file.name","r"))==NULL)
      fprintf(stderr,"ERROR: Unable to open file\n");
   ...
   /* Read in NURB
   */
   if(!nrb_read(data_file,&nurb))
      fprintf(stderr,"ERROR: Unable read NURBS from file\n");   
\end{verbatim}

\func{void}{nrb\_revolve}\index{nrb\_revolve}
\param{PR\_nurb}{*nrb1}
\param{PR\_nurb}{*nrb2}
\fend

Do a surface of revolution about the z axis.
Assumes curve is in x-z plane.
Implemented as per Piegl~\cite{piegl:csc}.
This will use the (3D) projection of CURVE onto y= 0 plane.

e.g.,
\begin{verbatim}
   PR_nurb circle, new_nurb;
   Pvector3 point;
   Pmatrix3 matrix;
   ...
   /* Create a circle
   */
   nrb_circle(&circle);
   /* Displacement the circle
   *  - shift in X
   *  - rotate to XZ plane
   */
   point = ptk_vector3(2.0, 0.0, 0.0);
   ptk_shift3(&point, PREPLACE, matrix);
   ptk_rotate3(90.0, 1, PPRECONCATENATE, matrix);
   nrb_xform(&circle, matrix);
   /* Revolve the circle to create a torus
   */
   nrb_revolve(&circle, &new_nurb);
\end{verbatim}

\func{void}{nrb\_ruled}\index{nrb\_ruled}
\param{PR\_nurb}{*nrb1, *nrb2}
\param{PR\_nurb}{*nrb3}
\param{Pint}{error}
\fend

Do a ruled surface between nrb1 and nrb2. Taken from Piegl~\cite{piegl:csc}.
                                                    
e.g.,
\begin{verbatim}
   PR_nurb square, circle, new_nurb;
   Pvector3 point;
   Pmatrix3 matrix;
   int err;
   ...
   /* Create some different objects
   */
   nrb_square(&square);
   nrb_circle(&circle);
   /* Displacement the circle
   */
   point = ptk_vector3(0.0,0.0,2.0);
   ptk_shift3(&point, PREPLACE, matrix);
   nrb_xform(&circle,matrix);
   /* Create a ruled surface between the the two objects
   */
   nrb_ruled(&circle, &square, &new_nurb, &err);
   nrb_draws(&new_nurb)
\end{verbatim}
 
\func{void}{nrb\_scaleknots}\index{nrb\_scaleknots}
\param{Pfloat}{new\_tmin, new\_tmax}
\param{PR\_dir}{*kk}
\fend

This routine rescales a knot vector to within new limits.

e.g.,
\begin{verbatim}
   PR_nurb *nurb;
   ...
   /* Set the order, number of control points and the number of knots
   */
   nurb->pf_u.pf_k  = 3;
   nurb->pf_u.pf_n  = 5;
   nurb->pf_u.pf_nt = 8;
   ...
   /* Allocate space for the knots in the u direction
   */
   nrb_allocateknots(&nurb->pf_u);
   nrb_makeknots(0.5, 2.0, &nurb->pf_u);
   ...
   /* Re-scale the knots vector to 0.0 - 1.0
   */
   nrb_scaleknots(0.0, 1.0, &nurb->pf_u);
\end{verbatim}
 
\func{void}{nrb\_seterrorcount}
\param{Pint}{i}
\fend

Sets the maximum number of errors that are reported. The default is 10.

Useful for debugging purposes.

\func{void}{nrb\_split}\index{nrb\_split}
\param{PR\_nurb}{*nrb}
\param{Pfloat}{t}
\param{PR\_nurb}{*nrb1, *nrb2}
\fend

Split a NURBS in two.

e.g.,
\begin{verbatim}
   PR_nurb circle, part1_nurb, part2_nurb;
   float split_point;
   Pvector3 point;
   Pmatrix3 matrix;
   int err;
   ...
   nrb_circle(&circle) ;
   /* Calculate a split point in the knot sequence
   */
   split_point=xx;
   /* Split NURBS into two NURBS objects
   */
   nrb_split(&circle, split_point, &part1_nurb, &part2_nurb);
\end{verbatim}

\func{void}{nrb\_stats}\index{nrb\_stats}
\param{FILE}{*fp}
\fend

Prints out statistics concerning the free lists to file \pardesc{fp}.

Useful for debugging purposes.

\func{void}{nrb\_subdivc}\index{nrb\_subdivc}
\param{PR\_nurb}{*nrb1, *nrb2}
\param{Pint}{mu, j}
\fend

Calculates the control points corresponding to new knots---called by
{\tt nrb\_osloc}\index{nrb\_osloc}.

\func{void}{nrb\_tessalate}\index{nrb\_tessalate}
\param{PR\_nurb}{*nrb1}
\param{Pint}{nx}
\param{PR\_nurb}{*nrb2}
\fend

Increase the refinement of the nrb1 by nx, by inserting new knots. The routine
transposes the NURB.

This routine could also be used to evaluate a NURBS to a given tolerance
returning a list of points on the NURBS in the form of the control points.

e.g.,
\begin{verbatim}
   PR_nurb nurb1, nurb2, new_nurb;
   ...
   /* Create a NURB
   */
   ...
   /*  Check to see if the NURBS is a curve
   */
   if(nurb1.pf_v.pf_nt > 1)
   {
      /* The NURBS is a surface, so tessalate a NURBS in both the 
      * U and V directions
      */
      nrb_tessalate(&nurb1, 20, &nurb2);
      nrb_tessalate(&nurb2, 20, &new_nurb);
   }
   else
   {
      /* The NURBS is a curve, so only need to tessalate the NURBS in 
      * single direction
      */
      nrb_tessalate(&nurb1, 20, &new_nurb);
      nrb_transpose(&new_nurb);   
   }
\end{verbatim}

\func{void}{nrb\_transpose}\index{nrb\_transpose}
\param{PR\_nurb}{*nrb}
\fend

Transpose a NURBS in the x and y directions.

e.g.,
\begin{verbatim}
   PR_nurb nurb1, temp_nurb;
   ...
   /* As a result of this degree elevation the NURBS is transposed
   */
   nrb_elevate(TRUE,&nurb1,&temp_nurb); 
   /* This transpose corrects the previous transposition, (transpose U and V)
   */
   nrb_transpose(&temp_nurb);
   /* Copy the nurb back to the original one 
   */
   nrb_copy(&temp_nurb,&nurb1); 
\end{verbatim}

\func{void}{nrb\_unionknots}\index{nrb\_unionknots}
\param{PR\_dir}{*k1,*k2,*k3}
\fend

Create a union of knot sequences.

e.g.,
\begin{verbatim}
   PR_nurb nurb1, nurb2;
   ...
   nurb1.pf_u.pf_k  = 3;
   nurb1.pf_u.pf_n  = 5;
   nurb1.pf_u.pf_nt = 8;
   nurb2.pf_u.pf_k  = 4;
   nurb2.pf_u.pf_n  = 6;
   nurb2.pf_u.pf_nt = 10;
   ...
   nrb_makeknots(0.0, 1.0, &nurb1.pf_u);
   nrb_makeknots(0.0, 1.0, &nurb2.pf_u);
   ...
   /* Create a new knot vector
   */
   nrb_unionknots(&nurb2.pf_u, &nurb1.pf_u, &nurb1.pf_u);
   ...
   nrb_dump(&nurb1);
\end{verbatim}

\func{void}{nrb\_write}\index{nrb\_write}
\param{FILE}{*fp}
\param{PR\_nurb}{*nrb}
\fend

Write a PR\_nurb representation to a file.

e.g.,
\begin{verbatim}
   PR_nurb nurb;
   FILE *data_file;
   ...
   nrb_torus(&nurb);
   ...
   if((data_file=fopen("file.name","w"))==NULL)
      fprintf(stderr,"ERROR: Unable to open file\n");
   ...
   /* Write NURB
   */
   nrb_write(data_file,&nurb);
\end{verbatim}

\func{void}{nrb\_xform}\index{nrb\_xform}
\param{PR\_nurb}{*nrb}
\param{Pmatrix3}{xx}
\fend

Transforms the control points of \pardesc{nrb} using matrix \pardesc{xx},
and returns them in \pardesc{nrb}.

e.g.,
\begin{verbatim}
   PR_nurb circle, new_nurb;
   Pvector3 point;
   Pmatrix3 matrix;
   ...
   /* Create a circle
   */
   nrb_circle(&circle);
   /* Displacement the circle
   *  - shift in X
   *  - rotate to XZ plane
   */
   point = ptk_vector3(2.0, 0.0, 0.0);
   ptk_shift3(&point, PREPLACE, matrix);
   ptk_rotate3(90.0, 1, PPRECONCATENATE, matrix);

   /* Perform the actual transformation on the NURBS according to the matrix
   */
   nrb_xform(&circle, matrix);
\end{verbatim}

\subsection{Creation Operators}

\func{void}{nrb\_arc}\index{nrb\_arc}
\param{Pfloat}{theta1, theta2}
\param{PR\_nurb}{*nrb}
\fend

Create an arc of a circle centered at (0,0,0), with radius 1 in XY plane.
The arc starts and finishes at {\tt theta1}, and {\tt theta2} degrees 
respectively.

e.g., 
\begin{verbatim}
   PR_nurb nurb;
   float arc_begin=0.0, arc_end=90.0;
   ...
   nrb_clear(&nurb);
   /* Allocate space for the knots in the u direction
   */
   nrb_arc(arc_begin, arc_end, &nurb);
\end{verbatim}

\func{void}{nrb\_circle}\index{nrb\_circle}
\param{PR\_nurb}{*nrb}
\fend
Make a unit circle in the XY plane, with it's centre at (0,0,0).

e.g.,
\begin{verbatim}
   PR_nurb circle;
   ...
   /* Create a NURBS representation of a circle
   */
   nrb_circle(&circle);
\end{verbatim}

\func{void}{nrb\_polyline}\index{nrb\_polyline}
\param{Pint}{npts}
\param{Ppoint3}{*pp}
\param{PR\_nurb}{*nrb}
\fend

Generate the NURBS representation of a line.

e.g.,
\begin{verbatim}
   PR_nurb nurb;
   int order, number_of_points;
   float *pp;
   ...
   /* Initialize a nurb with a give set of values
   */
   nrb_init(order,number_of_points+order,0,1,&nurb);
   /* Set the data for the polyline
   */
   for(i=0;i<number_of_points;i++)
      pp[i]=data_points[i];
   /* Create the polyline
   */
   nrb_polyline(number_of_points, pp, &nurb);
\end{verbatim}

\func{void}{nrb\_torus}\index{nrb\_torus}
\param{PR\_nurb}{*nrb}
\fend

Generate the NURBS representation of a torus about the origin.

e.g.,
\begin{verbatim}
   PR_nurb torus;
   ...
   /* Create a NURBS representation of a torus
   */
   nrb_torus(&torus);
\end{verbatim}

\func{void}{nrb\_triangle}\index{nrb\_triangle}
\param{PR\_nurb}{*nrb}
\fend

Generate the NURBS representation of a triangle about the origin.

e.g.,
\begin{verbatim}
   PR_nurb triangle;
   ...
   /* Create a NURBS representation of a triangle
   */
   nrb_triangle(&triangle);
\end{verbatim}

\func{void}{nrb\_square}\index{nrb\_square}
\param{PR\_nurb}{*nrb}
\fend

Create a NURBS representation of a square about the origin.

e.g.,
\begin{verbatim}
   PR_nurb square;
   ...
   /* Create a NURBS representation of a square
   */
   nrb_square(&square);
\end{verbatim}

\func{void}{nrb\_sphere}\index{nrb\_sphere}
\param{PR\_nurb}{*nrb}
\fend

Generate the NURBS representation of a sphere about the origin.

e.g.,
\begin{verbatim}
   PR_nurb sphere;
   ...
   /* Create a NURBS representation of a sphere
   */
   nrb_sphere(&sphere);
\end{verbatim}

\func{void}{nrb\_vase}\index{nrb\_vase}
\param{PR\_nurb}{*nrb}
\fend

Generate the NURBS representation of a vase about the origin.

e.g.,
\begin{verbatim}
   PR_nurb vase;
   ...
   /* Create a NURBS representation of a vase
   */
   nrb_vase(&vase);
\end{verbatim}

\subsection{Drawing Procedures}

The following drawing procedures are implemented using DEC PHIGS and are
provided for completeness. 

\func{void}{nrb\_drawc}\index{nrb\_drawc}
\param{PR\_nurb}{*nrb}
\param{Pfloat}{t}
\param{PE\_dir}{xory}
\fend

Draw a NURBS curve together with it control polygon.

e.g.,
\begin{verbatim}
   PR_nurb circle;
   ...
   /* Create a NURBS representation of a circle
   */
   nrb_circle(&circle);
   /* Open PHIGS structure
   */
   popenstruct(NURB_STRUC);
      /* Draw the circle
      */
      nrb_drawc(&circle,0.05,PVudir);
\end{verbatim}

\func{void}{nrb\_drawcnet}\index{nrb\_drawcnet}
\param{PR\_nurb}{*nrb}
\param{Pint}{start}
\param{PE\_dir}{xory}
\fend

Draw a NURBS curve's defining control polygon.

e.g.,
\begin{verbatim}
   PR_nurb circle;
   ...
   /* Create a NURBS representation of a circle
   */
   nrb_circle(&circle);
   /* Open PHIGS structure
   */
   popenstruct(NURB_STRUC);
      /* Draw the circle's control polygon
      */
      nrb_drawcnet(&circle, 1, PVudir);
\end{verbatim}

\func{void}{nrb\_draws}\index{nrb\_draws}
\param{PR\_nurb}{*nrb}
\fend

Draw a NURBS surface together with it control polygon.

e.g.,
\begin{verbatim}
   PR_nurb torus;
   ...
   /* Create a NURBS representation of a torus
   */
   nrb_torus(&torus);
   /* Open PHIGS structure
   */
   popenstruct(NURB_STRUC);
      /* Draw the torus
      */
      nrb_draws(&torus);
\end{verbatim}

\func{void}{nrb\_drawsnet}\index{nrb\_drawsnet}
\param{PR\_nurb}{*nrb}
\fend

Draw a NURBS surface's defining control polygon.

e.g.,
\begin{verbatim}
   PR_nurb torus;
   ...
   /* Create a NURBS representation of a torus
   */
   nrb_torus(&torus);
   /* Open PHIGS structure
   */
   popenstruct(NURB_STRUC);
      /* Draw the torus
      */
      nrb_drawsnet(&torus);
\end{verbatim}

\func{void}{nrb\_phigsplus}\index{nrb\_phigsplus}
\param{PR\_nurb}{*nrb}
\fend

This routine actually draws the NURBS using PHIGS PLUS primitives. 
It is provided for completeness. If another application programming interface
is used this routine must be rewritten.

e.g.,
\begin{verbatim}
   PR_nurb nurb;
   ...
   /* Construct a NURB
   */
   nrb_init(order_u,number_knots_u,order_v,number_knots_v,&nurb);
   nrb_makeknots(0.0,1.0,&nurb.pf_u);
   nrb_makeknots(0.0,1.0,&nurb.pf_v);
   nrb_allocatepts(npt,&nurb.pf_ppp);
   /* Set the control points
   */
   ...
   /* Open PHIGS structure
   */
   popenstruct(NURB_STRUC);
      /* Draw the NURB
      */
      nrb_phigsplus(&nurb);
\end{verbatim}

\newpage

\section{Installation}

\begin{figure}
\centerline{\psfig{figure=nurb-structure.ps,width=4in}}
\caption{\label{fig:nurb_structure}NURBS library directory structure.}
\end{figure}

\index{Installation procedure}
There are two different methods of installation of the procedure library
depending on the type of machine to be installed on. Both methods create the
directory structure as shown in figure~\ref{fig:nurb_structure}.

The header files may be copied into the system header file directory or left as
is. If the files are copied into the system area then the various {\tt
makefiles} must be updated. 

Currently, the NURBS library is built in the form of a shared executable library
for VMS and an object library for UNIX. This to can be built and installed into
the appropriate system area, but at present is created in {\tt library}.
If the library is to be moved into the system area then again the {\tt
makefiles} must be updated.

\subsection{For UNIX}
\index{Installation for UNIX}

The library is provided in the form of a compressed tar archive. Once the
archive has been obtained. 

\begin{enumerate}
\item Uncompress the archive by typing

\begin{verbatim}
   > uncompress nurb.tar.Z
\end{verbatim}
\item Untar the archive

\begin{verbatim}
   > tar xvf nurb.tar target-directory
\end{verbatim}

This will extract the library from the {\tt target-directory} creating the
correct directory structure for the library and placing the files in the
correct place below the {\tt target-directory}.

\end{enumerate}

\subsection{For VMS}
\index{Installation for VMS}

The library is provided in the form of a backup save set. Once the archive has
been obtained.

\begin{enumerate}
\item Restore the files from the save set in to an appropriate place in the
directory structure.

\begin{verbatim}
   > BACKUP NURB.BCK/SAVE_SET [target-directory...]
\end{verbatim}

This will restore the library correctly into the VMS directory structure,
correctly placing the files in the correct places.

\end{enumerate}

\subsection{Building the Library}
\index{Library installation}

For both VMS and UNIX systems it is assumed that \LaTeX, {\tt bibtex} and {\tt
idxtex} are available to produce the documentation.

\subsubsection{UNIX}

A number of {\tt makefiles} exist to build the various parts of the library.
Each {\tt makefile} is called by the main {\tt makefile} which is located at
the top of the NURBS library structure, in {\tt nurb}.

\begin{itemize}
\item {\underline{To Build the Entire Distribution}}

\begin{verbatim}
   > make all
\end{verbatim}

\item {\underline{To Build the Documentation}}

\begin{verbatim}
   > make docs
\end{verbatim}

\item {\underline{To Build the Library}}

\begin{verbatim}
   > make library
\end{verbatim}

\end{itemize}

\subsubsection{VMS}
\index{Installation for VMS}

A single build file exists in the form of a VMS command procedure. This is
located at the top of the NURBS library directory structure. 

Alias a symbol to execute the command procedure.

\begin{verbatim}
> build :== @makefile
\end{verbatim}

\begin{itemize}

\item {\underline{To Build the Entire Distribution}}

\begin{verbatim}
   > build all
\end{verbatim}

\item {\underline{To Build the Documentation}}

\begin{verbatim}
   > build docs
\end{verbatim}

\item {\underline{To Build the Library}}

\begin{verbatim}
   > build library
\end{verbatim}

\end{itemize}

\section{Example Programs}
\index{Programming example}

Provided with this distribution are a number of example programs to demonstrate
the use and also test the procedure library. These programs are located in the 
{\tt nrb\_demos} directory.

\begin{itemize}
\item {\tt nrbtst00.c} Simple program to create a NURB
\item {\tt nrbtst01.c} Test transformations
\item {\tt nrbtst02.c} Create a ruled surface
\item {\tt nrbtst03.c} Test routine {\tt nrb\_bvalue}
\item {\tt nrbtst04.c} Test routine {\tt nrb\_oslo}
\item {\tt nrbtst05.c} Test routine {\tt nrb\_boehmc}
\item {\tt nrbtst06.c} Create a simple surface
\item {\tt nrbtst07.c} Test routine {\tt nrb\_interpolate}
\item {\tt nrbtst08.c} Test routine {\tt nrb\_interpolate}
\item {\tt nrbdemo1.c} Test routine {\tt nrb\_extrude}
\item {\tt nrbdemo2.c} Interactive demonstration program written in DEC PHIGS
\item {\tt trantest.c} Test the TRAN module
\end{itemize}

Note that since the NURBS routines make use of a separate object which is
derived from the PHIGS Toolkit project, also available from Kent, this to
included in this version of the distribution. 

The following is an example program {\tt nrbdemo1.c}, showing how to make 
use of the NURBS procedure described above. 

\verbatimfile{../demos/nrbdemo1.c}

\subsection{Interactive NURBS Demonstration}

The program {\tt nrbdemo2.c} is an interactive demonstration of the NURB
procedure library. The program is written using DEC PHIGS version 2.2 which
supports PHIGS PLUS primitives, the program could be ported to other versions of
PHIGS PLUS quite easily. It also gives a good example of how to use the
procedure library.

The program uses the procedure library to generate a number of different NURBS 
objects which can be manipulated by routines in the library.

The objects are created by using the creation and constructions
operators.

\begin{itemize}
\item Torus.
\item Cylinder.
\item Cone.
\item Sphere.
\item Cuboid.
\item Tetrahedron.
\item Triangular Prism.
\item Vase.
\item Circle.
\item Square.
\item Triangle.
\item Ruled Surface.
\end{itemize}

The operations on the NURBS objects give an indication of how easy
the procedure library is to use.

\begin{itemize}
\item Elevate a NURB,
\item Transpose a NURB,
\item Refine a NURBS knot vector,
\end{itemize}

as well as a number of interactive functions which include rotation and
scaling.

\section{Compiling and Linking}
\index{Compiling and linking}

There are two different ways in which to build the program depending on the
operating system. In both cases a number of compiler directives must be issued 
in order to build the programs correctly. 

The NURB library is designed to
coexist with the PHIGS Toolkit (PTK) and as such share a number of common header
files. There are three cases inwhich both the NURB library and the Toolkit can
exist.

\begin{enumerate}
\item Just PTK

PTK and no NURB, no action need be taken
\item Just NURBS

NURB and no PTK, define NURB

\item NURB and PTK

Define PTKNURB
\end{enumerate}

\subsection{Build for VMS}
\index{Compiling and linking}

If the NURBS shared executable library has not been built and placed into the
system area then the {\tt linker} must be told explicitly where the library is
located. This is done be defining a {\tt logical symbol} for the library,
indicating the full path to the library.

e.g.,
\begin{verbatim}
   DEFINE NURBS DISK$USERS_C:[YIP.NURBS.LIBRARY]NURB.EXE
\end{verbatim}

Compile with:

\begin{verbatim}
   CC/INCLUDE_DIRECTORY=[-.INCLUDE] NRBDEMO1
\end{verbatim}

Link with:

\begin{verbatim}
   LINK NRBDEMO1,NURBS/OPT,VAXCRTL/OPT
\end{verbatim}

and run with

\begin{verbatim}
   RUN NRBDEMO1
\end{verbatim}

The option files, {\tt NURBS.OPT} and {\tt VAXCRTL.OPT} contain details of
the locations of the shared libraries that must be linked with the programs.

\begin{verbatim}
   NURBS.OPT:

   DISK$USERS_C:[YIP.NURBS.LIBRARY]NURB.EXE/SHARE
\end{verbatim}                                                         

\begin{verbatim}
   VAXCRTL.OPT:

   SYS$LIBRARY:VAXCRTL.EXE/SHARE
\end{verbatim}

\subsection{Build for UNIX}                                             
\index{Compiling and linking}

Compile with:

\begin{verbatim}
   cc -c nrbdemo.o nrbdemo1.c -I../library
\end{verbatim}

Link with:

\begin{verbatim}
   cc -o nrbdemo1 nrbdemo1.o ../library/libnurb.a -lm
\end{verbatim}

and run with

\begin{verbatim}
   nrbdemo1
\end{verbatim}

All the demonstration and test programs in the \pardesc{demos} directory
can be compiled and linked in a similar manner.

\newpage

\nocite{*}
\bibliography{nurbclib}

\newpage

\input{nurbclib.ind}

\end{document}
