隐式曲面的多分辨率法向网格逼近

法向网格是一种新型的曲面多分辨率描述方式，其中每个层次都可以表示为其前一个粗糙层次的法向偏移．文中提出一种基于法向网格表示的隐式曲面多分辨率网格逼近算法．首先通过基于空间剖分技术的多边形化算法获得隐式曲面的粗糙逼近网格，并利用网格均衡化方法对粗糙网格进行优化，消除其中的狭长三角形；然后利用法向细分规则迭代地对网格中的三角面片进行细分，并利用区间算术技术沿法向方向对隐式曲面进行逼近．最终生成的隐式曲面分片线性逼近网格为法向网格．该逼近网格为隐式曲面提供了一种多分辨率表示，网格具有细分连通性，其数据量较传统的多边形化算法所生成的网格有大幅度的压缩．该算法可用于隐式曲面的多级绘制、累进传输及相关数字几何处理．     

Polygonization of implicit surfaces with sharp features by edge-spinning

This paper presents an adaptive approach for polygonization of implicit surfaces. The algorithm generates a well-shaped triangular mesh with respect to a given approximation error. The error is proportional to a local surface curvature estimation. Polygonization of surfaces of high curvature, as well as surfaces with sharp features, is possible using a simple technique combined with a particle system approach. The algorithm is based on a surface tracking scheme, and it is compared with other algorithms based on a similar principle, such as the marching cube and the marching triangle algorithms.     

Variational implicit surface meshing

In this paper, we propose a new algorithm to mesh implicit surfaces which produces meshes both with a good triangle aspect ratio as well as a good approximation quality. The number of vertices of the output mesh is defined by the end-user. For this goal, we perform a two-stage processing: an initialization step followed by an iterative optimization step. The initialization step consists in capturing the surface topology and allocating the vertex budget. The optimization algorithm is based on a variational vertices relaxation and triangulation update. In addition a gradation parameter can be defined to adapt the mesh sampling to the curvature of the implicit surface. We demonstrate the efficiency of the approach on synthetic models as well as real-world acquired data, and provide comparisons with previous approaches.     

离散三角网格模型顶点法矢量估算

提出一种新的三角网格模型顶点法矢估算方法,采用以三角网格顶点一阶邻域三角形的形状因子与顶点到三角形质心距进行综合加权的方法。同时指出：在同等三角网格曲面,随着三角网格划分精度的提升,网格顶点法矢估算精度有增大趋势;在同等网格划分精度条件下,对于平均曲率小以及平均曲率变化率小的三角网格模型,其网格顶点法矢估算精度也有增大趋势。实例计算和误差分析表明,该方法的计算结果更为精确合理。     

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.     

一种基于不平滑度的网格简化算法

在三维建模中,一个物体的网格模型常常包含数以百万计的三角形面片,给模型的存储、绘制、渲染、传输及交互处理带来诸多不便。提出一种三角形折叠法,计算各个顶点的不平滑度,基于顶点不平滑度确定各三角形的权值,并对符合折叠要求的三角形求解折叠后新顶点的位置及累积不平滑度,通过实例验证证明该算法在简化网格时能较好地保持模型整体特征。     

The sharp upper bound on the distance between a parametric patch and its interpolated triangle

In computer aided geometric design （CAGD） and computer graphics, it is a general manipulation to approximate a surface by triangulation mesh. Thus a key problem is to estimate the error of the approximation. So far, many papers have given various estimate bounds of the distance between a parametric patch of a C2 surface and an arbitrary triangle whose vertices are on the patch, but these estimates are all imperfect, some of them have large error, some of them have complicated representation formulae. By using a succinct new method, a sharp upper estimate of the maximum distance between a patch and a triangle is obtained and a strict proof is given. This is very valuable for CAGD.     

Obtuse triangle suppression in anisotropic meshes

