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
by