Non-Uniform Recursive Doo-Sabin Surfaces Doo-Sabin NURDS,Limit point ule h Doo-Sabin es to meshe 199.Sed .Limit pe kd,iBegie时C Theofpoperoll The Non-Uniform Recursive Doo-Sabin Surfaces Zhangjin Huanga,b,c,∗ , Guoping Wangd,e aSchool of Computer Science and Technology, University of Science and Technology of China, PR China bKey Laboratory of Software in Computing and Communication, Anhui Province, PR China cUSTC-SICT Joint Laboratory on Network and Communication, PR China dKey Laboratory of Machine Perception (MOE), Peking University, PR China eSchool of Electronic Engineering and Computer Science, Peking University, PR China Abstract This paper presents a generalization of Catmull-Clark-variant Doo-Sabin surfaces and non-uniform biquadratic B-spline sur￾faces called NURDSes (Non-Uniform Recursive Doo-Sabin Surfaces). One step of NURDS refinement can be factored into one non-uniform linear subdivision step plus one dual step. Compared to the prior non-uniform Doo-Sabin surfaces (i.e., quadratic NURSSes), NURDSes are convergent for arbitrary n-sided faces. Closed form limit point rules, which are important for applica￾tions in adaptive rendering and NC machining, are given as well. Keywords: Doo-Sabin surfaces, NURBS, Limit point rules 1. Introduction The Doo-Sabin [1] and the Catmull-Clark scheme [2] are generalizations of the subdivision rules for biquadratic and bicubic B-splines to meshes of arbitrary topology, respectively. In the same paper [2], Catmull and Clark also proposed a vari￾ant of Doo-Sabin subdivision, which could be interpreted as one linear subdivision step followed by one dual step [3, 4]. In 1998, Sederberg et al. [5] introduced non-uniform re￾cursive subdivision surfaces (NURSSes) that extended non￾uniform tensor product B-spline surfaces to control grids of arbitrary topology for the first time. Quadratic and cubic NURSSes correspond to non-uniform Doo-Sabin and Catmull￾Clark surfaces, respectively. To obtain stationary refinement rules, a restriction that opposing edges of each four-sided face have the same knot interval is placed on cubic NURSSes to generate NURCCs [6]. Limit point rules are useful for adaptive rendering of sub￾division surfaces [7]. For a stationary subdivision scheme, an eigenanalysis can be performed for each configuration of knot intervals to obtain the limit point using the method described in [8]. However, general limit point rules for NURCCs have not yet become available. Recently, M¨uller et al. presented two different approaches to extend both bicubic NURBS and Catmull-Clark surfaces. Extended Subdivision Surfaces (ES￾ubs) [9] offer limit point rules but are nonstationary. DINUS [10] is a stationary scheme which provides limit point as well as limit normal rules. Quadratic NURSSes [5] are the only subdivision surfaces that generalize both non-uniform biquadratic B-spline sur￾faces and original Doo-Sabin surfaces [1]. In Doo-Sabin like ∗Corresponding author. Tel.:+86 551 3603829 Email addresses: zhuang@ustc.edu.cn (Zhangjin Huang), wgp@pku.edu.cn (Guoping Wang) schemes, the extraordinary points are at the ”centers” of n-sided faces with n , 4. Qin et al. point out that quadratic NURSSes converge for n ≤ 12, but may diverge when n > 12 [11]. As a stationary scheme, a detailed eigenanalysis has been performed for quadratic NURSSes [12], but no closed form limit point rules are known for this scheme to date. As for the Catmull￾Clark variant of Doo-Sabin subdivision [2], no non-uniform counterpart has ever been presented to the best of our knowl￾edge. This paper introduces a non-uniform extension to the Catmull-Clark-variant Doo-Sabin surfaces (CCDSes) called NURDSes (Non-Uniform Recursive Doo-Sabin Surfaces). NURDSes are the subdivision surfaces that generalize non￾uniform biquadratic B-spline to control meshes of arbitrary topology and that generalize CCDSes to non-uniform knot vec￾tors. Just like NURSS and NURCC, ”NURDS” can as well stand for ”Non-Uniform Rational Doo-Sabin Surfaces”. By analyzing non-uniform biquadratic B-spline subdivision and the CCDS scheme, NURDSes are devised to have the anal￾ogous properties as follows: • Repeated averaging: One NURDS refinement step can be decomposed into one linear subdivision step followed by one dual step. • Convergence: The NURDS refinement is convergent for extraordinary points with arbitrary valence. • Limit point: For an n-sided face, its weighted centroid is the limit point of its associated extraordinary point. That is, an n-sided face converges to its weighted centroid which is on the limit surface. The rest of this paper is organized as follows. The next section briefly reviews the Catmull-Clark variant of Doo-Sabin Preprint submitted to Computer-Aided Design August 30, 2011