Curve-fitting with piecewise parametric cubics

ABSTRACT

Parametric piecewise-cubic functions are used throughout the computer graphics industry to represent curved shapes. For many applications, it would be useful to be able to reliably derive this representation from a closely spaced set of points that approximate the desired curve, such as the input from a digitizing tablet or a scanner. This paper presents a solution to the problem of automatically generating efficient piecewise parametric cubic polynomial approximations to shapes from sampled data. We have developed an algorithm that takes a set of sample points, plus optional endpoint and tangent vector specifications, and iteratively derives a single parametric cubic polynomial that lies close to the data points as defined by an error metric based on least-squares. Combining this algorithm with dynamic programming techniques to determine the knot placement gives good results over a range of shapes and applications.

References

1. 1.Aho, A.V., Hopcroft, J.E. and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974.
2. 2.Barnhill, R.E. and Riesenfeld, R.F., eds., Computer Aided Geometric Design, Academic Press, New York, 1974.
3. 3.Baudelaire, P. and Stone, M., "Techniques for Interactive Raster Graphics." Computer Graphics 14, 3 (1980), 302-307.
4. 4.Baudelaire, P.,The Draw User's Manual, internal report. Xerox Palo Alto Research Center, Palo Alto, CA, 1978.
5. 5.Baudelaire, P., The Fred User's Manual, internal report. Xerox Palo Alto Research Center, Palo Alto, CA, 1976.
6. 6.Bellman, R., Dynamic Programming, University Press, Princeton, N.J., 1957.
7. 7.Chung, W.L., "Automatic Curve Fitting Using and Adaptive Local Algorithm." ACM Transactions on Mathematical Software 6, 1 (1980), 45-57.
8. 8.Conte, S.D., and de Boor, C., Elementary Numerical Analysis: An Algorithmic Approach, second edition, McGraw-Hill, New York, 1972.
9. 9.Cox, M. G., "Curve Fitting with Piecewise Polynomials." J. Inst. Maths Applications 8, (1971), 36-52.
10. 10.de Boor, C., A Practical Guide to Splines, Springer-Verlag, 1978.
11. 11.Dierckx, P., "Algorithms for Smoothing Data with Periodic and Parametric Splines." Computer Graphics and Image Processing 20, (1982), 171-184.
12. 12.Faux, I.D., and Pratt, M.J., Computational Geometry for Design and Manufacture, Ellis Horwood, 1979.
13. 13.Flegal, R., private communication. Xerox Palo Alto Research Center, Palo Alto, CA, 1978.
14. 14.Ichida, K and Yoshimoto, F., "Curve Fitting by a One-Pass Method with a Piecewise Cubic Polynomial." ACM Transactions on Mathematical Software 3, 2 (1977), 164-174.
15. 15.Knuth, D.E., TEX and Metafont: New Directions in Typesetting, Digital Press and American Mathematical Society, 1979.
16. 16.Lipkie, D.E., Evans, S.R., Newlin, J.K., and Weissman, R.L., "Star Graphics: An Object-Oriented Implementation." Computer Graphics 16, 3 (1982), 115-124.
17. 17.Manning, J. R., "Continuity Conditions for Spline Curves." Computer Journal 17, (1974), 181-186.
18. 18.Nielson, G. M. "Some Piecewise Polynomial Alternatives to Splines in Tension" in Computer Aided Geometric Design, Barnhill, R.E. and Riesenfeld, R.F., eds., Academic Press, New York, 1974.
19. 19.Pavlidis, T., Algorithms for Graphics and Image Processing, Computer Science Press, 1982.
20. 20.Reeves, W. T., "Quantitative Representation of Complex Dynamic Shapes for Motion Analysis." PhD Thesis, Department of Computer Science, University of Toronto, 1980.
21. 21.Rice, J. R., The Approximation Of Functions, vols. 1 and 2, Addison-Wesley, Reading, Mass., 1964.
22. 22.Rice, J. R., Algorithm 525. ADAPT, adaptive smooth curve fitting, ACM Transactions on Mathematical Software 4, 1 (1978) 82-94.
23. 23.Rogers, D. F., and Adams, J.A., Mathematical Elements for Computer Graphics, McGraw-Hill, New York, 1976.
24. 24.Schultz, M., Spline Analysis, Prentice-Hall, Englewood Cliffs, N.J., 1973.
25. 25.Schumaker, Larry L., Spline Functions: Basic Theory, John Wiley & Sons, New York, 1981.
26. 26.Stone, M., The Griffin User's Manual, internal report. Xerox Palo Alto Research Center, Palo Alto, CA, 1979.
27. 27.Warnock, J. and Wyatt, D., "A Device Independent Graphics Imaging Model for use with Raster Devices." Computer Graphics 16, 3 (1982), 313-320.
28. 28.Wu, S., Abel, J.F., and Greenburg, D.P., "An Interactive Computer Graphics Approach to Surface Representation." CACM 20, 10 (1977), 703-712.
29. 29.Yamaguchi, F., "A New Curve Fitting Method Using a CRT Computer Display." Computer Graphics and Image Processing, 7 (1978), 425-437.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

    • Numerical analysis

      • Computations on polynomials

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming

    • Approximation algorithms analysis