“Efficient, fair interpolation using Catmull-Clark surfaces” by Halstead, Kass and DeRose

  • ©Mark A. Halstead, Michael Kass, and Tony DeRose




    Efficient, fair interpolation using Catmull-Clark surfaces



    We describe an efficient method for constructing a smooth
    surface that interpolates the vertices of a mesh of arbitrary
    topological type. Normal vectors can also be interpolated at
    an arbitrary subset of the vertices. The method improves
    on existing interpolation techniques in that it is fast, robust
    and general.
    Our approach is to compute a control mesh whose
    Catmull-Clark subdivision surface interpolates the given
    data and minimizes a smoothness or “fairness” measure of
    the surface. Following Celniker and Gossard, the norm we
    use is based on a linear combination of thin-plate and membrane energies. Even though Catmull-Clark surfaces do not
    possess closed-form parametrizations, we show that the relevant properties of the surfaces can be computed efficiently
    and without approximation. In particular, we show that (1)
    simple, exact interpolation conditions can be derived, and
    (2) the fairness norm and its derivatives can be computed
    exactly, without resort to numerical integration.


    1. A. A. Ball and J. T. Storry. Conditions for tangent plane continuity over recursively defined B-spline surfaces. A CM Transactions on Graphics, 7(2):83-102, April 1988.
    2. E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10(6):350-355, 1978.
    3. George Celniker and Dave Gossard. Deformable curve and surface finite elements for free-form shape design. In Proceedings of SIGGRAPH ’91, pages 257-265, July 1991.
    4. G. Chaikin. An algorithm for high speed curve generation. Computer Graphics and Image Processing, 3:346- 349, 1974.
    5. R. Clough and J. Tocher. Finite element stiffness matrices for analysis of plate bending. In Matrix Methods in Structural Mechanics (Proceedings of the conference held at Wright-Patterson Air Force Base, Ohio, 26-28 October 1965), pages 515-545, 1966.
    6. D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design, 10(6):356-360, 1978.
    7. Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, 2nd edition, 1989.
    8. G. Herron. Techniques for visual continuity. In G. Farin, editor, Geometric Modeling, pages 163-174. SIAM, 1987.
    9. Charles T. Loop. Smooth subdivision surfaces based on triangles. M.S. Thesis, Department of Mathematics, University of Utah, August 1987.
    10. Michael Lounsbery, Stephen Mann, and Tony DeRose. Parametric surface interpolation. IEEE Computer Graphics and Applications, 12(5):45-52, September 1992.
    11. Henry P. Moreton and Carlo S~quin. Functional optimization for fair surface design. In Proceedings of SIG- GRAPH ’92, pages 167-176, July 1992.
    12. Ahmad H. Nasri. Polyhedral subdivision methods for free-form surfaces. A CM Transactions on Graphics, 6(1):29-73, January 1987.
    13. Malcolm Sabin. Recursive division singular points. Unpublished manuscript, June 1992.
    14. L. Shirman and C. S~quin. Local surface interpolation with B~zier patches. Computer Aided Geometric Design, 4(4):279-296, 1988.

ACM Digital Library Publication: