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.     

Out-of-Core remeshing of large polygonal meshes

We propose an out-of-core method for creating semi-regular surface representations from large input surface meshes. Our approach is based on a streaming implementation of the MAPS remesher of Lee et al. [18]. Our remeshing procedure consists of two stages. First, a simplification process is used to obtain the base domain. During simplification, we maintain the mapping information between the input and the simplified meshes. The second stage of remeshing uses the mapping information to produce samples of the output semi-regular mesh. The out-of-core operation of our method is enabled by the synchronous streaming of a simplified mesh and the mapping information stored at the original vertices. The synchronicity of two streaming buffers is maintained using a specially designed write strategy for each buffer. Experimental results demonstrate the remeshing performance of the proposed method, as well as other applications that use the created mapping between the simplified and the original surface representations.     

四边形网格的去边细分方法

提出一种四边形网格细分算法：每细分一次四边形网格，其数目增加为原来的两倍，细分二次结果相当于一次二分细分和一个旋转．该算法采用三次B样条张量积的形式，其生成曲面在规则点具有C^2连续性，在非规则点具有C^1连续性．由于该细分算法对网格几何操作简单，所得网格数据量增长相对缓慢，适合于3D图像重构及网络传输等应用领域。     

Progressive Interpolation based on Catmull‐Clark Subdivision Surfaces

We introduce a scheme for constructing a Catmull‐Clark subdivision surface that interpolates the vertices of a quadrilateral mesh with arbitrary topology. The basic idea here is to progressively modify the vertices of an original mesh to generate a new control mesh whose limit surface interpolates all vertices in the original mesh. The scheme is applicable to meshes with any size and any topology, and it has the advantages of both a local scheme and a global scheme.     

基于Catmull-Clark细分的新细分算法的研究

提出一种四边形网格细分算法：每细分一次四边形网格,其数目增加为原来的两倍,细分二次结果相当于一次二分细分,采用边数缓慢增长的策略,使生成的曲面光滑连续。该算法生成曲面在规则点具有C2连续性,在非规则点具有C1连续性。该算法对网格几何操作简单,所得网格数据量增长相对缓慢,适合3D图像重构及网络传输等应用领域。由于文中细分算法对初始网格的拓扑变更,因此第一次细分会产生扭曲现象,但后面的细分会逐步光滑。     

A Shrink Wrapping Approach to Remeshing Polygonal Surfaces

Due to their simplicity and flexibility, polygonal meshes are about to become the standard representation for surface geometry in computer graphics applications. Some algorithms in the context of multiresolution representation and modeling can be performed much more efficiently and robustly if the underlying surface tesselations have the special subdivision connectivity. In this paper, we propose a new algorithm for converting a given unstructured triangle mesh into one having subdivision connectivity. The basic idea is to simulate the shrink wrapping process by adapting the deformable surface technique known from image processing. The resulting algorithm generates subdivision connectivity meshes whose base meshes only have a very small number of triangles. The iterative optimization process that distributes the mesh vertices over the given surface geometry guarantees low local distortion of the triangular faces. We show several examples and applications including the progressive transmission of subdivision surfaces.     

Fitting Sharp Features with Loop Subdivision Surfaces

Various methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.     

Localized Quadrilateral Coarsening

In this paper we introduce a coarsening algorithm for quadrilateral meshes that generates quality, quad-only connectivity during level-of- coarsening creation. A novel aspect of this work is development and implementation of a localized adaptation of the polychord collapse operator to better control and preserve important surface components. We describe a novel weighting scheme for automatic deletion selection that considers surface attributes, as well as localized queue updates that allow for improved data structures and computational performance opportunities over previous techniques. Additionally, this work supports optional and intuitive user controls for tailored simplification results.     

Filling N-Sided Regions by Quad Meshes for Subdivision Surfaces

Given an n-sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad-based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.     

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

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

Generalized B-spline subdivision-surface wavelets for geometry compression

We present a new construction of lifted biorthogonal wavelets on surfaces of arbitrary two-manifold topology for compression and multiresolution representation. Our method combines three approaches: subdivision surfaces of arbitrary topology, B-spline wavelets, and the lifting scheme for biorthogonal wavelet construction. The simple building blocks of our wavelet transform are local lifting operations performed on polygonal meshes with subdivision hierarchy. Starting with a coarse, irregular polyhedral base mesh, our transform creates a subdivision hierarchy of meshes converging to a smooth limit surface. At every subdivision level, geometric detail is expanded from wavelet coefficients and added to the surface. We present wavelet constructions for bilinear, bicubic, and biquintic B-spline subdivision. While the bilinear and bicubic constructions perform well in numerical experiments, the biquintic construction turns out to be unstable. For lossless compression, our transform is computed in integer arithmetic, mapping integer coordinates of control points to integer wavelet coefficients. Our approach provides a highly efficient and progressive representation for complex geometries of arbitrary topology.     

Adaptive and Feature-Preserving Subdivision for High-Quality Tetrahedral Meshes

We present an adaptive subdivision scheme for unstructured tetrahedral meshes inspired by the       -subdivision scheme for triangular meshes. Existing tetrahedral subdivision schemes do not support adaptive refinement and have traditionally been driven by the need to generate smooth three-dimensional deformations of solids. These schemes use edge bisections to subdivide tetrahedra, which generates octahedra in addition to tetrahedra. To split octahedra into tetrahedra one routinely chooses a direction for the diagonals for the subdivision step. We propose a new topology-based refinement operator that generates only tetrahedra and supports adaptive refinement. Our tetrahedral subdivision algorithm is motivated by the need to have one representation for the modeling, the simulation and the visualization and so to bridge the gap between CAD and CAE. Our subdivision algorithm design emphasizes on geometric quality of the tetrahedral meshes, local and adaptive refinement operations, and preservation of sharp geometric features on the boundary and in the interior of the physical domain.     

