|
CGAL 5.5.1 - 3D Alpha Wrapping
|
|
CGAL 5.5.1 - 3D Alpha Wrapping
|
Various tasks in geometric modeling and processing require 3D objects represented as valid surface meshes, where "valid" refers to meshes that are watertight, intersection-free, orientable, and 2-manifold. Such representations offer well-defined notions of interior/exterior and geodesic neighborhoods.
3D data are usually acquired through measurements followed by reconstruction, designed by humans, or generated through imperfect automated processes. As a result, they can exhibit a wide variety of defects including gaps, missing data, self-intersections, degeneracies such as zero-volume structures, and non-manifold features.
Given the large repertoire of possible defects, many methods and data structures have been proposed to repair specific defects, usually with the goal of guaranteeing specific properties in the repaired 3D model. Reliably repairing all types of defects is notoriously difficult and is often an ill-posed problem as many valid solutions exist for a given 3D model with defects. In addition, the input model can be overly complex with unnecessary geometric details, spurious topological structures, nonessential inner components, or excessively fine discretizations. For applications such as collision avoidance, path planning, or simulation, getting an approximation of the input can be more relevant than repairing it. Approximation herein refers to an approach capable of filtering out inner structures, fine details and cavities, as well as wrapping the input within a user-defined offset margin.
Given an input 3D geometry, we address the problem of computing a conservative approximation, where conservative means that the output is guaranteed to strictly enclose the input. We seek unconditional robustness in the sense that the output mesh should be valid (oriented, 2-manifold, and without self-intersections), even for raw input with many defects and degeneracies. The default input is a soup of 3D triangles, but the generic interface leaves the door open to other types of finite 3D primitives such as triangle soups and point sets.
Many approaches have been devised to enclose a 3D model within a volume, featuring different balances between the runtime and quality (i.e., tightness) of the approximation. Within the simplest cases, an axis-aligned or oriented bounding box clearly satisfies some desired properties; however, the approximation error is uncontrollable and often very large. Computing the convex hull of the input also matches some of the desired properties and improves the quality of the result, albeit at the price of increasing the runtime. However, the approximation remains crude, especially in the case of several components.
The convex hull is, in fact, a special case of alpha shapes (Chapter_3D_Alpha_Shapes). Mathematically, the alpha shape is a subcomplex of the Delaunay triangulation, with simplicies being part of the complex depending on the size of their minimal (empty) Delaunay ball. Intuitively, constructing 3D alpha shapes can be thought of as carving 3D space with an empty ball of user-defined radius alpha. Alpha shapes yield provable, good piecewise-linear approximations of a shape [1], but are defined on point sets, whereas we wish to deal with more general input data, such as triangle soups. Even after sampling the triangle soup, alpha shapes do not guarantee to be conservative for any alpha. Finally, inner structures are also carved within the volumes, instead of being filtered out.
Inspired by alpha shapes, we replace the above notion of carving by shrink-wrapping: we iteratively construct a subcomplex of a 3D Delaunay triangulation by starting from a simple 3D Delaunay triangulation enclosing the input, and then iteratively removing eligible tetrahedra that lie on the boundary of the complex. In addition, the underlying triangulation—and thus the complex incidentally—is refined as shrinking proceeds. Thus, instead of carving from the convex hull of the input data as in alpha shapes, we construct an entirely new mesh through a Delaunay refinement-like algorithm. The refinement algorithm inserts Steiner points on the boundary of an offset volume, defined as a level set of the unsigned distance field to the input.
This process both prevents the creation of inner structures within the output and avoids superfluous computations. In addition, detaching our mesh construction from the geometry and discretization of the input has several advantages: (1) the underlying data is not restricted to a specific format (triangle soups, polygon soups, point clouds, etc.) as all that is required is answering three basic geometric queries: (a) the distance between a point and the input, (b) the projection of a query point onto the input, (c) an intersection test between a tetrahedron and the input, and (2) The user has more freedom to trade tightness to the input for final mesh complexity, as constructing a conservative approximation on a large offset of the input requires fewer mesh elements.
Initialization. The algorithm is initialized by inserting the eight corner vertices of a loose bounding box into a 3D Delaunay triangulation. In the 3D Delaunay triangulation of CGAL, all triangle facets are adjacent to two tetrahedron cells. Each facet of the boundary of the Delaunay triangulation, which coincides with one facet of the convex hull of the triangulation vertices, is adjacent to a so-called infinite tetrahedron cell, an abstract cell connected to the so-called infinite vertex to ensure the aforementioned double-facet adjacency. Initially, all infinite cells are tagged as outside, and all finite tetrahedron cells are tagged as inside.
Shrink-wrapping. The shrink-wrapping algorithm proceeds by traversing the cells of the Delaunay triangulation from outside to inside, flood-filling from one cell to its adjacent cell, and tagging the adjacent cell as outside whenever possible (the term possible is specified later). Flood filling is implemented via a priority queue of Delaunay triangle facets representing the traversal between the two adjacent cells of the facet, from outside to inside. These triangle facets are referred to as gates in the following.
Given an outside cell and its adjacent inside cell, the common facet (i.e., a gate) is said to be alpha-traversable if its circumradius is larger than the user-defined parameter alpha, where circumradius refers to the radius of the relating triangle's Delaunay ball. Intuitively, cavities smaller than alpha are not accessible as their gates are not alpha-traversable.
Initialized by the alpha-traversable gates on the convex hull, the priority queue contains only alpha-traversable gates and is sorted by decreasing order of the circumradius of the gate. Traversal can be seen as a continuous process that advances along dual Voronoi edges of the gates, with a pencil of empty balls circumscribing the gate.
When traversing from an outside cell \( c_o \) to an inside cell \( c_i \) through an alpha-traversable facet \( f \), two criteria are tested to prevent the wrapping process from colliding with the input:
(1) We check for an intersection between the dual Voronoi edge of \( f \), i.e. the segment between the circumcenters of the two incident cells, and the offset surface, defined as the level set of unsigned isosurface to the input. If one or several intersections exists, the first intersection point, along the dual Voronoi edge oriented from outside to inside is inserted into the triangulation as a Steiner point.
(2) If the dual Voronoi edge does not intersect the offset surface but the neighboring cell \( c_i \) intersects the input, we compute the projection of the circumcenter of \( c_i \) onto the offset surface, and insert it into the triangulation as a Steiner point (which destroys \( c_i \)).
After each of the above Steiner point insertions, all new incident cells are tagged as inside, and the newly alpha-traversable gates are pushed into the priority queue.
If none of the above two criteria are met, the neighboring cell \( c_i \) is traversed and tagged as outside. Alpha-Traversable facets of \( c_i \) that are separating inside from outside cells are pushed as new gates into the priority queue.
Once the queue empties—a process that is guaranteed as facets (and their circumradii) become smaller due to the insertion of new Steiner points—the construction phase terminates. The output triangle surface mesh is extracted from the Delaunay triangulation as the set of facets separating inside from outside cells.
The figure below depicts the steps of the algorithm in 2D.
The algorithm is proven to terminate and to produce a 2-manifold triangulated surface mesh that strictly encloses the input data. The key element to the proof is that we wrap from outside to inside and never allow a cell that intersects the input to be flagged inside. Furthermore, both criteria that lead to refinement of the triangulation insert Steiner points that are guaranteed to break the cells in need of refinement and reduce the neighbor facets circumradii.
Because the main refinement criterion is the insertion of an intersection between a dual Voronoi edge and an offset of the input, or the projection of a Voronoi vertex onto the offset of the input, the algorithm has similarities to popular meshing algorithms based on Delaunay filtering and refinement (see Chapter_3D_Mesh_Generation).
Our algorithm takes as input a set of triangles in 3D, provided either as a triangle soup or as a triangle surface mesh, and two user-defined scalar parameters: the alpha and the offset values. It proceeds by shrink-wrapping and refining a 3D Delaunay triangulation starting from a loose bounding box of the input. The parameter alpha refers to the size of cavities or holes that cannot be traversed during wrapping, and hence to the final level of detail, as alpha acts like a sizing field in a common Delaunay refinement algorithm (Chapter_3D_Mesh_Generation). The parameter offset refers to the distance between the vertices of the refined triangulation and the input, so that a large offset translates into a loose enclosing of the input. This second parameter offers a means to control the trade-off between tightness and complexity.
The main entry point of the component is the global function CGAL::alpha_wrap_3() that generates the alpha wrap; this function takes as input a polygon soup or a polygon mesh. There is no prerequisite on the input connectivity so that it can take an arbitrary triangle soup, with islands, self-intersections, or overlaps, as well as combinatorial or geometrical degeneracies.
The underlying traits class must be a model of the Kernel concept. It should use a floating point number type as inexactness is inherent to the algorithm since there is no closed form description of new vertices on the offset surface.
The output is a triangle surface mesh whose type is chosen by the user, under the constraint that it must be a model of the MutableFaceGraph concept.
The two parameters of the algorithm impact both the level of detail and complexity of the output mesh.
The main parameter, alpha, controls whether a Delaunay facet is traversable during shrink-wrapping. Alpha's main purpose is to control the size of the empty balls used during wrapping, and thus to determine which features will appear in the output: indeed, a facet is alpha-traversable if its circumradius is larger than alpha; hence, the algorithm can only shrink-wrap through straits or holes with diameters larger than alpha. A second, less direct consequence is that as long as a facet has a circumradius larger than alpha, the incident inside cell will be visited and possibly refined. Therefore, when the algorithm terminates, all facets have a circumradius smaller than alpha. This parameter thus also behaves like a sizing criterion on the triangle facets of the output.
The second parameter, the offset distance, controls the distance from the input and thus the definition of the offset isosurface onto which the vertices of the output mesh are located. This parameter controls the tightness of the result, which has, in turn, a few consequences. Firstly, locating vertices away from the input enables the algorithm to generate a less complex mesh, especially in convex areas. A trivial example of this behavior would be a very dense mesh of a sphere, for which an as-tight-as-possible envelope would also be very dense. Secondly, the farther the isosurface is from the input, the more new points are inserted through the first criterion (i.e., through intersection with dual Voronoi edge, see Section Algorithm); thus, the quality of the output improves in terms of angles of the triangle elements. Finally, and depending on the value of the alpha parameter, a large offset can also offer defeaturing capabilities. However using a small offset parameter will tend to better preserve sharp features as projection Steiner points tend to project onto convex sharp features.
By default, we recommend to set the offset parameter to a small fraction of alpha, so that alpha becomes the main parameter that controls the final level of detail.
The image below illustrates the impact of both parameters.
The offset parameter is crucial to our approach because it guarantees that the output is a closed, 2-manifold surface mesh. Indeed, and even when the input is a zero-volume structure such as a single 3D triangle, the output wrap is a thin volume enclosing the said triangle Figure 61.2.
Users should keep in mind that the wrapping algorithm has no means of determining whether it is acting on the inside or the outside of the unsigned distance field, and will thus produce two-sided wraps in the case of holes in the input and values of alpha smaller than the size of the holes.
The charts below plots the computation times of the wrapping algorithm on the Thingi10k dataset, as well as the complexity of the output triangle mesh.
Here is an example with an input triangle mesh, with alpha set to 1/20 of the bounding box longest diagonal edge length, and offset set to 1/30 of alpha (i.e., 1/600 of the bounding box diagonal edge length).
File Alpha_wrap_3/triangle_mesh_wrap.cpp
Here is an example with a point cloud.
File Alpha_wrap_3/point_set_wrap.cpp
1.8.13