Point clouds and polygonal meshes are widely used when modeling real-world scenarios. Here, point clouds arise, for instance, from acquisition processes applied in various surroundings, such as reverse engineering, rapid prototyping, or cultural preservation. Based on these raw data, polygonal meshes are created to, for example, run various simulations. For such applications, the utilized meshes must be of high quality. This paper presents an algorithm to derive triangle meshes from unstructured point clouds. The occurring edges have a close to uniform length and their lengths are bounded from below. Theoretical results guarantee the output to be manifold, provided suitable input and parameter choices. Further, the paper presents several experiments establishing that the algorithms can compete with widely used competitors in terms of quality of the output and timing and the output is stable under moderate levels of noise. Additionally, we expand the algorithm to detect and respect features on point clouds as well as to remesh polyhedral surfaces, possibly with features. Supplementary material, an extended preprint, a link to a previously published version of the article, utilized models, and implementation details are made available online .

In various application fields, such as fluid-, cell-, or crowd-simulations, spatial data structures are very important. They answer nearest neighbor queries which are instrumental in performing necessary computations for, e.g., taking the next time step in the simulation. Correspondingly, various such data structures have been developed, one being the neighborhood grid . In this paper, we consider combinatorial aspects of this data structure. Particularly, we show that an assumption on uniqueness, made in previous works, is not actually satisfied. We extend the notions of the neighborhood grid to arbitrary grid sizes and dimensions and provide two alternative, correct versions of the proof that was broken by the dissatisfied assumption. Furthermore, we explore both the uniqueness of certain states of the data structure as well as when the number of these states is maximized. We provide a partial classification by using the hook-length formula for rectangular Young tableaux. Finally, we conjecture how to extend this to all 2-dimensional cases. • A combinatorial perspective on the Neighborhood Grid spatial data structure • Introducing a polynomial time construction of stable states ( Theorem 3.1 ) • Analyzing the run time of our construction ( Theorem 4.3 and Corollary 4.4 ) • Disproving an implicit uniqueness assumption of previous work ( Proposition 5.5 ) • Sharing several enumerative open problems and conjectures

This paper presents a simple and effective two-stage mesh denoising algorithm, where in the first stage, face normal filtering is done by using bilateral normal filtering in a robust statistics framework. Tukey's bi-weight function is used as similarity function in the bilateral weighting, which is a robust estimator and stops the diffusion at sharp edges to retain features and removes noise from flat regions effectively. In the second stage, an edge-weighted Laplace operator is introduced to compute a differential coordinate. This differential coordinate helps the algorithm to produce a high-quality mesh without any face normal flips and makes the method robust against high-intensity noise.

This paper presents a two-stage mesh denoising algorithm. Unlike other traditional averaging approaches, our approach uses an element-based normal voting tensor to compute smooth surfaces. By introducing a binary optimization on the proposed tensor together with a local binary neighborhood concept, our algorithm better retains sharp features and produces smoother umbilical regions than previous approaches. On top of that, we provide a stochastic analysis on the different kinds of noise based on the average edge length. The quantitative results demonstrate that the performance of our method is better compared to state-of-the-art smoothing approaches.

Abstract 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.

Abstract Despite the success of quad‐based 2D surface parameterization methods, effective parameterization algorithms for 3D volumes with cubes, i.e. hexahedral elements, are still missing. C ube C over is a first approach for generating a hexahedral tessellation of a given volume with boundary aligned cubes which are guided by a frame field. The input of C ube C over is a tetrahedral volume mesh. First, a frame field is designed with manual input from the designer. It guides the interior and boundary layout of the parameterization. Then, the parameterization and the hexahedral mesh are computed so as to align with the given frame field. C ube C over has similarities to the Q uad C over algorithm and extends it from 2D surfaces to 3D volumes. The paper also provides theoretical results for 3D hexahedral parameterizations and analyses topological properties of the appropriate function space.

We introduce FreeLence, a novel and simple single-rate compression coder for triangle manifold meshes. Our method uses free valences and exploits geometric information for connectivity encoding. Furthermore, we introduce a novel linear prediction scheme for geometry compression of 3D meshes. Together, these approaches yield a significant entropy reduction for mesh encoding with an average of 20-30 % over leading single-rate regiongrowing coders, both for connectivity and geometry.