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 language | English |
---|---|
Pages (from-to) | 479-488 |
Number of pages | 10 |
Journal | Computer-Aided Design and Applications |
Volume | 20 |
Issue number | 3 |
DOIs | |
State | Published - 2023 |
Bibliographical note
Publisher Copyright:© 2023.
Funding
This research is supported in part by NNSFC (Grant No. 61572020)
Funders | Funder number |
---|---|
National Natural Science Foundation of P.R. China | 61572020 |
Keywords
- 3D shape modeling
- interpolation
- subdivision surface
ASJC Scopus subject areas
- Computational Mechanics
- Computer Graphics and Computer-Aided Design
- Computational Mathematics