On the algebraic and geometric foundations of computer graphics

ABSTRACT

Today's computer graphics is ostensibly based upon insights from projective geometry and computations on homogeneous coordinates. Paradoxically, however, projective spaces and homogeneous coordinates are incompatible with much of the algebra and a good deal of the geometry currently in actual use in computer graphics. To bridge this gulf between theory and practice, Grassmann spaces are proposed here as an alternative to projective spaces. We establish that unlike projective spaces, Grassmann spaces do support all the algebra and geometry needed for contemporary computer graphics. We then go on to explain how to exploit this algebra and geometry for a variety of applications, both old and new, including the graphics pipeline, shading algorithms, texture maps, and overcrown surfaces.

REFERENCES

• 1: James F. Blinn, A homogeneous formulation for lines in 3 space, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.237-241, July 20-22, 1977, San Jose, California
• 2: Jim Blinn, Jim Blinn's corner: a trip down the graphics pipeline, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: James F. Blinn , Martin E. Newell, Clipping using homogeneous coordinates, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.245-251, August 23-25, 1978
• 4: COX, D., LITTLE,J.,AND O'SHEA, D. 1998. Using Algebraic Geometry. Springer-Verlag, New York.
• 5: T. D. DeRose, A coordinate-free approach to geometric programming, Theory and practice of geometric modeling, Springer-Verlag New York, Inc., New York, NY, 1989
• 6: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 7: J.-C. Fiorot , P. Jeannin , M. C. Harrison, Rational curves and surfaces: applications to CAD, John Wiley & Sons, Inc., New York, NY, 1992
• 8: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: Ronald N. Goldman, Illicit expressions in vector algebra, ACM Transactions on Graphics (TOG), v.4 n.3, p.223-243, July 1985 [doi>10.1145/282957.282969]
• 10: GOLDMAN, R. N. 1991. More matrices and transformations: Shear and pseudoperspective. In Graphics Gems II, Jim Arvo, Ed. Academic Press, Orlando, Fla., pp. 338-341.
• 11: Ron Goldman, The Ambient Spaces of Computer Graphics and Geometric Modeling, IEEE Computer Graphics and Applications, v.20 n.2, p.76-84, March 2000 [doi>10.1109/38.824547]
• 12: Ron Goldman, Baseball Arithmetic and the Laws of Pseudoperspective, IEEE Computer Graphics and Applications, v.21 n.2, p.70-78, March 2001 [doi>10.1109/38.909017]
• 13: GOLDMAN, R. N. 2002. Applications of the mass distributions and vector spaces associated with rational Bezier curves and surfaces. In preparation.
• 14: GRASSMANN, H. G. 1894-1911. Gesammelte Mathematische und Physikalische Werke. B. G. Teubner, Leipzig.
• 15: HECKBERT,P.AND MORETON, H. 1991. Interpolation for Polygon Texture Mapping and Shading. In State of the Art in Computer Graphics: Visualization and Modeling, D. Rogers and R. Earnshaw, Ed. Springer-Verlag, New York.
• 16: KOGAN, B. Y. 1974. The Application of Mechanics to Geometry. The University of Chicago Press, Chicago, Ill.
• 17: Richard M. Murray , S. Shankar Sastry , Li Zexiang, A Mathematical Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994
• 18: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 19: Michael A. Penna , Richarad R. Patterson, Projective geometry and its applications to computer graphics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 20: RAMSHAW, L. 2001. On Multiplying Points: The Paired Algebras of Forms and Sites. SRC Research Report #169, COMPAQ Corporation, Palo Alto, Calif.
• 21: RIESENFELD, R. 1981. Homogeneous coordinates and the projective plane in computer graphics. IEEE CG&A 1, 50-55.
• 22: ROBERTS, L. G. 1965. Homogeneous matrix representation and manipulation of N-dimensional constructs. The Computer Display Review, C. W. Adams Associates, Inc., Cambridge, Mass., pp. 1-16.
• 23: SWIMMER, A. 2002. Ceva, Menelaus and the associative law. Unpublished manuscript.
• 24: USPENSKII, V. A. 1961. Some applications of mechanics to mathematics. Blaisdell Publishing Company, New York.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

General Terms:
Algorithms, Theory

Keywords:
Grassmann space, homogeneous coordinates, mass-points, projective space