Interpolation with interval and point tension controls using cubic weighted v-splines

ABSTRACT

Various methods have been developed to control the shape of an interpolating curve for computer-aided design applications. Some methods are better suited for controlling the tension of the curve on an interval, while others are better suited for controlling the tension at the individual interpolation points. The weighted v-spline is a C1 piecewise cubic polynomial interpolant that generalizes C2 cubic splines, weighted splines, and v-splines. Shape controls are available to “tighten” the weighted v-spline on intervals and/or at the interpolation points. The mathematical theory is presented together with short algorithms for parametric interpolation.

REFERENCES

• 1: AHLBERG, J. H., NILSON, E. N., AND WALSH, J.L. The Theory of Splines and Their Applications. Academic Press, New York, 1967.
• 2: BARSK, B.A. Exponential and polynomial methods for applying tension to an interpolating spline curve, Comput. Vision Graph. Image Process. 27, 1 (July 1984), 1-18.
• 3: Brian A. Barsky , John C. Beatty, Local Control of Bias and Tension in Beta-splines, ACM Transactions on Graphics (TOG), v.2 n.2, p.109-134, April 1983 [doi>10.1145/357318.357321]
• 4: BARSKY, B. A., AND THOMAS, S.W. TRANSPLINE--A system for representing curves using tranformations among four spline formulations. Comput. J. 24, 3 (Aug. 1981), 271-277.
• 5: CARMICHAEL, R. L. A collection of procedures for defining airplane surfaces for input to PANAIR. In Computer-Aided Geometry Modeling, J. N. Shoosrnith and R. E. Fulton, Eds. NASA Conference Publication 2272, Washington, D.C., 1982, pp. 327-346.
• 6: Samuel Daniel Conte , Carl W. De Boor, Elementary Numerical Analysis: An Algorithmic Approach, McGraw-Hill Higher Education, 1980
• 7: DE BOOR, C. A Practical Guide to Splines. Springer-Verlag, New York, 1978.
• 8: T D DeRose , B A Barsky, An intuitive approach to geometric continuity for parametric curves and surfaces, Proceedings of Graphics Interface '85 on Computer-generated images: the state of the art, p.159-175, January 1986, Montreal, Quebec, Canada
• 9: EPSTEIN, M. P. On the influence of parameterization in parametric interpolation. SIAM J. Numer. Anal. 13, 2 (Apr. 1976), 261-268.
• 10: Gerald Farin, Some remarks on V2-splines, Computer Aided Geometric Design, v.2 n.4, p.325-328, Dec. 1985 [doi>10.1016/S0167-8396(85)80007-8]
• 11: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 12: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 13: Thomas A. Foley, Local control of interval tension using weighted splines, Computer Aided Geometric Design, v.3 n.4, p.281-294, 1987 [doi>10.1016/0167-8396(86)90004-X]
• 14: FRITSCH, F. N., AND CARLSON, R.E. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17, 2 (Apr. 1980), 238-246.
• 15: GORDON, W.J. Spline-blended surface interpolation through curve networks. J. Math. Mech. 18, 10 (Apr. 1969), 931-952.
• 16: GORDON, W. J., AND RIESENFELD, R.F. B-spline curves and surfaces, in Computer Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, Eds. Academic Press, New York, 1974, pp. 95-126.
• 17: B. K. P. Horn, The Curve of Least Energy, ACM Transactions on Mathematical Software (TOMS), v.9 n.4, p.441-460, Dec. 1983 [doi>10.1145/356056.356061]
• 18: Doris H. U. Kochanek , Richard H. Bartels, Interpolating splines with local tension, continuity, and bias control, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.33-41, July 1984
• 19: MARIN, S.P. An approach to data parameterization in parametric cubic spline interpolation problems. J. Approx. Theory 41, 3 (May 1984), 64-86.
• 20: NIELSON, G.M. Some piecewise polynomial alternatives to splines under tension. In Computer Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, Eds. Academic Press, New York, 1974, pp. 209-235.
• 21: NIELSON, G.M. Computation of v-splines. Tech. Rep. NR 044-433-11, Mathematics Dept., Arizona State Univ., Tempe, 1974.
• 22: NIELSON, G.M. Rectangular v-splines. IEEE Comput. Graph. 6, 2 (Feb. 1986), 35-40.
• 23: SALKAUSKAS, K. C1 splines for interpolation of rapidly varying data. Rocky Mr. J. Math. 14, 1 (Winter 1984), 239-250.
• 24: SCHUMAKER, L.L. Spline Functions: Basic Theory. Wiley, New York, 1981.
• 25: SCHWEIKERT, D. G. An interpolation curve using a spline in tension. J. Math. Phys. 45, 3 (Sept. 1966), 312-317.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation
      G.1.6 Optimization
          Subjects: Constrained optimization

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

General Terms:
Algorithms, Theory