一种保持特征的三角网格光顺方法

网格光顺是逆向工程中一种常用的数据处理手段,其主要目的是为了减少网格模型中的噪声,提高网格模型的质量。但网格上的一些特征常常会在光顺时丢失。如何在光顺时保持网格模型的特征成为提高光顺质量的一个关键问题。在实现常用光顺方法的基础上,该文提出了一种能较好保持网格特征的自适应光顺方法,通过对特征进行判断,根据网格顶点的不同性质对其采用不同的操作方法以达到光顺和保持特征的目的。     

Non-iterative approach for global mesh optimization

This paper presents a global optimization operator for arbitrary meshes. The global optimization operator is composed of two main terms, one part is the global Laplacian operator of the mesh which keeps the fairness and another is the constraint condition which reserves the fidelity to the mesh. The global optimization operator is formulated as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Our global mesh optimization approach can be effectively used in at least three applications: smoothing the noisy mesh, improving the simplified mesh, and geometric modeling with subdivision-connectivity. Many experimental results are presented to show the applicability and flexibility of the approach.     

Smoothing of optical flow using robustified diffusion kernels

This paper proposes a new optical flow smoothing methodology combining vector diffusion and robust statistics. Vector smoothing using diffusion preserves moving object boundaries and the main motion discontinuities. According to a study provided in the paper, diffusion does not remove the outliers but spreads them out, introducing a bias in the neighbourhood. In this paper robust statistics operators such as the median and alpha-trimmed mean are considered for robustifying the diffusion kernels. The robust diffusion smoothing process is extended to 3-D lattices as well. The proposed algorithms are applied for smoothing artificially generated vector fields as well as the optical flow estimated from image sequences.     

Hexahedral mesh smoothing via local element regularization and global mesh optimization

The quality of finite element meshes is one of the key factors that affect the accuracy and reliability of finite element analysis results. In order to improve the quality of hexahedral meshes, we present a novel hexahedral mesh smoothing algorithm which combines a local regularization for each hexahedral mesh, using dual element based geometric transformation, with a global optimization operator for all hexahedral meshes. The global optimization operator is composed of three main terms, including the volumetric Laplacian operator of hexahedral meshes and the geometric constraints of surface meshes which keep the volumetric details and the surface details, and another is the transformed node displacements condition which maintains the regularity of all elements. The global optimization operator is formulated as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Several experimental results are presented to demonstrate that our method obtains higher quality results than other state-of-the-art approaches.     

Mesh Parametrization Driven by Unit Normal Flow

Based on mesh deformation, we present a unified mesh parametrization algorithm for both planar and spherical domains. Our approach can produce intermediate frames from the original meshes to the targets. We derive and define a novel geometric flow: ‘unit normal flow (UNF)’ and prove that if UNF converges, it will deform a surface to a constant mean curvature (CMC) surface, such as planes and spheres. Our method works by deforming meshes of disk topology to planes, and spherical meshes to spheres. Our algorithm is robust, efficient, simple to implement. To demonstrate the robustness and effectiveness of our method, we apply it to hundreds of models of varying complexities. Our experiments show that our algorithm can be a competing alternative approach to other state-of-the-art mesh parametrization methods. The unit normal flow also suggests a potential direction for creating CMC surfaces.     

A Frequency-Domain Approach to Watermarking 3D Shapes

This paper presents a robust watermarking algorithm with informed detection for 3D polygonal meshes. The algorithm is based on our previous algorithm [ 22 ] that employs mesh‐spectral analysis to modify mesh shapes in their transformed domain. This paper presents extensions to our previous algorithm so that (1) much larger meshes can be watermarked within a reasonable time, and that (2) the watermark is robust against connectivity alteration (e.g., mesh simplification), and that (3) the watermark is robust against attacks that combine similarity transformation with such other attacks as cropping, mesh simplification, and smoothing. Experiment showed that our new watermarks are resistant against mesh simplification and remeshing combined with resection, similarity transformation, and other operations..     

任意拓扑结构网格模型自适应调整和光顺算法

