Modeling smooth shape using subdivision on differential coordinates

Traditional subdivision schemes are applied on Euclidean coordinates (the spatial geometry of the control mesh). Although the subdivision limit surfaces are almost everywhere C² continuous, their mean-curvature normals are only C⁰. In order to generate higher quality surfaces with better-distributed mean-curvature normals, we propose a novel framework to apply subdivision for shape modeling, which combines subdivision with differential shape processing. Our framework contains two parts: subdivision on differential coordinates (a kind of differential geometry of the control mesh), and mutual conversions between Euclidean coordinates and differential coordinates. Further discussions about various strategies in both parts include a special subdivision method for mean-curvature normals, additional surface editing options, and a version of our framework for curve design. Finally, we demonstrate the improvement on surface quality by comparing the results between our framework and traditional subdivision methods.     

曲线插值约束的LOOP细分曲面

提出基于Loop细分方法的曲线插值方法,不需要修改细分规则,只需以插值曲线的控制多边形为中心多边形,向其两侧构造对称三角网格带,该对称三角网格带将收敛于插值曲线。因此,包含有该三角网格带的多面体网格的极限曲面将经过插值曲线。若要插值多条相交曲线只需在交点处构造全对称三角网格。运用该方法可在三角网格生成的细分曲面中插值多达六条的相交曲线。     

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.     

Loop subdivision surfaces interpolating -spline curves

This paper presents a novel method for defining a Loop subdivision surface interpolating a set of popularly-used cubic B-spline curves. Although any curve on a Loop surface corresponding to a regular edge path is usually a piecewise quartic polynomial curve, it is found that the curve can be reduced to a single cubic B-spline curve under certain constraints of the local control vertices. Given a set of cubic B-spline curves, it is therefore possible to define a Loop surface interpolating the input curves by enforcing the interpolation constraints. In order to produce a surface of local or global fair effect, an energy-based optimization scheme is used to update the control vertices of the Loop surface subjecting to curve interpolation constraints, and the resulting surface will exactly interpolate the given curves. In addition to curve interpolation, other linear constraints can also be conveniently incorporated. Because both Loop subdivision surfaces and cubic B-spline curves are popularly used in engineering applications, the curve interpolation method proposed in this paper offers an attractive and essential modeling tool for computer-aided design.     

快速收敛的四边形网格三分细分模式

提出了四边形网格的三分细分模式.对于正则和非正则四边形网格,分别采用不同的细分模板获得新的细分顶点.从双三次B样条中推导出正则四边形网格的三分细分模板,极限曲面C²连续;对细分矩阵进行傅里叶变换,推导出非正则四边形网格的三分细分模板,极限曲面C¹连续.提出的三分细分模式可以解决任意拓扑四边形网格的曲面细分问题.与其他细分模式相比,具有收敛速度快、适用范围广等优点.最后给出了四边形网格细分的实例.     

A framework for quad/triangle subdivision surface fitting: Application to mechanical objects

In this paper we present a new framework for subdivision surface approximation of three‐dimensional models represented by polygonal meshes. Our approach, particularly suited for mechanical or Computer Aided Design (CAD) parts, produces a mixed quadrangle‐triangle control mesh, optimized in terms of face and vertex numbers while remaining independent of the connectivity of the input mesh. Our algorithm begins with a decomposition of the object into surface patches. The main idea is to approximate the region boundaries first and then the interior data. Thus, for each patch, a first step approximates the boundaries with subdivision curves (associated with control polygons) and creates an initial subdivision surface by linking the boundary control points with respect to the lines of curvature of the target surface. Then, a second step optimizes the initial subdivision surface by iteratively moving control points and enriching regions according to the error distribution. The final control mesh defining the whole model is then created assembling every local subdivision control meshes. This control polyhedron is much more compact than the original mesh and visually represents the same shape after several subdivision steps, hence it is particularly suitable for compression and visualization tasks. Experiments conducted on several mechanical models have proven the coherency and the efficiency of our algorithm, compared with existing methods.     

A New Class of Guided C2 Subdivision Surfaces Combining Good Shape with Nested Refinement

Converting quadrilateral meshes to smooth manifolds, guided subdivision offers a way to combine the good highlight line distribution of recent G‐spline constructions with the refinability of subdivision surfaces. This avoids the complex refinement of G‐spline constructions and the poor shape of standard subdivision. Guided subdivision can then be used both to generate the surface and hierarchically compute functions on the surface. Specifically, we present a C² subdivision algorithm of polynomial degree bi‐6 and a curvature bounded algorithm of degree bi‐5. We prove that the common eigenstructure of this class of subdivision algorithms is determined by their guide and demonstrate that their eigenspectrum (speed of contraction) can be adjusted without harming the shape. For practical implementation, a finite number of subdivision steps can be completed by a high‐quality cap. Near irregular points this allows leveraging standard polynomial tools both for rendering of the surface and for approximately integrating functions on the surface.     

√2 Subdivision for quadrilateral meshes

This paper presents a $\sqrt2$ subdivision scheme for quadrilateral meshes that can be regarded as an extension of a 4-8 subdivision with new subdivision rules and improved capability and performance. The proposed scheme adopts a so-called $\sqrt2$ split operator to refine a control mesh such that the face number of the refined mesh generally equals the edge number and is thus about twice the face number of the coarse mesh. Smooth rules are designed in reference to the 4-8 subdivision, while a new set of weights is developed to balance the flatness of surfaces at vertices of different valences. Compared to the 4-8 subdivision, the presented scheme can be naturally generalized for arbitrary control nets and is more efficient in both space and computing time management. Analysis shows that limit surfaces produced by the scheme are C⁴ continuous for regular control meshes and G¹ continuous at extraordinary vertices.     

Optimization methods for scattered data approximation with subdivision surfaces

We present a method for scattered data approximation with subdivision surfaces which actually uses the true representation of the limit surface as a linear combination of smooth basis functions associated with the control vertices. A robust and fast algorithm for exact closest point search on Loop surfaces which combines Newton iteration and non-linear minimization is used for parameterizing the samples. Based on this we perform unconditionally convergent parameter correction to optimize the approximation with respect to the L² metric, and thus we make a well-established scattered data fitting technique which has been available before only for B-spline surfaces, applicable to subdivision surfaces. We also adapt the recently discovered local second order squared distance function approximant to the parameter correction setup. Further we exploit the fact that the control mesh of a subdivision surface can have arbitrary connectivity to reduce the L^∞ error up to a certain user-defined tolerance by adaptively restructuring the control mesh. Combining the presented algorithms we describe a complete procedure which is able to produce high-quality approximations of complex, detailed models.     

Generating subdivision surfaces from profile curves

The construction of freeform models has always been a challenging task. A popular approach is to edit a primitive object such that its projections conform to a set of given planar curves. This process is tedious and relies very much on the skill and experience of the designer in editing 3D shapes. This paper describes an intuitive approach for the modeling of freeform objects based on planar profile curves. A freeform surface defined by a set of orthogonal planar curves is created by blending a corresponding set of sweep surfaces. Each of the sweep surfaces is obtained by sweeping a planar curve about a computed axis. A Catmull-Clark subdivision surface interpolating a set of data points on the object surface is then constructed. Since the curve points lying on the computed axis of the sweep will become extraordinary vertices of the subdivision surface, a mesh refinement process is applied to adjust the mesh topology of the surface around the axis points. In order to maintain characteristic features of the surface defined with the planar curves, sharp features on the surface are located and are retained in the mesh refinement process. This provides an intuitive approach for constructing freeform objects with regular mesh topology using planar profile curves.     

Accuracy-Based Sampling and Reconstruction with Adaptive Meshes for Parallel Hierarchical Triangulation

Recent advances in range finding techniques have made the task of acquiring surface data for 3-D objects easier and more accurate. With most advanced techniques, range and color data are acquired simultaneously. Since the number of such acquired data is generally very large, a surface model capable of compressing data while maintaining a specified accuracy is required. The objective of this work is to construct a polyhedral representation of input data for surfaces. This representation adapts to local intrinsic surface properties while preserving their discontinuities. In this paper, we present an accuracy-based adaptive sampling and reconstruction technique for hierarchical triangulation of 3D objects. We have developed a parallel algorithm for adaptive mesh generation that recursively bisects mesh elements by increasing the number of mesh nodes according to local surface properties, such as surface orientation, curvature, and color. The recursive subdivision based on such viewpoint-invariant properties yields a hierarchical surface triangulation that is intrinsic to the surface. This approach also satisfies the absolute accuracy criteria, since nodes are generated as required until the entire surface has been approximated within a specified level of accuracy. We have also developed a parallel algorithm that detects and preserves both depth (C⁰) and orientation (C¹) discontinuities, without the formation of cracks which normally occur during independent subdivision. The algorithm has been successfully applied to adaptive sampling and reconstruction of both range and color images of human faces and Japanese antique dolls with fine grained color-texture.     

Local and singularity-free G 1 triangular spline surfaces using a minimum degree scheme

We develop a scheme for constructing G ¹ triangular spline surfaces of arbitrary topological type. To assure that the scheme is local and singularity-free, we analyze the selection of scalar weight functions and the construction of the boundary curve network in detail. With the further requirements of interpolating positions, normals, and surface curvatures, we show that the minimum degree of such a triangular spline surface is 6. And we present a method for constructing boundary curves network, which consists of cubic Bézier curves. To deal with certain singular cases, the base mesh must be locally subdivided and we proposed an adaptive subdivision strategy for it. An application of our G ¹ triangular spline surfaces to the approximation of implicit surfaces is described. The visual quality of this scheme is demonstrated by some examples.     

