\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig}

\textheight= 8in \textwidth=5.5in
\parindent =0pt
\hsize = 5in
%\voffset = 1 in
%\hoffset= 1 in
\parindent = 0pt
\parskip = 0.2cm
\tolerance = 10000
\input{../../newcomm}

\begin{document}


\title{PN Patches}
    \author {Gerald Farin}
\maketitle

A recent use of triangular \bz\ patches is in computer graphics,
where they are used for rendering triangle meshes, see
\cite{vpbm01}, \cite{ovwyv97}, \cite{leejen01}. Suppose you have a
relatively coarse triangle mesh, such that even with Gouraud or
Phong shading you will not get a nice looking object. Suppose
further that you have a normal defined at every vertex.

The goal is to build a cubic \bz\ patch over each triangle, such
that the resulting collection of \bz\ triangles forms a continuous
surfaces. This surface will not be $G^1$, however. This defect
will be overcome by a display trick, explained below.

Let us concentrate on one triangular facet. It has three vertices,
which we denote by $\bb_{300}, \bb_{030}, \bb_{003}$. At each of
these vertices, we also have a normal, and we denote them by ${\bf
n}_{200}, {\bf n}_{020}, {\bf n}_{002}$ -- this notation will be
explained shortly. Our desired \bz\ patch needs three boundary
curves; let's concentrate on the one from $\bb_{300}$ to
$\bb_{030}$. We need \bz\ points $\bb_{210}$ and $\bb_{120}$ in
order to have a boundary control polygon. They are found by using
a point/normal interpolation algorithm. In order to find
$\bb_{210}$, we define $\bb'_{210}=(2\bb_{300}+\bb_{030})/3$. Then
we project $\bb'_{210}$ into the plane defined by point
$\bb_{300}$ and normal ${\bf n}_{200}$ and obtain
$$
    \bb_{210}=\bb'_{210} -\frac{1}{3}({\bf
    n}_{200}[\bb_{030}-\bb_{300}]){\bf n}_{200}.
$$
This process is illustrated in Figure \ref{fig:pnbound} and
repeated for $\bb_{120}$.

\begin{figure}
    \epsfig{file=pn_input.ps, height = 1.5 in}
    \caption{PN patches: left, input data. Right: boundary control polygons.}
    \label{fig:pnbound}
\end{figure}

We repeat for the remaining two boundaries. One control point is
still undetermined, namely $\bb_{111}$. We determine it from
$$
    \bb_{111}= \frac{1}{4}\sum_{0jk,i0k,0jk}\bb_{ijk} -
    \frac{1}{6}[\bb_{300}+\bb_{030}+\bb_{003}].
$$

At this point, we have built a cubic patch over each triangular
facet. The resulting overall surface will not be smooth, for the
reasons outlined in Section 18.4. The trick now is to modify the
display algorithm such that it {\em looks} smooth.

When we render a surface, we need to break it down into an
appropriate number of triangular facets, compute the normals at
the vertices, and feed all to the shader. For a \bz\ triangle,
this is done by 1. running the \dca\ for each vertex and 2.
extracting the surface normal from it. For PN patches, these two
processes are separated. The point evaluation is as usual, but the
normal is computed differently. In fact, it is not the true
surface normal but rather one that ``looks better".

A {\em display normal} $\dd(\uu)$  will be computed from
\begin{equation}
    \dd(\uu)=\sum_{\iabs=2} B^2_\ii(\uu)\dd_\ii.
    \label{eq:pnormals}
\end{equation}
The six display control normals $\dd_\ii$ are found as follows:
$$
    \dd_{200}={\bf n}_{200},~~\dd_{020}={\bf n}_{020},~~\dd_{002}={\bf
    n}_{002}.
$$

The three remaining ones are not that simple. Concentrating on the
edge $u_3=0$, and the display normal $\dd_{1/2}$ at
$(\frac{1}{2},\frac{1}{2},0)$, we might set
$$
    \dd_{1/2}=\frac{1}{2}\dd_{200} + \frac{1}{2}\dd_{020}
$$
and normalize to get a unit normal.  This choice, however, would
give an undesirable normal if $\dd_{200}$ and $\dd_{020}$ were
close to being equal, meaning that the corresponding boundary
curve has an inflection point. See Figure \ref{fig:pnormal}

\begin{figure}
    \epsfig{file=pnormal.ps, height = 2 in}
    \caption{PN normals: left, simple averaging. Right, averaging
    followed by reflection.}
    \label{fig:pnormal}
\end{figure}

A better choice was found to be  constructing a plane
perpendicular to $ \overline{\bb_{300} ,\bb_{030}}$ and reflecting
the above $\dd_{1/2}$ across this plane for the final display
normal value of $\dd_{1/2}$. This gives

\beq
    \dd_{1/2}=\dd_{200}+\dd_{020} -
    2\frac{(\bb_{030}-\bb_{300})(\dd_{200}+\dd_{020})}{\|\bb_{030}-\bb_{300}\|^2}
    (\bb_{030}-\bb_{300}).
    \label{eq:pnormal1}
\eeq

The display normal $\dd_{110}$ is then defined to equal
$\dd_{1/2}$.

With this arrangements of display control normals, we are
guaranteed continuous normals along common boundary curves between
patches. While the resulting display is not accurate, it is smooth
-- which is what matters if good looks for rendering is important!

An improvement over (\ref{eq:pnormal1}) is as follows. The
assignment
$$
    \dd_{110} = \dd_{1/2}
$$
does not guarantee that
$\dd(\frac{1}{2},\frac{1}{2},0)=\dd_{1/2}.$ In order to achieve
this, we need to set
\beq
    \dd_{110}=\frac{3}{2}\dd_{1/2}-\frac{1}{4}\dd_{200} -
    \frac{1}{4}\dd_{020}.
\eeq

\bibliographystyle{plain}
\bibliography{../../../papers/refs}
\end{document}