在改进拉普拉斯算子的同时，吸取平均曲率法的优点，提出一种任意网格模型自适应调整和光顺算法．该算法通过沿法矢方向和在切平面上同时对网格顶点进行调整，保证了调整后模型不仅光顺，而且网格形状均匀；该算法还可以根据不同的精度自动地对网格调整进行控制，有效地保留了原始模型中的特征信息．应用实例表明，该算法可以保证在满足精度要求的条件下，得到更合理的三角网格模型．     

Efficient mesh optimization schemes based on Optimal Delaunay Triangulations

In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted L¹ norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.     

改进的三维ODT四面体网格质量优化算法

针对密度非均匀四面体网格,提出一种改进的三维ODT(optimal Delaunay triangulation)网格光顺算法,提高了ODT的适应性.在四面体网格中,以每一内部节点为核心节点,创建由与该节点相连接的四面体单元构成的星形结构;根据网格尺寸场把其星形结构转换到以核心点为中心的归一化空间内,然后在归一化空间内应用经典ODT光顺算法对核心点位置进行优化;通过中值重心坐标将核心点转换回物理空间;这样,通过逐一优化内部节点的空间位置达到优化四面体网格整体质量的目的.算例表明,该算法有效、健壮;对于密度非均匀的四面体网格,其光顺效果比经典的ODT算法更好.     

一种基于曲率流的网格平滑方法

文章通过从频域角度分析网格上的拉普拉斯平滑,提出网格上的一种基于曲率流的隐式平滑方法。实验结果表明,此算法具有良好的鲁棒性,适用于对不规则的大规模网格进行平滑。     

基于小波变换的3维网格水印

3维网格数据是不规则采样的数据集,传统的图像变换域水印算法不能直接应用到网格上.提出了一种小波变换域的鲁棒网格水印算法.该算法对半规则的多分辨率网格进行小波变换,得到一个基网格和一系列小波系数.在对小波系数的统计特性进行实验分析的基础上,选择在低频子带的小波系数中嵌入水印,并对小波系数的切向和法向分量设计了不同的嵌入强度,以减小几何失真.实验结果表明,该水印算法满足不可见性,并具有较强的鲁棒性.     

An automatic 3D mesh generation method for domains with multiple materials

This paper describes an automatic and efficient approach to construct unstructured tetrahedral and hexahedral meshes for a composite domain made up of heterogeneous materials. The boundaries of these material regions form non-manifold surfaces. In earlier papers, we developed an octree-based isocontouring method to construct unstructured 3D meshes for a single material (homogeneous) domain with manifold boundary. In this paper, we introduce the notion of a material change edge and use it to identify the interface between two or several different materials. A novel method to calculate the minimizer point for a cell shared by more than two materials is provided, which forms a non-manifold node on the boundary. We then mesh all the material regions simultaneously and automatically while conforming to their boundaries directly from volumetric data. Both material change edges and interior edges are analyzed to construct tetrahedral meshes, and interior grid points are analyzed for proper hexahedral mesh construction. Finally, edge-contraction and smoothing methods are used to improve the quality of tetrahedral meshes, and a combination of pillowing, geometric flow and optimization techniques is used for hexahedral mesh quality improvement. The shrink set of pillowing schemes is defined automatically as the boundary of each material region. Several application results of our multi-material mesh generation method are also provided.     

复杂开曲面的鲁棒布尔运算

在计算机辅助几何设计中,布尔运算是一种构造实体的常用方法。自从19 世纪 80 年代布尔运算被提出后,该方向的研究工作大多是在效率与鲁棒性间做权衡,为了保证输入 网格表示某个实体的边界,大部分算法严格要求其没有洞和边界边。故此提出一种与上不同的 高效的、鲁棒的适用广的布尔运算算法,其能在非实体网格上被执行。首先,将输入网格合并, 然后在解决合并出现的自交问题后,将网格沿着非流形边分割成许多不同的流形块,并且检测 出流形块所围成的胞体;然后通过添加虚拟流形块的方法计算胞体的环绕数,并标记胞体关于 输入网格的属性,从而得到正确的布尔运算结果。     

Winslow Smoothing on Two-Dimensional Unstructured Meshes

