shaun@attila.esa.oz (Shaun) (10/12/89)
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.
Shaun Arundell: shaun@attila.esa.oz.AU (shaun%attila.esa.oz.AU@UUNET.UU.NET)
{uunet,mcvax,ukc,nttlab}!munnari!attila.esa.oz!shaun
--
Shaun Arundell: shaun@attila.esa.oz.AU (shaun%attila.esa.oz.AU@UUNET.UU.NET)
{uunet,mcvax,ukc,nttlab}!munnari!attila.esa.oz!shaunrhbartels@watcgl.waterloo.edu (Richard Bartels) (10/13/89)
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<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. > >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
steveb@eve.WV.TEK.COM (10/19/89)
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 represent algebraic surfaces). In addition we get some nice added properties. 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 EMAIL: steveb@orca.WV.TEK.COM PHONE: (503) 685-2463 USMAIL: P.O. Box 1000 61-028, Wilsonville, OR 97070-1000
steveb@eve.WV.TEK.COM (10/20/89)
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... ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ To: steveb@eve.WV Cc: mikep@tekirl.labs.TEK.COM Subject: Date: 19 Oct 89 10:53:09 PDT (Thu) From: mikep@tekirl.labs.TEK.COM 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 Message-Id: <8910192346.AA12791@eve.WV.TEK.COM> Date: Thu, 19 Oct 89 16:46:04 PDT To: mikep@tekirl.labs.TEK.COM Cc: steveb@eve.WV, mikep@tekirl.labs.TEK.COM, jt 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 EMAIL: steveb@orca.WV.TEK.COM PHONE: (503) 685-2463 USMAIL: P.O. Box 1000 61-028, Wilsonville, OR 97070-1000