\input header.tex


\title{Parametric Surface Interrogations}

\section{Some more Differential Geometry}

The derivative of an implicit surface is the derivative of its function with respect to position.   This derivative is a standard function in vector field theory called the {\bf gradient} or {\bf grad}.  Within solid body transforms it transforms as a displacement, and it has the property of being perpendicular to the zero-set surface.  We call it the {\bf surface normal} and typically denote it by $N$.   Note that in the plane equation we used the symbology $f = [P-Q].N$ so that $df/dP = N$.  This was not an accident.  In general the gradient, $N$, varies with position.  Only in the plane case is it constant.

The derivatives of a parametric surface with respect to $u$ and $v$ are displacements lying locally tangent to the surface. (They are the tangents to curves which lie entirely within the surface).   We denote them by $P_u$ and $P_v$, which are shorter than the equivalent $\partial P/\partial u$ and $\partial P/\partial v$.  If we take the cross product of these two, in the conventional sequence $$P_u \times P_v$$ we get a vector which is perpendicular to both of them and which is therefore perpendicular to the surface.  Again we call this the surface normal and denote it by $N$.

In both types of surface we can take higher derivatives.  Just as the second derivative of a curve affects the local curvature, the second derivatives of a surface affect the surface curvature.

Note that there are three second derivatives of a parametric surface, $\partial^2P/\partial u^2$, $\partial^2P/\partial u\partial v$ and $\partial^2P/\partial v^2$, and the components of these vectors along $N$ influence the three components of scalar curvature.  The other 
components influence the taper and swirl of the parametrisation within the surface.

There are nine numbers (six independent numbers) in the second derivative tensor of an implicit surface and it is simplest just to follow where the algebra leads when they are needed, rather than trying to determine direct geometric interpretation.

\section{API}

The basic interrogations relevant to parametric surfaces in general are:-

\pop evaluation
\pop evaluation of derivatives
\pop definition of boundary

\filbreak
The first two of these are straightforward parallels to the curve case.  The third is inherently more complex in that the valid region may be bounded by a curve, and this curve may legitimately have a number of connected components, quite apart from any geometric complexity it may have.

\filbreak
We will assume that the boundary curve is actually represented by a collection of pieces, each defined as a map from a curve parameter, $t$, to a pair of surface parameters $u,v$.
We also assume that the orientation of each of these pieces is such that if the curve is traversed in the direction of increasing $t$, the valid region of surface locally is on the right (i.e. if $du/dt=0, dv/dt>0$, then the valid region is on the side of greater $u$).

\filbreak
Because the map $\R\rightarrow\R^2$ defining a boundary segment can be composed with the map $\R\rightarrow\R^3$ which defines the surface, we can treat such a curve as a parametric curve and interrogate it as such, so that we can find the intersections with a plane, for example.

\filbreak
Note that we do not have to handle the segments in any particular sequence.  We must insist, however, that they form one or more closed loops.

\filbreak
If no other boundary is present, the implicit boundary consists of four segments:-
\pop $u=0,v=t$
\pop $v=1,u=t$
\pop $u=1,v=1-t$
\pop $v=0,u=1-t$
 
\section{Nearest Point}

This is in some ways the simplest surface interrogation.  We wish to find the point $P(u,v)$ of the surface for which the scalar function $r(u,v) = |P(u,v)-Q|$ is smallest.  Note that minimising $r^2$ avoids a lot of algebraic and numerical overhead.

\filbreak
There are three classes of possible such points:-

\pop points at the ends of the edge segments.
\pop points in the interior of the edge segments
\pop points in the interior of the surface

\filbreak
We focus here on the third of these, at which the conditions hold$$dr^2(u,v)/du,dv =0$$

Let 
$$\eqalign{
 f(u,v) &= dr^2/du = 2P_u.[P-Q]\cr
 g(u,v) &= dr^2/dv = 2P_v.[P-Q]
}$$

\filbreak
A Newton formulation can be set up as
$$\left[\matrix{\delta u\cr\delta v}\right] =
-\left[\matrix {f_u&f_v\cr g_u&g_v}\right]^{-1}
\left[\matrix{f\cr g}\right]$$

\filbreak
If the initial guess is sufficiently close to a local minimum this iteration will home in efficiently.  The two major problems are that it will also home in on a local maximum, which also satisfies the equations, and that the local minimum need not be a global one.

\filbreak
Local maxima can be avoided by using a hill-climbing method instead whenever the matrix in the Newton method is not positive definite.  This involves moving in whatever direction reduces $r^2$ fastest.  This is just $$-\left[\matrix{f\cr g}\right]$$
The two methods can be combined by adding a multiple of the identity matrix to the Newton matrix sufficient to make the sum positive definite, before solution for $\delta u,\delta v$.

\filbreak
Our only hope for avoiding a local minimum which is not global is either to rely on characteristics of the problem in which the nearest point interrogation is embedded, or else to use a spatter of starting points.

\filbreak
If the problem is likely to have only a single minimum, as is the case with the relatively uncontorted surfaces found in manufactured objects, a good strategy is to use the search for  corner and edge candidates to provide a start point.  Each edge end point is either itself a  candidate or else provides a starting point for hunting for an interior edge point.  Each interior edge nearest point is either a candidate which can be ranked with others for finding the global minimum, or else provides a starting point for searching the interior of the face.


\filbreak
Nearest point is a good example of a {\bf nilvariate} interrogation, which results in just a single point. Its individual subtlety is that there is always a nearest point, which might be on the boundary.  This does not have to be unique, since a point on the axis of a cylinder has a ring of nearest points, but in the absence of such degeneracy the solution is usually unique.  This is in contrast to the similar {\bf foot-point} problem which explicitly looks for points where the surface is perpendicular to the vector joining the surface point to a fixed point.  The latter can have many solutions or none.   So can the structurally similar {\bf raycasting} problem where we look for the intersection of the surface with a linear ray in a given direction from a given point.

