More Web Proxy on the site http://driver.im/

research-article

A unified interpolatory subdivision scheme for quadrilateral meshes

Authors:

Chongyang Deng,

Weiyin MaAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 32, Issue 3

Article No.: 23, Pages 1 - 11

https://doi.org/10.1145/2487228.2487231

Published: 04 July 2013 Publication History

Abstract

For approximating subdivision schemes, there are several unified frameworks for effectively constructing subdivision surfaces generalizing splines of an arbitrary degree. In this article, we present a similar unified framework for interpolatory subdivision schemes. We first decompose the 2n-point interpolatory curve subdivision scheme into repeated local operations. By extending the repeated local operations to quadrilateral meshes, an efficient algorithm can be further derived for interpolatory surface subdivision. Depending on the number n of repeated local operations, the continuity of the limit curve or surface can be of an arbitrary order C^L, except in the surface case at a limited number of extraordinary vertices where C¹ continuity with bounded curvature is obtained. Boundary rules built upon repeated local operations are also presented.

Supplementary Material

MP4 File (tp131.mp4)

Download
22.71 MB

References

[1]

Augsdorfer, U. H., Cashman, T. J., Dodgson, N. A., and Sabin, M. A. 2009. Numerical checking of C¹ for arbitrary degree quadrilateral subdivision schemes. In Mathematics of Surfaces, E. Hancock, R. Martin, and M. Sabin, Eds., Lecture Notes in Computer Science, vol. 5654, Springer, 45--54.

Digital Library

[2]

Cai, Z. 1995. Convergence, error estimation and some properties of four-point interpolation subdivision scheme. Comput. Aid. Geom. Des. 12, 5, 459--468.

Digital Library

[3]

Cashman, T. J. 2012. Beyond catmull-clark&quest; A survey of advances in subdivision surface methods. Comput. Graph. Forum 31, 1, 42--61.

Digital Library

[4]

Cashman, T. J., Augsdorfer, U. H., Dodgson, N. A., and Sabin, M. A. 2009a. NURBS with extraordinary points: High-degree, non-uniform, rational subdivision schemes. ACM Trans. Graph. 28, 3, 46:1--46:9.

Digital Library

[5]

Cashman, T. J., Dodgson, N. A., and Sabin, M. A. 2009b. A symmetric, non-uniform, refine and smooth subdivision algorithm for general degree B-splines. Comput. Aid. Geom. Des. 26, 1, 94--104.

Digital Library

[6]

Catmull, E. and Clark, J. 1978. Recursively generated b-spline surfaces on arbitrary topology meshes. Comput. Aid. Des. 10, 6, 350--355.

[7]

Daubechies, I. 1992. Ten Lectures on Wavelets. SIAM.

Digital Library

[8]

Deslauriers, G. and Dubuc, S. 1989. Symmetric iterative interpolation processes. Construct. Approx. 5, 1, 49--68.

[9]

Dong, B. and Shen, Z. 2007. Pseudo-splines, wavelets and framelets. Appl. Comput. Harmon. Anal. 22, 1, 78--104.

[10]

Doo, D. and Sabin, M. 1978. Analysis of the behaviour of recursive division surfaces near extraordinary points. Comput. Aid. Des. 10, 6, 356--360.

[11]

Dubuc, S. 1986. Interpolation through an iterative scheme. J. Math. Anal. Appl. 114, 1, 185--204.

[12]

Dyn, N., Hormann, K., Sabin, M. A., and Shen, Z. 2008. Polynomial reproduction by symmetric subdivision schemes. J. Approx. Theory 155, 1, 28--42.

Digital Library

[13]

Dyn, N. and Levin, D. 2002. Subdivision schemes in geometric modelling. Acta Numerica 11, 73--114.

[14]

Dyn, N., Levin, D., and Gregory, J. A. 1987. A four-point interpolatory subdivision scheme for curve design. Comput. Aid. Geom. Des. 4, 4, 257--268.

Digital Library

[15]

Dyn, N., Levin, D., and Gregory, J. A. 1990. A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. 9, 2, 160--169.

Digital Library

[16]

Eirola, T. 1992. Sobolev characterization of solutions of dilation equations. SIAM J. Math. Anal. 23, 4, 1015--1030.

Digital Library

[17]

Fang, M., Ma, W., and Wang, G. 2010. A generalized curve subdivision scheme of arbitrary order with a tension parameter. Comput. Aid. Geom. Des. 27, 9, 720--733.

