Distance Between a Catmull-Clark Subdivision Surface and Its Limit Mesh t eggeai o the of th 肉 ea of the d.sb The Ca e 781B 2 Definition and notation 2.1 Distances a Distance Between a Catmull-Clark Subdivision Surface and Its Limit Mesh Zhangjin Huang∗ Peking University Guoping Wang† Peking University Abstract In geometry processing a refined control mesh is often used to ap￾proximate a Catmull-Clark subdivision surface (CCSS). By push￾ing the control points to their limit positions, a limit mesh of the subdivision surface is obtained. We present a bound on the distance between a CCSS patch and its limit face in terms of the maximum norm of the second order differences of the control points. The bound shows that the limit mesh may approximate the limit sur￾face better than the corresponding control mesh in general. Con￾sequently, for a given error tolerance, fewer subdivision steps are needed if the refined control mesh is replaced with the correspond￾ing limit mesh. CR Categories: I.3.5 [Computer Graphics]: Computational Ge￾ometry and Object Modeling—Curve, surface, solid and object rep￾resentations Keywords: Subdivision surfaces, limit mesh, distance bound, sub￾division depth 1 Introduction The Catmull-Clark subdivision surface (CCSS) was designed to generalize the bicubic B-spline surface to the meshes of arbitrary topology [Catmull and Clark 1978]. Because a CCSS is defined as the limit of a sequence of recursively subdivided control meshes, a piecewise linear approximation (for example, a refined control mesh after several steps of subdivision) is often used to approx￾imate the limit surface in applications such as surface rendering, surface trimming, and surface/surface intersection. It is natural to ask the following questions: How to estimate the error (distance) between a CCSS and its approximation (for instance, the control mesh)? How many (as small as possible) steps of subdivision are needed to satisfy a user-specified error tolerance? Because of the exponential growth in the numbers of mesh faces with successive subdivisions, one more or less step may make a great difference in mesh density. And subdivision depth (step) estimation relies on the approximation representation and its error estimate. The bounds on the maximal distance between a CCSS patch and its control mesh in terms of the maximum norm of the second or￾der differences (called second order norm) of the control points have been studied in [Cheng and Yong 2006; Cheng et al. 2006; Chen and Cheng 2006; Huang et al. 2006]. Though some tech￾niques such as matrix based [Chen and Cheng 2006] and optimiza￾tion based [Huang et al. 2006] are adopted to improve the distance ∗e-mail: hzj@graphics.pku.edu.cn †e-mail: wgp@graphics.pku.edu.cn estimate, for an extraordinary CCSS patch, the subdivision depth for a given error tolerance is still very large. Another piecewise linear approximation to a subdivision surface, obtained by pushing the control points to their limit positions, has been applied in surface interpolation [Halstead et al. 1993] and fit￾ting [Hoppe et al. 1994]. But the approximation error has not been investigated yet. We reformulate this approximation representation as follows. Extracting a submesh consisting of all interior control points from the control mesh of a CCSS, then pushing the con￾trol points to their limit positions, we get a limit mesh of the CCSS, which inscribes the limit surface (see Figure 1). For a closed CCSS, submesh extraction is not needed since its control points are all in￾terior. To bound the distance between a CCSS patch and its limit face, we introduce a distance bound function, and develop a way to find the maximum of the distance bound function for extraordinary cases. The bound reveals that the limit mesh may approximate the limit surface better than the corresponding control mesh in general. Given an error tolerance, the limit mesh approximation needs fewer subdivision steps than the control mesh approximation. The paper is organized as follows. Section 2 introduces some definitions and notations. In Section 3 and Section 4, we derive bounds for regular CCSS patches and extraordinary CCSS patches, respectively. And a subdivision depth estimation method for the limit mesh approximation is presented in Section 5. In Section 6, we compare the limit mesh approximation with the control mesh approximation. Finally we conclude the paper with some future works. 2 Definition and notation Without loss of generality, we assume the initial control mesh has been subdivided at least once or twice, isolating the extraordinary vertices so that each face is a quadrilateral and contains at most one extraordinary vertex. 2.1 Distances Figure 1: A Catumull-Clark subdivision surface, its control mesh and the corresponding limit mesh