\section{Plane Section}

This is the simplest example of a {\bf univariate} interrogation, in which the required result is itself a curve.

The first point to note is that the curve in which a plane cuts a surface can be too complicated to treat as purely parametric.  Algebraically, a plane cut through a polynomial surface is of high genus, which tells us that there will normally be no 1:1 map from the reals even for individual pieces:  topologically the intersection curve can consist of a number of closed loops.

The best we can do is to treat the curve as a number of approximating pieces.  The simplest of these is to determine a collection of polygons whose vertices lie on the curve (i.e. lie both on the surface and the plane).  

\filbreak
The simplest situation is that in which we expect the plane sections that we want to cut to be open curves, with ends on the boundary of the surface.   First we find the ends by doing plane cuts on all pieces of the boundary.  From the local differential geometry we can determine which of these can be start points for cuts to be traversed with the positive side of the plane to be on the right in the parameter plane.  The others will be end points.

\filbreak
From a given start point, we can determine the direction in the parameter plane in which the   plane function stays constant.   Let the plane be $f(P) = 0$, then for a direction $\delta u,\delta v$ in the parameter plane we find that 
$$\eqalign{
\delta P &\approx P_u\delta u + P_v\delta v\cr
\delta f &\approx df/dP.P_u\delta u + df/dP.P_v\delta v\cr
= 0 \hbox{ if } \delta u &=\alpha df/dP.P_v\cr
    \hbox{ and } \delta v &=-\alpha df/dP.P_u
}$$

We can also determine the curvature of this path from the second derivatives.

This is now a very similar situation to that in which we were drawing a parametric curve. We can determine the size of $\alpha$ from the local curvature.

\filbreak
This gives a new point $(u,v)$ which is our estimate of the next point along the intersection curve.  It is, however, only an estimate, and to find the next actual point we need to home in on a surface point which actually lies on the plane.  Newton is very likely indeed to work well in this circumstance, but we only have one plane equation and need two to determine updates to both $u$ and $v$.   We get the second one by setting up an approximation to the step length as a function of $u$ and $v$ and trying to get the ideal.
The situation is asymmetric between the two conditions in that we probably want the next point to lie on the plane to a high degree of accuracy, but it is not worth worrying if the step length is a few percent out.  Thus small errors in step length do not trigger extra iterations once the point lies acceptably close to the plane.

This process of taking a major step and then iterating to a point on the curve is repeated until it reaches the boundary again. (An open curve must have two ends.)

\filbreak
If there are no open intersection curves, it is possible to hunt for closed loops by setting up a grid of points across the surface and systematically checking for changes of sign of $f$.   Tracing the curve needs then to record which edges of the grid have been crossed, and there is also detail in checking when a loop of curve has been completed.

\filbreak
The main problems are:- 
\pop That of robustness during the tracing.  If two leaves of the curve come close together because the surface is hyperbolic and almost tangential to the plane, it is hard to ensure that the marching process does not get lost.  It is always possible to find configurations where Newton fails to converge.

\pop That of missing small loops of intersection.  This is not important if we are calculating the shapes of frames in aircraft structures, but does matter if we are checking for interference between two parts of a mechanism.

\filbreak
\section{Surface Intersections}

You will have noticed that the description of plane sections was in fact couched in more general terms $f(P)$ rather than $[P-Q].N$.  The same approach therefore covers intersections of parametric surfaces with all implicit surfaces, not just planes.  The technology will need local enhancement if the implicit surface does not have continuous derivatives (as would be the case if it contained a Boolean combination) but it is not seriously different.

The intersection of one parametric surface with another also follows much the same structure, in which first a starting point is found, then a major step is taken along the curve, and finally minor steps are taken to home in on a point actually lying on the intersection.

We could use the nearest point algorithm to pretend that the second surface is an implicit one, but it is more efficient to iterate in the four variables, two parameters in each surface.  Newton works just as well in four variables as two.

\filbreak
\section{Offset Surfaces}

There are three scenarios in which offset surfaces are important in engineering:-

\pop skin thicknesses.  If the outside lines of an aircraft, ship or car are defined as surfaces, we need to determine the shapes of the structural members which mate with the insides of those skins.  These are of the order of less than a millimetre for car skins, a couple of millimetres for aircraft skins and a centimetre or so for ship plates.   In the conic lofting systems of the 1950's and 1960's it was typical that the master definition was of the inside of the skin, precisely to avoid this problem.

\pop cutter form.   If we are machining a surface on a numerically controlled machine tool, we need to allow for the shape and size of the cutter.  These are typically of the order of a few centimetres, but if we are machining a small scale model this is the equivalent of tens of centimetres at full scale. 

\pop centres for rolling ball blends.  One way of defining a blend for a concave corner is to fill it with clay and then roll a ball along it to squeeze out the extra, leaving a blend surface with circular cross sections.  The numerical equivalent of this is to offset the two surfaces by the blend radius, calculate the intersection (which is the locus of centres) and  also the contact points on the two surfaces, and then fit a pipe surface.

Suppose that we have a base surface $P(u,v)$.  At each point of it we have a surface normal, $N$, and this determines the direction of offset.  This means that from $u,v$ we can compute $P$ and $N$, and thence the corresponding offset point, $Q$ say.  Compounding these maps we get that $Q$ is a function of $u$ and $v$ and thus that $Q(u,v)$ is a parametric surface.

All our interrogations which depend only on the surface being parametric and not on it being polynomial (offset surfaces are not) will still work.




\end
 