pcb@cacs.usl.edu (Peter C. Bahrs) (10/04/90)
Suppose I am modeling cones and cylinders algebraically and parametrically. How can I draw these? I do not want to do ray tracing. Is there a common technique(s) that will rendering these things without having to make a zillion polygons? A lot of algorithms require verticies and edges which are transformed and projected to 2d and then drawn. Well I have no real edges... Any ideas? or references? /*----------- Thanks in advance... --------------------------------------+ | Peter C. Bahrs | | The USL-NASA Project | | Center For Advanced Computer Studies INET: pcb@swamp.cacs.usl.edu | | 2 Rex Street | | University of Southwestern Louisiana ...!uunet!dalsqnt!gator!pcb | | Lafayette, LA 70504 | +-----------------------------------------------------------------------*/
leech@homer.cs.unc.edu (Jonathan Leech) (10/04/90)
In article <15822@rouge.usl.edu> pcb@cacs.usl.edu (Peter C. Bahrs) writes: >Suppose I am modeling cones and cylinders algebraically and parametrically. >How can I draw these? I do not want to do ray tracing. Is there a common >technique(s) that will rendering these things without having to make a >zillion polygons? See Jim Blinn's wonderful short paper, ``The Algebraic Properties of Homogeneous Second Order Surfaces.'' This describes direct rendering of arbitrary quadrics (synopsis: represent the surface as a homogeneous matrix; similarity transform the matrix for modelling, viewing, and perspective; find screenspace boundaries of the quadric; solve the resulting equation for Z-depth and normal vector at each pixel). I believe this appeared in SIGGRAPH course notes in '84 or '85; my copy is a draft so I'm not sure which course. -- Jon Leech (leech@cs.unc.edu) __@/ "We've already learned something we didn't know and that's fun!" - Dr. James Westphal on the first Hubble photo
ph@miro.Berkeley.EDU (Paul Heckbert) (10/14/90)
In article <15822@rouge.usl.edu> pcb@cacs.usl.edu (Peter C. Bahrs) writes: >Suppose I am modeling cones and cylinders algebraically and parametrically. >How can I draw these? I do not want to do ray tracing. Is there a common >technique(s) that will rendering these things without having to make a >zillion polygons? You can do it using scan conversion, at each pixel solving a quadratic equation. It turns out that the perspective transformation of a quadric surface (such as ellipsoids, hyperboloids, cones, cylinders, etc) is a quadric surface. For instance, a sphere in world space transforms to an ellipsoid in screen space when the camera transformation is perspective and the sphere is entirely in front of or behind the viewer. (If the sphere intersects the w=0 plane, it transforms into a hyperboloid of two sheets). Now you have a second degree surface in screen space, so you can plug in screen x and screen y and get a quadratic equation for screen z at each pixel. That was the method used for quadric surface rendering by Tom Duff et al at NYIT and by Jim Blinn at JPL. Much of the relevant algebra was discussed in this news group a couple years back. Here are some excerpts: ----------------------------------------------------- From: scm@onion.cs.reading.ac.uk (Stephen Marsh) Newsgroups: comp.graphics Subject: Can You Transform Quadric Surfaces With 4x4 Matrices? Date: 26 Jan 87 11:48:28 GMT Organization: Comp. Sci. Dept., Reading Univ. UK. Can anyone help me with this problem? I am trying to represent some solid objects by using quadric surfaces which seem to be a favourite amongst geometric modellers and to then move them around in a world model. If I have a surface defined by Q(x,y,z) = ax^2 + by^2 + cz^2 + dxy + eyz + fxz + gx + hy + iz + k (ie sphere, cone etc) does anyone know if there is a straight-forward way of transforming this surface in my world model using the usual 4x4 scale, rotate and translate matrices? I know that you can scale a sphere by altering k and translate it by adding values to a,b or c, but this doesn't seem to be a very logical approach. Will I have to re-express these quadric solids as a lot of polygons, surface patches etc etc? If you know of some mathematical way of re-expressing the above equation so that the usual transformations can be applied, I would be pleased to hear from you. Name: Steve Marsh E-mail: scm@onion.cs.reading.ac.uk Establishment: University of Reading, UK. Research: Systems Architecture Group. Department: Department of Computer Science Phone me at: (0734) 875123 ext 7881 from inside UK ----------------------------------------------------- From: ph@pixar.UUCP (Paul Heckbert) Newsgroups: comp.graphics,sci.math Subject: Re: Can You Transform Quadric Surfaces With 4x4 Matrices? Date: 30 Jan 87 22:38:09 GMT Organization: Pixar -- Marin County, California Summary: yes Represent the point (x,y,z) by the homogeneous row vector P = [x, y, z, 1] and plane (or normal vector) ax+by+cz+d=0 by column vector N = [a, b, c, d]^t, where M^t means transpose of matrix M. The equation P*N=0 (where '*' denotes matrix multiplication) determines all the planes N passing through point P, or all the points P which lie on plane N. Note the duality of points and planes. Represent the quadric surface axx+bxy+cxz+dx+eyy+fyz+gy+hzz+iz+j=0 by the matrix [ a b/2 c/2 d/2 ] Q = [ b/2 e f/2 g/2 ] [ c/2 f/2 h i/2 ] [ d/2 g/2 i/2 j ] Points on the quadric surface satisfy P*Q*P^t=0 (substitute P and Q above to check) and planes tangent to the surface satisfy N^t*Q^-1*N=0, where M^-1 means matrix inverse or adjoint. Note the duality once again. If T is a 4x4 transformation matrix (perspective, rotation, scaling, translation, etc) then to transform point P by T: P' = P*T and to transform plane N by T: N' = T^-1*N, where M*N is matrix multiplication (see footnote). To transform a quadric: Q' = T^-1*Q*T^-1^t. You can substitute the expressions above into P'*Q'*P'^t=0 to check that it works. A non-intuitive consequence of this is that any perspective transformation of a quadric is a quadric! A perspective transformation of a sphere, for example, can be a hyperboloid of two sheets. The normal vector or tangent plane can be found by taking the gradient of the quadratic form: N = grad(P*Q*P^t)/2 = Q*P^t for a point P on the surface. If P is not on the surface, this plane N is still geometrically meaningful; it is called the "polar plane" of P, and dually, the "pole" of the plane N is P = N^t*Q^-1. References: E. A. Maxwell, General Homogeneous Coordinates in Space of Three Dimensions, Cambridge U. Press, London, 1951. Paul Heckbert, The Mathematics of Quadric Surface Rendering and SOID, New York Inst. of Tech. Computer Graphics Lab TM4, July 1984. Jim Blinn, The Algebraic Properties of Homogeneous Second Order Surfaces, The Mathematics of Computer Graphics seminar notes, ACM SIGGRAPH '84, July 1984. footnote: This formula for transforming planes makes perfect sense if you remember the correspondence between plane equations in the two coordinate systems: P'*N'=0 <==> P*N=0 : P'*N' = (P*T)*(T^-1*N) = P*(T*T^-1)*N = P*N Interesting note: some computer graphicists mistakenly transform normals (planes) using N' = T^t*N, but this is correct only for rotations. ----------------------------------------------------- From: stolfi@jumbo.dec.com (Jorge Stolfi) Newsgroups: comp.graphics Subject: Re: Can You Transform Quadric Surfaces With 4x4 Matrices? Date: 29 Jan 87 20:30:37 GMT Organization: DEC Systems Research Center Summary: Sure: Q --> M~ Q M~' Stephen Marsh asked: > If I have a surface defined by > > Q(x,y,z) = ax^2 + by^2 + cz^2 + dxy + eyz + fxz + gx + hy + iz + k > > (ie sphere, cone etc) does anyone know if there is a > straightforward way of transforming this surface using the > usual 4x4 scale, rotate and translate matrices? Let the coordinates of a point p be written as a 4-element row vector [x y z 1] (or [X Y Z W] in homogeneous coordinates, where x=X/W, y=Y/W, z=Z/W). A projective transformation (one that preserves straight lines) of R^3 is determined by a 4x4 matrix M, such that the image of a point p is simply the product p M of the 4-vector p by the matrix M. Linear, Euclidean, and affine transformations or R^3 (rotations, translations, scalings, reflections, etc.) are all special cases of projective maps. For example, a translation by (dx, dy, dz) is given by the matrix 1 0 0 0 0 1 0 0 0 0 1 0 dx dy dz 1 A quadratic surface can be represented by a symmetric 4x4 matrix Q, such that a point p lies on the surface if and only if the matrix product p Q p' = 0, where p' is the transpose of p, i.e. the 4-element COLUMN vector <x y z 1>. Specifically, the quadratic surface with equation ax^2 + by^2 + cz^2 + dxy + eyz + fxz + gx + hy + iz + k = 0 is given by the matrix a d/2 f/2 g/2 d/2 b e/2 h/2 f/2 e/2 c i/2 g/2 h/2 i/2 k So, how do we map a quadratic surface Q by a map M? We want a surface K such that p is on Q if and only if (p M) is on K; that is, we want a matrix K such that p Q p' = 0 iff (p M) K (p M)' = 0 Since (p M)' = M' p', we conclude that K = M~ Q M~' will do the trick, where M~ is the inverse of M, and M~' its transpose. j.