Digital Library

[18]

Hassan, M. F., Ivrissimitzis, I. P., Dodgson, N. A., and Sabin, M. A. 2002. An interpolating 4-point C² ternary stationary subdivision scheme. Comput. Aid. Geom. Des. 19, 1, 1--18.

Digital Library

[19]

Kobbelt, L. 1996. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Comput. Graph. Forum 15, 3, 409--420.

[20]

Lane, J. M. and Riesenfeld, R. F. 1980. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 2, 1, 35--46.

Digital Library

[21]

Li, G. and Ma, W. 2005. Interpolatory ternary subdivision surfaces. Comput. Aid. Geom. Des. 23, 1, 45--77.

Digital Library

[22]

Li, G. and Ma, W. 2007. A method for constructing interpolatory subdivision schemes and blending subdivision. Comput. Graph. Forum 26, 2, 185--201.

[23]

Li, G., Ma, W., and Bao, H. 2005. A new interpolatory subdivision for quadrilateral meshes. Comput. Graph. Forum 24, 1, 3--16.

[24]

Lin, S., Luo, X., You, F., and Li, Z. 2008. Deducing interpolating subdivision schemes from approximating subdivision schemes. ACM Trans. Graph. 27, 5, 146:1--146:7.

Digital Library

[25]

Maillot, J. and Stam, J. 2001. A unified subdivision scheme for polygonal modeling. Comput. Graph. Forum 20, 3, 471--479.

[26]

Oswald, P. and Schroder, P. 2003. Composite primal/dual square-root-of-three subdivision schemes. Comput. Aid. Geom. Des. 20, 3, 135--164.

Digital Library

[27]

Peters, J. and Reif, U. 2008. Subdivision Surfaces. Springer.

Digital Library

[28]

Prautzsch, H. 1998. Smoothness of subdivision surfaces at extraordinary points. Adv. Comput. Math. 9, 3--4, 377--389.

[29]

Prautzsch, H. and Chen, Q. 2011. Analyzing midpoint subdivision. Comput. Aid. Geom. Des. 28, 7, 407--419.

Digital Library

[30]

Reif, U. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Comput. Aid. Geom. Des. 12, 2, 153--174.

Digital Library

[31]

Schaefer, S. and Goldman, R. 2009. Non-uniform subdivision for B-splines of arbitrary degree. Comput. Aid. Geom. Des. 26, 1, 75--81.

Digital Library

[32]

Schaefer, S. and Warren, J. 2002. A factored interpolatory subdivision scheme for quadrilateral surfaces. In Curve and Surface Fitting Saint-Malo, 373--382.

[33]

Silva, S., Madeira, J., and Santos, B. S. 2009. Polymeco: An integrated environment for polygonal mesh analysis and comparison. Comput. Graph. 33, 2, 181--191.

Digital Library

[34]

Stam, J. 2001. On subdivision schemes generalizing uniform b-spline surfaces of arbitrary degree. Comput. Aid. Geom. Des. 18, 5, 383--396.

Digital Library

[35]

Warren, J. and Weimer, H. 2001. Subdivision Methods for Geometric Design: A Constructive Approach. Morgan Kaufmann, San Fransisco, CA.

Digital Library

[36]

Weissman, A. 1989. A 6-point interpolatory subdivision scheme for curve design. M.S. thesis, Tel-Aviv University.

[37]

Zorin, D. and Schroder, P. 2001. A unified framework for primal/dual quadrilateral subdivision schemes. Comput. Aid. Geom. Des. 18, 5, 429--454.

Digital Library

[38]

Zorin, D., Schroder, P., Derose, T., Kobbelt, L., Levin, A., and Sweldens, W. 2000. Subdivision for modeling and animation. In ACM SIGGRAPH Course Notes, n. 23. ACM Press, New York.

[39]

Zorin, D., Schroder, P., and Sweldens, W. 1996. Interpolating subdivision for meshes with arbitrary topology. In Proceedings of the SIGGRAPH International Conference on Computer Graphics and Interactive Techniques. J. Fujii, Ed., ACM Press, New York, 189--192.

Digital Library

Cited By

