Abstract Grid preserving maps of triangulated surfaces were introduced for quad meshing because the 2D unit grid in such maps corresponds to a sub‐division of the surface into quad‐shaped charts. These maps can be obtained by solving a mixed integer optimization problem: Real variables define the geometry of the charts and integer variables define the combinatorial structure of the decomposition. To make this optimization problem tractable, a common strategy is to ignore integer constraints at first, then to enforce them in a so‐called quantization step. Actual quantization algorithms exploit the geometric interpretation of integer variables to solve an equivalent problem: They consider that the final quad mesh is a sub‐division of a T‐mesh embedded in the surface, and optimize the number of sub‐divisions for each edge of this T‐mesh. We propose to operate on a decimated version of the original surface instead of the T‐mesh. It is easier to implement and to adapt to constraints such as free boundaries, complex feature curves network etc .

Abstract We propose a method to simultaneously decompose a 3D object into power diagram cells and to integrate given functions in each of the obtained simple regions. We offer a novel, highly parallel algorithm that lends itself to an efficient GPU implementation. It is optimized for algorithms that need to compute many decompositions, for instance, centroidal Voronoi tesselation algorithms and incompressible fluid dynamics simulations. We propose an efficient solution that directly evaluates the integrals over every cell without computing the power diagram explicitly and without intersecting it with a tetrahedralization of the domain. Most computations are performed on the fly, without storing the power diagram. We manipulate a triangulation of the boundary of the domain (instead of tetrahedralizing the domain) to speed up the process. Moreover, the cells are treated independently one from another, making it possible to trivially scale up on a parallel architecture. Despite recent Voronoi diagram generation methods optimized for the GPU, computing integrals over restricted power diagrams still poses significant challenges; the restriction to a complex simulation domain is difficult and likely to be slow. It is not trivial to determine when a cell of a power diagram is completely computed, and the resulting integrals (e.g. the weighted Laplacian operator matrix) do not fit into fast (shared) GPU memory. We address all these issues and boost the performance of the state‐of‐the‐art algorithms by a factor 2 to 3 for (unrestricted) Voronoi diagrams and a ×50 speed‐up with respect to CPU implementations for restricted power diagrams. An essential ingredient to achieve this is our new scheduling strategy that allows us to treat each Voronoi/power diagram cell with optimal settings and to benefit from the fast memory.

Mapping a triangulated surface to 2D space (or a tetrahedral mesh to 3D space) is an important problem in geometry processing. In computational physics, untangling plays an important role in mesh generation: it takes a mesh as an input, and moves the vertices to get rid of foldovers. In fact, mesh untangling can be considered as a special case of mapping where the geometry of the object is to be defined in the map space and the geometric domain is not explicit, supposing that each element is regular. In this paper, we propose a mapping method inspired by the untangling problem and compare its performance to the state of the art. The main advantage of our method is that the untangling aims at producing locally injective maps, which is the major challenge of mapping. In practice, our method produces locally injective maps in very difficult settings, both in 2D and 3D. We demonstrate it on a large reference database as well as on more difficult stress tests. For a better reproducibility, we publish the code in Python for a basic evaluation, and in C++ for more advanced applications.

SUMMARY: SPLATCHE3 simulates genetic data under a variety of spatially explicit evolutionary scenarios, extending previous versions of the framework. The new capabilities include long-distance migration, spatially and temporally heterogeneous short-scale migrations, alternative hybridization models, simulation of serial samples of genetic data and a large variety of DNA mutation models. These implementations have been applied independently to various studies, but grouped together in the current version. AVAILABILITY AND IMPLEMENTATION: SPLATCHE3 is written in C++ and is freely available for non-commercial use from the website http://www.splatche.com/splatche3. It includes console versions for Linux, MacOs and Windows and a user-friendly GUI for Windows, as well as detailed documentation and ready-to-use examples.

Most additive manufacturing processes fabricate objects by stacking planar layers of solidified material. As a result, produced parts exhibit a so-called staircase effect, which results from sampling slanted surfaces with parallel planes. Using thinner slices reduces this effect, but it always remains visible where layers almost align with the input surfaces. In this research we exploit the ability of some additive manufacturing processes to deposit material slightly out of plane to dramatically reduce these artifacts. We focus in particular on the widespread Fused Filament Fabrication (FFF) technology, since most printers in this category can deposit along slightly curved paths, under deposition slope and thickness constraints. Our algorithm curves the layers, making them either follow the natural slope of the input surface or on the contrary, make them intersect the surfaces at a steeper angle thereby improving the sampling quality. Rather than directly computing curved layers, our algorithm optimizes for a deformation of the model which is then sliced with a standard planar approach. We demonstrate that this approach enables us to encode all fabrication constraints, including the guarantee of generating collision-free toolpaths, in a convex optimization that can be solved using a QP solver. We produce a variety of models and compare print quality between curved deposition and planar slicing.

