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.     

Motorcycle graph enumeration from quadrilateral meshes for reverse engineering

Recently proposed quad-meshing techniques allow the generation of high-quality semi-regular quadrilateral meshes. This paper outlines the generation of quadrilateral segments using such meshes. Quadrilateral segments are advantageous in reverse engineering because they do not require surface trimming or surface parameterization. The motorcycle graph algorithm of Eppstein et al. produces the motorcycle graph of a given quadrilateral mesh consisting of quadrilateral segments. These graphs are preferable to base complexes, because the mesh can be represented with a smaller number of segments, as T-joints (where the intersection of two neighboring segments does not involve the whole edge or the vertex) are allowed in quadrilateral segmentation.The proposed approach in this study enumerates all motorcycle graphs of a given quadrilateral mesh and optimum graph for reverse engineering is then selected. Due to the high computational cost of enumerating all these graphs, the mesh is cut into several sub-meshes whose motorcycle graphs are enumerated separately. The optimum graph is then selected based on a cost function that produces low values for graphs whose edges trace a large number of highly curved regions in the model. By applying several successive enumeration steps for each sub-mesh, a motorcycle graph for the given mesh is found. We also outline a method for the extraction of feature curves (sets of highly curved edges) and their integration into the proposed algorithm. Quadrilateral segments generated using the proposed techniques are validated by B-spline surfaces.     

Anisotropic quadrilateral mesh generation: An indirect approach

In this paper a new indirect approach is presented for anisotropic quadrilateral mesh generation based on discrete surfaces. The ability to generate grids automatically had a pervasive influence on many application areas in particularly in the field of Computational Fluid Dynamics. In spite of considerable advances in automatic grid generation there is still potential for better performance and higher element quality. The aim is to generate meshes with less elements which fit some anisotropy criterion to satisfy numerical accuracy while reducing processing times remarkably. The generation of high quality volume meshes using an advancing front algorithm relies heavily on a well designed surface mesh. For this reason this paper presents a new technique for the generation of high quality surface meshes containing a significantly reduced number of elements. This is achieved by creating quadrilateral meshes that include anisotropic elements along a source of anisotropy.     

Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework

In this work, we present a simultaneous untangling and smoothing technique for quadrilateral and hexahedral meshes. The algorithm iteratively improves a quadrilateral or hexahedral mesh by minimizing an objective function defined in terms of a regularized algebraic distortion measure of the elements. We propose several techniques to improve the robustness and the computational efficiency of the optimization algorithm. In addition, we have adopted an object-oriented paradigm to create a common framework to smooth meshes composed by any type of elements, and using different minimization techniques. Finally, we present several examples to show that the proposed technique obtains valid meshes composed by high-quality quadrilaterals and hexahedra, even when the initial meshes contain a large number of tangled elements.     

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.     

Hexahedral Mesh Generation by Successive Dual Cycle Elimination

We propose a new method for constructing all-hexahedral finite element meshes. The core of our method is to build up a compatible combinatorial cell complex of hexahedra for a solid body which is topologically a ball, and for which a quadrilateral surface mesh of a certain structure is prescribed. The step-wise creation of the hex complex is guided by the cycle structure of the combinatorial dual of the surface mesh. Our method transforms the graph of the surface mesh iteratively by changing the dual cycle structure until we get the surface mesh of a single hexahedron. Starting with a single hexahedron and reversing the order of the graph transformations, each transformation step can be interpreted as adding one or more hexahedra to the so far created hex complex. Given an arbitrary solid body, we first decompose it into simpler subdomains equivalent to topological balls by adding virtual 2-manifolds. Secondly, we determine a compatible quadrilateral surface mesh for all subdomains created. Then, in the main part we can use the core routine to build up a hex complex for each subdomain independently. The embedding and smoothing of the combinatorial mesh(es) finishes the mesh generation process. First results obtained for complex geometries are encouraging.     

Motorcycle Graphs: Canonical Quad Mesh Partitioning

We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.     

Spectral Geometry Processing with Manifold Harmonics

We present an explicit method to compute a generalization of the Fourier Transform on a mesh. It is well known that the eigenfunctions of the Laplace Beltrami operator (Manifold Harmonics) define a function basis allowing for such a transform. However, computing even just a few eigenvectors is out of reach for meshes with more than a few thousand vertices, and storing these eigenvectors is prohibitive for large meshes. To overcome these limitations, we propose a band‐by‐band spectrum computation algorithm and an out‐of‐core implementation that can compute thousands of eigenvectors for meshes with up to a million vertices. We also propose a limited‐memory filtering algorithm, that does not need to store the eigenvectors. Using this latter algorithm, specific frequency bands can be filtered, without needing to compute the entire spectrum. Finally, we demonstrate some applications of our method to interactive convolution geometry filtering. These technical achievements are supported by a solid yet simple theoretic framework based on Discrete Exterior Calculus (DEC). In particular, the issues of symmetry and discretization of the operator are considered with great care.     

