Scan line display of algebraic surfaces

ABSTRACT

A robust algorithm is presented for scan line display of algebraic surfaces of arbitrary degree and topology. The algorithm correctly displays singularities of any complexity, even those missed by ray tracing or polygonization, and (for surfaces of degree less than eight) offers a significant speed improvement over ray tracing. Antialiasing can generally be accomplished very quickly. In addition to its typical function of shaded raster display, the algorithm is particularly adept at quickly plotting silhouette and intersection curves. A practical use for the algorithm is to display boolean combinations of algebraic half spaces, including blend surfaces.A new polynomial basis is introduced, referred to as the Bernstein pyramid polynomial basis, which enhances numerical stability and which simplifies several computations such as scan planesurface intersection and silhouette detection.

REFERENCES

• 1: Dennis S. Arnon, Topologically reliable display of algebraic curves, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.219-227, July 1983
• 2: Arnon, D.S. and Rauen, J., On the display of cell decompositions of algebraic surfaces, XEROX Technical Report, 1988.
• 3: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 4: Bradshaw, C.B., Surfaces of functions of three variables, M.S. Thesis, Department of Civil Engineering, Brigham Young University, 1982.
• 5: R T Farouki, The characterization of parametric surface sections, Computer Vision, Graphics, and Image Processing, v.33 n.2, p.209-236, Feb. 1986 [doi>10.1016/0734-189X(86)90115-5]
• 6: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 7: R. T. Farouki , V. T. Rajan, Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design, v.5 n.1, p.1-26, June 1988 [doi>10.1016/0167-8396(88)90016-7]
• 8: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 9: Goldman, R.N., Sederberg, T.W. and Anderson, D.C., Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves, Computer Aided Geometric Design, 1, 1984, 327-356.
• 10: Hall, M. and Warren, J., Adaptive tessellation of implicitly defined surfaces, Rice COMP TR88-84, 1988, Rice University.
• 11: Pat Hanrahan, Ray tracing algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.83-90, July 1983
• 12: Hoffmann, C.M. and Hopcroft, I.E., Automatic surface generation in computer aided design, The Visual Con~outer, 1, 1985, 95-100.
• 13: Lane, J.M. and Riesenfeld, R.F., Bounds on a polynomial, B/T, 21, 1, 1981, 112-117.
• 14: Mahl, R., Visible surface algorithms for quadric patches, IEEE Transactions on Computers, C.21, 1, 1972, 1-4.
• 15: Alan E. Middleditch , Kenneth H. Sears, Blend surfaces for set theoretic volume modelling systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.161-170, Jul. 1985
• 16: Owen, J.C. and Rockwood, A.P., Intersection of general implicit surfaces. In Geometric Modeling: Algorithms and New Trends, G. Farin, editor, SIAM, Philadelphia, 1987, 335-346.
• 17: Patrikalakis, N.M. and Kriezis, G.A., Piecewise continuous algebraic surfaces in terms of B-splines, MITSG 88-5, Massachusetts Institute of Technology, August 1988.
• 18: Petersen, C.S., Adaptive contouring of three-dimensional surfaces, Computer Aided Geometric Design, 1, 1984, 61-74.
• 19: Rockwood, A.P. and Owen, J.C., Blending surfaces in solid modeling. In Geometrk: Modeling: Algorithms and New Trends, G. Farin, editor, SIAM, Philadelphia, 1987, 335-346.
• 20: Salmon, G. Analytic Geometry of Three Dimensions, Longmarts, Green and Co., 1912.
• 21: Sederberg, T.W., Piecewise algebraic surface patches, Computer Aided Geometric Design, 2, 1985, 53-59.
• 22: Thomas W Sederberg , Scott R Parry, Comparison of three curve intersection algorithms, Computer-Aided Design, v.18 n.1, p.58-64, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80013-6]
• 23: T. W. Sederberg, Algorithm for algebraic curve intersection, Computer-Aided Design, v.21 n.9, p.547-554, Nov. 1989 [doi>10.1016/0010-4485(89)90015-8]
• 24: Sederberg, T.W., Spencer, M.R. and de Boor, C., Real root approximation of polynomials in Bernstein form, in preparation.
• 25: G. L. Tindle, Tetrahedral triangulation, Proceedings on Mathematics of surfaces II, p.387-394, October 1987, Cardiff, United Kingdom
• 26: Joe David Warren, On algebraic surfaces meeting with geometric continuity, Cornell University, Ithaca, NY, 1986
• 27: Ruth A. Weiss, BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces, Journal of the ACM (JACM), v.13 n.2, p.194-204, April 1966 [doi>10.1145/321328.321330]
• 28: Zundel, A.K., Scan line rendering of algebraic surfaces and half spaces, M.S. Thesis, Department of Civil Engineering, Brigham Young University, 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms