Error bounds for Loop subdivision surfaces

In this paper, we obtain the error bounds on the distance between a Loop subdivision surface and its control mesh. Both local and global bounds are derived by means of computing and analysing the control meshes with two rounds of refinement directly. The bounds can be expressed with the maximum edge length of all triangles in the initial control mesh. Our results can be used as posterior estimates and also can be used to predict the subdivision depth for any given tolerance.     

Estimating subdivision depth of Catmull-Clark surfaces

In this paper, both general and exponential bounds of the distance between a uniform Catmull-Clark surface and its control polyhedron are derived. The exponential bound is independent of the process of subdivision and can be evaluated without recursive subdivision. Based on the exponential bound, we can predict the depth of subdivision within a user-specified error tolerance. This is quite useful and important for pre-computing the subdivision depth of subdivision surfaces in many engineering applications such as surface/surface intersection,mesh generation, numerical control machining and surface rendering.     

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.     

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.     

Evolutions of Polygons in the Study of Subdivision Surfaces

We employ the theory of evolving n-gons in the study of subdivision surfaces. We show that for subdivision schemes with small stencils the eigenanalysis of an evolving polygon, corresponding either to a face or to the 1-ring neighborhood of a vertex, complements in a geometrically intuitive way the eigenanalysis of the subdivision matrix. In the applications we study the types of singularities that may appear on a subdivision surface, and we find properties of the subdivision surface that depend on the initial control polyhedron only.     

Hierarchical Functional Maps between Subdivision Surfaces

We propose a novel approach for computing correspondences between subdivision surfaces with different control polygons. Our main observation is that the multi‐resolution spectral basis functions that are open used for computing a functional correspondence can be compactly represented on subdivision surfaces, and therefore can be efficiently computed. Furthermore, the reconstruction of a pointwise map from a functional correspondence also greatly benefits from the subdivision structure. Leveraging these observations, we suggest a hierarchical pipeline for functional map inference, allowing us to compute correspondences between surfaces at fine subdivision levels, with hundreds of thousands of polygons, an order of magnitude faster than existing correspondence methods. We demonstrate the applicability of our results by transferring high‐resolution sculpting displacement maps and textures between subdivision models.     

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.     

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.     

Compliance control safety: An architecture-independent analysis

Safe manipulator/task interaction is defined and quantified based on interaction forces resulting from manipulator motion commands. H¹ and H^*** safety bounds are introduced for evaluation of compliance control designs deriving from any control architecture or design method. Compliance control design examples are presented to demonstrate the use of these bounds, and to demonstrate the need to consider safety bounds of the type proposed. © 1994 John Wiley & Sons, Inc.     

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.     

基于参数分解的正则四边形插值细分曲面的快速求值

提出了两种正则四边形网格插值细分曲面的求值算法.算法基于参数m-进制分解和构造矩阵序列,通过参数分解数列对应的矩阵乘积得到基函数值,得到初始网格上对应控制点的权值,从而实现插值细分曲面求值.算法1 基于2D 细分掩模,算法2 基于张量积.数值实验表明,算法高效且低存储.     

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     

证据合成的格结构研究

在粗糙集和证据理论体系结构的基拙上,分析粗糙集和证据理论中合成质量函数的不同方法,研究细分偏序 格中划分与证据理论中的正交组合运算的关系利用粒度分析细分偏序格上划分的变化情况,证明了在细分偏序格 的上、下确界与所有上、下界所对应的划分中,获取的质量函数并不对应于证据理论中质量函数正交运算的结论,从而 澄清了不同知识粒度下粗糙集中所有划分获取的质量函数与证据理论中正交运算之间的关系。     

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

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

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.     

A Method for Constructing Interpolatory Subdivision Schemes and Blending Subdivisions

This paper presents a universal method for constructing interpolatory subdivision schemes from known approximatory subdivisions. The method establishes geometric rules of the associated interpolatory subdivision through addition of further weighted averaging operations to the approximatory subdivision. The paper thus provides a novel approach for designing new interpolatory subdivision schemes. In addition, a family of subdivision surfaces varying from the given approximatory scheme to its associated interpolatory scheme, namely the blending subdivisions, can also be established. Based on the proposed method, variants of several known interpolatory subdivision schemes are constructed. A new interpolatory subdivision scheme is also developed using the same technique. Brief analysis of a family of blending subdivisions associated with the Loop subdivision scheme demonstrates that this particular family of subdivisions are globally C¹ continuous while maintaining bounded curvature for regular meshes. As a further extension of the blending subdivisions, a volume‐preserving subdivision strategy is also proposed in the paper.     

Ternary butterfly subdivision

This paper presents an interpolating ternary butterfly subdivision scheme for triangular meshes based on a 1–9 splitting operator. The regular rules are derived from a C² interpolating subdivision curve, and the irregular rules are established through the Fourier analysis of the regular case. By analyzing the eigenstructures and characteristic maps, we show that the subdivision surfaces generated by this scheme is C¹ continuous up to valence 100. In addition, the curvature of regular region is bounded. Finally we demonstrate the visual quality of our subdivision scheme with several examples.     

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.     

A New Subdivision Strategy for Range Computations

We present a new subdivision strategy in interval analysis for computing the ranges of functions. We show through several real-world examples that the proposed subdivision strategy is more efficient than the widely used uniform and adaptive subdivision strategies of Moore (Methods and Applications of Interval Analysis, SIAM, Philadelphia, 1979).