Hierarchical and variational geometric modeling with wavelets

ABSTRACT

This paper discusses how wavelet techniques may be applied to a variety of geometric modeling tools. In particular, wavelet decompositions are shown to be useful for hierarchical control point or least squares editing. In addition, direct curve and surface manipulation methods using an underlying geometric variational principle can be solved more efficiently by using a wavelet basis. Because the wavelet basis is hierarchical, iterative solution methods converge rapidly. Also, since the wavelet coefficients indicate the degree of detail in the solution, the number of basis functions needed to express the variational minimum can be reduced, avoiding unnecessary computation. An implementation of a curve and surface modeler based on these ideas is discussed and experimental results are reported.

REFERENCES

• 1: BAKIELS, R., AND BEATTY, J. ATechnique for the Direct Manipulation of Spline Curves. In Graphics Interface I989 (1389). pp. 33-39.
• 2: 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
• 3: Charles K. Chui, An introduction to wavelets, Academic Press Professional, Inc., San Diego, CA, 1992
• 4: CHUI, C. K. And QUAK, E. Wavelets on a Bounded Interval. Numerical Methods of Application Theory 9 (1992), 53-75
• 5: COHEN. A., DACIHECIIIE. I., AND FEAIJVEAI.I. J. C. Biorthogonal Bases of Compactly Supported Wavelets. Communication on Pure and Applied Mathematics 4. (1992). 485-560.
• 6: COHEN. E., LYCHE, T.. AND RIESENFELD. R. Discrete B-Splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics. Computer Graphics and Image Processing 14, 2 (October 1980). 87-111.
• 7: DAHMEN. W.. AND KUNOTI, A. Multilevel Preconditioning. Numeriwhe Mathenmatik 63 (1092). 3 15-344.
• 8: 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]
• 9: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 10: FORSEY, D., AND WENG, L. Multi-resolution Surface Approximation for Animation. In Graphics inferface (1993).
• 11: 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]
• 12: Steven J. Gortler , Peter Schröder , Michael F. Cohen , Pat Hanrahan, Wavelet radiosity, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.221-230, September 1993 [doi>10.1145/166117.166146]
• 13: GOFZTLEF:. S. J. Wavelet Mcrhodsfor Compurcr Graphics. F'hT) thesis. Princeton Ilniversity. January 1995.
• 14: Mark Halstead , Michael Kass , Tony DeRose, Efficient, fair interpolation using Catmull-Clark surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.35-44, September 1993 [doi>10.1145/166117.166121]
• 15: S. Jaffard , Ph. Laurençot, Orthonormal wavelets, analysis of operators, and applications to numerical analysis, Wavelets: a tutorial in theory and applications, Academic Press Professional, Inc., San Diego, CA, 1993
• 16: Zicheng Liu , Steven J. Gortler , Michael F. Cohen, Hierarchical spacetime control, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.35-42, July 1994 [doi>10.1145/192161.192169]
• 17: IAXSSBERY, M., DEROSE. T.. AND WARREN. I. Multiresolution Analysis for ;Surfaces of Arbitrary Topological Type. Tech. Rep. TR 93- 10-05b. Department of Computer Science and Engineering. Princeton University, Ocloher 1993.
• 18: LYCHE. T., AND MOKKEN, K. Spline Wavelets of Minimal Support. In Numerical Merhods in Approxinuztiorl nleory, D.Braess and L. L. Schumaker, Eds.. vol. 9. Birkhauser Verlag. BaseI, 1992. pp. 177-194.
• 19: 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]
• 20: MEINGIJFT. J. Multivariate Interpolatiou at Arbitrary Points Made Simple. Jounznl of Applied Morhermrics mui Physics (UMPj 30 (1979), 292-304.
• 21: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.167-176, July 1992
• 22: PENTLAND, A. FI Solutions 10 Physical Equilibrium and Inrerpolation Prohlcm. 771 Visual Cornpurer 8, 5 (1992). 303-314.
• 23: Sam Qian , John Weiss, Wavelets and the numerical solution of partial differential equations, Journal of Computational Physics, v.106 n.1, p.155-175, May 1993 [doi>10.1006/jcph.1993.1100]
• 24: RANDO, T.. AND ROLILIEQ J. Designing Faired Parametric Stufaces. Computer Aided Design 23, 7 (September I99 1). 492497.
• 25: R. Szeliski, Fast Surface Interpolation Using Hierarchical Basis Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.6, p.513-528, June 1990 [doi>10.1109/34.56188]
• 26: D Terzopoulos, Image analysis using multigrid relaxation methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.129-139, March 1986 [doi>10.1109/TPAMI.1986.4767767]
• 27: Demetri Terzopoulos, Regularization of inverse visual problems involving discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.4, p.413-242, July 1986 [doi>10.1109/TPAMI.1986.4767807]
• 28: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
• 29: H Yserentant, On the multi-level splitting of finite element spaces, Numerische Mathematik, v.49 n.4, p.379-412, Aug. 1986 [doi>10.1007/BF01389538]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

  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, Experimentation, Performance