Iterative Interpolation based 3D Shape Generation Using General Catmull-Clark Subdivision Surfaces

Shuhua Lai, Jason Lai, Anastasia Kazadi, Seifalla A. Moustafa, Fuhua Cheng

Research output: Contribution to journalArticlepeer-review

Abstract

An algorithm for fast construction of a smooth subdivision surface that inter-polates the vertices of an arbitrary input mesh M is presented. The central idea of the proposed algorithm is to find the inverse A−1 of the matrix A that calculates the limit points of M with respect to a chosen subdivision scheme. However, instead of a costly matrix computation process, a technique to calculate A−1 indirectly by representing it as an infinite series of matrices is developed. With this infinite series of matrices, one can construct an infinite iterative series of meshes, which converges to a mesh whose subdivision surface inter-polates the given input mesh M. Most importantly, control points of these infinite iterative series of meshes can be calculated locally based on the chosen subdivision scheme. Hence, the matrices A and A−1 do not have to be really constructed. They are simply used in a theoretical derivation to obtain the iteration formula. The construction of the interpolation surface is done basically by iteratively adjusting vertices of the given mesh locally until some given error tolerance is reached. The concept of iterative interpolation has been presented in the literature before. The main differences between our algorithm and existing approaches are five-fold: 1). Our algorithm is the first one that derives the iterative equation from the perspective of computing A−1 . 2). Rigorous mathematical proof is provided that guarantees the existence, convergence and uniqueness of A−1 . 3). Our iterative interpolation algorithm, as proven in the paper, converges at an exponential rate, is a local process and does not in-volve costly matrix computation. Hence the new method is very fast and can handle meshes with large number of vertices. 4). Our algorithm does not require fairing in the construction process because solution to the above interpolation process is unique. 5). Although only the general Catmull-Clark subdivision surface is used here for deriving the iterative algorithm, the idea of the proposed algorithm works for other popular subdivision schemes as well.

Original languageEnglish
Pages (from-to)479-488
Number of pages10
JournalComputer-Aided Design and Applications
Volume20
Issue number3
DOIs
StatePublished - 2023

Bibliographical note

Publisher Copyright:
© 2023.

Funding

This research is supported in part by NNSFC (Grant No. 61572020)

FundersFunder number
National Natural Science Foundation of P.R. China61572020

    Keywords

    • 3D shape modeling
    • interpolation
    • subdivision surface

    ASJC Scopus subject areas

    • Computational Mechanics
    • Computer Graphics and Computer-Aided Design
    • Computational Mathematics

    Fingerprint

    Dive into the research topics of 'Iterative Interpolation based 3D Shape Generation Using General Catmull-Clark Subdivision Surfaces'. Together they form a unique fingerprint.

    Cite this