We propose a GPU algorithm that computes a 3 D 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 global 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 multi-core CPU implementations. To ease the reproducibility of our results, the full documented source code is included in the supplemental material.

Given a tetrahedral mesh, the algorithm described in this article produces a smooth 3D frame field, i.e. a set of three orthogonal directions associated with each vertex of the input mesh. The field varies smoothly inside the volume, and matches the normals of the volume boundary. Such a 3D frame field is a key component for some hexahedral meshing algorithms, where it is used to steer the placement of the generated elements. We improve the state-of-the art in terms of quality, efficiency and reproducibility. Our main contribution is a non-trivial extension in 3D of the existing least-squares approach used for optimizing a 2D frame field. Our algorithm is inspired by the method proposed by Huang et al. [2011], improved with an initialization that directly enforces boundary conditions. Our initialization alone is a fast and easy way to generate frames fields that are suitable for remeshing applications. For better robustness and quality, the field can be further optimized using nonlinear optimization as in Li et al [2012]. We make the remark that sampling the field on vertices instead of tetrahedra significantly improves both performance and quality.

This article introduces a method that generates a hexahedral-dominant mesh from an input tetrahedral mesh. It follows a three-step pipeline similar to the one proposed by Carrier Baudoin et al.: (1) generate a frame field, (2) generate a pointset P that is mostly organized on a regular grid locally aligned with the frame field, and (3) generate the hexahedral-dominant mesh by recombining the tetrahedra obtained from the constrained Delaunay triangulation of P . For step (1), we use a state-of-the-art algorithm to generate a smooth frame field. For step (2), we introduce an extension of Periodic Global Parameterization to the volumetric case. As compared with other global parameterization methods (such as CubeCover), our method relaxes some global constraints to avoid creating degenerate elements, at the expense of introducing some singularities that are meshed using non-hexahedral elements. For step (3), we build on the formalism introduced by Meshkat and Talmor, fill in a gap in their proof, and provide a complete enumeration of all the possible recombinations, as well as an algorithm that efficiently detects all the matches in a tetrahedral mesh. The method is evaluated and compared with the state of the art on a database of examples with various mesh complexities, varying from academic examples to real industrial cases. Compared with the method of Carrier-Baudoin et al., the method results in better scores for classical quality criteria of hexahedral-dominant meshes (hexahedral proportion, scaled Jacobian, etc.). The method also shows better robustness than CubeCover and its derivatives when applied to complicated industrial models.

We present a geometric representation of a tetrahedral mesh that is solely based on dihedral angles. We first show that the shape of a tetrahedral mesh is completely defined by its dihedral angles. This proof leads to a set of angular constraints that must be satisfied for an immersion to exist in R 3 . This formulation lets us easily specify conditions to avoid inverted tetrahedra and multiply-covered vertices, thus leading to locally injective maps. We then present a constrained optimization method that modifies input angles when they do not satisfy constraints. Additionally, we develop a fast spectral reconstruction method to robustly recover positions from dihedral angles. We demonstrate the applicability of our representation with examples of volume parameterization, shape interpolation, mesh optimization, connectivity shapes, and mesh compression.

We are proposing an algorithm for tracing polylines that are oriented by a direction field defined on a triangle mesh. The challenge is to ensure that two such polylines cannot cross or merge. This property is fundamental for mesh segmentation and is impossible to enforce with existing algorithms. The core of our contribution is to determine how polylines cross each triangle. Our solution is inspired by EdgeMaps where each triangle boundary is decomposed into inflow and outflow intervals such that each inflow interval is mapped onto an outflow interval. To cross a triangle, we find the inflow interval that contains the entry point, and link it to the corresponding outflow interval, with the same barycentric coordinate. To ensure that polylines cannot merge or cross, we introduce a new direction field representation, we resolve the inflow/outflow interval pairing with a guaranteed combinatorial algorithm, and propagate the barycentric positions with arbitrary precision number representation. Using these techniques, two streamlines crossing the same triangle cannot merge or cross, but only locally overlap when all streamline extremities are located on the same edge. Cross-free and merge-free polylines can be traced on the mesh by iteratively crossing triangles. Vector field singularities and polyline/vertex crossing are characterized and consistently handled.

