Meshing

Delaunay Mesh Simplification with Differential Evolution

Abstract: Delaunay meshes (DM) are a special type of manifold triangle meshes where the local Delaunay condition holds everywhere, and have important applications in digital geometry processing. This paper addresses the general DM simplification problem: given an arbitrary manifold triangle mesh M with n vertices and the user-specified target resolution m (< n), compute a Delaunay mesh M* with m vertices that has the least Hausdorff distance to M. To solve the problem, we abstract the simplification process using a 2D Cartesian grid model, in which each grid point corresponds to triangle meshes with a certain number of vertices and a simplification process can be viewed as a monotonic path on the grid. We develop a novel differential-evolution-based method to compute the optimal path, which leads to a high-quality Delaunay mesh. Extensive evaluation shows that our method consistently outperforms the existing methods in terms of approximation error. In particular, our method is highly effective for CAD models and man-made objects with sharp features but less geometric details. Moreover, our method is fully automatic and can preserve sharp features well and deal with models with multiple components, whereas the existing methods often fail.

Authors/Presenter(s): Ran Yi, Tsinghua University, China
Yong-Jin Liu, Tsinghua University, China
Ying He, Nanyang Technological University, Singapore

Layered Fields for Natural Tessellations on Surfaces

Abstract: Mimicking natural tessellation patterns is a fascinating multi-disciplinary problem. Geometric methods aiming at reproducing such partitions on surface meshes are commonly based on the Voronoi model and its variants, and are often faced with challenging issues such as metric estimation, geometric, topological complications, and most critically parallelization. In this paper, we introduce an alternate model which may be of value for resolving these issues. We drop the assumption that regions need to be separated by lines. Instead, we regard region boundaries as narrow bands and we model the partition as a set of smooth functions layered over the surface. Given an initial set of seeds or regions, the partition emerges as the solution of a time dependent set of partial differential equations describing concurrently evolving fronts on the surface. Our solution does not require geodesic estimation, elaborate numerical solvers, or complicated data structures. The cost per time-iteration is dominated by the multiplication and addition of two sparse matrices. Extension of our approach in a Lloyd's algorithm fashion can be easily achieved. As our approach relies mainly on basic linear algebra kernels, it lends itself to efficient implementation on modern graphics hardware.

Authors/Presenter(s): Rhaleb Zayer, Max Planck Institute for Informatics, Germany
Daniel Mlakar, Graz University of Technology, Austria
Markus Steinberger, Graz University of Technology, Max Planck Institute for Informatics, Austria
Hans-Peter Seidel, Max Planck Institute for Informatics, Germany

Meshless Voronoi on the GPU

Abstract: We propose a GPU algorithm that computes a 3D Voronoi diagram. Our algorithm is tailored for applications that solely make use of the geometry of the Voronoi cells, such as Lloyd's relaxation used in meshing, or some numerical schemes used in fluid simulations and astrophysics. Since these applications only require the geometry of the Voronoi cells, they do not need the combinatorial mesh data structure computed by the classical algorithms (Bowyer-Watson). Thus, by exploiting the specific spatial distribution of the point-sets used in this type of applications, our algorithm computes each cell independently, in parallel, based on its nearest neighbors. In addition, we show how to compute integrals over the Voronoi cells by decomposing them on the fly into tetrahedra, without needing to compute any combinatorial information. The advantages of our algorithm is that it is fast, very simple to implement, has constant memory usage per thread and does not need any synchronization primitive. These specificities make it particularly efficient on the GPU: it gains one order of magnitude as compared to the fastest state-of-the-art multicore CPU implementations. To ease the reproducibility of our results, the full documented source code is included in the supplemental material.

Authors/Presenter(s): Nicolas Ray, INRIA, France
Dmitry Sokolov, Université de Lorraine, France
Sylvain Lefebvre, INRIA, France
Bruno Lévy, INRIA, France

There are 174 Subdivisions of the Hexahedron into Tetrahedra

Abstract: This article answers an important theoretical question: How many different subdivisions of the hexahedron into tetrahedra are there? It is well known that the cube has five subdivisions into 6 tetrahedra and one subdivision into 5 tetrahedra. However, all hexahedra are not cubes and moving the vertex positions increases the number of subdivisions. Recent hexahedral dominant meshing methods try to take these configurations into account for combining tetrahedra into hexahedra, but fail to enumerate them all: they use only a set of 10 subdivisions among the 174 we found in this article. The enumeration of these 174 subdivisions of the hexahedron into tetrahedra is our combinatorial result. Each of the 174 subdivisions has between 5 and 15 tetrahedra and is actually a class of 2 to 48 equivalent instances which are identical up to vertex relabeling. We further show that exactly 171 of these subdivisions have a geometrical realization, i.e. there exist coordinates of the eight hexahedron vertices in a three-dimensional space such that the geometrical tetrahedral mesh is valid. We exhibit the tetrahedral meshes for these configurations and show in particular subdivisions of hexahedra with 15 tetrahedra that have a strictly positive Jacobian.

Authors/Presenter(s): Jeanne Pellerin, Université catholique de Louvain, Belgium
Kilian Verhetsel, Université catholique de Louvain, Belgium
Jean-François Remacle, Université catholique de Louvain, Belgium