基于顶点法向量约束的Catmull-Clark细分插值方法

提出一种基于顶点法向量约束实现插值的两步Catmull-Clark细分方法.第一步,通过改造型Catmull-Clark细分生成新网格.第二步,通过顶点法向量约束对新网格进行调整.两步细分分别运用渐进迭代方法和拉格朗日乘子法,使得极限曲面插值于初始控制顶点和法向量.实验结果证明了该方法可同时实现插值初始控制顶点和法向量,极限曲面具有较好的造型效果.     

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

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

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

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

Similarity based interpolation using Catmull–Clark subdivision surfaces

A new method for constructing a Catmull–Clark subdivision surface (CCSS) that interpolates the vertices of a given mesh with arbitrary topology is presented. The new method handles both open and closed meshes. Normals or derivatives specified at any vertices of the mesh (which can actually be anywhere) can also be interpolated. The construction process is based on the assumption that, in addition to interpolating the vertices of the given mesh, the interpolating surface is also similar to the limit surface of the given mesh. Therefore, construction of the interpolating surface can use information from the given mesh as well as its limit surface. This approach, called similarity based interpolation, gives us more control on the smoothness of the interpolating surface and, consequently, avoids the need of shape fairing in the construction of the interpolating surface. The computation of the interpolating surface’s control mesh follows a new approach, which does not require the resulting global linear system to be solvable. An approximate solution provided by any fast iterative linear system solver is sufficient. Nevertheless, interpolation of the given mesh is guaranteed. This is an important improvement over previous methods because with these features, the new method can handle meshes with large number of vertices efficiently. Although the new method is presented for CCSSs, the concept of similarity based interpolation can be used for other subdivision surfaces as well.     

Making Doo-Sabin surface interpolation always work over irregular meshes

This paper presents a reliable method for constructing a control mesh whose Doo-Sabin subdivision surface interpolates the vertices of a given mesh with arbitrary topology. The method improves on existing techniques in two respects: (1) it is guaranteed to always work for meshes of arbitrary topological type; (2) there is no need to solve a system of linear equations to obtain the control points. Extensions to include normal vector interpolation and/or shape adjustment are also discussed.     

Interpolation over arbitrary topology meshes using a two-phase subdivision scheme

The construction of a smooth surface interpolating a mesh of arbitrary topological type is an important problem in many graphics applications. This paper presents a two-phase process, based on a topological modification of the control mesh and a subsequent Catmull-Clark subdivision, to construct a smooth surface that interpolates some or all of the vertices of a mesh with arbitrary topology. It is also possible to constrain the surface to have specified tangent planes at an arbitrary subset of the vertices to be interpolated. The method has the following features: 1) it is guaranteed to always work and the computation is numerically stable, 2) there is no need to solve a system of linear equations and the whole computation complexity is O(K) where K is the number of the vertices, and 3) each vertex can be associated with a scalar shape handle for local shape control. These features make interpolation using Catmull-Clark surfaces simple and, thus, make the new method itself suitable for interactive free-form shape design.     

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.     

隐式曲面重新多边形化

首先用Bloomenthal的多边形化算法生成一个粗糙的初始网格;然后在初始网格上分布若干个新顶点,新顶点可以均匀分布,也可以按曲率分布;再把初始网格上的老顶点和新顶点连接起来,生成一个中间网格,从中间网格上删除初始网格上的老顶点,得到重新多边形化的网格;最后细分这个网格．实验结果表明：该算法可以生成近似等边的、大小由曲率指导的三角网格．     

Polynomial splines over general T-meshes

The present authors have introduced polynomial splines over T-meshes (PHT-splines) and provided theories and applications for PHT-splines over hierarchical T-meshes. This paper generalizes PHT-splines to arbitrary topology over general T-meshes with any structures (GPT-splines). GPT-spline surfaces can be constructed through a unified scheme to interpolate the local geometric information at the basis vertices of the T-mesh. We also discuss general edge insertion and removal algorithms for GPT-splines. As applications, we present algorithms to construct a GPT-spline surface from a quadrilateral mesh and to simplify a tensor-product B-spline surface into a GPT-spline surface with superfluous edges removal.     

Vertex location optimisation for improved remeshing

Remeshing aims to produce a more regular mesh from a given input mesh, while representing the original geometry as accurately as possible. Many existing remeshing methods focus on where to place new mesh vertices; these samples are placed exactly on the input mesh. However, considering the output mesh as a piecewise linear approximation of some geometry, this simple scheme leads to significant systematic error in non-planar regions. Here, we use parameterised meshes and the recent mathematical development of orthogonal approximation using Sobolev-type inner products to develop a novel sampling scheme which allows vertices to lie in space near the input surface, rather than exactly on it. The algorithm requires little extra computational effort and can be readily incorporated into many remeshing approaches. Experimental results show that on average, approximation error can be reduced by 40% with the same number of vertices.     

Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains

