Medial Axis Construction in Three Dimensions and its Application to Mesh Generation

An algorithm for the construction of the medial axis of a three-dimensional body given by a triangulation of its bounding surface is described. The indirect construction is based on the Delaunay-triangulation of a set of sample points on the bounding surface. The point set is refined automatically so as to capture the correct topology of the medial axis. The computed medial axis (or better medial surface) is then used for hex-dominant mesh generation. Quad-dominant meshes are generated on the medial subfaces first and extruded to the boundary of the body at both sides. The resulting single cell layer is subdivided in direction normal to the boundary, yielding columns of hexahedral and three-sided prismatic cells. The resulting volume mesh is orthogonal at the boundary and ‘semi-structured’ between boundary and medial surface. Mixed cell types (tets, pyramids, degenerate hexahedra) may result along the medial surface. An advancing front algorithm (paving) is used for meshing the subfaces of the medial surface. Development of the mesh generator has not been fully completed with respect to degenerate parts of the medial axis. First medium-complexity bodies have been meshed, however, showing moderate meshing times.     

Higher-order Finite Elements for Hybrid Meshes Using New Nodal Pyramidal Elements

We provide a comprehensive study of arbitrarily high-order finite elements defined on pyramids. We propose a new family of high-order nodal pyramidal finite element which can be used in hybrid meshes which include hexahedra, tetrahedra, wedges and pyramids. Finite elements matrices can be evaluated through approximate integration, and we show that the order of convergence of the method is conserved. Numerical results demonstrate the efficiency of hybrid meshes compared to pure tetrahedral meshes or hexahedral meshes obtained by splitting tetrahedra into hexahedra.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Streaming compression of hexahedral meshes

We describe a method for streaming compression of hexahedral meshes. Given an interleaved stream of vertices and hexahedra our coder incrementally compresses the mesh in the presented order. Our coder is extremely memory efficient when the input stream also documents when vertices are referenced for the last time (i.e. when it contains topological finalization tags). Our coder then continuously releases and reuses data structures that no longer contribute to compressing the remainder of the stream. This means in practice that our coder has only a small fraction of the whole mesh in memory at any time. We can therefore compress very large meshes—even meshes that do not fit in memory. Compared to traditional, non-streaming approaches that load the entire mesh and globally reorder it during compression, our algorithm trades a less compact compressed representation for significant gains in speed, memory, and I/O efficiency. For example, on the 456k hexahedra “blade” mesh, our coder is twice as fast and uses 88 times less memory (only 3.1 MB) with the compressed file increasing about 3% in size. We also present the first scheme for predictive compression of properties associated with hexahedral cells.     

Selective Padding for Polycube‐Based Hexahedral Meshing

Hexahedral meshes generated from polycube mapping often exhibit a low number of singularities but also poor‐quality elements located near the surface. It is thus necessary to improve the overall mesh quality, in terms of the minimum scaled Jacobian (MSJ) or average SJ (ASJ). Improving the quality may be obtained via global padding (or pillowing), which pushes the singularities inside by adding an extra layer of hexahedra on the entire domain boundary. Such a global padding operation suffers from a large increase of complexity, with unnecessary hexahedra added. In addition, the quality of elements near the boundary may decrease. We propose a novel optimization method which inserts sheets of hexahedra so as to perform selective padding, where it is most needed for improving the mesh quality. A sheet can pad part of the domain boundary, traverse the domain and form singularities. Our global formulation, based on solving a binary problem, enables us to control the balance between quality improvement, increase of complexity and number of singularities. We show in a series of experiments that our approach increases the MSJ value and preserves (or even improves) the ASJ, while adding fewer hexahedra than global padding.     

A geometrical approach to mesh smoothing

We study the problem of smoothing finite element meshes of triangles and tetrahedra, where vertices are recursively moved to improve the overall quality of the elements with respect to a given shape quality metric. We propose a geometric approach to solving the local optimization problem. Level sets of the given metric are used to characterize the set of optimal point(s). We also introduce a new mesh quality metric for tetrahedra.     