Volume-Surface Trees

Many algorithms in computer graphics improve their efficiency by using Hierarchical Space Subdivision Schemes (HS³), such as octrees, kD‐trees or BSP trees. Such HS³ usually provide an axis‐aligned subdivision of the 3D space embedding a scene or an object. However, the purely volume‐based behavior of these schemes often leads to strongly imbalanced surface clustering. In this article, we introduce the VS‐Tree, an alternative HS³ providing efficient and accurate surface‐based hierarchical clustering via a combination of a global 3D decomposition at coarse subdivision levels, and a local 2D decomposition at fine levels near the surface. First, we show how to efficiently construct VS‐Trees over meshes and point‐based surfaces, and analyze the improvement it offers for cluster‐based surface simplification methods. Then we propose a new surface reconstruction algorithm based on the volume‐surface classification of the VS‐Tree. This new algorithm is faster than state‐of‐the‐art reconstruction methods and provides a final semi‐regular mesh comparable to the output of remeshing algorithms.     

Pseudo‐Spline Subdivision Surfaces

Pseudo‐splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo‐splines include uniform odd‐degree B‐splines and the interpolatory 2n‐point subdivision schemes, and the other pseudo‐splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo‐spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo‐spline surfaces can be arbitrarily smooth in regular mesh regions and C¹ at extraordinary vertices as our numerical analysis reveals.     

Matrix-valued 4-point spline and 3-point non-spline interpolatory curve subdivision schemes

The objective of this paper is to study and construct matrix-valued templates for interpolatory curve subdivision. Since our investigation of this problem was motivated by the need of such subdivision stencils as boundary templates for interpolatory surface subdivision, we provide both spline and non-spline templates that are necessarily symmetric, due to the lack of direction-orientation in carrying out surface subdivision in general. For example, the minimum-supported Hermite interpolatory C¹ cubic spline curve subdivision scheme, with the skew-symmetric basis function for interpolating first derivatives, does not meet the symmetry specification. Non-spline C² interpolatory templates constructed in this paper are particularly important, due to their smaller support needed to minimize undesirable surface oscillations, when adopted as boundary templates for interpolatory C² surface subdivision. The curve subdivision templates introduced in this paper are adopted as boundary stencils for interpolatory surface subdivision with matrix-valued templates.     

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     

Least Squares Subdivision Surfaces

The usual approach to design subdivision schemes for curves and surfaces basically consists in combining proper rules for regular configurations, with some specific heuristics to handle extraordinary vertices. In this paper, we introduce an alternative approach, called Least Squares Subdivision Surfaces (LS), where the key idea is to iteratively project each vertex onto a local approximation of the current polygonal mesh. While the resulting procedure haves the same complexity as simpler subdivision schemes, our method offers much higher visual quality, especially in the vicinity of extraordinary vertices. Moreover, we show it can be easily generalized to support boundaries and creases. The fitting procedure allows for a local control of the surface from the normals, making LS³ very well suited for interactive freeform modeling applications. We demonstrate our approach on diadic triangular and quadrangular refinement schemes, though it can be applied to any splitting strategies.     

G 2 interpolation and blending on surfaces

We introduce a method for curvature-continuous (G ²) interpolation of an arbitrary sequence of points on a surface (implicit or parametric) with prescribed tangent and geodesic curvature at every point. The method can also be used forG ² blending of curves on surfaces. The interpolation/blending curve is the intersection curve of the given surface with a functional spline (implicit) surface. For the construction of blending curves, we derive the necessary formulas for the curvature of the surfaces. The intermediate results areG ² interpolation/blending methods in IR².     

Smooth multiple B-spline surface fitting with Catmull%ndash;Clark subdivision surfaces for extraordinary corner patches

This paper presents an algorithm for simultaneously fitting smoothly connected multiple surfaces from unorganized measured data. A hybrid mathematical model of B-spline surfaces and Catmull–Clark subdivision surfaces is introduced to represent objects with general quadrilateral topology. The interconnected multiple surfaces are G ² continuous across all surface boundaries except at a finite number of extraordinary corner points where G ¹ continuity is obtained. The algorithm is purely a linear least-squares fitting procedure without any constraint for maintaining the required geometric continuity. In case of general uniform knots for all surfaces, the final fitted multiple surfaces can also be exported as a set of Catmull–Clark subdivision surfaces with global C ² continuity and local C ¹ continuity at extraordinary corner points. Published online: 14 May 2002 Correspondence to: W. Ma