Detecting and reconstructing subdivision connectivity

inverse subdivision algorithms , with linear time and space complexity, to detect and reconstruct uniform Loop, Catmull–Clark, and Doo–Sabin subdivision structure in irregular triangular, quadrilateral, and polygonal meshes. We consider two main applications for these algorithms. The first one is to enable interactive modeling systems that support uniform subdivision surfaces to use popular interchange file formats which do not preserve the subdivision structure, such as VRML, without loss of information. The second application is to improve the compression efficiency of existing lossless connectivity compression schemes, by optimally compressing meshes with Loop subdivision connectivity. Our Loop inverse subdivision algorithm is based on global connectivity properties of the covering mesh, a concept motivated by the covering surface from Algebraic Topology. Although the same approach can be used for other subdivision schemes, such as Catmull–Clark, we present a Catmull–Clark inverse subdivision algorithm based on a much simpler graph-coloring algorithm and a Doo–Sabin inverse subdivision algorithm based on properties of the dual mesh. Straightforward extensions of these approaches to other popular uniform subdivision schemes are also discussed. Published online: 3 July 2002     

Analyzing midpoint subdivision

Midpoint subdivision generalizes the Lane–Riesenfeld algorithm for uniform tensor product splines and can also be applied to non-regular meshes. For example, midpoint subdivision of degree 2 is a specific Doo–Sabin algorithm and midpoint subdivision of degree 3 is a specific Catmull–Clark algorithm. In 2001, Zorin and Schröder were able to prove C¹-continuity for midpoint subdivision surfaces analytically up to degree 9. Here, we develop general analysis tools to show that the limiting surfaces under midpoint subdivision of any degree ?2 are C¹-continuous at their extraordinary points.     

Improved error estimate for extraordinary Catmull–Clark subdivision surface patches

Based on an optimal estimate of the convergence rate of the second order norm, an improved error estimate for extraordinary Catmull–Clark subdivision surface (CCSS) patches is proposed. If the valence of the extraordinary vertex of an extraordinary CCSS patch is even, a tighter error bound and, consequently, a more precise subdivision depth for a given error tolerance, can be obtained. Furthermore, examples of adaptive subdivision illustrate the practicability of the error estimation approach.     

Adjustable speed surface subdivision

We introduce a non-uniform subdivision algorithm that partitions the neighborhood of an extraordinary point in the ratio σ:1−σ, where σ(0,1). We call σ the speed of the non-uniform subdivision and verify C¹ continuity of the limit surface. For σ=1/2, the Catmull–Clark limit surface is recovered. Other speeds are useful to vary the relative width of the polynomial spline rings generated from extraordinary nodes.     

Biorthogonal wavelet construction for hybrid quad/triangle meshes

Ever since its introduction by Stam and Loop, the quad/triangle subdivision scheme, which is a generalization of the well-known Catmull–Clark subdivision and Loop subdivision, has attracted a great deal of interest due to its flexibility of allowing both quads and triangles in the same model. In this paper, we present a novel biorthogonal wavelet—constructed through the lifting scheme—that accommodates the quad/triangle subdivision. The introduced wavelet smoothly unifies the Catmull–Clark subdivision wavelet (for quadrilateral meshes) and the Loop subdivision wavelet (for triangular meshes) in a single framework. It can be used to flexibly and efficiently process any complicated semi-regular hybrid meshes containing both quadrilateral and triangular regions. Because the analysis and synthesis algorithms of the wavelet are composed of only local lifting operations allowing fully in-place calculations, they can be performed in linear time. The experiments demonstrate sufficient stability and fine fitting quality of the presented wavelet, which are similar to those of the Catmull–Clark subdivision wavelet and the Loop subdivision wavelet. The wavelet analysis can be used in various applications, such as shape approximation, progressive transmission, data compression and multiresolution edit of complex models.

Parametric G n blending of curves and surfaces

We introduce a simple blending method for parametric curves and surfaces that produces families of parametrically defined, G ⁿ –continuous blending curves and surfaces. The method depends essentially on the parameterizations of the curves/surfaces to be blended. Hence, the flexibility of the method relies on the existence of suitable parameter transformations of the given curves/surfaces. The feasibility of the blending method is shown by several examples. The shape of the blend curve/surface can be changed in a predictable way with the aid of two design parameters (thumb weight and balance).     

Extension of the Nicholls-Lee-Nichols algorithm to three dimensions

A new algorithm for clipping a line segment against a pyramid in E ³ is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment. It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that of existing algorithms, including the Cohen–Sutherland, Liang–Barsky, and Cyrus–Beck algorithms.     