建筑结构模型的四边形网格生成算法

为提高建筑结构有限元分析计算的效率,提出建筑结构模型的四边形网格生成算法．首先采用改进的折半查找算法快速建立相应的结构模型索引信息;然后根据四边形网格划分的原则调整模型边界;最后采用分区域模板法对整体结构模型进行四边形网格的自动生成．算例表明该算法可以根据有限元分析计算中模型的特点简化模型,降低计算时间．     

Quad‐Mesh Generation and Processing: A Survey

Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrisation and remeshing.     

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.     

Analysis and optimal design of plates and shells under dynamic loads – I: finite element and sensitivity analysis

In this paper we consider the development, integration, and application of reliable and efficient computational tools for the geometry modeling, mesh generation, structural analysis, and sensitivity analysis of variable-thickness plates and free-form shells under dynamic loads. A flexible shape-definition tool for surface modeling using Coons patches is considered to represent the shape and the thickness distribution of the structure, followed by an automatic mesh generator for structured meshes on the shell surface. Nine-node quadrilateral Mindlin–Reissner shell elements degenerated from 3D elements and with an assumed strain field, the so-called Huang–Hinton elements, are used for the FE discretization of the structure. The Newmark direct integration algorithm is used for the time discretization of the dynamic equilibrium equations for both the structural analysis and the semi-analytical (SA) sensitivity analysis. Alternatively, the sensitivities are computed by using the global finite difference (FD) method. Several examples are considered. In a companion paper, the tools presented here are combined with mathematical programming algorithms to form a robust and reliable structural optimization process to achieve better dynamic performance on the shell designs.     

Perfect Laplacians for Polygon Meshes

A discrete Laplace‐Beltrami operator is called perfect if it possesses all the important properties of its smooth counterpart. It is known which triangle meshes admit perfect Laplace operators and how to fix any other mesh by changing the combinatorics. We extend the characterization of meshes that admit perfect Laplacians to general polygon meshes. More importantly, we provide an algorithm that computes a perfect Laplace operator for any polygon mesh without changing the combinatorics, although, possibly changing the embedding. We evaluate this algorithm and demonstrate it at applications.     

边界简化与多目标优化相结合的高质量四边形网格生成

目的 高质量四边形网格生成是计算机辅助设计、等几何分析与图形学领域中一个富有挑战性的重要问题。针对这一问题,提出一种基于边界简化与多目标优化的高质量四边形网格生成新框架。方法 首先针对亏格非零的平面区域,提出一种将多连通区域转化为单连通区域的方法,可生成高质量的插入边界;其次,提出"可简化角度"和"可简化面积比率"两个阈值概念,从顶点夹角和顶点三角形面积入手,将给定的多边形边界简化为粗糙多边形;然后对边界简化得到的粗糙多边形进行子域分解,并确定每个子域内的网格顶点连接信息;最后提出四边形网格的均匀性和正交性度量目标函数,并通过多目标非线性优化技术确定网格内部顶点的几何位置。结果 在同样的离散边界下,本文方法与现有方法所生成的四边网格相比,所生成的四边网格顶点和单元总数目较少,网格单元质量基本类似,计算时间成本大致相同,但奇异点数目可减少70% 80%,衡量网格单元质量的比例雅克比值等相关指标均有所提高。结论 本文所提出的四边形网格生成方法能够有效减少网格中的奇异点数目,并可生成具有良好光滑性、均匀性和正交性的高质量四边形网格,非常适用于工程分析和动画仿真。     

Fast and Scalable Mesh Superfacets

In the field of computer vision, the introduction of a low‐level preprocessing step to oversegment images into superpixels – relatively small regions whose boundaries agree with those of the semantic entities in the scene – has enabled advances in segmentation by reducing the number of elements to be labeled from hundreds of thousands, or millions, to a just few hundred. While some recent works in mesh processing have used an analogous oversegmentation, they were not intended to be general and have relied on graph cut techniques that do not scale to current mesh sizes. Here, we present an iterative superfacet algorithm and introduce adaptations of undersegmentation error and compactness, which are well‐motivated and principled metrics from the vision community. We demonstrate that our approach produces results comparable to those of the normalized cuts algorithm when evaluated on the Princeton Segmentation Benchmark, while requiring orders of magnitude less time and memory and easily scaling to, and enabling the processing of, much larger meshes.     

A Projective Framework for Polyhedral Mesh Modelling

