一种带噪声的密集三角网格细分曲面拟合算法

实现了一个从带噪声的密集三角形拟合出带尖锐特征的细分曲面拟合系统.该系统包括了一种改进的基于图像双边滤波器的网格噪声去除方法,模型的尖锐特征提取以及保持尖锐特征的网格简化和拓扑优化.为了处理局部细节特征和模型数据量问题,提出了自适应细分方法,并将根据给定精度估计最少细分深度引入到细分曲面拟合系统中,使得拟合得到的细分曲面模型具有良好的细节特征和数据量小等特点.大量3D模型实验结果和实际工程应用结果表明了该细分曲面拟合系统的有效性.     

A direct approach for subdivision surface fitting from a dense triangle mesh

This article presents a new and direct approach for fitting a subdivision surface from an irregular and dense triangle mesh of arbitrary topological type. All feature edges and feature vertices of the original mesh model are first identified. A topology- and feature-preserving mesh simplification algorithm is developed to further simplify the dense triangle mesh into a coarse mesh. A subdivision surface with exactly the same topological structure and sharp features as that of the simplified mesh is finally fitted from a subset of vertices of the original dense mesh. During the fitting process, both the position masks and subdivision rules are used for setting up the fitting equation. Some examples are provided to demonstrate the proposed approach.     

Conjugate-Gradient Progressive-Iterative Approximation for Loop and Catmull-Clark Subdivision Surface Interpolation

Loop and Catmull-Clark are the most famous approximation subdivision schemes, but their limit surfaces do not interpolate the vertices of the given mesh. Progressive-iterative approximation (PIA) is an efficient method for data interpolation and has a wide range of applications in many fields such as subdivision surface fitting, parametric curve and surface fitting among others. However, the convergence rate of classical PIA is slow. In this paper, we present a new and fast PIA format for constructing interpolation subdivision surface that interpolates the vertices of a mesh with arbitrary topology. The proposed method, named Conjugate-Gradient Progressive-Iterative Approximation (CG-PIA), is based on the Conjugate-Gradient Iterative algorithm and the Progressive Iterative Approximation (PIA) algorithm. The method is presented using Loop and Catmull-Clark subdivision surfaces. CG-PIA preserves the features of the classical PIA method, such as the advantages of both the local and global scheme and resemblance with the given mesh. Moreover, CG-PIA has the following features. 1) It has a faster convergence rate compared with the classical PIA and W-PIA. 2) CG-PIA avoids the selection of weights compared with W-PIA. 3) CG-PIA does not need to modify the subdivision schemes compared with other methods with fairness measure. Numerous examples for Loop and Catmull-Clark subdivision surfaces are provided in this paper to demonstrate the efficiency and effectiveness of CG-PIA.     

带尖锐特征的Loop细分曲面拟合系统

实现了一个基于带尖锐特征的Loop细分曲面的三角网格拟合系统,其基本原理来自文献,但在系统设计层面对原算法作了相当大的补充和完善．整个系统框架包括尖锐特征提取、保持尖锐特征的三角网格简化、保持尖锐特征的网格平滑和拓扑优化、基于最近点策略的重采样和线性拟合系统求解．所得到的拟合曲面质量较原来的结果有了显著提高。     

形状可调的Loop 细分曲面渐进插值方法

针对Loop 细分无法调整形状与不能插值的问题,提出了一种形状可调的Loop 细分 曲面渐进插值方法。首先给出了一个既能对细分网格顶点统一调整又便于引入权因子实现细分曲 面形状可调的等价Loop 细分模板。其次,通过渐进迭代调整初始控制网格顶点生成新网格,运 用本文的两步Loop 细分方法对新网格进行细分,得到插值于初始控制顶点的形状可调的Loop 细分曲面。最后,证明了该方法的收敛性,并给出实例验证了该方法的有效性。     

细分曲面拟合的局部渐进插值方法

逼近型细分方法生成的细分曲面其品质要优于插值型细分方法生成的细分曲面.然而,逼近型细分方法生成的细分曲面不能插值于初始控制网格顶点.为使逼近型细分曲面具有插值能力,一般通过求解全局线性方程组,使其插值于网格顶点.当网格顶点较多时,求解线性方程组的计算量很大,因此,难以处理稠密网格.与此不同,在不直接求解线性方程组的情况下,渐进插值方法通过迭代调整控制网格顶点,最终达到插值的效果.渐进插值方法可以处理稠密的任意拓扑网格,生成插值于初始网格顶点的光滑细分曲面.并且经证明,逼近型细分曲面渐进插值具有局部性质,也就是迭代调整初始网格的若干控制顶点,且保持剩余顶点不变,最终生成的极限细分曲面仍插值于初始网格中被调整的那些顶点.这种局部渐进插值性质给形状控制带来了更多的灵活性,并且使得自适应拟合成为可能.实验结果验证了局部渐进插值的形状控制以及自适应拟合能力.     