A simple method for interpolating meshes of arbitrary topology by Catmull–Clark surfaces

Interpolating an arbitrary topology mesh by a smooth surface plays important role in geometric modeling and computer graphics. In this paper we present an efficient new algorithm for constructing Catmull–Clark surface that interpolates a given mesh. The control mesh of the interpolating surface is obtained by one Catmull–Clark subdivision of the given mesh with modified geometric rule. Two methods—push-back operation based method and normal-based method—are presented for the new geometric rule. The interpolation method has the following features: (1) Efficiency: we obtain a generalized cubic B-spline surface to interpolate any given mesh in a robust and simple manner. (2) Simplicity: we use only simple geometric rule to construct control mesh for the interpolating subdivision surface. (3) Locality: the perturbation of a given vertex only influences the surface shape near this vertex. (4) Freedom: for each edge and face, there is one degree of freedom to adjust the shape of the limit surface. These features make interpolation using Catmull–Clark surfaces very simple and thus make the method itself suitable for interactive free-form shape design.     

Interpolating an Unlimited Number of Curves Meeting at Extraordinary Points on Subdivision Surfaces*

Interpolating curves by subdivision surfaces is one of the major constraints that is partially addressed in the literature. So far, no more than two intersecting curves can be interpolated by a subdivision surface such as Doo‐Sabin or Catmull‐Clark surfaces. One approach that has been used in both of theses surfaces is the polygonal complex approach where a curve can be defined by a control mesh rather than a control polygon. Such a definition allows a curve to carry with it cross derivative information which can be naturally embodied in the mesh of a subdivision surface. This paper extends the use of this approach to interpolate an unlimited number of curves meeting at an extraordinary point on a subdivision surface. At that point, the curves can all meet with either C ⁰ or C ¹ continuity, yet still have common tangent plane. A straight forward application is the generation of subdivision surfaces through 3‐regular meshes of curves for which an easy interface can be used.     

Evolving Guide Subdivision

To overcome the well-known shape deficiencies of bi-cubic subdivision surfaces, Evolving Guide subdivision (EG subdivision) generalizes C² bi-quartic (bi-4) splines that approximate a sequence of piecewise polynomial surface pieces near extraordinary points. Unlike guided subdivision, which achieves good shape by following a guide surface in a two-stage, geometry-dependent process, EG subdivision is defined by five new explicit subdivision rules. While formally only C¹ at extraordinary points, EG subdivision applied to an obstacle course of inputs generates surfaces without the oscillations and pinched highlight lines typical for Catmull-Clark subdivision. EG subdivision surfaces join C² with bi-3 surface pieces obtained by interpreting regular sub-nets as bi-cubic tensor-product splines and C² with adjacent EG surfaces. The EG subdivision control net surrounding an extraordinary node can have the same structure as Catmull-Clark subdivision: two rings of 4-sided facets around each extraordinary nodes so that extraordinary nodes are separated by at least one regular node.     

The normalform of a space curve and its application to surface design

x )=0 with ∥▿h∥=1. The normalform function h is (unlike the latter cases) not differentiable at curve points. Despite of this disadvantage the normalform is a suitable tool for designing surfaces which can be treated as common implicit surfaces. Many examples (bisector surfaces, constant distance sum/product surfaces, metamorphoses, blending surfaces, smooth approximation surfaces) demonstrate applications of the normalform to surface design. Published online: 25 July 2001     

Reparameterization of piecewise rational Bezier curves and its applications

degree . Although the curve segments are C ¹ continuous in three dimensions, they may be C ⁰ continuous in four dimensions. In this case, the multiplicity of each interior knot cannot be reduced and the B-spline basis function becomes C ⁰ continuous. Using a surface generation method, such as skinning these kinds of rational B-spline curves to construct an interpolatory surface, may generate surfaces with C ⁰ continuity. This paper presents a reparameterization method for reducing the multiplicity of each interior knot to make the curve segments C ¹ continuous in four dimensions. The reparameterized rational B-spline curve has the same shape and degree as before and also has a standard form. Some applications in skinned surface and ruled surface generation based on the reparameterized curves are shown. Published online: 19 July 2001     

Characterizing degrees of freedom for geometric design of developable composite Bézier surfaces

