Algebraic surface design with Hermite interpolation

ABSTRACT

This paper presents an efficient algorithm called Hermite interpolation, for constructing low-degree algebraic surfaces, which contain, with C1 or tangent plane continuity, any given collection of points and algebraic space curves having derivative information. Positional as well as derivative constraints on an implicitly defined algebraic surface are translated into a homogeneous linear system, where the unknowns are the coefficients of the polynomial defining the algebraic surface. Computaional details of the Hermite interpolation algorithm are presented along with several illustrative applications of the interpolation technique to construction of joining or blending surfaces for solid models as well as fleshing surfaces for curved wire frame models. A heuristic approach to interactive shape control of implicit algebraic surfaces is also given, and open problems in algebraic surface design are discussed.

REFERENCES

• 1: ABHYANKAR, S. S. Algebraic space curves. Univ. of Montreal, 1970. Montreal Lecture Notes.
• 2: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 3: 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]
• 4: BAJAJ, C., IHM, I., AND WARREN, J. Higher order interpolation and }east squares approximation using implicit algebraic surfaces. Tech. Rep. 91-035, Dept. of Computer Science, Purdue University, Apr. 1991.
• 5: Chanderjit Bajaj , Myung Soo Kim, Generation of configuration space obstacles: moving algebraic surfaces, International Journal of Robotics Research, v.9 n.1, p.92-112, February 1990 [doi>10.1177/027836499000900104]
• 6: BARNHII,I., R. Surfaces in computer aided geometric design: A survey with new results. Comput. Aided Geom. Des. 2 (1985), 1-17.
• 7: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 8: Wolfgang Dahmen, Smooth piecewise quadric surfaces, Mathematical methods in computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1989
• 9: DEBooR, C. A Practical Guide to Splines. Springer-Verlag, New York, 1978.
• 10: Anthony David Derose, Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design (curves, surfaces, splines), 1985
• 11: G Farin, Triangular Berstein-Be´zier patches, Computer Aided Geometric Design, v.3 n.2, p.83-127, August 1986 [doi>10.1016/0167-8396(86)90016-6]
• 12: 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]
• 13: GOLDMAN, R.N. The role of surfaces in solid modeling. In Geometric Modeling.' Algorithm.~ and New Trends, G. Farin, Ed., SIAM, Philadelphia, 1987, pp. 69-90.
• 14: GoLtm, G. E., AND VAN LOAN, C.F. Matrix Computation. The Johns Hopkins Univ. Press, Baltimore, MD, 1983.
• 15: Christoph Hoffmann , John Hopcrott, Quadratic blending surfaces, Computer-Aided Design, v.18 n.6, p.301-306, July/Aug. 1986 [doi>10.1016/0010-4485(86)90091-6]
• 16: 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
• 17: OWEN, J. C., aNI) Roc~wool), A. P. Blending surfaces in solid modeling. In Geometri( Modeling: Algorithms and New Trends, G. Farin, Ed., SIAM, Philadelphia, 1987, pp 367-383.
• 18: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.145-152, July 1987
• 19: SEDFRBERC,, T. W. Piecewise algebraic surface patches. Comput. Aided Geom. Des. 2, 1-~q (1985), 53-59.
• 20: 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]
• 21: 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]
• 22: SEMPI,E, J., AN{) R{)TH, L. Introduction to Algebraic Geometry. Oxford University Press Oxford, U.K., 1949.
• 23: WALKUR, R. Algebraic Curves. Springer Verlag, New York, 1978.
• 24: Joe David Warren, On algebraic surfaces meeting with geometric continuity, Cornell University, Ithaca, NY, 1986
• 25: J. Warren, Blending algebraic surfaces, ACM Transactions on Graphics (TOG), v.8 n.4, p.263-278, Oct. 1989 [doi>10.1145/77269.77270]

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

General Terms:
Algorithms, Design, Theory

Keywords:
Algebraic surface, Hermite interpolation, computer-aided geometric design, geometric continuity, linear systems