ACCEPTED MANUSCRIPT of a Catmull a surface by its limi mesh Zhangjin Huang Jiansong Deng,Guoping Wang CCSS. nd on CCSS a eaa.Pt epth csti 1ga1the.T:+861062765819 29Mg20
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT A bound on the approximation of a Catmull-Clark subdivision surface by its limit mesh Zhangjin Huang a,b,∗, Jiansong Deng c , Guoping Wang a aSchool of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China bDepartment of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui 230027, China cDepartment of Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, China Abstract A Catmull-Clark subdivision surface (CCSS) is a smooth surface generated by recursively refining its control meshes, which are often used as linear approximations to the limit surface in geometry processing. For a given control mesh of a CCSS, by pushing the control points to their limit positions, another linear approximation – a limit mesh of the CCSS is obtained. In general a limit mesh might approximate a CCSS better than the corresponding control mesh. We derive 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 and a constant that depends only on the valence of the patch. A subdivision depth estimation formula for the limit mesh approximation is also proposed. For a given error tolerance, fewer subdivision steps are needed if the refined control mesh is replaced with the corresponding limit mesh. Key words: Catmull-Clark subdivision surfaces, Limit mesh, Distance bound, Subdivision depth ∗ Corresponding author. Tel.: +86 10 62765819; fax: +86 10 62755798. Email addresses: zhangjin.huang@gmail.com (Zhangjin Huang), dengjs@ustc.edu.cn (Jiansong Deng), gwang@graphics.pku.edu.cn (Guoping Wang). Preprint submitted to Elsevier 29 May 2008
ACCEPTED MANUSCRIPT 1 Introduction car ap aeinappicl its app dtusalsd ea出 1 n repres ired by 206 exte it nd Qin2004.tsm hCCsand ed bounds f cd a e.Then Chen a(2006)im
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT 1 Introduction The Catmull-Clark subdivision surface (CCSS) was designed to generalize the bicubic uniform B-spline surface to 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 linear approximation (for example, a refined control mesh after several steps of subdivision) is often used to approximate the limit surface in applications such as surface rendering, surface trimming, and surface/surface intersection. It is natural to ask the following questions: ”How does one estimate the error (distance) between a CCSS and its approximation (for instance, the control mesh)?” and ”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 number of mesh faces with successive subdivisions, one step, more or one less, can mean a great difference in mesh density. Also, subdivision depth (step) estimation relies on the approximation representation and its error estimate. Inspired by ideas for computing the bounds on the approximation of polynomials and splines by their control structure (Nairn et al., 1999; Reif, 2000; Lutterkort and Peters, 2001), many efforts have been devoted to estimating error bounds and subdivision depths for subdivision surfaces. Mustafa et al. derived error bounds for general binary and ternary subdivision curves/surfaces in terms of the maximal first order differences of the control points (Mustafa et al., 2006; Mustafa and Deng, 2007). Their bounds work for regular tensor product subdivision surfaces, and, to some extent, have only theoretical values. As one of the most widely used subdivision surfaces, the CCSS receives more attention than others. The first attempt to derive bounds on the approximation of the CCSS by its control mesh was made by Wang and Qin (2004). Using the distance between the control points and their limits to describe how the control mesh approximates to the limit surface, they derived bounds for the distance between a CCSS and its control mesh and a corresponding subdivision depth estimation method. Their work is based on the assumption that the distance between a CCSS and its control mesh reaches a maximum value at some vertex. But this is not always true. Being aware of this, Cheng and Yong (2006) estimated the distance between a CCSS and its control mesh patch by patch. For a regular patch, the bound is given in terms of the maximum norm of the second order differences (called the second order norm) of the control points; whereas for an extraordinary patch, the bound is expressed in terms of the first order norm of the control points. They also derived a new subdivision depth estimation technique. Then Cheng et al. (2006) improved the error estimate and subdivision depth estimation for an extraordinary CCSS patch by introducing the second order norm into its control mesh. Furthermore, Chen 2
ACCEPTED MANUSCRIPT 2007c e the fzACatmiLcCarkaubiwianurt and the coeresponding the limit andin edein CC petches.rep
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT and Cheng (2006) presented another improvement by using a matrix representation of the second order norm, in the estimate of the convergence rate of the second order norm of an extraordinary CCSS patch. Most recently, Huang and Wang (2007) evaluated the optimal convergence rate of the second order norm by solving constrained minimization problems. Nevertheless, for an extraordinary CCSS patch, the subdivision depth for a given error tolerance is still very large. Since the prior works all focus on the approximation of a CCSS with its control mesh, we turn our attention to other linear approximations. Fig. 1. A Catmull-Clark subdivision surface, its control mesh and the corresponding limit mesh. Another known linear approximation to a subdivision surface, obtained by pushing the control points of a control mesh to their limit positions, has been applied in surface interpolation (Halstead et al., 1993) and fitting (Hoppe et al., 1994). But the approximation error has not yet been investigated. 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 control points to their limit positions, we get a limit mesh for the CCSS, which inscribes the limit surface (see Fig. 1). For a closed CCSS, submesh extraction is not needed since its control points are all interior. 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 and fewer mesh faces than the control mesh approximation. This paper is organized as follows. Section 2 introduces some definitions and notation. In Sections 3 and 4, we derive distance bounds for regular CCSS patches and extraordinary CCSS patches, respectively. And a subdivision depth estimation method for limit mesh approximation is presented in Section 5. In Section 6, we compare limit mesh with control mesh approximation. 3
ACCEPTED MANUSCRIPT Finally we conclude the paper with discussion of future work 2 Deflnition and notation ● 2.1 Distances of the natch s (sre Fis. e Is-Fu训 2 Second order norm
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Finally we conclude the paper with discussion of future work. 2 Definition and notation Without loss of generality, we assume the initial control mesh has been subdivided at least twice, isolating the extraordinary vertices so that each face is a quadrilateral and contains at most one extraordinary vertex. 2.1 Distances Given a control mesh and the corresponding limit mesh of a Catmull-Clark subdivision surface S˜, for each interior mesh face F in the control mesh, there is a corresponding limit face F in the limit mesh, and a corresponding surface patch S in the limit surface S˜. The limit face F is a quadrilateral formed by connecting the four corner points of the patch S. 2n+8 control points in the 1-neighborhood of F form S’s control mesh, where n is the valence of F’s only extraordinary vertex (if it has one and n = 4 if not) and called the valence of the patch S (see Fig. 2a). A CCSS patch S can be parameterized over the unit square Ω = [0, 1] × [0, 1] as S(u, v) (Stam, 1998). Let F(u, v) be the bilinear parameterization of the corresponding limit face F over Ω. For (u, v) ∈ Ω, we denote S(u, v) − F(u, v) as the distance between the points S(u, v) and F(u, v). The distance between a CCSS patch S and the corresponding limit face F is defined as the maximum distance between S(u, v) and F(u, v), that is, max (u,v)∈Ω S(u, v) − F(u, v) , which is also called the distance between the patch S and the limit mesh of the surface S˜. 2.2 Second order norms Let Π = {Pi : i = 1, 2,..., 2n + 8} be the control mesh of an extraordinary patch S = S0 0, with P1 being an extraordinary vertex of valence n. The control points are ordered following Stam’s method (Stam, 1998) (Fig. 2a). The second order norm of Π (or S), denoted M = M0 = M0 0 , is defined as the maximum norm of the following 2n + 10 second order differences (SODs) {αi : i = 4
ACCEPTED MANUSCRIPT 2+8 2+ 1.+10)of the control points (Cheng006) 2P+P +P 2+7 ( spect y(Fig)
ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT 2n + 1 2 3 2n + 8 8 1 4 2n + 7 7 6 5 2n + 6 2n + 5 2n +4 2n +3 2n + 2 9 S = S0 0 (a) 2n+1 2 3 2n+8 2n+17 9 8 1 4 2n+7 2n+16 7 6 5 2n+6 2n+15 2n+5 2n+4 2n+3 2n+2 2n+14 2n+13 2n+12 2n+11 2n+10 2n+9 S1 0 S1 3 S1 1 S1 2 (b) Fig. 2. (a) Ordering of the control points of an extraordinary patch. (b) Ordering of the new control points (solid dots) after a Catmull-Clark subdivision. 1,..., 2n + 10} of the control points (Cheng et al., 2006): M = max{{P2i − 2P1 + P2((i+1)%n+1) : 1 ≤ i ≤ n} ∪{P2i+1 − 2P2(i%n)+2 + P2(i%n)+3 : 1 ≤ i ≤ n} ∪{P2 − 2P3 + P2n+8, P1 − 2P4 + P2n+7, P6 − 2P5 + P2n+6, P4 − 2P5 + P2n+3, P1 − 2P6 + P2n+4, P8 − 2P7 + P2n+5, P2n+6 − 2P2n+7 + P2n+8, P2n+2 − 2P2n+6 + P2n+7, P2n+2 − 2P2n+3 + P2n+4, P2n+3 − 2P2n+4 + P2n+5}} = max{αi : i = 1,..., 2n + 10} . (1) For a regular patch (n = 4), there are only two second order differences with the form P2i − 2P1 + P2((i+1)%n+1). Thus, the second order norm of a regular patch is defined as the maximum norm of 16 second order differences. By performing a Catmull-Clark subdivision on Π, one gets 2n+17 new vertices P1 i , i = 1,..., 2n + 17 (see Fig. 2b), which are called the level-1 control points of S. All these level-1 control points compose the level-1 control mesh of S: Π1 = {P1 i : i = 1, 2,..., 2n + 17}. We use Pk i and Πk to represent the level-k control points and level-k control mesh of S, respectively, after applying k subdivision steps to Π. The level-1 control points form four control point sets Π1 0, Π1 1, Π1 2 and Π1 3, corresponding to the control meshes of the subpatches S1 0, S1 1, S1 2 and S1 3, respectively (see Fig.2b), where Π1 0 = {P1 i : 1 ≤ i ≤ 2n + 8}, and the other three control point sets Π1 1, Π1 2 and Π1 3 are shown in Fig. 3. The subpatch S1 0 is an extraordinary patch, but S1 1, S1 2 and S1 3 are regular patches. Following the notation in Eq. (1), one can define the second order norms M1 i for S1 i , i = 0, 1, 2, 3, respectively. M1 = max{M1 i : i = 0, 1, 2, 3} is defined as the 5