This paper studies geometric design of developable composite Bézier surfaces from two boundary curves. The number of degrees of freedom (DOF) is characterized for the surface design by deriving and counting the developability constraints imposed on the surface control points. With a first boundary curve freely chosen, (2m+3), (m+4), and five DOFs are available for a second boundary curve of a developable composite Bézier surface that is G⁰, G¹, and G², respectively, and consists of m consecutive patches, regardless of the surface degree. There remain five and (7-2m) DOFs for the surface with C¹ and C² continuity. Allowing the end control points to superimpose produces Degenerated triangular patches with four and three DOFs left, when the end ruling vanishes on one and both sides, respectively. Examples are illustrated to demonstrate various design methods for each continuity condition. The construction of a yacht hull with a patterned sheet of paper unrolled from 3D developable surfaces validates practicality of these methods in complex shape design. This work serves as a theoretical foundation for applications of developable composite Bézier surfaces in product design and manufacturing.     

Surface approximation to scanned data

A method to approximate scanned data points with a B-spline surface is presented. The data are assumed to be organized in the form of Q _i,j, i=0,…,n; j=0,…,m _i, i.e., in a row-wise fashion. The method produces a C ^{(p-1, q-1)} continuous surface (p and q are the required degrees) that does not deviate from the data by more than a user-specified tolerance. The parametrization of the surface is not affected negatively by the distribution of the points in each row, and it can be influenced by a user-supplied knot vector.     

Filling n-sided regions with NURBS patches

n -sided region with G ^ɛ continuous NURBS patches that interpolate boundary curves and approximate given cross-boundary derivatives. The NURBS surfaces joining along inner or boundary curves have normal vectors that do not deviate more than the user-specified angular tolerance ɛ. The method is general in that there are no restrictions on the number of boundary curves, and the cross-boundary derivatives can be specified independently. To satisfy all conditions, only one degree elevation is needed.     

Interpolating meshes of boundary intersecting curves by subdivision surfaces

C ⁰ (creases) or C ¹ continuity across the interpolated curves.     

General triangular midpoint subdivision

In this paper, we introduce triangular subdivision operators which are composed of a refinement operator and several averaging operators, where the refinement operator splits each triangle uniformly into four congruent triangles and in each averaging operation, every vertex will be replaced by a convex combination of itself and its neighboring vertices. These operators form an infinite class of triangular subdivision schemes including Loop's algorithm with a restricted parameter range and the midpoint schemes for triangular meshes. We analyze the smoothness of the resulting subdivision surfaces at their regular and extraordinary points by generalizing an established technique for analyzing midpoint subdivision on quadrilateral meshes. General triangular midpoint subdivision surfaces are smooth at all regular points and they are also smooth at extraordinary points under certain conditions. We show some general triangular subdivision surfaces and compare them with Loop subdivision surfaces.     

Ratioquadrics: an alternative model for superquadrics

This paper presents a new family of 2D curves and its extension to 3D surfaces, respectively, calledrationconics andratioquadrics that have been designed as alternatives to the well-known superconics and superquadrics. This new model is intended as an improvement to the original one on three main points: first, it involves lower computation cost and provides better numerical robustness; second, it offers higher order continuities (C ¹/G ² orC ²/G ² instead ofC ⁰/G ⁰); and third, it provides a greater variety of shapes for the resulting curves and surfaces. All these improvements are obtained by replacing the signed power function involved in the formulation of superconics and superquadrics by linear or quadratic rational polynomials.     

A New Interpolatory Subdivision for Quadrilateral Meshes

This paper presents a new interpolatory subdivision scheme for quadrilateral meshes based on a 1–4 splitting operator. The scheme generates surfaces coincident with those of the Kobbelt interpolatory subdivision scheme for regular meshes. A new group of rules are designed for computing newly inserted vertices around extraordinary vertices. As an extension of the regular masks,the new rules are derived based on a reinterpretation of the regular masks. Eigen‐structure analysis demonstrates that subdivision surfaces generated using the new scheme are C¹ continuous and, in addition, have bounded curvature.     

Smooth spline surface generation over meshes of irregular topology

An efficient method for generating a smooth spline surface over an irregular mesh is presented in this paper. Similar to the methods proposed by [1, 2, 3, 4], this method generates a generalised bi-quadratic B-spline surface and achieves C ¹ smoothness. However, the rules to construct the control points for the proposed spline surfaces are much simpler and easier to follow. The construction process consists of two steps: subdividing the initial mesh once using the Catmull–Clark [5] subdivision rules and generating a collection of smoothly connected surface patches using the resultant mesh. As most of the final mesh is quadrilateral apart from the neighbourhood of the extraordinary points, most of the surface patches are regular quadratic B-splines. The neighbourhood of the extraordinary points is covered by quadratic Zheng–Ball patches [6].