SUMMARY: SPLATCHE2 is a program to simulate the demography of populations and the resulting molecular diversity for a wide range of evolutionary scenarios. The spatially explicit simulation framework can account for environmental heterogeneity and fluctuations, and it can manage multiple population sources. A coalescent-based approach is used to generate genetic markers mostly used in population genetics studies (DNA sequences, SNPs, STRs or RFLPs). Various combinations of independent, fully or partially linked genetic markers can be produced under a recombination model based on the ancestral recombination graph. Competition between two populations (or species) can also be simulated with user-defined levels of admixture between the two populations. SPLATCHE2 may be used to generate the expected genetic diversity under complex demographic scenarios and can thus serve to test null hypotheses. For model parameter estimation, SPLATCHE2 can easily be integrated into an Approximate Bayesian Computation (ABC) framework. AVAILABILITY AND IMPLEMENTATION: SPLATCHE2 is a C++ program compiled for Windows and Linux platforms. It is freely available at www.splatche.com, together with its related documentation and example data. CONTACT: [email protected]

Abstract Surface materials are commonly described by attributes stored in textures (for instance, color, normal, or displacement). Interpolation during texture lookup provides a continuous value field everywhere on the surface, except at the chart boundaries where visible discontinuities appear. We propose a solution to make these seams invisible, while still outputting a standard texture atlas. Our method relies on recent advances in quad remeshing using global parameterization to produce a set of texture coordinates aligning texel grids across chart boundaries. This property makes it possible to ensure that the interpolated value fields on both sides of a chart boundary precisely match, making all seams invisible. However, this requirement on the uv coordinates needs to be complemented by a set of constraints on the colors stored in the texels. We propose an algorithm solving for all the necessary constraints between texel values, including through different magnification modes (nearest, bilinear, biquadratic and bicubic), and across facets using different texture resolutions. In the typical case of bilinear magnification and uniform resolution, none of the texels appearing on the surface are constrained. Our approach also ensures perfect continuity across several MIP‐mapping levels.

Abstract Many objects have patterns that vary in appearance at different surface locations. We say that these are differences in materials, and we present a material‐space approach for interactively designing such textures. At the heart of our approach is a new method to pre‐calculate and use a 3D texture tile that is periodic in the spatial dimensions (s, t) and that also has a material axis along which the materials change smoothly. Given two textures and their feature masks, our algorithm produces such a tile in two steps. The first step resolves the features morphing by a level set advection approach, improved to ensure convergence. The second step performs the texture synthesis at each slice in material‐space, constrained by the morphed feature masks. With such tiles, our system lets a user interactively place and edit textures on a surface, and in particular, allows the user to specify which material appears at given positions on the object. Additional operations include changing the scale and orientation of the texture. We support these operations by using a global surface parameterization that is closely related to quad re‐meshing. Re‐parameterization is performed on‐the‐fly whenever the user's constraints are modified.

Many algorithms in texture synthesis, nonphotorealistic rendering (hatching), or remeshing require to define the orientation of some features (texture, hatches, or edges) at each point of a surface. In early works, tangent vector (or tensor) fields were used to define the orientation of these features. Extrapolating and smoothing such fields is usually performed by minimizing an energy composed of a smoothness term and of a data fitting term. More recently, dedicated structures ( N -RoSy and N -symmetry direction fields ) were introduced in order to unify the manipulation of these fields, and provide control over the field's topology (singularities). On the one hand, controlling the topology makes it possible to have few singularities, even in the presence of high frequencies (fine details) in the surface geometry. On the other hand, the user has to explicitly specify all singularities, which can be a tedious task. It would be better to let them emerge naturally from the direction extrapolation and smoothing. This article introduces an intermediate representation that still allows the intuitive design operations such as smoothing and directional constraints, but restates the objective function in a way that avoids the singularities yielded by smaller geometric details. The resulting design tool is intuitive, simple, and allows to create fields with simple topology, even in the presence of high geometric frequencies. The generated field can be used to steer global parameterization methods (e.g., QuadCover).

Many algorithms in computer graphics and geometry processing use two orthogonal smooth direction fields (unit tangent vector fields) defined over a surface. For instance, these direction fields are used in texture synthesis, in geometry processing or in nonphotorealistic rendering to distribute and orient elements on the surface. Such direction fields can be designed in fundamentally different ways, according to the symmetry requested: inverting a direction or swapping two directions might be allowed or not. Despite the advances realized in the last few years in the domain of geometry processing, a unified formalism is still lacking for the mathematical object that characterizes these generalized direction fields. As a consequence, existing direction field design algorithms are limited to using nonoptimum local relaxation procedures. In this article, we formalize N -symmetry direction fields, a generalization of classical direction fields. We give a new definition of their singularities to explain how they relate to the topology of the surface. Specifically, we provide an accessible demonstration of the Poincaré-Hopf theorem in the case of N -symmetry direction fields on 2-manifolds. Based on this theorem, we explain how to control the topology of N -symmetry direction fields on meshes. We demonstrate the validity and robustness of this formalism by deriving a highly efficient algorithm to design a smooth field interpolating user-defined singularities and directions.