We present a novel framework for polyhedral mesh editing with face‐based projective maps that preserves planarity by definition. Such meshes are essential in the field of architectural design and rationalization. By using homogeneous coordinates to describe vertices, we can parametrize the entire shape space of planar‐preserving deformations with bilinear equations. The generality of this space allows for polyhedral geometric processing methods to be conducted with ease. We demonstrate its usefulness in planar‐quadrilateral mesh subdivision, a resulting multi‐resolution editing algorithm, and novel shape‐space exploration with prescribed transformations. Furthermore, we show that our shape space is a discretization of a continuous space of conjugate‐preserving projective transformation fields on surfaces. Our shape space directly addresses planar‐quad meshes, on which we put a focus, and we further show that our framework naturally extends to meshes with faces of more than four vertices as well.     

High quality refinable G‐splines for locally quad‐dominant meshes with T‐gons

Polyhedral modeling and re‐meshing algorithms use T‐junctions to add or remove feature lines in a quadrilateral mesh. In many ways this is akin to adaptive knot insertion in a tensor‐product spline, but differs in that the designer or meshing algorithm does not necessarily protect the consistent combinatorial structure that is required to interpret the resulting quad‐dominant mesh as the control net of a hierarchical spline – and so associate a smooth surface with the mesh as in the popular tensor‐product spline paradigm. While G‐splines for multi‐sided holes or generalized subdivision can, in principle, convert quad‐dominant meshes with T‐junctions into smooth surfaces, they do not preserve the two preferred directions and so cause visible shape artifacts. Only recently have n‐gons with T‐junctions (T‐gons) in unstructured quad‐dominant meshes been recognized as a distinct challenge for generalized splines. This paper makes precise the notion of locally quad‐dominant mesh as quad‐meshes including τ‐nets, i.e. T‐gons surrounded by quads; and presents the first high‐quality G‐spline construction that can use τ‐nets as control nets for spline surfaces suitable, e.g., for automobile outer surfaces. Remarkably, T‐gons can be neighbors, separated by only one quad, both of T‐gons and of points where many quads meet. A τ‐net surface cap consists of 16 polynomial pieces of degree (3,5) and is refinable in a way that is consistent with the surrounding surface. An alternative, everywhere bi‐3 cap is not formally smooth, but achieves the same high‐quality highlight line distribution.     

Implicit Hierarchical Quad‐Dominant Meshes

We present a method for producing quad‐dominant subdivided meshes, which supports both adaptive refinement and adaptive coarsening. A hierarchical structure is stored implicitly in a standard half‐edge data structure, while allowing us to efficiently navigate through the different level of subdivision. Subdivided meshes contain a majority of quad elements and a moderate amount of triangles and pentagons in the regions of transition across different levels of detail. Topological LOD editing is controlled with local conforming operators, which support both mesh refinement and mesh coarsening. We show two possible applications of this method: we define an adaptive subdivision surface scheme that is topologically and geometrically consistent with the Catmull–Clark subdivision; and we present a remeshing method that produces semi‐regular adaptive meshes.     

Polycube Simplification for Coarse Layouts of Surfaces and Volumes

Representing digital objects with structured meshes that embed a coarse block decomposition is a relevant problem in applications like computer animation, physically‐based simulation and Computer Aided Design (CAD). One of the key ingredients to produce coarse block structures is to achieve a good alignment between the mesh singularities (i.e., the corners of each block). In this paper we improve on the polycube‐based meshing pipeline to produce both surface and volumetric coarse block‐structured meshes of general shapes. To this aim we add a new step in the pipeline. Our goal is to optimize the positions of the polycube corners to produce as coarse as possible base complexes. We rely on re‐mapping the positions of the corners on an integer grid and then using integer numerical programming to reach the optimal. To the best of our knowledge this is the first attempt to solve the singularity misalignment problem directly in polycube space. Previous methods for polycube generation did not specifically address this issue. Our corner optimization strategy is efficient and requires a negligible extra running time for the meshing pipeline. In the paper we show that our optimized polycubes produce coarser block structured surface and volumetric meshes if compared with previous approaches. They also induce higher quality hexahedral meshes and are better suited for spline fitting because they reduce the number of splines necessary to cover the domain, thus improving both the efficiency and the overall level of smoothness throughout the volume.     

Automatic generation of finite element meshes

This paper describes a new algorithm for the automatic generation of finite element meshes of arbitrary multiply connected domains. The strategy is based upon the construction of a mapping from the generated mesh into a regular one. The scheme is designed for maximum flexibility and is able to generate meshes of triangular or quadrilateral curved elements. Several examples are presented to illustrate the applicability of the algorithm.