Local refinement based on the 7-triangle longest-edge partition

A vailable online at www.sciencedirect.com Mathematics and Computers in Simulation 79 (2009) 2444–2457 Local refinement based on the 7-triangle longest-edge partition Ángel Plazaa,∗, Alberto Márquezb, Auxiliadora Moreno-Gonzálezb, José P. Suárezc aDepartment of Mathematics, ULPGC, 35017-Las Palmas de Gran Canaria, Spain bDepartment of Mathematics, University of Seville, Spain cDepartment of Cartography and Graphic Engineering, ULPGC, Spain Available online 31 January 2009 Abstract The triangle longest-edge bisection constitutes an efficient scheme for refining a mesh by reducing the obtuse triangles, since the largest interior angles are subdivided. In this paper we specifically introduce a new local refinement for triangulations based on the longest-edge trisection, the 7-triangle longest-edge (7T-LE) local refinement algorithm. Each triangle to be refined is subdivided in seven sub-triangles by determining its longest edge. The conformity of the new mesh is assured by an automatic point insertion criterion using the oriented 1-skeleton graph of the triangulation and three partial division patterns. © 2009 IMACS. Published by Elsevier B.V. All rights reserved. Keywords: Local refinement; Longest-edge based algorithms; Skeleton 1. Introduction In the last years many different strategies have been developed to locally refine triangular and tetrahedral meshes. There are two main steps in local adaptive refinement: the refinement of a subset of elements based on local error indicators, and the consistent transition between refined and unrefined cells [1,3]. We refer to the latter as ‘mesh conformity’. Several refinement and improvement techniques for two- and three-dimensional triangulations are available [2,5,13,4,7]. Some of them are based on edge bisection of the elements, triangles or tetrahedra. Intwodimensions,the4-TriangleLongest-Edge(4T-LE)partitionandtheassociatedlocalrefinementwasintroduced by Rivara in [13,16,14]. This partition was extended to tetrahedral meshes in [8], where the tetrahedral mesh is locally refined after the skeleton of the triangulation, that is, the set of triangular faces of the tetrahedra, has been divided by the 4T-LE partition. The 4T-LE partition of a given triangle tnever produces an angle smaller than half the minimum original angle [18], and besides, it shows a remarkable mesh quality improvement [16] between certain limits, as recently studied in [12]. In order to devise a new strategy to improve mesh quality through iterative refinement, in this paper we use a new triangle partition, the seven-triangle longest-edge (7T-LE) partition [6]. This partition, first, positions two equally spaced points per edge and, then, the interior of the triangle is divided into seven sub-triangles in a manner compatible with the subdivision of the edges. Three of the new sub-triangles are similar to the original, two are similar to the new triangle also generated by the 4T-LE, and the other two triangles are, in general, better shaped. ∗Corresponding author. Tel.: +34 928 458827; fax: +34 928 458711. E-mail address: [email protected] (Á. Plaza). 0378-4754/$36.00 © 2009 IMACS. Published by Elsevier B.V. All rights reserved. doi:10.1016/j.matcom.2009.01.009 Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 2445 Fig. 1. (a) LE partition of triangle t0and (b) 4T-LE partition of triangle t0. The outline of this paper is as follows: Section 2summarizes the 4T-LE partition and its improvement property, showing the limitations of this improvement. Section 3presents the new 7T-LE partition and shows in a geometric diagram that the new triangles generated by the 7T-LE partition are better shaped that those generated by the 4T-LE partition. Section 4introduces the new local refinement algorithm based on the 7T-LE partition, by using the 1-skeleton oriented graph approach [20]. Also the inverse counterpart algorithm for derefining a sequence of triangulation is presented. The paper closes with some conclusions and ongoing research. 2. The 4T-LE partition and its improvement property Here the 4-triangle longest-edge partition and its self-improvement is summarized. The section closes with an example illustrating the limits of the characteristic improvement. Inthe following,foranytrianglet,theedgesandangleswillberespectivelydenoted indecreasing orderr1≥r2≥r3, and γ≥β≥α. Furthermore, t(α, β, γ ) will be the class of similar triangles with angles γ≥β≥α. Interchangeably, twill represent an element of the class t∈t(α, β, γ ) or the class itself. Definition 1. (edge bisection and longest-edge bisection) The longest-edge (LE) partition of a triangle t0is obtained by joining the midpoint of the longest edge of t0with the opposite vertex (Fig. 1 (a)). The 4-triangle longest-edge (4T-LE) partition is obtained by joining the midpoint of the longest edge to the opposite vertex and to the midpoints of the two remaining edges (see Fig. 1(b)). Note that the two subtriangles with edges coincident with the longest edge of the parent are similar to the parent. The remaining two subtriangles form a similar pair that, in general, are not similar to the parent triangle. We refer to such new triangle shapes as ‘dissimilar’ to those preceding. Since the first 4T-LE partition of any triangle t0introduces two new edges parallel to the edges of t0, the first 4T-LE partition of a single triangle t0produces two triangles similar to t0and two (potentially) new similar triangles t1; and, consequently, the iterative 4T-LE partition of any triangle t0introduces (at most) one new dissimilar triangle per iteration [16]. Theiterative4-triangle longest-edge partition produces a finite sequence of ‘better’trianglessatisfyingtheproperties illustrated in the following diagram until triangle tNbecomes non-obtuse, where αI, and γIare respectively the smallest and the largest angles of triangle ti. The arrow emanating from triangle tito triangle ti+1means that the (first) 4-triangle longest-edge partition of triangle tiproduces the new dissimilar triangle ti+1: We refer the reader to [12] in which the self-improvement property of the 4T-LE partition has been studied in detail. By way of example, consider the initial triangle t0with angles (α, β, γ )=(1.95,32.595,145.455). The evolution of the smallest angle and largest angle for each of the new triangles generated by the 4T-LE partition is shown in Fig. 2. 2446 Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 Fig. 2. Evolution of minimum and maximum angles by the 4T-LE partition of an initial triangle through iterative refinement. Therefore, the self-improvement property of the 4T-LE partition, as proved both experimentally and mathematically in [12], needs to be handled with caution as this example clearly demonstrates. Since the 4T-LE partition is based on the bisection of the edges, by locating midpoints on the edges of the triangle, we have introduced here a new triangular partition based on the trisection of the edges at equally spaced points. Our goal is to use this partition to introduce a new local refinement algorithm. 3. The 7-triangle longest-edge partition In this section, a new longest-edge partition is presented. This partition is based on the trisection of the edges of the triangle, instead of the bisection of the edges as the 4T-LE. Definition 2. (7-triangle longest-edge partition) The 7-triangle longest-edge (7T-LE) partition of a triangle t0is obtained as follows: 1. Position two equally spaced points per edge and join them, using parallel segments, to the edges, at the points closest to each vertex (see Fig. 3 (a)). 2. Join the two interior points of the longest edge of the initial triangle to the base points of the opposite sub-triangle in such a way that they do not intersect (see Fig. 3(b)). 3. Triangulate the interior quadrangle by the shortest diagonal (see Fig. 3(c)). Fig. 3. 7T-LE partition of triangle t0: (a) edge trisection and cut off the corner triangles by parallel segments to the edges, (b) interior points of the LE are connected to the base points of opposite triangle and (c) triangulation of the interior quadrangle by the shortest diagonal. Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 2447 Fig. 4. Evolution of minimum and maximum angles by the 7T-LE partition. It should be noted that, due to parallelism, the first three sub-triangles obtained are similar to the initial one (t0), whereas the second two sub-triangles are similar to the first-class Rivara triangle (t1). Finally, the last two triangles are not given with the 4T-LE Rivara partition and, consequently, will be called here, tn1. Note also that the area of sub-triangles t0and t1is 1/9 of the area of the initial triangle, whereas the area of each sub-triangle tn1is 2/9ofthe area of the initial triangle. In order to compare the evolution of new triangles for the 7T-LE partition we consider the same initial triangle as before, that is t0with angles (α, β, γ )=(1.95,32.595,145.455). The evolution of the smallest angle and largest angle for each of the new triangles generated by the 7T-LE partition is shown in Fig. 4. It should be noted that the new triangles are better shaped that those produced by the 4T-LE partition. Basing our hypotheses on the trisection of the edges, some other partitions may be considered. We present here one of these possibilities, also based on a local Delaunay triangulation: Definition 3. (7-triangle Delaunay partition) The 7-triangle Delaunay (7T-D) partition of a triangle t0is obtained as follows: 1. Position two equally spaced points per edge. 2. Triangulate the cloud of points using the Delaunay triangulation (see Fig. 5(b)). It should be noted that the 7T-D partition is not equivalent to the 7T-LE partition since the division of the interior hexagon depends upon the specific distribution of the distances between the vertices (see Fig. 5). Fig. 5. Two different 7T partitions of an obtuse triangle t0. 2448 Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 Fig. 6. 7T-LE partition and 3T-LE partition of an obtuse triangle t0. 3.1. Mesh quality improvement for the 7T-LE partition Note that the new triangle tn1generated by the 7T-LE partition may also be seen as one of the triangles generated by the 3T-LE partition division, used in the local refinement associated with the 4T-LE partition (see Fig. 6). Lemma 4. The number of dissimilar triangles arising in the iterative application of the 7T-LE partition to any initial triangle t0≡ABC is bounded. See reference [6] for a proof of this result, and for a discussion and comparison between partition 4T-LE and 7T-LE depending on the shape of the initial triangle. In order to experimentally show the result of previous Lemma, we use here a geometrical diagram introduced in [10]. For a given triangle the longest edge is scaled to have unit length. It follows that the set of all triangles is bounded by this horizontal segment (longest edge) and by two bounding exterior circular arcs of unit radius. This mapping domain comprised by the horizontal segment of extreme points (0,0) and (1,0), the unit circular arcs which center at these extreme points, allows us to represent the shape evolution for the new triangles generated by iterative application of any triangle partition. Here we carried out the following computational experiment. Select a point (x, y) within the mapping domain. Point (x, y) defines the apex of a target triangle with additional vertices at (0,0) and (1,0). For this triangle, 7T-LE division is successively applied as long as a new dissimilar tn1triangle appears. This means that we recursively apply 7T-LE and stop when the shapes of new generated triangles are the same as those already generated in previous refinement steps. The number of such refinements to reach termination defines the number of dissimilar triangles associated with the initial triangles associated with the initial triangle and this numerical value is assigned to the initial point (x, y) chosen. This process is progressively applied to a large sample of triangles (points) uniformly distributed over the domain. Finally, we graph the respective values of dissimilar triangles in a corresponding color map to obtain the result in Fig. 7. The same experiment for the 4T-LE partition is shown in Fig. 8. It should be noted that the dark blue region in the previous figure corresponds to the region in which all the trajectories end, with total independence of the initial position. Therefore, for the 7T-LE partition, a lower bound for the maximum of the smallest angles for triangles tn1is α=30◦corresponding to the apex with x=1/4, or the apex with x=3/4. Note also that the smallest angle in each of the regions generated in this way, is bounded from below with total independence of the initial point of the respective trajectories. This is a remarkable feature in comparison with the evolution of the angles for the 4T-LE partition. In the 4T-LE partition these lower bounds depend on the geometry of the initial triangle. See [12] for details, and observe, for instance, Fig. 9 left. For a better understanding of the self-improvement property of the 4T-LE partition and the limits of this property as given in this paper, the successive triangles obtained have been normalized to share the longest edge. The various triangles obtained in the first test problem are depicted in Fig. 9. The evolution of the new triangles generated by the 7T-LE partition vs. the triangles generated by the 4T-LE partition can be observed, at a first glance, from the diagrams in Fig. 10. There, the apexes of the triangles have been numbered in the order in which they have been generated. Apexes of triangles generated by the 4T-LE partition are joined by a Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 2449 Fig. 7. Color diagram representing triangle classes generated by a Montecarlo experiment for the 7T-LE partition. Fig. 8. Dissimilar triangle classes generated by computer experiment for the 4T-LE partition. Fig. 9. Evolution of dissimilar triangles of example test 1. 2450 Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 Fig. 10. Evolution of the triangles given by the 4T-LE partition (bold line) vs. 7T-LE partition (dashed line) for different initial triangles. bold line, while the apexes of the new triangles coming from the 7T-LE partition are jointed by a dashed line. Note, that in general, triangles on the dashed line are better shaped that the corresponding triangles on the bold line. 4. Local refinement algorithm based on the 7T-LE partition Similarly to the local refinement based on the 4T-LE partition, we present here a local refinement based now on the 7T-LE partition. That is, the particular triangles to be refined the 7T-LE partition is chosen for dividing. Then, in order to assure the conformity of the arising new mesh we use one of the partial partitions given in Fig. 11, where for comparison the partial partitions used by the local refinement based on the 4T-LE partition are also shown. Observe that 4T-LE partitions used 1 midpoint per edge subdivided, while 7T-LE partition used two interior, equally spaced, points per edge subdivided. In the local refinement algorithm presented here we use the concept of 1-skeleton, see reference [20] for details. Here we use the concepts of longest-edge propagation path (LEPP) and 1-skeleton of a two-dimensional triangulation. The (LEPP) of a triangle tinto a given triangulation as defined by Rivara [14] is the ordered list of triangles {t=t0,t 1,...,t n}such that triangle tiis the neighbor triangle of ti−1adjacent to the longest-edge of ti−1. Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 2451 Fig. 11. Partial partitions of a triangle depending on the number of edges subdivided for the 4T-LE local refinement (left) and for the 7T-LE local refinement (right). On the other hand for a triangulation τits 1-skeleton is the undirected graph G1(τ)=G1(P, L), where Pis the set of edges of τand Lrepresents the topological adjacency relationship between two different nodes (edges) of P. So two edges A, and Bare connected in G1(P, L), that is ∃l∈Lsuch that l≈(A, B) if they share a extreme node in τ, that is, if A∩B/=∅. The edges of any triangle may be classified into two types. The longest-edge will be edge type 1, and the other two edges will be type 2. This classification induces an order into the 1-skeleton graph by considering the relation R=‘length of edge xin the triangle is less than length of edge y. This order relation induces an orientation into the graph representing such order. See Fig. 12 for the 1-skeleton (oriented) graph associated to a single triangle (a) and to a whole triangulation (b). Let t0a triangle in a given triangulation τ, and eian edge of t0. We will denote by LEPP (ei,G 1(τ)) the LEPP of the neighbor triangle to t0sharing with t0edge ei. The refinement of triangular meshes involves two main tasks. The first is the subdivision of the target triangles and the second is the propagation to successive neighbor triangles to preserve conformity. If the refinement is uniform then all triangles in the mesh are refined and no propagation is induced on the mesh. Refinement can also be used locally for a small group of triangles in a mesh and in this case a neighbor triangle refinement (propagation) is Fig. 12. 1-skeleton oriented graph for a single triangle (a) and for a whole triangulation (b). 2452 Á. Plaza et al. / Mathematics and Computers in Simulation 79 (2009) 2444–2457 induced in the mesh to preserve conformity. In the LE schemes the longest edge of triangle tis first bisected (or trisected) to form two (or three) subtriangles. Then, to preserve mesh conformity, the refinement is continued to the associated edge neighbor using a longest-edge strategy until the propagating path terminates. In the 4T-LE and also for the 7T-LE scheme, LE refinement propagates through all three neighbors triangles of tas in the basic LE scheme preceding. The refinement may also be viewed as follows: (1) identify and divide by trisection the edges specified by the overall refinement indicators (steps 1 and 2 in the scheme of the algorithm bellow) and (2) subdivide the individual triangles to define the new triangulation (step 3). Concerning computational efficiency, it should be noted that the 7T-LE algorithm is of linear complexity with respect to the number of nodes. In this sense, from the computational efficiency point of view, the 4T-LE and the 7T-LE algorithms are equivalent. However, as can be observed in the example bellow, the 7T-LE algorithm produces denser meshes for the same refinement steps. It is interesting to note that if G1is the 1-skeleton directed graph of a 2D conforming triangulation τ, then G1does not contain cycles [20]. In addition, updating the 1-skeleton directed graph data structure by applying 4T-LE (and also the 7T-LE) partition affects only up to three graph nodes in each refinement step. Note that from a computational point of view, this fact ensures the locality of the 1-skeleton directed graph data structure. An example of local refinement based on the 7T-LE partition is presented in Fig. 13. In both cases only a small region is chosen to be subdivided by the 4T-LE partition, and by the 7T-LE partition. Notice that by the 7T-LE procedure a more localized refinement is achieved in fewer refinement steps. For a comparison of the quality measurement evolution when each partition is locally applied, the mean value of the quality measurement ηhas been used in this example. Bearing in mind that for each triangle t, the quality measurement ηis defined by η(t)=4A√3 l2 1+l2 2+l2 3