The All-Hex Geode-Template for Conforming a Diced Tetrahedral Mesh to any Diced Hexahedral Mesh

Take a hexahedral mesh and an adjoining tetrahedral mesh that splits each boundary quadrilateral into two triangles. Separate the meshes with a buffer layer of hexes. Dice the original hexes into eight, and the tetrahedra into four hexahedra. Then I show that the buffer layer hexes can be filled with the geode-template, creating a conforming all-hex mesh of the entire model. The geode-template is composed of 26 hexahedra. The hexahedra have acceptable quality, depending on the geometry of the buffer layer. The method used to generate the geode-template is general, based on interleaving completed dual surfaces, and might be extended to other transition problems.     

Interactive quadrangulation with Reeb atlases and connectivity textures

Creating high-quality quad meshes from triangulated surfaces is a highly nontrivial task that necessitates consideration of various application specific metrics of quality. In our work, we follow the premise that automatic reconstruction techniques may not generate outputs meeting all the subjective quality expectations of the user. Instead, we put the user at the center of the process by providing a flexible, interactive approach to quadrangulation design. By combining scalar field topology and combinatorial connectivity techniques, we present a new framework, following a coarse to fine design philosophy, which allows for explicit control of the subjective quality criteria on the output quad mesh, at interactive rates. Our quadrangulation framework uses the new notion of Reeb atlas editing, to define with a small amount of interactions a coarse quadrangulation of the model, capturing the main features of the shape, with user prescribed extraordinary vertices and alignment. Fine grain tuning is easily achieved with the notion of connectivity texturing, which allows for additional extraordinary vertices specification and explicit feature alignment, to capture the high-frequency geometries. Experiments demonstrate the interactivity and flexibility of our approach, as well as its ability to generate quad meshes of arbitrary resolution with high-quality statistics, while meeting the user’s own subjective requirements.     

边收缩池化的网格变分自编码器

目的 3D形状分析是计算机视觉和图形学的一个重要研究课题。虽然现有方法使用基于图的卷积将基于图像的深度学习推广到3维网格,但缺乏有效的池化操作限制了其网络的学习能力。针对具有相同连通性,但几何形状不同的网格模型数据集,本文利用网格简化的边收缩操作建立网格层次结构,提出了一种新的网格池化操作。方法 本文改进了传统的网格简化方法,以避免生成高度不规则的三角形,利用改进的网格简化方法定义了新的网格池化操作。网格简化的边收缩操作建立的网格层次结构之间存在对应关系,有利于网格池化的定义。新定义的池化操作有效地编码了层次结构中较粗糙和较稠密网格之间的对应关系。最后提出了一种带有边收缩池化和图卷积的变分自编码器（variational auto-encoder,VAE）结构,以探索3D形状的隐空间并用于3D形状的生成。结果 由于引入了新定义的池化操作和图卷积操作,提出的网络结构比原始MeshVAE需要的参数更少,因此可以处理更稠密的网格模型。结论 实验表明提出的方法具有更好的泛化能力,并且在各种应用中更可靠,包括形状生成、形状插值和形状嵌入。     

The receding front method applied to hexahedral mesh generation of exterior domains

Two of the most successful methods to generate unstructured hexahedral meshes are the grid-based methods and the advancing front methods. On the one hand, the grid-based methods generate high-quality hexahedra in the inner part of the domain using an inside–outside approach. On the other hand, advancing front methods generate high-quality hexahedra near the boundary using an outside–inside approach. To combine the advantages of both methodologies, we extend the receding front method: an inside–outside mesh generation approach by means of a reversed advancing front. We apply this approach to generate unstructured hexahedral meshes of exterior domains. To reproduce the shape of the boundaries, we first pre-compute the mesh fronts by combining two solutions of the Eikonal equation on a tetrahedral reference mesh. Then, to generate high-quality elements, we expand the quadrilateral surface mesh of the inner body towards the unmeshed external boundary using the pre-computed fronts as a guide.     

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.     

