Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!watmath!watcgl!rhbartels From: rhbartels@watcgl.waterloo.edu (Richard Bartels) Newsgroups: comp.graphics Subject: Re: 3d Surface Patches Summary: (Long) Keywords: patches, 3d Message-ID: <11890@watcgl.waterloo.edu> Date: 13 Oct 89 15:13:50 GMT References: <415@attila.esa.oz> Reply-To: rhbartels@watcgl.waterloo.edu (Richard Bartels) Organization: U. of Waterloo, Ontario Lines: 195 In article <415@attila.esa.oz> shaun@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 >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[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. > >6. Knots > 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