Some applications of Loop-subdivision wavelet tight frames to?the?processing of 3D graphics

Multiresolution analysis based on subdivision wavelets is an important method of 3D graphics processing. Many applications of this method have been studied and developed, including denoising, compression, progressive transmission, multiresolution editing and so on. Recently Charina and St?ckler firstly gave the explicit construction of wavelet tight frame transform for subdivision surfaces with irregular vertices, which made its practical applications to 3D graphics became a subject worthy of investigation. Based on the works of Charina and St?ckler, we present in detail the wavelet tight frame decomposition and reconstruction formulas for Loop-subdivision scheme. We further implement the algorithm and apply it to the denoising, compression and progressive transmission of 3D graphics. By comparing it with the biorthogonal Loop-subdivision wavelets of Bertram, the numerical results illustrate the good performance of the algorithm. Since multiresolution analysis based on subdivision wavelets or subdivision wavelet tight frames requires the input mesh to be semi-regular, we also propose a simple remeshing algorithm for constructing meshes which not only have subdivision connectivity but also approximate the input mesh.     

用逼近型√3细分方法构造闭三角网格的插值曲面

为了避免用逼近型3~(1/2)细分方法构造插值曲面过程中出现的烦琐运算,利用3细分方法极限点计算公式,提出一种用逼近型3~(1/2)细分方法构造闭三角网格插值曲面的方法.给定待插值的闭三角网格,先用一个新的几何规则与原3~(1/2)细分方法的拓扑规则细分一次得到一个初始网格,用3~(1/2)细分方法细分该初始网格得到插值曲面;新几何规则根据极限点公式确定,保证了初始网格的极限曲面插值待插值的三角网格.由于初始网格的顶点仅与待插值顶点2邻域内的点相关,所以插值曲面具有良好的局部性,即改变一个待插值点的位置时,只影响插值曲面在其附近的形状.该方法中只有确定初始网格顶点的几何规则与原3细分方法不同,故易于整合到原有的细分系统中.实验结果表明,该方法具有计算简单、有充分的自由度调整插值曲面的形状等特点,使得利用3~(1/2)细分方法构造三角网格的插值曲面变得极其简单.     

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.     

Efficient skeleton-guided displaced subdivision surfaces

Displacement mapping is a computer graphics technique that uses scalar offsets along normals on a base surface to represent and render a model with highly geometric details. The technique natively compresses the model and saves memory I/O. A subdivision surface is the ideal base surface, due to its good geometric properties, such as arbitrary topology, global smoothness, and multi-resolution via hardware tessellation, among others. Two of the main challenges in displacement mapping representation are constructing the base surface faithfully and generating displacement maps efficiently. In this paper, we propose an efficient skeleton-guided displaced subdivision surfaces method. The construction of the base mesh is guided by a sketched skeleton. To make the shape of the base surface fit the input model well, we develop an efficient progressive GPU-based subdivision fitting method. Finally, a GPU-based raycasting method is proposed to sample the input model and generate the displacement maps. The experimental results demonstrate that the proposed method can efficiently generate a high-quality displacement mapping representation. Compared with the traditional displaced subdivision surface method, the proposed method is more suitable for the modern rendering pipeline and has higher efficiency.     

基于边折叠和质点-弹簧模型的网格简化优化算法

通过边折叠实现网格曲面简化，提出了保持曲面特征的边折叠基本规则，引入边折叠顺序控制因子λ，给出了折叠点坐标获取方法，简化过程中网格边长度趋于均匀．在曲面简化基础上，利用质点-弹簧模型优化网格形状．将网格顶点邻域参数化到二维域上，在质点-弹簧模型中引入约束弹簧，约束调整网格顶点，并逆映射到三维原始曲面上，局部优化网格顶点的相邻网格；调整曲面上所有网格顶点，在全局上优化网格形状．在曲面简化优化过程中，建立原始模型曲面和简化优化后曲面之间的双向映射关系；曲面的网格顶点始终在原始模型表面上滑动，并以双向Hausdorff距离衡量、控制曲面间的形状误差．应用实例表明：文中算法稳定、高效，适合于任意复杂的二维流形网格．     

Progressive Lossless Mesh Compression Via Incremental Parametric Refinement

In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.     

基于逆3 细分的渐进网格生成算法研究

提出一种基于逆3 细分的渐进网格生成算法,用于解决图形的快速传输和显示问 题。算法的基本思路是：将细密网格通过边折叠操作得到简化网格,以细分极限点逼近原始网 格为准则进行网格调整,采用3 细分得到高密度网格,调整后进行逆3 细分,即逐层次删除 部分顶点,生成用于重构渐进网格模型的基网格,并记录每层删除顶点在采用本层表示时相对 于细分计算位置的几何调整量。3 细分过程中三角片数量增长速度较慢,采用逆3 细分利于 生成多层次的渐进网格,经实例验证,逆3 细分生成渐进网格的效果能满足快速、多分辨率显 示要求。     

渐进网格及其在移动计算中的应用

在移动计算中,3维图形通常是由几何造型的网格来表示。为了解决移动图形的存储、传输和显示问题,提出了一种基于逆细分的构建渐进网格的算法,给出了渐进网格通过网格传输和在移动终端上渲染3维图形的方法。细密的网格通过逐层地、分批地删除其冗余信息,最后生成由基网格和一系列误差值组成的渐进网格。在算法实施时,将Loop逼近型细分模式作为插值型细分模式进行操作。该算法共分3个关键步骤:网格分裂、奇点预测、网格更新。简化后的渐进网格可以无损还原。实验结果表明,该算法效率高,比以往的方法速度快。