The Winslow equations from structured elliptic grid generation are adapted to smoothing of two-dimensional unstructured meshes using a finite difference approach. We use a local mapping from a uniform N-valent logical mesh to a local physical subdomain. Taylor Series expansions are then applied to compute the derivatives which appear in the Winslow equations. The resulting algorithm for Winslow smoothing on unstructured triangular and quadrilateral meshes gives generally superior qualilty than traditional Laplacian smoothing, while retaining the resistance to mesh folding on structured quadrilateral meshes.     

Bilateral recovering of sharp edges on feature-insensitive sampled meshes

A variety of computer graphics applications sample surfaces of 3D shapes in a regular grid without making the sampling rate adaptive to the surface curvature or sharp features. Triangular meshes that interpolate or approximate these samples usually exhibit relatively big error around the insensitive sampled sharp features. This paper presents a robust general approach conducting bilateral filters to recover sharp edges on such insensitive sampled triangular meshes. Motivated by the impressive results of bilateral filtering for mesh smoothing and denoising, we adopt it to govern the sharpening of triangular meshes. After recognizing the regions that embed sharp features, we recover the sharpness geometry through bilateral filtering, followed by iteratively modifying the given mesh's connectivity to form single-wide sharp edges that can be easily detected by their dihedral angles. We show that the proposed method can robustly reconstruct sharp edges on feature-insensitive sampled meshes.     

Mesh analysis using geodesic mean-shift

In this paper, we introduce a versatile and robust method for analyzing the feature space associated with a given mesh surface. The method is based on the mean-shift operator, which was shown to be successful in image and video processing. Its strength lies in the fact that it works in a single joint space of geometry and attributes called the feature-space. The mean-shift procedure works as a gradient ascend finding maxima of an estimated probability density function in feature-space. Our method for using the mean-shift technique on surfaces solves several difficulties. First, meshes as opposed to images do not present a regular and uniform sampling of domain. Second, on surface meshes the shifting procedure must be constrained to stay on the surface and preserve geodesic distances. We define a special local geodesic parameterization scheme, and use it to generalize the mean-shift procedure to unstructured surface meshes. Our method can support piecewise linear attribute definitions as well as piecewise constant attributes.     

Curvilinear Mesh Adaptation Using Radial Basis Function Interpolation and Smoothing

We present a new iterative technique based on radial basis function (RBF) interpolation and smoothing for the generation and smoothing of curvilinear meshes from straight-sided or other curvilinear meshes. Our technique approximates the coordinate deformation maps in both the interior and boundary of the curvilinear output mesh by using only scattered nodes on the boundary of the input mesh as data sites in an interpolation problem. Our technique produces high-quality meshes in the deformed domain even when the deformation maps are singular due to a new iterative algorithm based on modification of the RBF shape parameter. Due to the use of RBF interpolation, our technique is applicable to both 2D and 3D curvilinear mesh generation without significant modification.     

A Constrained Resampling Strategy for Mesh Improvement

In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state‐of‐the‐art.     

Template-based quadrilateral mesh generation from imaging data

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.     

Hierarchical Quad Meshing of 3D Scanned Surfaces

In this paper we present a novel method to reconstruct watertight quad meshes on scanned 3D geometry. There exist many different approaches to acquire 3D information from real world objects and sceneries. Resulting point clouds depict scanned surfaces as sparse sets of positional information. A common downside is the lack of normals, connectivity or topological adjacency data which makes it difficult to actually recover a meaningful surface. The concept described in this paper is designed to reconstruct a surface mesh despite all this missing information. Even when facing varying sample density, our algorithm is still guaranteed to produce watertight manifold meshes featuring quad faces only. The topology can be set‐up to follow superimposed regular structures or align naturally to the point cloud's shape. Our proposed approach is based on an initial divide and conquer subsampling procedure: Surface samples are clustered in meaningful neighborhoods as leafs of a kd‐tree. A representative sample of the surface neighborhood is determined for each leaf using a spherical surface approximation. The hierarchical structure of the binary tree is utilized to construct a basic set of loose tiles and to interconnect them. As a final step, missing parts of the now coherent tile structure are filled up with an incremental algorithm for locally optimal gap closure. Disfigured or concave faces in the resulting mesh can be removed with a constrained smoothing operator.