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 ap￾proximate 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 tol￾erance?”. Because of the exponential growth in the number of mesh faces with successive subdivisions, one step, more or one less, can mean a great differ￾ence 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 polyno￾mials 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. de￾rived 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 ten￾sor 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 approxima￾tion 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 subdivi￾sion 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 es￾timate and subdivision depth estimation for an extraordinary CCSS patch by introducing the second order norm into its control mesh. Furthermore, Chen 2