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[0]<=u) && (u<u[1]) ) then {definition-1 of b[i](u)}

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

else if( (u[2]<=u) && (u<u[3]) ) 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.

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[0]*B[0](u) + cf[1]*B[1](u) + cf[2]*B[2](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[0](u) = 1, B[1](u) = u, B[2](u) = u*u

cf[0] = A, cf[1] = B, cf[2] = C.

Bezier: B[0](u) = (1-u)*(1-u), B[1](u) = 2*u*(1-u), B[2](u) = u*u

cf[0] = A, cf[1] = A+B/2, cf[2] = 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

ugly heads somewhere or other.

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.

Back to the surface assembly now. The endpoints of the segment intervals,

u[0], u[1], 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[0], u[1], 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[0]=u[1]=u[2] <= u < u[3] ) then ...

else if( u[3]=u[4] <= u < u[5] ) then ...

etc.

The common value of u[0],...,u[2] is a joint.

The "tokens" or "place holders" or "members of the knot sequence"

u[0], u[1], u[2] 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