We present a new globally smooth parameterization method for the triangulated surfaces of arbitrary topology. Given two orthogonal piecewise linear vector fields defined over the input mesh (typically the estimated principal curvature directions), our method computes two piecewise linear periodic functions, aligned with the input vector fields, by minimizing an objective function. The bivariate function they define is a smooth parameterization almost everywhere on the surface, except in the vicinity of singular vertices, edges, and triangles, where the derivatives of the parameterization vanish. We extract a quadrilateral chart layout from the parameterization function and propose an automatic procedure to detect the singularities, and fix them by splitting and reparameterizing the containing charts. Our method can construct both quasiconformal (angle preserving) and quasi-isometric (angle and area preserving) parameterizations. The more restrictive class of quasi-isometric parameterizations is constructed at the expense of introducing more singularities. The constructed parameterizations can be used for a variety of geometry processing applications. Since we can align the parameterization with the principal curvature directions, our result is particularly suitable for surface fitting and remeshing.

Accurately representing higher-order singularities of vector fields defined on piecewise linear surfaces is a non-trivial problem. In this work, we introduce a concise yet complete interpolation scheme of vector fields on arbitrary triangulated surfaces. The scheme enables arbitrary singularities to be represented at vertices. The representation can be considered as a facet-based "encoding" of vector fields on piecewise linear surfaces. The vector field is described in polar coordinates over each facet, with a facet edge being chosen as the reference to define the angle. An integer called the period jump is associated to each edge of the triangulation to remove the ambiguity when interpolating the direction of the vector field between two facets that share an edge. To interpolate the vector field, we first linearly interpolate the angle of rotation of the vectors along the edges of the facet graph. Then. we use a variant of Nielson's side-vertex scheme to interpolate the vector field over the entire surface. With our representation, we remove the bound imposed on the complexity of singularities that a vertex can represent by its connectivity. This bound is a limitation generally exists in vertex-based linear schemes. Furthermore, using our data structure, the index of a vertex of a vector field can be combinatorily determined. We show the simplicity of the interpolation scheme with a GPU-accelerated algorithm for a LIC-based visualization of the so-defined vector fields, operating in image space. We demonstrate the algorithm applied to various vector fields on curved surfaces.

A texture atlas is an efficient way to represent information (like colors, normals, displacement maps) on triangulated surfaces. The LSCM method (Least Square Conformal Maps) automatically generates a texture atlas from a meshed model. For large charts (over 100k facets), the convergence of the numerical solver may be slow. It is well known that the conformality criterion, minimized by LSCM, also corresponds to a harmonically condition, meaning that barycentric coordinates are locally preserved through the parametization. This has two different consequences: cascadic multigrid methods (coarse to fine) are well adapted to this criterion, and dramatically speed up the convergence of the numerical solver; the obtained parametization naturally minimizes texture swimming when used to texture-map a progressive mesh. In this paper, we introduce HLSCM (Hierarchical LSCM), a cascadic multigrid version of LSCM. As an example of possible applications, the paper shows how normal maps and simplified models can be automatically generated from large scanned meshes, the visual appearance of the model can be preserved even when 90% of the vertices are removed from the initial model.

A Texture Atlas is an efficient color representation for 3D Paint Systems. The model to be textured is decomposed into charts homeomorphic to discs, each chart is parameterized, and the unfolded charts are packed in texture space. Existing texture atlas methods for triangulated surfaces suffer from several limitations, requiring them to generate a large number of small charts with simple borders. The discontinuities between the charts cause artifacts, and make it difficult to paint large areas with regular patterns.In this paper, our main contribution is a new quasi-conformal parameterization method, based on a least-squares approximation of the Cauchy-Riemann equations. The so-defined objective function minimizes angle deformations, and we prove the following properties: the minimum is unique, independent of a similarity in texture space, independent of the resolution of the mesh and cannot generate triangle flips. The function is numerically well behaved and can therefore be very efficiently minimized. Our approach is robust, and can parameterize large charts with complex borders.We also introduce segmentation methods to decompose the model into charts with natural shapes, and a new packing algorithm to gather them in texture space. We demonstrate our approach applied to paint both scanned and modeled data sets.