Anisotropic meshes are triangulations of a given domain in the plane or in higher dimensions, with elements elongated along prescribed directions. Anisotropic triangulations are known to be well suited for interpolation of functions or solving PDEs. Assuming that the anisotropic shape requirements for mesh elements are given through a metric field varying over the domain, we propose a new approach to anisotropic mesh generation, relying on the notion of anisotropic Delaunay meshes. An anisotropic Delaunay mesh is defined as a mesh in which the star of each vertex $v$ consists of simplices that are Delaunay for the metric associated to vertex $v$. This definition works in any dimension and allows us to define a simple refinement algorithm. The algorithm takes as input a domain and a metric field and provides, after completion, an anisotropic mesh whose elements are sized and shaped according to the metric field.

Anisotropic simplicial meshes are triangulations with elements elongated along prescribed directions. Anisotropic meshes have been shown well suited for interpolation of functions or solving PDEs. They can also significantly enhance the accuracy of a surface representation. Given a surface S endowed with a metric tensor field, we propose a new approach to generate an anisotropic mesh that approximates S with elements shaped according to the metric field. The algorithm relies on the well-established concepts of restricted Delaunay triangulation and Delaunay refinement and comes with theoretical guarantees. The star of each vertex in the output mesh is Delaunay for the metric attached to this vertex. Each facet has a good aspect ratio with respect to the metric specified at any of its vertices. The algorithm is easy to implement. It can mesh various types of surfaces like implicit surfaces, polyhedra, or isosurfaces in 3D images. It can handle complicated geometries and topologies, and very anisotropic metric fields.

CGALmesh is the mesh generation software package of the Computational Geometry Algorithm Library (CGAL). It generates isotropic simplicial meshes—surface triangular meshes or volume tetrahedral meshes—from input surfaces, 3D domains, and 3D multidomains, with or without sharp features. The underlying meshing algorithm relies on restricted Delaunay triangulations to approximate domains and surfaces and on Delaunay refinement to ensure both approximation accuracy and mesh quality. CGALmesh provides guarantees on approximation quality and on the size and shape of the mesh elements. It provides four optional mesh optimization algorithms to further improve the mesh quality. A distinctive property of CGALmesh is its high flexibility with respect to the input domain representation. Such a flexibility is achieved through a careful software design, gathering into a single abstract concept, denoted by the oracle, all required interface features between the meshing engine and the input domain. We already provide oracles for domains defined by polyhedral and implicit surfaces.

Abstract We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.

Extracting a computer model of a real scene from a sequence of views, is one of the most challenging and fundamental problems in computer vision. Stereo vision algorithms allow us to extract from the images a sparse 3D point cloud on the scene surfaces. However, computing an accurate mesh of the scene based on such poor quality data points (noise, sparsity) is very difficult. Here we describe a simple yet original approach that uses both the stereo vision extracted point cloud and the calibrated images. Our method is a three-stage process in which the first stage merges, filters and smoothes the input 3D points. The second stage builds for each calibrated image a triangular depth-map and fuses the set of depth-maps into a triangle soup that minimize violations of size and visibility constraints. Finally, a mesh is computed from the triangle soup using a reconstruction method that combines restricted Delaunay triangulation and Delaunay refinement.

Abstract Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because they contain multi‐material junctions forming features such as surface patches, edges and corners. The resulting meshes should preserve these features to ensure the visual quality and the mechanical soundness of the models. We present a feature preserving Delaunay refinement algorithm which can be used to generate high‐quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.

Various definitions of so called anisotropic Voronoi diagrams have been proposed. These diagrams are typically parameterized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a triangulation, with elements shaped according to the specified anisotropic metric field. We propose an alternative approach to anisotropic mesh generation, relying on the notion of locally uniform anisotropic mesh. A locally uniform anisotropic mesh is a mesh such that the star around each vertex v coincides with the star that v would have if the metric on the domain was uniform and equal to the metric at v. This definition allows to define a simple refinement algorithm which relies on elementary predicates, and provides, after completion, an anisotropic mesh in dimensions 2 and 3.

