Higher-order interpolation and least-squares approximation using implicit algebraic surfaces

ABSTRACT

In this article, we characterize the solution space of low-degree, implicitly defined, algebraic surfaces which interpolate and/or least-squares approximate a collection of scattered point and curve data in three-dimensional space. The problem of higher-order interpolation and least-squares approximation with algebraic surfaces under a proper normalization reduces to a quadratic minimization problem with elegant and easily expressible solutions. We have implemented our algebraic surface-fitting algorithms, and included them in the distributed and collaborative geometric environment SHASTRA. Several examples are given to illustrate how our algorithms are applied to algebraic surface design.

REFERENCES

• 1: ALRANO A. 1974. Representation of digitized contours in terms of conic arcs and straight line segments. Comput. Graph. Image Process. 3, 23-33.
• 2: Vinod Anupam , Chandrajit L. Bajaj, Collaborative multimedia scientific design in SHASTRA, Proceedings of the first ACM international conference on Multimedia, p.447-456, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.168458]
• 3: BAJAJ, C. 1993. The emergence of algebraic curves and surfaces in geometric design. In Directions in Geometric Computing. Information Geometers Press, United Kingdom, 1-27.
• 4: Chandrajit L. Bajaj, Surface fitting using implicit algebraic surface patches, Topics in surface modeling, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 5: Chandrajit L. Bajaj, Geometric Modeling with Algebraic Surfaces, Proceedings of the 3rd IMA Conference on the Mathematics of Surfaces, p.3-48, September 19-21, 1988
• 6: Chanderjit L. Bajaj , Insung Ihm, Algebraic surface design with Hermite interpolation, ACM Transactions on Graphics (TOG), v.11 n.1, p.61-91, Jan. 1992 [doi>10.1145/102377.120081]
• 7: Chandrajit L. Bajaj , Insung Ihm, Smoothing polyhedra using implicit algebraic splines, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.79-88, July 1992
• 8: BAJAJ, C., ANO XU, G. 1992. A Splines: Local interpolation and approximation using Ckcontinuous piecewise real algebraic curves. Computer Science Tech. Rep. CAPO-92-95, Purdue Univ., West Lafayette, Ind.
• 9: C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
• 10: 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]
• 11: BOOKST~nN, F. 1979. Fitting conic sections to scattered data. Comput. Graph. Image Process. 9, 56-71.
• 12: Anthony David Derose, Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design (curves, surfaces, splines), 1985
• 13: R T Farouki, The approximation of non-degenerate offset surfaces, Computer Aided Geometric Design, v.3 n.1, p.15-43, May 1986 [doi>10.1016/0167-8396(86)90022-1]
• 14: Joe Warren , Thomas Garrity, Geometric continuity, Computer Aided Geometric Design, v.8 n.1, p.51-65, Feb. 1991 [doi>10.1016/0167-8396(91)90049-H]
• 15: GNANAD~;SIKAN, R. 1977. Methods for Statistical Data Analysis of Multivariate Observations. John Wiley & Sons, New York.
• 16: GOLUB, G. 1973. Some modified matrix eigenvalue problems. SIAM Rev. 15, 2,318-334.
• 17: GOLUB, G., ANI) USDERWOOI), R. 1970. Stationary values of the ratio of quadratic forms subject to linear constraints. Z. Agnew. Math. Phys. 21,318-326.
• 18: Gokthq, G., AND VAN LOAN, C. 1983. Matrix Computation. The Johns Hopkins University Press, Baltimore, Md.
• 19: HOFFMANN, C., AND HOPCROFT, J. 1987. The potential method for blending surfaces and corners. In Geometric Modeling: Algorithms and New Trends. SIAM, Philadelphia, Pa., 347 -366.
• 20: Insung Ihm, On surface design with implicit algebraic surfaces, Purdue University, West Lafayette, IN, 1992
• 21: KUNZ, E. 1985. Introduction to Commutative Algebra and Algebraic Geometry. Birkhauser, New York.
• 22: MACAUI,~Y, F. 1916. The Algebraic Theory of Modular Systems. Cambridge University Press, London, U.K.
• 23: MoortE, D., AND WARREN, J. 1991. Approximation of dense scattered data using algebraic surfaces. In Proceedings of the 24th Hawaii International Conference on System Sciences (Kauai, Hawaii). IEEE Computer Society Press, Washington, D.C., 681-690.
• 24: OWEN, J., ^ND ROCKWOOl), A. 1987. Blending surfaces in solid modeling. In Geometric Modeling: Algorithms and New Trends. SIAM, Philadelphia, Pa., 367-383.
• 25: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.145-152, July 1987
• 26: SAM}mow, P. 1982. Fitting conic sections to very scattered data: An iterative refinement of the bookstein algorithm. Comput. Graph. Image Process. 18, 97-108.
• 27: Thomas A. Sederberg, Surfaces: Techniques for Cubic Algebraic Surfaces, IEEE Computer Graphics and Applications, v.10 n.4, p.14-25, July 1990 [doi>10.1109/38.56295]
• 28: Thomas W. Sederberg, Techniques for Cubic Algebraic Surfaces, IEEE Computer Graphics and Applications, v.10 n.5, p.12-21, September 1990 [doi>10.1109/38.59032]
• 29: SEI)EI~BI~;RG, T. 1985. Piecewise algebraic surface patches. Comput. Aided Geom. Des. 2, 1-3, 53-59.
• 30: STRANC, G. Linear Algebra and Its Applications. 3rd ed. Harcourt Brace Jovanovich, San Diego, Calif.
• 31: J. Warren, Blending algebraic surfaces, ACM Transactions on Graphics (TOG), v.8 n.4, p.263-278, Oct. 1989 [doi>10.1145/77269.77270]
• 32: Joe David Warren, On algebraic surfaces meeting with geometric continuity, Cornell University, Ithaca, NY, 1986
• 33: J. R. Woodwark, Blends in geometric modelling, Proceedings on Mathematics of surfaces II, p.255-297, October 1987, Cardiff, United Kingdom

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas
      G.1.2 Approximation
          Subjects: Least squares approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

  J. Computer Applications

General Terms:
Algorithms

Keywords:
algebraic surface, computer-aided geometric design, constrained quadratic optimization, distributed geometric-design environment, geometric continuity