Wang XMa W(2024)A class of new tuned primal subdivision schemes with high-quality limit surface in extraordinary regionsACM Transactions on Graphics10.1145/368798743:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687987
Hamza YHamza MRababah ARano S(2024)HSS-progressive interpolation for Loop and Catmull–Clark Subdivision SurfacesScientific African10.1016/j.sciaf.2024.e0207023(e02070)Online publication date: Mar-2024
https://doi.org/10.1016/j.sciaf.2024.e02070
Ma WWang XMa Y(2023)An Unified λ-subdivision Scheme for Quadrilateral Meshes with Optimal Curvature Performance in Extraordinary RegionsACM Transactions on Graphics10.1145/361840042:6(1-15)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618400
Show More Cited By

Index Terms

A unified interpolatory subdivision scheme for quadrilateral meshes
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Recommendations

Constructing an Interpolatory Subdivision Scheme from Doo-Sabin Subdivision
CADGRAPHICS '11: Proceedings of the 2011 12th International Conference on Computer-Aided Design and Computer Graphics

This paper presents an interpolatory subdivision scheme derived from the Doo-Sabin subdivision scheme. We first present the relations among three curve subdivision schemes, namely a four point interpolatory subdivision scheme, a cubic B-spline curve ...
Surface interpolation of meshes by geometric subdivision

Subdivision surfaces are generated by repeated approximation or interpolation from initial control meshes. In this paper, two new non-linear subdivision schemes, face based subdivision scheme and normal based subdivision scheme, are introduced for ...
Interpolatory ternary subdivision surfaces

This paper proposes an interpolatory ternary subdivision for quadrilateral meshes that produces C2 continuous limit surfaces for regular meshes while achieves G1 continuity with bounded curvature at extraordinary vertices. The subdivision splits each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 32, Issue 3

June 2013

129 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2487228

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2013

Accepted: 01 January 2013

Revised: 01 December 2012

Received: 01 November 2011

Published in TOG Volume 32, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation
Open Project Program of the State Key Lab of CAD&GG
City University of Hong Kong
Research Grants Council, University Grants Committee, Hong Kong
Zhejiang University

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
622
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)4

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XMa W(2024)A class of new tuned primal subdivision schemes with high-quality limit surface in extraordinary regionsACM Transactions on Graphics10.1145/368798743:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687987
Hamza YHamza MRababah ARano S(2024)HSS-progressive interpolation for Loop and Catmull–Clark Subdivision SurfacesScientific African10.1016/j.sciaf.2024.e0207023(e02070)Online publication date: Mar-2024
https://doi.org/10.1016/j.sciaf.2024.e02070
Ma WWang XMa Y(2023)An Unified λ-subdivision Scheme for Quadrilateral Meshes with Optimal Curvature Performance in Extraordinary RegionsACM Transactions on Graphics10.1145/361840042:6(1-15)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618400
Yang X(2023)Point-normal subdivision curves and surfacesComputer Aided Geometric Design10.1016/j.cagd.2023.102207104(102207)Online publication date: Jul-2023
https://doi.org/10.1016/j.cagd.2023.102207
Wang ZLi YLiu JMa WDeng C(2023)Gauss–Seidel progressive iterative approximation (GS-PIA) for subdivision surface interpolationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-021-02318-939:1(139-148)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s00371-021-02318-9
Deng JZuo BLuo HXie WYang J(2022)A Parallel Computing Schema Based on IGAComputer Modeling in Engineering & Sciences10.32604/cmes.2022.020631132:3(965-990)Online publication date: 2022
https://doi.org/10.32604/cmes.2022.020631
Zhang JTian YLi X(2022)Improved non-uniform subdivision scheme with modified Eigen-polyhedronVisual Computing for Industry, Biomedicine, and Art10.1186/s42492-022-00115-25:1Online publication date: 11-Jul-2022
https://doi.org/10.1186/s42492-022-00115-2
Zaitseva T(2022)New types of smooth subdivision algorithmsACM SIGGRAPH 2022 Posters10.1145/3532719.3543261(1-2)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3532719.3543261
李万(2021)Comparative Research and Application of Four Approximation Subdivision AlgorithmsAdvances in Applied Mathematics10.12677/AAM.2021.10100610:01(52-61)Online publication date: 2021
https://doi.org/10.12677/AAM.2021.101006
Ejaz SMustafa GBaleanu DChu Y(2021)The refinement-schemes-based unified algorithms for certain nth order linear and nonlinear differential equations with a set of constraintsAdvances in Difference Equations10.1186/s13662-021-03283-22021:1Online publication date: 23-Feb-2021
https://doi.org/10.1186/s13662-021-03283-2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents