Hermite interpolation of rational space curves using real algebraic surfaces

ABSTRACT

We present a simple characterization of the lowest degree, implicitly defined, real algebraic surfaces, which smoothly contain any given number of points and algebraic space curves, of arbitrary degree. The characterization is constructive, yielding efficient algorithms for generating families of such algebraic surfaces. Smooth containment of space curves yields C1-continuous surface fitting, and is a generalization of standard Hermite interpolation applied to fitting curves through point data, equating derivatives at those points. We deal with the containment and matching of “normals” (vectors orthogonal to tangents), possibly varying along the entire span of the space curves. Such Hermite interpolated surfaces prove useful as “blending” or “joining” surfaces for solid models as well as “fleshing” surfaces for curved wireframe models.

REFERENCES

• 1: 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
• 2: 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]
• 3: Anthony David Derose, Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design (curves, surfaces, splines), 1985
• 4: P O Fjällström, Smoothing of polyhedral models, Proceedings of the second annual symposium on Computational geometry, p.226-235, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10540]
• 5: 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]
• 6: Hoffmann, C., and Hopcroft, J., (1987), "The Potential Method for Blending Surfaces and Corners", Geometric Modeling: Algorithms and New Trends, ed. G. Farin, SIAM, 347-366.
• 7: Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
• 8: 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
• 9: Owen, J., and Rockwood, A., (1987), "Blending Surfaces in Solid Geometric Modeling ", Geometn'c Modeling: Algorithms and New Trends, ed. G. Farin, SIAM, 347-366.
• 10: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.145-152, August 1987
• 11: Rossignac, J., and Requicha, A., (1984), "Constant-Radius Blending in Solid Modeling", Computers in MAthematical Engineering, 2, 655- 673.
• 12: Ramon F. Sarraga, G1 interpolation of generally unrestricted cubic Be´zier curves, Computer Aided Geometric Design, v.4 n.1-2, p.23-39, July 1987 [doi>10.1016/0167-8396(87)90022-7]
• 13: Sederberg, T., (1985), "Piecewise Algebraic Surface Patches", Computer Aided Geometric Design, 2, 53-59.
• 14: Joe David Warren, On algebraic surfaces meeting with geometric continuity, Cornell University, Ithaca, NY, 1986
• 15: J. Warren, Blending quadric surfaces with quadric and cubic surfaces, Proceedings of the third annual symposium on Computational geometry, p.341-347, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41995]
• 16: 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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory