Civil Engineering Reference
In-Depth Information
5.3.3 Boundary recovery by introducing Steiner points
5.3.3.1 Introduction
With the help of additional points, missing edges and facets could be recovered. An edge
is represented as a series of broken line segments separated by Steiner points, and a face is
represented by a concatenation of sub-triangles supported on Steiner points. Such meshes are
known as conforming DT (Karamete et al. 2000; Shewchuk 2008), and if topological integ-
rity of boundary edges and facets are not required, the boundary recovery process can stop
at this point. However, if a
constrained
DT including topological integrity is required, all
Steiner points have to be removed or re-positioned towards the interior of the domain. George
et al. (2003) improved their previous work (George et al. 1991) to propose a method to mesh
an arbitrary polyhedron. By this method, Steiner points are first inserted on the constrained
boundary edges and faces, which are suppressed one by one later in a subsequent process. A
triangulation of the missing edges/facets is constructed by connecting those Steiner points
introduced at the surface, and flat elements of zero volume are created to recover the related
topological structure. Du and Wang (2004) inserted Steiner points on boundaries through
a heuristic approach to reduce the number of Steiner points. They used an edge-swap proce-
dure on the missing boundary facets to remove some of the Steiner points. However, there
is a drawback in the method proposed by George et al. (2003) and Du and Wang (2004): a
number of
locked
Steiner points are generated, which could not be easily removed. Chen et
al. (2011) combined the work of Du and Wang and Liu et al. (2007) by employing the
small
polyhedron reconnection
to reduce the number of Steiner points in the final mesh. However,
their method still faces the problem of
locked
Steiner points. Guan et al. (2006) proposed a
technique named
dressing wound
. Compared to the method proposed by George et al. or Du
and Wang, it introduced more Steiner points; however, this method provided a new perspec-
tive for the boundary recovery problem in the way how Steiner points could be removed. Si
and Gaertner (2011) introduced Steiner points to edges and faces so as to preserve them in
the Delaunay point insertion process, and boundary faces will exist as a concatenation of
small triangular facets. These Steiner points are to be removed as far as possible at a later
stage to ensure topological integrity with the given boundary surface.
To sum up, there are still rooms for improvement in boundary recovery for meshing
arbitrary polyhedrons. Ideas for the boundary recovery of the 3D DT will be discussed to
address some of the difficulties. The method described in Section 5.3.3.2 focuses on a sys-
tematic removal of Steiner points. As a departure from the previous works, in the process
of removing Steiner points, the sequence and the locations in the removal of these points
are optimised to reduce the number of
locked
Steiner points as much as possible. Moreover,
a linear programming optimisation is adopted to determine the feasible space in relocating
Steiner points. Compared with Laplacian smoothing-based methods, it guarantees finding
feasible positions for Steiner points should they exist.
5.3.3.2 Insertion algorithm and boundary recovery
For a polyhedron bounded by a set of triangular facets, the 3D DT of the boundary points
will generate the convex hull of the points, but there is no guarantee that the boundary fac-
ets of a concave or multi-connected polyhedron will be present in the DT. For the boundary
integrity of a general polyhedron, additional work is needed to be done after point insertion.
Following the partial recovery of some edges and facets by local element swaps 2-3, 3-2
and 4-4 (Lo 1997), Steiner points can be inserted to recover the missing boundary edges
and facets, which have to be removed or repositioned to ensure the topological integrity of