Anisotropic triangle meshes are used for efficient approximation of surfaces and flow data in finite element analysis, and in these applications it is desirable to have as few obtuse triangles as possible to reduce the discretization error. We present a variational approach to suppressing obtuse triangles in anisotropic meshes. Specifically, we introduce a hexagonal Minkowski metric, which is sensitive to triangle orientation, to give a new formulation of the centroidal Voronoi tessellation (CVT) method. Furthermore, we prove several relevant properties of the CVT method with the newly introduced metric. Experiments show that our algorithm produces anisotropic meshes with much fewer obtuse triangles than using existing methods while maintaining mesh anisotropy.     

Approximating isosurfaces by guaranteed-quality triangular meshes

We describe a new method for approximating an implicit surface F by a piecewise-flat triangulated surface whose triangles are as close as possible to equilateral. The main advantage is improved mesh quality which is guaranteed for smooth surfaces. The GradNormal algorithm generates a triangular mesh that gives a piecewise-differentiable approximation of F, with angles between 35.2 and 101.5 degrees. As the mesh size approaches 0, the mesh converges to F through surfaces that are isotopic to F.     

用内法向量与二次误差度量修补三角网格孔洞

为了高效地修复含孔洞的三角网格模型,提出基于内法向量与二次误差度量(QEM)的孔洞修补算法.在识别孔洞边界之后,计算边界点的凹凸性与对应夹角角度,并利用最小角-曲率原则寻找最优修补点;根据三角形生成原则以及内法向计算方法生成新的三角形完成粗修补;最后利用二次型误差滤波函数对粗修补的网格进行优化处理.在VisualStudio2013环境下,对不同种类的含孔洞模型,利用提出算法以及孔洞修补经典算法进行实验,结果表明,文中算法修补的网格质量优于对比算法.     

Approximating digital 3D shapes by rational Gaussian surfaces

A method for approximating spherical topology digital shapes by rational Gaussian (RaG) surfaces is presented. Points in a shape are parametrized by approximating the shape with a triangular mesh, determining parameter coordinates at mesh vertices, and finding parameter coordinates at shape points from interpolation of parameter coordinates at mesh vertices. Knowing the locations and parameter coordinates of the shape points, the control points of a RaG surface are determined to approximate the shape with a required accuracy. The process starts from a small set of control points and gradually increases the control points until the error between the surface and the digital shape reduces to a required tolerance. Both triangulation and surface approximation proceed from coarse to fine. Therefore, the method is particularly suitable for multiresolution creation and transmission of digital shapes over the Internet. Application of the proposed method in editing of 3D shapes is demonstrated.     

Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

Optimized surface discretization of functionally defined multi-material objects

We present in this paper an algorithm for meshing implicit surfaces based on the Delaunay triangulation of a point-set adaptively sampled on an implicit surface. To improve the quality of the resulting triangular mesh, we use at each iteration a mesh optimization algorithm with the following objectives: optimizing the connectivity, retrieving the sharp features, regularizing the triangles shapes and minimizing the approximation error. Then, we extend this algorithm in order to handle functionally defined heterogeneous object surfaces, while maintaining a good quality for the triangles’ shapes and the mesh features (geometrical sharp features and boundaries between different materials).     

反求工程中的隐式曲面快速自适应性多边形算法

论文给出一种反求工程中基于三角形细分的隐式曲面快速自适应性多边形化方法。该文先由输入的三维扫描数据点利用空间延展的MarchingCubes方法得到隐式曲面较为粗糙的三角形表面网格形状,再利用该文的自适应性优化方法对粗糙网格从三个方面自适应性调整,即调整网格顶点法向,控制曲率,再补偿网格抽样率。从而生成的三角网格和采样点具有局部适应性,能随着曲率的变化自动控制采样点的疏密程度,消除了逼近网格中的T-形边。实验表明,恢复的隐式曲面能很好地反映形状特征,能满足反求工程的实时需求。     

On marching cubes

A characterization and classification of the isosurfaces of trilinear functions is presented. Based upon these results, a new algorithm for computing a triangular mesh approximation to isosurfaces for data given on a 3D rectilinear grid is presented. The original marching cubes algorithm is based upon linear interpolation along edges of the voxels. The asymptotic decider method is based upon bilinear interpolation on faces of the voxels. The algorithm of this paper carries this theme forward to using trilinear interpolation on the interior of voxels. The algorithm described here will produce a triangular mesh surface approximation to an isosurface which preserves the same connectivity/separation of vertices as given by the isosurface of trilinear interpolation.     