Perfect Matching Quad Layouts for Manifold Meshes

This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.     

Single-rate near lossless compression of animated geometry

Representing mesh geometry in local rather than the world coordinate systems is very useful in many 3D animation processing applications. One can investigate the representation of vertex locations relative to a local coordinate frame (LCF) in the compression of dynamic 3D meshes. Unlike the world coordinates, which scatter in a wide range and show non-linear behavior of the vertices, the local coordinates exhibit a large clustering behavior of the vertex over time. This property is very useful for exploiting a large coherence over the vertex trajectory and between neighboring vertices. In this paper, we discuss the use of the LCF in static and animated mesh encoding and we introduce a new connectivity-guided predictive scheme for single-rate compression for animated meshes. The proposed geometry encoding strategy is based on a region growing encoding order, and only the differences between original and predicted locations are encoded in a local coordinate system, which splits into two tangential and one normal components. The approach is simple, efficient, and well-suited for real time applications.     

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.     

基于特征点检测的三维模型最佳视点选择

针对三维模型最佳视点选择问题,提出了一种基表面特征点检测的视点选择算法。首先引入一种基于局部平均形心距离差的顶点显著性度量方法,认为三维网格模型表面某顶点的显著性是由该顶点与形心之间距离和该顶点邻域内的顶点与形心之间距离的平均差值来刻画,而不是该点所在位置的弯曲程度所决定;然后根据顶点的显著性大小进行三维模型表面特征点检测;最后针对视点球体上的每个候选视点分析该视点下可见特征点的几何分布和显著度大小计算视点质量,提取出最佳视点。实验结果验证了基于三维模型特征点的视点选择方法的有效性,在能够选择出质量较优的视点的同时保证算法的效率。     

Connectivity-Based Segmentation for GPU-Accelerated Mesh Decompression

We present a novel algorithm to partition large 3D meshes for GPU-accelerated decompression.Our formulation focuses on minimizing the replicated vertices between patches,and balancing the numbers of faces of patches for efficient parallel computing.First we generate a topology model of the original mesh and remove vertex positions.Then we assign the centers of patches using geodesic farthest point sampling and cluster the faces according to the geodesic distance to the centers.After the segmentation we swap boundary faces to fix jagged boundaries and store the boundary vertices for whole-mesh preservation.The decompression of each patch runs on a thread of GPU,and we evaluate its performance on various large benchmarks.In practice,the GPU-based decompression algorithm runs more than 48x faster on NVIDIA GeForce GTX 580 GPU compared with that on the CPU using single core.     

Sweep造型法在管线三维可视化中的应用

管线三维可视化中的一个重要问题是如何根据管线中心线坐标计算得到管线表面顶点的坐标,难点在于管线转折处的表面处理。采用“sweep+mesh”的造型方法可生成整张连续的管道表面而不必在管线转折处做拼接处理。此方法通过在管线中心线各分段点上建立局部坐标系（标架）,计算得到分段点对应的管线表面顶点的坐标,并生成连续的mesh网格。为建立连续的标架,提出了对管线进行倒圆角及分段处理,再递推生成标架的方法。结果表明：管线表面顶点坐标正确,整个表面光滑连续。     

Field‐Aligned and Lattice‐Guided Tetrahedral Meshing

We present a particle‐based approach to generate field‐aligned tetrahedral meshes, guided by cubic lattices, including BCC and FCC lattices. Given a volumetric domain with an input frame field and a user‐specified edge length for the cubic lattice, we optimize a set of particles to form the desired lattice pattern. A Gaussian Hole Kernel associated with each particle is constructed. Minimizing the sum of kernels of all particles encourages the particles to form a desired layout, e.g., field‐aligned BCC and FCC. The resulting set of particles can be connected to yield a high quality field‐aligned tetrahedral mesh. As demonstrated by experiments and comparisons, the field‐aligned and lattice‐guided approach can produce higher quality isotropic and anisotropic tetrahedral meshes than state‐of‐the‐art meshing methods.