A unified framework for primal/dual quadrilateral subdivision schemes. (English) Zbl 0969.68155

Summary: Quadrilateral subdivision schemes come in primal and dual varieties, splitting faces or respectively vertices. The scheme of Catmull-Clark is an example of the former, while the Doo-Sabin scheme exemplifies the latter. In this paper we consider the construction of an increasing sequence of alternating primal/dual quadrilateral subdivision schemes based on a simple averaging approach. Beginning with a vertex split step we successively construct variants of Doo-Sabin and Catmull-Clark schemes followed by novel schemes generalizing B-splines of bidegree up to nine. We prove the schemes to be \(C^{1}\) at irregular surface points, and analyze the behavior of the schemes as the number of averaging steps increases. We discuss a number of implementation issues common to all quadrilateral schemes. In particular we show how both primal and dual quadrilateral schemes can be implemented in the same code, opening up new possibilities for more flexible geometric modeling applications and \(p\)-versions of the Subdivision Element Method. Additionally we describe a simple algorithm for adaptive subdivision of dual schemes.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI


[1] Biermann, H.; Levin, A.; Zorin, D., Piecewise smooth subdivision surfaces with normal control, Proceedings of SIGGRAPH, 2000, 113-120 (2000)
[2] Catmull, E.; Clark, J., Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-Aided Design, 10, 6, 350-355 (1978)
[3] Cavaretta, A.S., Dahmen, W., Micchelli, C.A. Stationary subdivision. Mem. Amer. Math. Soc. 93 (453); Cavaretta, A.S., Dahmen, W., Micchelli, C.A. Stationary subdivision. Mem. Amer. Math. Soc. 93 (453) · Zbl 0741.41009
[4] Cirak, F.; Ortiz, M.; Schröder, P., Subdivision surfaces: A new paradigm for thin-shell finite-element analysis, Int. J. Numer. Meth. Engng., 47, 2039-2072 (2000) · Zbl 0983.74063
[5] Cohen, E.; Lyche, T.; Riesenfeld, R., Discrete b-splines and subdivision techniques in computer aided geometric design and computer graphics, Computer Graphics and Image Processing, 14, 2, 87-111 (1980)
[6] Doo, D.; Sabin, M., Analysis of the behaviour of recursive division surfaces near extraordinary points, Computer-Aided Design, 10, 6, 356-360 (1978)
[7] Dyn, N.; Levin, D.; Gregory, J. A., A butterfly subdivision scheme for surface interpolation with tension control, ACM Trans. Graph., 9, 2, 160-169 (1990) · Zbl 0726.68076
[8] Habib, A.; Warren, J., Edge and vertex insertion for a class of \(c^1\) subdivision surfaces, Computer Aided Geometric Design, 16, 4, 223-247 (1999), Previously available as a TR, Rice University, August 1997 · Zbl 0916.68151
[9] Jury, E. I., Theory and Applications of the \(z\)-Transform Method (1964), Wiley: Wiley New York
[10] Kobbelt, L., Interpolatory subdivision on open quadrilateral nets with arbitrary topology, (Proceedings of Eurographics 96, Computer Graphics Forum (1996)), 409-420
[11] Kobbelt, L., \(3\) subdivision, Proceedings of SIGGRAPH, 2000, 103-112 (2000)
[12] Loop, C., Smooth subdivision surfaces based on triangles, Master’s Thesis (1987), University of Utah, Department of Mathematics
[13] Peters, J.; Reif, U., The simplest subdivision scheme for smoothing polyhedra, ACM Trans. Graph., 16, 4, 420-431 (1997)
[14] Prautzsch, H., Smoothness of subdivision surfaces at extraordinary points, Adv. Comput. Math., 9, 3-4, 377-389 (1998) · Zbl 0918.65094
[15] Qu, R., Recursive subdivision algorithms for curve and surface design, Ph.D. Thesis (1990), Brunel University
[16] Reif, U., A unified approach to subdivision algorithms near extraordinary points, Computer Aided Geometric Design, 12, 153-174 (1995) · Zbl 0872.65007
[17] Samet, H., The Design and Analysis of Spatial Data Structures (1990), Addison-Wesley: Addison-Wesley Reading, MA
[18] Stam, J., On subdivision schemes generalizing uniform b-spline surfaces of arbitrary degree, Computer Aided Geometric Design, 18, 5, 383-396 (2001) · Zbl 0970.68184
[19] Velho, L., Using semi-regular 4-8 meshes for subdivision surfaces, Journal of Graphics Tools, (2001) · Zbl 0971.68176
[20] Velho, L.; Zorin, D., 4-8 subdivision, Computer Aided Geometric Design, 18, 5, 397-427 (2001) · Zbl 0969.68157
[21] Warren, J., Weimer, H., 2001. Subdivision for geometric design, to appear; Warren, J., Weimer, H., 2001. Subdivision for geometric design, to appear
[22] Xu, X.; Kondo, K., Adaptive refinements in subdivision surfaces, (Eurographics 99 Proceedings (1999))
[23] Zorin, D., A method for analysis of \(c^1\)-continuity of subdivision surfaces, SIAM J. Numer. Anal., 37, 4, 1677-1708 (2000) · Zbl 0959.65021
[24] Zorin, D., Smoothness of subdivision on irregular meshes, Constructive Approximation, 16, 3, 359-397 (2000) · Zbl 0965.65024
[25] Zorin, D.; Schröder, P.; Sweldens, W., Interpolating subdivision for meshes with arbitrary topology, Proceedings of SIGGRAPH 96, 189-192 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.