Multiresolution curve editing with linear constraints

ABSTRACT

The use of multiresolution control toward the editing of freeform curves and surfaces has already been recognized as a valuable modeling tool [4, 8, 11]. Similarly, in contemporary computer aided geometric design, the use of constraints to precisely prescribe freeform shape is considered an essential capability [7, 18]. This paper presents a scheme that combines multiresolution control with linear constraints into one framework, allowing one to perform multiresolution manipulation of nonuniform B-spline curves, while specifying and satisfying various linear constraints on the curves.

Positional, tangential, and orthogonality constraints are all linear and can be easily incorporated into a multiresolution freeform curve editing environment, as will be shown. Moreover, we also show that the symmetry as well as the area constraints can be reformulated as linear constraints and similarly incorporated. The presented framework is extendible and we also portray this same framework in the context of freeform surfaces.

REFERENCES

• 1: D. Eberly and J. Lancaster. On Gray scale image measurements: I. Arc length and area. CVGIP: Graphical Models and Image Processing, Vol 53, No 6, 1991, pp 538-549.
• 2: E. Cohen, T. Lyche R. E Riesenfeld. Discrete B-splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics. CGIP, Vol 14, No. 2, pp 87-111, Oct 1980.
• 3: G. Elber and C. Gotsman. Multiresolution Control for Nonuniform B-spline Curve Editing. The third Pacific Graphics Conference on Computer Graphics and Applications, Seoul, Korea, pp 267-278, August 1995.
• 4: Adam Finkelstein , David H. Salesin, Multiresolution curves, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.261-268, July 1994 [doi>10.1145/192161.192223]
• 5: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 6: G. H. Golub and C. E Van Loan. Matrix Computation. The John Hopkins University Press, Baltimore and London, Third Edition, 1996.
• 7: Michael Gleicher, Integrating constraints and direct manipulation, Proceedings of the 1992 symposium on Interactive 3D graphics, p.171-174, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147194]
• 8: S.J. Gorder. Wavelet Methods for Computer Graphics. Ph.D. dissertation, Princeton University (1995).
• 9: S. Gortler. Private communications.
• 10: IRIT 8.0 User's Manual, October 2000, Technion. http://www.cs.technion.ac.il/,,dfit.
• 11: R. Kazinnik and G. Elber. Orthogonal Decomposition of Nonuniform B-spline Spaces using Wavelets. Computer Graphics forum, Vol 16, No 3, pp 27-38, September 1997.
• 12: Wayne Liu , Stephen Mann, An optimal algorithm for expanding the composition of polynomials, ACM Transactions on Graphics (TOG), v.16 n.2, p.155-178, April 1997 [doi>10.1145/248210.248221]
• 13: Carlos Gonzalez-Ochoa , Scott McCammon , Jörg Peters, Computing moments of objects enclosed by piecewise polynomial surfaces, ACM Transactions on Graphics (TOG), v.17 n.3, p.143-157, July 1998 [doi>10.1145/285857.285858]
• 14: C.E. Pearson. Handbook of Applied Mathematics, Selected Results and Methods. Van Nostrand Reinhold publishing, Second Edition, New York 1990.
• 15: M. Plavnik and G. Elber. Surface Design Using Global Constraints on Total Curvature. The VIII IMA Conference on Mathematics of Surfaces, Birmingham, September 1998.
• 16: Ari Rappoport , Alla Sheffer , Michel Bercovier, Volume-Preserving Free-Form Solids, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.19-27, March 1996 [doi>10.1109/2945.489383]
• 17: Panagiotis D. Kaklis , Nickolas S. Sapidis, Convexity-preserving interpolatory parametric splines of non-uniform polynomial degree, Computer Aided Geometric Design, v.12 n.1, p.1-26, Feb. 1995 [doi>10.1016/0167-8396(94)00029-R]
• 18: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  J. Computer Applications

General Terms:
Design, Performance, Theory

Keywords:
CAD, curves & surfaces, geometric modeling, wavelets