A New QEM for Parametrization of Raster Images

We present an image processing method that converts a raster image to a simplical two‐complex which has only a small number of vertices (base mesh) plus a parametrization that maps each pixel in the original image to a combination of the barycentric coordinates of the triangle it is finally mapped into. Such a conversion of a raster image into a base mesh plus parametrization can be useful for many applications such as segmentation, image retargeting, multi‐resolution editing with arbitrary topologies, edge preserving smoothing, compression, etc. The goal of the algorithm is to produce a base mesh such that it has a small colour distortion as well as high shape fairness, and a parametrization that is globally continuous visually and numerically. Inspired by multi‐resolution adaptive parametrization of surfaces and quadric error metric, the algorithm converts pixels in the image to a dense triangle mesh and performs error‐bounded simplification jointly considering geometry and colour. The eliminated vertices are projected to an existing face. The implementation is iterative and stops when it reaches a prescribed error threshold. The algorithm is feature‐sensitive, i.e. salient feature edges in the images are preserved where possible and it takes colour into account thereby producing a better quality triangulation.     

隐式曲面的快速适应性多边形化算法

通过将隐式曲面多边形化过程分为“构造”和“适应性采样”两个阶段，实现了隐式曲面多边形逼近网格的适应性构造．通过基于空间延展的Marching Cubes方法得到隐式曲面较为粗糙的均匀多边形化逼近，根据曲面上的局部曲率分布，运用适应性细分规则对粗糙网格进行细分迭代，并利用梯度下降法将细分出的新顶点定位到隐式曲面上；最终得到的多边形网格是适应性的单纯复形网格，其在保持规定逼近精度的前提下，减少了冗余三角形的产生，网格质量有明显改善．该算法可用于隐式曲面的交互式可视化过程．     

An analytical representation of conformal mapping for genus-zero implicit surfaces and its application to surface shape similarity assessment

This paper develops an analytical representation of conformal mapping for genus-zero implicit surfaces based on algebraic polynomial functions, and its application to surface shape similarity assessment. Generally, the conformal mapping often works as a tool of planar or spherical parameterization for triangle mesh surfaces. It is further exploited for implicit surface matching in this study. The method begins with discretizing one implicit surface by triangle mesh, where a discrete harmonic energy model related to both the mesh and the other implicit surface is established based on a polynomial-function mapping. Then both the zero-center constraint and the landmark constraints are added to the model to ensure the uniqueness of mapping result with the Möbius transformation. By searching optimal polynomial coefficients with the Lagrange–Newton method, the analytical representation of conformal mapping is obtained, which reveals all global and continuous one-to-one correspondent point pairs between two implicit surfaces. Finally, a shape similarity assessment index for (two) implicit surfaces is proposed through calculating the differences of all the shape index values among those corresponding points. The proposed analytical representation method of conformal mapping and the shape assessment index are both verified by the simulation cases for the closed genus-zero implicit surfaces. Experimental results show that the method is effective for genus-zero implicit surfaces, which will offer a new way for object retrieval and manufactured surface inspection.     

逼近散乱点云数据的三角形网格精确剖分

基于自组织特征映射神经网络构建的三角形网格模型可以实现测量点云 压缩后的Delaunay 三角逼近剖分,但该模型存在逼近误差和边缘误差。为减小三角形网格 的逼近误差和边缘误差,构建了精确逼近的三角形网格模型。首先采用整个测量点云,对三 角形网格模型中的所有神经元进行整体训练;然后对三角形网格中的网格神经元的位置权 重,沿网格顶点法矢方向进行修正;最后采用测量点云中的边界点集,对三角形网格模型中 的网格边界神经元进行训练。算例表明,应用该模型,可以有效减小三角形网格的边缘误差, 三角形网格逼近散乱点云的逼近精度得到大幅提高并覆盖散乱点云整体分布范围。