## 3d Surface Patches

### 3d Surface Patches

Can anybody help with a classification scheme and explanation of 3d patch terminology.

1. Patches can be bilinear or bicubic

I Understand this

2. Patches can be rational or nonrational

I Don't understand this

3. Patches can be uniform or non uniform

I Don't understand this

4. Types of patches

Bezier          (Understand)
Spline          (Understand)
Hermite         (don't understand)
Power           (don't understand)
CatmullRom      (don't understand)

5. Basis Matrices & Power Matrices

I know each bicubic has 2 4x4 matrices (one for U and one for V). I am a bit unclear
about the distinction between a power matrix and a  basis matrix.
Also what is meant by
"a basis matrix that is used to transform from the power basis to the preferred basis ?".

6. Knots

What is meant by know values

7. Ducks

What are ducks.

I have a fair idea about most of the above, by have a little difficulty with some of the ideas and
terms used. I have read Foley & Van Dam, Newman & Sproull, RanKin, Rogers & Adams. Each explain
a little but none unify the concepts.

Also I have a specific question about texturing mapping and patch (U, V) interpolation.
I want to group a IxJ array of similar type patches together and interpolate
[U1 -> [0, 1], V1 -> [0,  1] across the entire array of
patches. I want to do this so that I can map a single unit square texture onto the entire
patch array surface, not just repeat the texture for each patch in the array.

I know that I have asked for a lot of information, but any help unifying concepts would
be appreciated.

{uunet,mcvax,ukc,nttlab}!munnari!attila.esa.oz!shaun

--

{uunet,mcvax,ukc,nttlab}!munnari!attila.esa.oz!shaun

### 3d Surface Patches

In article <4...@attila.esa.oz> sh...@attila.esa.oz (Shaun) writes:
>Can anybody help with a classification
>scheme and explanation of 3d patch terminology.

I'll try, but be warned that terminology differs from
reference to reference.

>1. Patches can be bilinear or bicubic

Actually, patches (and we are probably talking tensor-product patches here)
can be linear-quadratic, bilinear, quintic-cubic, heptic-constant, etc.
etc. etc.

We will regard a patch as

P(u,v) = sum(i=0 to m) { sum(j=0 to n) { a[i,j]*b[i](u)*c[j](v) } }

A surface is a number of such things in geometric association.  The
nomenclature of the patch, or surface, is taken from the functions "b" and "c".
If, for example, the b's are linear polynomials in u and the c's are quadratic
polynomials in v, the patch is linear-quadratic.  etc. etc.
To be a surface, the coefficients "a" have to be 3-D points, of course.

>2. Patches can be rational or nonrational

A rational patch has either or both of b and c as a quotient of functions; e.g.

b(u) = f(u)/g(u)

an integral ("nonrational") patch has niether "b" nor "c" of this form.

>3. Patches can be uniform or non uniform

The term "patch" is usually reserved for a single, bivariate construct.
A "surface" consists of many patches.  The above formula for P(u,v)
can still be used if b and c are now regarded as piecewise functions:

b[i](u) = if( (u<=u) && (u<u) ) then {definition-1 of b[i](u)}
else if( (u<=u) && (u<u) ) then {definition-2 of b[i](u)}
else if( (u<=u) && (u<u) ) then ... etc. etc.

I would not say that a single patch is uniform or nonuniform, but that
such a piecewise assembly is uniform if (u[s]-u[s-1]) = constant (independent
of the index "s").  However some might like to transfer the uniform/nonuniform
name to each individual patch of such an assembly.

Why is this concept useful?  If a surface is uniform, it is usually possible
to use one, generic definition for "b" and "c" rather than a separate one for
each "segment" (u[s-1] to u[s] interval, v[t-1] to v[t] interval).  The
space efficiency and programming simplicity is obvious.

>4. Types of patches

The type of a patch could be Bezier/B-spline or biBezier or etc. etc.
The same considerations apply here as to the naming according to degree.
What is at issue are the polynomial patches (surfaces) and the way in which
the polynomials "b" and "c" (or the piecewise polynomials "b" and "c")
are represented.  The "basis" that is used, in other words.  A polynomial

A + B*u + C*u*u

can also be represented as

A*{(1-u)*(1-u)} + (A+B/2)*{2*u*(1-u)} + (A+B+C)*{u*u};

The former is the power representation and the latter is the Bernstein
(Bezier) representation.  In general, a quadratic can be represented
as

cf*B(u) + cf*B(u) + cf*B(u)

provided that the basis polynomials "B" are linearly independent.  If they
are, one such selection of B's can be replaced by another to obtain the
same polynomial, if the coefficients "cf" are appropriately reorganized.
In my example:

Power:  B(u) = 1, B(u) = u, B(u) = u*u
cf = A,   cf = B,   cf = C.

Bezier:  B(u) = (1-u)*(1-u), B(u) = 2*u*(1-u), B(u) = u*u
cf = A,             cf = A+B/2,       cf = A+B+C

The two representations produce the same polynomial.  Plug in any value
of u, and the same polynomial value results.

Hermite and Catmull-Rom, loosely speaking, are two other representation
schemes.

Why is this important?  Certain things are simpler to state, program,
compute, and manipulate in one form than another.  However, no one
form is best for all possible applications, so a variety of different
representations contend for our consideration and understanding.

>5. Basis Matrices & Power Matrices

The concept of basis comes from linear algebra, where we learn that one
basis can be transformed into another by matrix multiplication.  Same thing
here.  All polynomials of degree less than or equal to k form a vector space
of dimension k+1 (quadratics have degree 2 and 3
coefficients/basis-polynomials/degrees-of-freedom).
For degree k polynomials, we should expect to be interested in (k+1) by (k+1)
matrices.  For cubics, 4x4 is the magic number.  If both "b" and "c" of our
patch are cubic ("bicubic", remember), then two 4x4 matrices will rear their

In my example above,

[ 1 u u*u ] [  1   0   0  ]  [ (1-u)*(1-u)  2*u*(1-u)  u*u ]
[ -2   2   0  ]
[  1  -2   1  ]

If I have code (or hardware) to evaluate a particular basis
faster than another,  I will probaly work conceptially in terms of one
basis, but evaluate in terms of another, and use such a matrix (explicitly
or in some implicit computation) to perform conversions.  On our laboratory
IRIS, for example, the internal workings of the graphics pipeline
prefer power representation (for the purpose of setting up a differencing
evaluation) while I prefer to work in B-splines.  A library routine is
provided to do the conversion, but I have to give it the so-called
"basis matrix" ("basis conversion matrix" would be a better name).

In the case of a multi-patch surface, it is possble to extent the basis
concept (and the associated vector space terminology) to piecewise polynomials.
A basis spline (or B-spline) is a multi-segment function that can be used
(with others of its class) to produce a multi-segment surface in
the same functional format as we used for the single patch P(u,v) above.
Alternative representations are possible here, too, between one choice
of basis splines and another.

>6. Knots

Back to the surface assembly now.  The endpoints of the segment intervals,
u, u, etc., are sometimes called knots, but are more properly called
"joins" or "joints".  It is sometimes interesting to explore what happens
when a segment is "pushed out of existence" by letting u[s-1] move up to
u[s].  The result is a loss of one degree of continuity in the piecewise
function "b" (and similarly for v[t-1] and "c").  This is useful.
Cusps, corners, ridges, and other krinkly things like that can be achieved
in surfaces by judicious use of continuity loss.  So the picture you want
to have in your mind is of a picewise construction process that starts out
with u, u, etc. all distinct ("knots" == "joints" at this stage),
and then you slide a few u[]'s together here and there to chop away
some continuity at the boundary between selected segments.  The result
will be a piecewise function:

if( u=u=u <= u < u ) then ...
else if( u=u <= u < u ) then ...
etc.

The common value of u,...,u is a joint.
The "tokens" or "place holders" or "members of the knot sequence"
u, u, u are the knots that reside on the joint.

It is complicated, but it allows one to extend the definition of a spline
to include the possiblility of variable-sized segments (including zero-length),
and it makes the control of continuity a straightforward concept.

>7. Ducks

>What are ducks.

Ducks are birds that swim, waddle, and quack :-)

(I think they are also weights used to press slim, flexible rods,
called "splines", onto anchor positions on engineering drawings.  The process
of tracing along the rod to produce a smooth curve used to be done in
the warehouse loft, for large drawings, so the process became known as
"lofting", and the boat hulls, or whatever, that were produced as an
outcome became known as "lofted surfaces".  This tid bit of history
came to us courtesy of R. A. Forrest.)

>I have a fair idea about most of the above, by have a little
>difficulty with some of the ideas and
>terms used. I have read Foley & Van Dam, Newman & Sproull,
>RanKin, Rogers & Adams. Each explain
>a little but none unify the concepts.

Ah.  You have been reading the wrong book :-)

-Richard Bartels

### 3d Surface Patches

Here's a little bit of help on the subject of surfaces patches.  I will try to
stay simple which means I'll no doubt be incomplete.

1. Rational 'vs' Non-Rational

Just think back to college math classes.  A rational polynomial equation is
an equation which consists of the division of 1 polynomial by another.  This
is as opposed to an integral (non-rational) equation.  Naturally, it follows
that a rational surface is the same thing.  Principally, there are 2 ways we
can represent a b-spline in power basis (I'll get to that); they are as a
polynomial (actually as the coefficients of a polynomial) or as the coef-
ficents of 2 polynomials, one divided by the other.  The latter case allows
the equation extensive flexability in terms of the types of surface it can
represent (ie not only can we represent free form surfaces but we can also
While a non-rational b-spline (for example) is order-2 diffenentiable,
variation diminishing (such that a straight line intersects the control poly
at least as many times as it intersects the curve), and invariant under a
linear transformation; a RATIONAL b-spline also gives us added local control
and the wonderfully useful property of PROJECTIVE INVARIANCE (in other words
it is not only invariant under a parallel projective transformation it is
also invarient under a perspective transformation.

2. Power and Basis

I think you have some confusion about terms.  You use the terms "Power Matrix'
and "Basis Matrix".  Now, somebody correct me if I'm misunderstanding what you
are asking, but I think you are addressing the general concept of conversion
from Power basis to any other basis using matrix multiplication.  That being
the case I guess we should start with a definition of the term BASIS.  If you
look at the polynomial:

P^n(t) = a0 + (a1)(t) + (a2)(t^2) + ... + (an)(t^n)

and exclude the coefficients:

a0, a1, a2, ..., an

you are left with the MONOMIALS:

1, t, t^2, ..., t^n

Since the monomials are n+1 linearly INDEPENDENT functions they constitute a
basis.  Take a look at a linear algebra book or de Boor (1978) if you don't
get that.

Any way, these functions are called BASIS FUNCTIONS.  These functions are
multiplied by the control points for the curve you are trying to define to
obtain the actual spline.  When I use splines as examples all properties and
concepts apply, also, to patches; It's just too much of a pain to write it
all out in both dimensions (BTW).  To define a b-spline from m control
vertices, you will have m basis functions (not too hard to see, huh ?).  This
gets into all sorts of stuff like end point interpolation which I won't get
into, since you say you understand it.

Now, on to (my perception of) your question.  As it happens, we can render a
curve in many different ways.  One of them is to take a polynomial and
evaluate it (which in a non-trivial case requires a hell of alot of multipli-
cation).  Another is to use forward differencing (See the Shantz and Chang
papers from the last 3 siggraphs).  As an example, lets say we want to evaluate
a bezier patch using forward differencing.  We need to convert from Bezier
basis to Forward Difference basis.  That can be accomplished by matrix
multiplication.  That, I think is the answer you want.

3. What are knots

As I mentioned above, for a b-spline, you will always have 1 basis function for
each control point.  Each time a new basis function begins you are, literally,
altering the polynomial representation.  As a result a curve is really repre-
sented by a set of polynomials.  The places (in parameter space) where these
various polynomials are tied together are called KNOTS.

I hope this helps, a bit,

Steve

-------------------------------------------------------------------------------
FROM:        STEVEN C. BILOW --  Software Engineer,  Tektronix

USMAIL:      P.O. Box 1000 61-028, Wilsonville, OR  97070-1000

### 3d Surface Patches

>As it happens, we can render a curve in many different ways.  One of
>them is to take a polynomial and evaluate it (which in a non-trivial
>case requires a hell of alot of multipli- cation).  Another is to use
>forward differencing (See the Shantz and Chang papers from the last 3
>siggraphs).

I would like very much to know if there is a way to do forward
differencing of rational functions, without stepping the numerator and
denominator separately followed by division on each step.  I have a
B-spline package that displays polynomial curves quite quickly
(everything is integer shift and add), but crawls when displaying
rational curves and surfaces (twice the cost of the polynomial case
*plus* two scaled integer to floating conversions, a floating divide,
and a conversion back to integer on every point).

Is there any result from algebra that suggests how this might be done,
or that it isn't possible?  If not possible, can anyone suggest a
method of *cheaply* splitting a rational function over a definite range
into pieces that can be approximated by polynomial curves, preferably
with a specified error bound.  I can't afford a recursive subdivision,
as that's slower than what I am currently using.

### 3d Surface Patches

To help clarify anything I might have said in my previous posting which is
unclear I offer the following e-mail dialog.  This is part of a discussion
between mathematician Mike Peters and myself regarding that posting.  If I
can clarify anything else, let me know.

Also, for the record, I can't remember who it was that didn't understand how
I could forward difference a rational polynomial, but:  The point is to convert
from 1 basis to another and through some minor contortions get something that
is evaluatable by forward differencing.  If that doesn't make sense please
let me know what you don't understand and I'll try to clarify it !!!

So... Here goes...

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Subject:
Date: 19 Oct 89 10:53:09 PDT (Thu)

Steve,
I scanned your posting. A couple of points, where did the order 2
differentiability come from and algebraic surfaces do not in general
have a rational parametric representation.

-MikeP

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

From: steveb

Date: Thu, 19 Oct 89 16:46:04 PDT

Fcc: savebox
Subject: What did I mean ???

Mike:

1. I said order-2 (order minus 2) not order 2 differentiable.  Granted I did
leave out the qualification that is must have no multiple internal knots.
The reference comes from Tiller83 (IEEE CG&A pg 62 Sept 1983):

" (P2) A B-spline curve of order k, having no multiple interior
knots, is k-2 differentiable."

2. OK, I admit it, I was unclear re: algebraic surfaces having rational
polynomial representation.  Here's what I meant: (for example) a sphere
can not be represented by an non-rational B-spline surface.  But, it
can be represented either algebraically OR AS A RATIONAL B-SPLINE (NURB).
That's what I meant.  Naturally, you are right.  I was unclear :-(.....

3. Also, for the record John T. asked me why I say rationality gives you
more local control.  You can, I'm sure, argue with me on that matter too.
Primarily because I didn't explain what I meant by "more".  So, for the
record I consider the ablilty to move a curve closer to/farther from a
control point by changing W an aspect of local control.  Since you get
that with a rational curve not a non-rational one, I consider that "more
local control".  Go ahead prove me wrong, you can, and you'll be right.
Barsky will say that you can get the same functionality without
rationality using beta splines.  And, of course he's right, also. (In fact
he's extremely right).

See ya soon,

Steve

-------------------------------------------------------------------------------
FROM:        STEVEN C. BILOW --  Software Engineer,  Tektronix

USMAIL:      P.O. Box 1000 61-028, Wilsonville, OR  97070-1000

Hi

Does anyone know why the UV mapping to bicubic patches does not work
when the patch is part of a CSG union.

As an example, I have 2 patches which are designed to fit back to back
with each other.  Each patch has its own pigment { and texture { with
a gif mapping of type 8 (UV).

If I leave these 2 objects in the scene as distinct objects, then all
is fine. If I do a simple Union with them - they dissapear!

If I remove the type 8 mappings, i can get plain coloured patches but
thats not what I want as then I can't (A) create more objects which
look the same, and (B) translate and rotate them easily.

Its (B) thats the main point!

Any ideas?

G.
--
QI'HoS  (Kirosh)  KLI #H1026
http://www.mickley.demon.co.uk