projects

Subdivision Schemes

Classic subdivision schemes (Catmull-Clark, Doo-Sabin, Loop) are based on low-degree spline subdivision and use simple rules to refine the meshes: either each face is split into four, or each vertex is split into four. Subdivision algorithms need not be restricted to the spline-based schemes or to simple vertex or face split refinement. Existing schemes can be extended by adding special rules for surfaces features and new subdivision schemes can be designed using different types of refinement.

Our research on subdivision schemes includes developing new subdivision rules for correct handling of piecewise smooth surfaces, higher order subdivision schemes, subdivision for 4-8 refinement, and interpolating subdivision. In all cases, we perform rigorous analysis of our schemes using theoretical tools that we have developed.

Piecewise smooth surfaces

In this paper we introduce improved rules for Catmull-Clark and Loop subdivision that overcome several problems with the original schemes, namely, lack of smoothness at extraordinary boundary vertices and folds near concave corners. In addition, our approach to rule modification allows the generation of surfaces with prescribed normals, both on the boundary and in the interior, which considerably improves control of the shape of surfaces. Some images illustrating piecewise-smooth surfaces are available here.

Piecewise Smooth Subdivision Surfaces with Normal Control. Henning Biermann, Adi Levin, Denis Zorin, Computer Graphics (SIGGRAPH 2000 Proceedings), pp. 113-120

Nonmanifold subdivision

In this project, we describe a subdivision algorithm that makes it possible to model nonmanifold surfaces. Any triangle mesh, subject to the only restriction that no two vertices of any triangle coincide, can serve as an input to the algorithm. Resulting surfaces consist of collections of manifold patches joined along nonmanifold curves and vertices; if desired, constraints can be imposed on the tangent planes of manifold patches sharing a curve or a vertex. The algorithm is an extension of a well-known Loop subdivision scheme, and uses techniques developed for piecewise linear surfaces. Some examples are available in the project homepage.

Nonmanifold Subdivision. Lexing Ying, Denis Zorin, Proceedings of IEEE Visualization 2001.

4-8 subdivision

The distinctive feature of 4-8 subdivision is that it uses bisection refinement as an elementary refinement operation, rather than more commonly used face or vertex splits. As a result, the number of triangles in a uniformly refined mesh grows by a factor of two at each step, rather than a factor of four; moreover, slower refinement rate allows one to obtain higher smoothness (C⁴) in the regular case using masks of small support. An additional advantage is that adaptive bisection refinement generates conforming meshes directly, in contrast to face and vertex split schemes which require an additional post-processing pass.

4--8 Subdivision. Luiz Velho, Denis Zorin, CAGD, volume 18, Issue 5, Pages 397-427.

Uniform approach to construction of higher order subdivision schemes

Subdivision rules for uniform splines of any order can be constructed using well-known Lane-Riesenfield algorithm: replicate each control point and apply averaging n times. We extend this approach to construct schemes of arbitrarily high order. Remarkably primal and dual subdivision schemes can be constructed in a unified framework (our sequence of schemes includes both the Catmull-Clark scheme, which is primal, and Doo-Sabin scheme which is dual).

A Unified Framework for Primal/Dual Quadrilateral Subdivision Schemes. Denis Zorin, Peter Schröder, CAGD, volume 18, Issue 5, Pages 429-454.

Interpolating subdivision

Several years ago, we have developed an interpolating scheme based on the Butterfly scheme of Dyn, Gregory, and Levin. Unlike the original butterfly scheme, our scheme produces surfaces which are C¹ everywhere, as confirmed by our analysis . Interpolating subdivision has a number of advantages, the greatest being that it interpolates the control points of the original mesh. At the same time the visual quality of interpolating surfaces is lower than the quality of approximating surfaces such as Loop and Catmull-Clark. Some example images are available here.

Interpolating subdivision for meshes of arbitrary topology D. Zorin, W. Sweldens, P. Schröder. SIGGRAPH 96 Conference Proceedings, pp. 189-192.