Semi-regular meshes describe surface models that exhibit a structural regularity that facilitates many geometric processing algorithms. We introduce a technique to construct semi-regular, quad-only meshes from input surface meshes of arbitrary polygonal type and genus. The algorithm generates a quad-only model through subdivision of the input polygons, then simplifies to a base domain that is homeomorphic to the original mesh. During the simplification, a novel hierarchical mapping method, keyframe mapping , stores specific levels-of-detail to guide the mapping of the original vertices to the base domain. The algorithm implements a scheme for refinement with adaptive resampling of the base domain and backward projects to the original surface. As a byproduct of the remeshing scheme, a surface parameterization is associated with the remesh vertices to facilitate subsequent geometric processing, i.e. texture mapping, subdivision surfaces and spline-based modeling.     

A Colour Interpolation Scheme for Topologically Unrestricted Gradient Meshes

Gradient meshes are a 2D vector graphics primitive where colour is interpolated between mesh vertices. The current implementations of gradient meshes are restricted to rectangular mesh topology. Our new interpolation method relaxes this restriction by supporting arbitrary manifold topology of the input gradient mesh. Our method is based on the Catmull‐Clark subdivision scheme, which is well‐known to support arbitrary mesh topology in 3D. We adapt this scheme to support gradient mesh colour interpolation, adding extensions to handle interpolation of colours of the control points, interpolation only inside the given colour space and emulation of gradient constraints seen in related closed‐form solutions. These extensions make subdivision a viable option for interpolating arbitrary‐topology gradient meshes for 2D vector graphics.     

二次B样条曲面顶点及法向插值

顶点位置插值是自由曲面造型的基本方法,法向插值在一些CAD／CAM系统中也有重要应用,文中利用子分曲面理论研究双二次B样条曲面的性质,在此基础上利用Doo-Sabin分子模式构造插值顶点位置和法向的双二次B样条曲面控制网络,得到插值曲面的参数表示,为了提高效率,对规模较大的网络数据,先把它成若干片子网格,分别求出满足子网格相关的插值条件的控制网格,最后再反它们整合在一起形成完整的控制网格,使得相应的二次B样条曲面插值所有顶点及法向。     

Polynomial surfaces interpolating arbitrary triangulations

Triangular Bezier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous triangular Bezier patches of degree five. The resulting surface has an explicit closed form representation and is defined locally. In this paper, we introduce a new method for visually smooth interpolation of arbitrary triangle meshes based on a regular 4-split of the domain triangles. Ensuring tangent plane continuity of the surface is not enough for producing an overall fair shape. Interpolation of irregular control-polygons, be that in 1D or in 2D, often yields unwanted undulations. Note that this undulation problem is not particular to parametric interpolation, but also occurs with interpolatory subdivision surfaces. Our new method avoids unwanted undulations by relaxing the constraint of the first derivatives at the input mesh vertices: The tangent directions of the boundary curves at the mesh vertices are now completely free. Irregular triangulations can be handled much better in the sense that unwanted undulations due to flat triangles in the mesh are now avoided.     

支持STL数据源的网格曲面动态空间索引

针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R^*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。     

渐进插值的LOOP曲面细分*

目前很多细分方法都存在不能用同一种方法处理封闭网格和开放网格的问题。对此,一种新的基于插值技术的LOOP曲面细分方法,其主要思想就是给定一个初始三角网格M,反复生成新的顶点,新顶点是通过其相邻顶点的约束求解得到的,从而构造一个新的控制网格M,在取极限的情况下,可以证明插值过程是收敛的;因为生成新顶点使用的是与其相连顶点的约束求解得到的,本质上是一种局部方法,所以,该方法很容易定义。它在本地方法和全局方法中都有优势,能处理任意顶点数量和任意拓扑结构的网格,从而产生一个光滑的曲面并忠实于给定曲面的形状,其控制     

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.     

A non-stationary subdivision scheme for the construction of deformable models with sphere-like topology

We present an affine-invariant non-stationary subdivision scheme for the recursive refinement of any triangular mesh that is regular or has extraordinary vertices of valence 4. In particular, when applied to an arbitrary convex octahedron, it produces a G¹-continuous surface with a blob-like shape as the limit of the recursive subdivision process. In case of a regular octahedron, the subdivision process provides an accurate representation of ellipsoids. Our scheme allows us to easily construct a new interactive 3D deformable model for use in the delineation of biomedical images, which we illustrate by examples that deal with the characterization of 3D structures with sphere-like topology such as embryos, nuclei, or brains.     

基于三角片拼合的STL网格模型重建算法

采用三角片拼合的方法递增建立网格模型,新增三角片被归纳为5种类型.首先通过半边匹配确定新增三角片的类型;然后针对每一种类型使用不同的方法去除冗余顶点,并同时建立拓扑关系;最后通过顶点数组紧缩消除顶点空隙,将半边hash表转化为半边数组,完成网格模型的重建.该模型为改进的半边结构,具有完整的形状和拓扑信息,可以表示非流形边,是法矢调整、网格分块等后续处理的理想起点.实验结果表明,文中算法高效、鲁棒、可扩展.     

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.