Surface interpolation of meshes by geometric subdivision

Subdivision surfaces are generated by repeated approximation or interpolation from initial control meshes. In this paper, two new non-linear subdivision schemes, face based subdivision scheme and normal based subdivision scheme, are introduced for surface interpolation of triangular meshes. With a given coarse mesh more and more details will be added to the surface when the triangles have been split and refined. Because every intermediate mesh is a piecewise linear approximation to the final surface, the first type of subdivision scheme computes each new vertex as the solution to a least square fitting problem of selected old vertices and their neighboring triangles. Consequently, sharp features as well as smooth regions are generated automatically. For the second type of subdivision, the displacement for every new vertex is computed as a combination of normals at old vertices. By computing the vertex normals adaptively, the limit surface is G¹ smooth. The fairness of the interpolating surface can be improved further by using the neighboring faces. Because the new vertices by either of these two schemes depend on the local geometry, but not the vertex valences, the interpolating surface inherits the shape of the initial control mesh more fairly and naturally. Several examples are also presented to show the efficiency of the new algorithms.     

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样条细分矩阵的特征结构进行分析,将细分模式转换到其特征空间,给出了带尖锐特征的B样条细分曲线的参数化形式。并用于处理带尖锐特征的光滑曲线拟合问题。以曲率极大点作为初始拟合点。利用推导的参数化公式构造曲线的尖锐部分并方便误差估计。拟合点为曲线段端点,误差估计时不仅优化计算速度,而且在曲线分支距离过近或自交情况下避免错误匹配。     

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.     

Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization

We propose a method for mapping polynomial volumes. Given a closed surface and an initial template volume grid, our method deforms the template grid by fitting its boundary to the input surface while minimizing a volume distortion criterion. The result is a point‐to‐point map distorting linear cells into curved ones. Our method is based on several extensions of Voronoi Squared Distance Minimization (VSDM) combined with a higher‐order finite element formulation of the deformation energy. This allows us to globally optimize the mapping without prior parameterization. The anisotropic VSDM formulation allows for sharp and semi‐sharp features to be implicitly preserved without tagging. We use a hierarchical finite element function basis that selectively adapts to the geometric details. This makes both the method more efficient and the representation more compact. We apply our method to geometric modeling applications in computer‐aided design and computer graphics, including mixed‐element meshing, mesh optimization, subdivision volume fitting, and shell meshing.     

A robust feature-preserving semi-regular remeshing method for?triangular meshes

Benefited from the hierarchical representations, 3D models generated by semi-regular remeshing algorithms based on either global parameterization or normal displacement have more advantages for digital geometry processing applications than the ones produced from traditional isotropic remeshing algorithms. Nevertheless, while original models have sharp features or multiple self-intersecting surfaces, it is still a challenge for previous algorithms to produce a semi-regular mesh with sharp features preservation as well as high mesh regularity. Therefore, this study proposes a robust semi-regular remeshing algorithm that uses a two-step surface segmentation scheme to build the high quality base mesh, as well as the regional relationship between the original surface and subdivision domain surface. Using the regional relationship, the proposed algorithm substantially enhances the accuracy and robustness of the backward projection process of subdivision vertices based on normal displacement. Furthermore, the mesh regularity of remeshed models is improved by the quadric mesh relaxation scheme. The experimental results demonstrate the capabilities of the proposed algorithm’s semi-regular remeshing to preserve geometric features and have good triangle aspect ratio.     

Loop细分曲面的优化拟合算法

提出一种用于构造给定三维模型的拟合Loop细分曲面的迭代优化算法,使得拟合曲面与原始模型之间的逼近误差最小.算法中的逼近误差定义为原始模型各面元到拟合曲面最小距离的积分.与Loop细分小波分解算法的比较表明,该算法以适度的运行时间代价得到了更优的结果.此外,该算法还可以加以推广,作为一类从输入模型生成其近似表示的优化算法的基础.     

Subdivision surfaces for CAD—an overview

