Multiresolution curves

ABSTRACT

We describe a multiresolution curve representation, based on wavelets, that conveniently supports a variety of operations: smoothing a curve; editing the overall form of a curve while preserving its details; and approximating a curve within any given error tolerance for scan conversion. We present methods to support continuous levels of smoothing as well as direct manipulation of an arbitrary portion of the curve; the control points, as well as the discrete nature of the underlying hierarchical representation, can be hidden from the user. The multiresolution representation requires no extra storage beyond that of the original control points, and the algorithms using the representation are both simple and fast.

REFERENCES

• 1: Adobe Press, PostScript Language Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 2: Michael Banks , Elaine Cohen, Real time spline curves from interactively sketched data, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.99-107, Mar. 1990
• 3: R. Bartels and J. Beatty. A technique for the direct manipulation of spline curves. In Proceedings of the 1989 Graphics Interface Confer-ence, pages 33-39, London, Ontario, Canada, June 1989.
• 4: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 5: Deborah F. Berman , Jason T. Bartell , David H. Salesin, Multiresolution painting and compositing, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.85-90, July 1994 [doi>10.1145/192161.192181]
• 6: Beylkin, R. Coifman, and V. Rokhlin. Fast wavelet transforms and merical algorithms I. Communications on Pure and Applied Math-atics, 44:141-183, 1991.
• 7: George Celniker , Dave Gossard, Deformable curve and surface finite-elements for free-form shape design, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.257-266, July 1991
• 8: Charles K. Chui, An introduction to wavelets, Academic Press Professional, Inc., San Diego, CA, 1992
• 9: C. K. Chui and E. Quak. Wavelets on a bounded interval. In D. Braess and L. L. Schumaker, editors, Numerical Methods in Approximation Theory, volume 9, pages 53-75. Birkhauser Verlag, Basel, 1992.
• 10: M. Dæhlen , T. Lyche, Decomposition of splines, Mathematical methods in computer aided geometric design II, Academic Press Professional, Inc., San Diego, CA, 1992
• 11: R. DeVore, B. Jawerth, and B. Lucier. Image compression through wavelet transform coding. IEEE Transactions on Information Theory, 38(2):719-746, March 1992.
• 12: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 13: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 14: D. Forsey and R. Bartels. Tensor products and hierarchical fitting. In Curves and Surfaces in Computer Vision and Graphics II, SPIE Pro-ceedings Vol. 1610, pages 88-96, 1991.
• 15: Barry Fowler, Geometric manipulation of tensor product surfaces, Proceedings of the 1992 symposium on Interactive 3D graphics, p.101-108, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147172]
• 16: Josef Hoschek , Dieter Lasser , Larry L. Schumaker, Fundamentals of computer aided geometric design, A. K. Peters, Ltd., Natick, MA, 1993
• 17: S. Hsu and I. Lee. Skeletal strokes. Proceedings of SIGGRAPH 94. In Computer Graphics, Annual Conference Series, 1994.
• 18: William M. Hsu , John F. Hughes , Henry Kaufman, Direct manipulation of free-form deformations, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.177-184, July 1992
• 19: M. Lounsbery, T. DeRose, and J. Warren. Multiresolution surfaces of arbitrary topological type. Technical Report 93-10-05B, University of Washington, Department of Computer Science and Engineering, Jan-uary 1994.
• 20: Tom Lyche , Knut Morken, Knot removal for parametric B-spline curves and surfaces, Computer Aided Geometric Design, v.4 n.3, p.217-230, Nov., 1987 [doi>10.1016/0167-8396(87)90013-6]
• 21: T. Lyche and K. M~rken. Spline-wavelets of minimal support. In D. Braess and L. L. Schumaker, editors, Numerical Methodsin Approx-imation Theory, volume 9, pages 177-194. Birkhauser Verlag, Basel, 1992.
• 22: S. G. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.7, p.674-693, July 1989 [doi>10.1109/34.192463]
• 23: Michael Plass , Maureen Stone, Curve-fitting with piecewise parametric cubics, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.229-239, July 25-29, 1983, Detroit, Michigan, United States
• 24: W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Fetterling. Nu-merical Recipes. Cambridge University Press, Cambridge, second edi-tion, 1992.
• 25: E. Quak and N. Weyrich. Decomposition and reconstruction algo-rithms for spline wavelets on a bounded interval. CAT Report 294, Center for Approximation Theory, Texas A&MUniversity, April 1993.
• 26: Michael P. Salisbury , Sean E. Anderson , Ronen Barzel , David H. Salesin, Interactive pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.101-108, July 1994 [doi>10.1145/192161.192185]
• 27: P. J. Schneider. Phoenix: An interactive curve design system based on the automatic fitting of hand-sketched curves. Master's thesis, Depart-ment of Computer Science and Engineering, University of Washing-ton, 1988. and surface finite el-ents Graphics, 25(4):257-
• 28: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Theory

Keywords:
curve compression, curve editing, curve fitting, curve smoothing, direct manipulation, scan conversion, wavelets