In this paper, a novel Delaunay-based variational approach to isotropic tetrahedral meshing is presented. To achieve both robustness and efficiency, we minimize a simple mesh-dependent energy through global updates of both vertex positions and connectivity. As this energy is known to be the ∠ 1 distance between an isotropic quadratic function and its linear interpolation on the mesh, our minimization procedure generates well-shaped tetrahedra. Mesh design is controlled through a gradation smoothness parameter and selection of the desired number of vertices. We provide the foundations of our approach by explaining both the underlying variational principle and its geometric interpretation. We demonstrate the quality of the resulting meshes through a series of examples.

We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC.The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem.

This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.

No abstract available.

This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The ilrst one is a method based on the Gram-Schmidt ortho,gonalisation process which has been proposed by Clark:son [Cla92]. We review the analysis of Clarkson and propose a variant of his method. The second method is arAextension ton x n determinants of the ABDPY method [ABD+94] which works only for 2 x 2 and 3 x 3 determinants. Both methods compute the signs of a n x n determinants whose entries are integers on b bits, by using an exact arithmetic on only b + O(n) bits. Furthermore, both methods are adaptive, dealing quickly with easy cases and resorting to the full-length computation only for null determinants.

No abstract available.

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions.Specifically, if S is a set of n points in general position in Jf?-d, the complexity of its Voronoi diagram under the Lm metric, and also under a simplicial distance function, are both shown to be qn[dlzl ).The upper bound for the case of the Lm metric folIows from a new upper bound, also proved in this paper, on the complexity of the union of n axis-parallel hypercubes in Eld.This complexity is @(n ~d/21 ), for d > 1, and it improves to @(nld/2J ), for d ~2, if all the hypercubes have the same size.Under the L1 metric, the complexity of the Voronoi diagram of a set of n points in general position in IR3 is shown to be @(n2 ).We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations.

We present a new technique to display a scene of three-dimensional isothetic parallelepipeds (3D-rectangles), viewed from infinity along one of the coordinate axes (axial view). In this situation, there always exists a topological sorting of the 3D-rectangles based on the relation of occlusion (a dominance relation). The arising total order is used to generate the axial view, where the two-dimensional view of each 3D-rectangle is incrementally added, starting from the closest 3D-rectangle. The proposedscene-sensitivealgorithm runs in timeO(Nlog2N+dlogN), whereNis the number of 3D-rectangles anddis the number of edges of the display. This improves over the previously best known technique based on the same approach.

We show, in this paper, how one can probe a class of non convex polyhedra and scenes of disjoint such polyhedra. A polyhedron of that class has convex faces; any two faces are not coplanar and any two edges are not colinear. The basic step of our method is a strategy for probing a single simple polygon with no colinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that discovers the exact shape of a simple polygon with no colinear edges by means of at most 3n - 3 probes, which is shown to be optimal in the worst-case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in the supporting planes of the faces of a scene of polyhedra of the class above. If the scene consists of k polyhedra with altogether n faces, we show that 8n2 - 6n + k probes are sufficient to discover the exact shapes of the polyhedra.

The authors present a strategy for discovering the exact shape of a simple (but not necessarily convex) polygon by means of a minimal number of simple probes. When each probe outcome consists of a contact point, a ray measuring that point and the normal to the object at the point, it is shown that 3n-3 probes are necessary and sufficient to discover the exact shape of a polygon with n noncollinear edges. Each probe can be determined in O(log n) time, yielding on O(n log n)-time O(n)-space algorithm.>

We present an optimal algorithm to reconstruct the planar cross section of a simple object from data points measured by rays. The rays are semi-infinite curves representing, for example, the laser beam or the articulated arms of a robot moving around the object. The object is assumed to be a unique simply connected object, and the contour to be reconstructed is a simple polygon having the data points as vertices and intersecting none of the measuring rays. Such a contour does not exist for any given sets of points and rays but only for legal data. In this paper, we prove that the solution to the contour problem is unique whenever such a solution exists. For a set of n points and n rays, the algorithm presented here provides in Ο(nlogn) time, a polygon which is the solution to the contour problem when the data are legal. Updating this contour if a new measure is available can be done in Ο(logn) time. Both results are asymptotically optimal in the worst-case. Moreover, once the solution has been found, we can check if the data are legal in Ο(nlogn) time.