Subdivision surfaces refer to a class of modelling schemes that define an object through recursive subdivision starting from an initial control mesh. Similar to B-splines, the final surface is defined by the vertices of the initial control mesh. These surfaces were initially conceived as an extension of splines in modelling objects with a control mesh of arbitrary topology. They exhibit a number of advantages over traditional splines. Today one can find a variety of subdivision schemes for geometric design and graphics applications. This paper provides an overview of subdivision surfaces with a particular emphasis on schemes generalizing splines. Some common issues on subdivision surface modelling are addressed. Several key topics, such as scheme construction, property analysis, parametric evaluation and subdivision surface fitting, are discussed. Some other important topics are also summarized for potential future research and development. Several examples are provided to highlight the modelling capability of subdivision surfaces for CAD applications.     

基于形状控制的细分曲面的局部渐进插值方法

提出一种基于形状控制的 Catmull-Clark 细分曲面构造方法,实现局部插值任意拓扑的四边形网格顶点。首先该方法利用渐进迭代逼近方法的局部性质,在初始网格中选取若干控制顶点进行迭代调整,保持其他顶点不变,使得最终生成的极限细分曲面插值于初始网格中的被调整点;其次该方法的 Catmull-Clark 细分的形状控制建立在两步细分的基础上,第一步通过对初始网格应用改造的 Catmull-Clark 细分产生新的网格,第二步对新网格应用 Catmull-Clark 细分生成极限曲面,改造的 Catmull-Clark 细分为每个网格面加入参数值,这些参数值为控制局部插值曲面的形状提供了自由度。证明了基于形状控制的 Catmull-Clark 细分局部渐进插值方法的收敛性。实验结果验证了该方法可同时实现局部插值和形状控制。     

非均匀B样条曲面顶点及法向插值

本文以非均匀Catmull-Clark细分模式下的轮廓删除法为基础,通过在细分网格中定义模板并调整细分网格的顶点位置,为非均匀B样条曲面顶点及法向插值给出了一个有效的方法．该细分网格由待插顶点形成的网格细分少数几次而获得．细分网格的顶点被分为模板内的顶点和自由顶点．各个模板内的顶点通过构造优化模型并求解进行调整,自由顶点用能量优化法确定．这一方法不仅避免了求解线性方程组得到控制顶点的过程,而且在调整顶点的同时也兼顾了曲面的光顺性．     

Interpolation by geometric algorithm

We present a novel geometric algorithm to construct a smooth surface that interpolates a triangular or a quadrilateral mesh of arbitrary topological type formed by n vertices. Although our method can be applied to B-spline surfaces and subdivision surfaces of all kinds, we illustrate our algorithm focusing on Loop subdivision surfaces as most of the meshes are in triangular form. We start our algorithm by assuming that the given triangular mesh is a control net of a Loop subdivision surface. The control points are iteratively updated globally by a simple local point-surface distance computation and an offsetting procedure without solving a linear system. The complexity of our algorithm is O(mn) where n is the number of vertices and m is the number of iterations. The number of iterations m depends on the fineness of the mesh and accuracy required.     

A general framework for analysis and comparison of surface mesh optimization techniques

Many different algorithms for surface mesh optimization (including smoothing, remeshing, simplification and subdivision), each giving different results, have recently been proposed. All these approaches affect vertices of the mesh. Vertex coordinates are modified, new vertices are added and some original ones are removed, with the result that the shape of the original surface is changed. The important question is how to evaluate the differences in shape between the input and output models. In this paper, we present a novel and versatile framework for analysis of various mesh optimization algorithms in terms of shape preservation. We depart from the usual strategy by measuring the changes in the approximated smooth surfaces rather than in the corresponding meshes. The proposed framework consists of two error metrics: normal-based and physically based. We demonstrate that our metrics allow more subtle changes in shape to be captured than is possible with some commonly used measures. As an example, the proposed tool is used to compare three different techniques, reflecting basic ideas on how to solve the surface mesh improvement problem.     

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.     

Non-Uniform Subdivision Surfaces with Sharp Features

Sharp features are important characteristics in surface modelling. However, it is still a significantly difficult task to create complex sharp features for Non-Uniform Rational B-Splines compatible subdivision surfaces. Current non-uniform subdivision methods produce sharp features generally by setting zero knot intervals, and these sharp features may have unpleasant visual effects. In this paper, we construct a non-uniform subdivision scheme to create complex sharp features by extending the eigen-polyhedron technique. The new scheme allows arbitrarily specifying sharp edges in the initial mesh and generates non-uniform cubic B-spline curves to represent the sharp features. Experimental results demonstrate that the present method can generate visually more pleasant sharp features than other existing approaches.