## 3 Method
### The Delaunay Mesh Construction Algorithm  
The vertex inserting is considered as an improved version of the edge splitting. For a local non-Delaunay mesh \(M\), it is possible to satisfy the local Delaunay property by choosing the appropriate position for inserting a new vertex. First, an assumption of a general situation and related inferences is given. As shown in Figure 3, the local non-Delaunay mesh \(M\) consists of four vertices \(v_{i},v_{g},v_{j}\) and \(v_{k}\). For a non-locally Delaunay edge \(e_{ij}\), the sum of the two opposite angles \(\angle v_{i}e_{k}v_{j}\)  
Figure 2: **(a)** Schematic of a 1-ring neighborhood \(\Omega(v_{i})\); **(b)** standard operations for the remeshing algorithm. and \(\angle v_{i}v_{g}v_{j}\) is greater than \(\pi\). In this case, at least one of the two opposite angles of \(e_{ij}\) exists as an obtuse angle, and \(e_{ij}\) is the longest edge of this obtuse triangle \(t_{ijk}\). Such that \(e_{ij}\) is not the shortest edge in the set \(E_{i}=\{e_{ij}|e_{ij}\in\Omega(v_{i})\}\) because there must exist both \(e_{ij}\) and \(e_{ik}\) belonging to \(\Omega(v_{i})\). Thus, we assume that edge \(e_{ia}\in E_{i}\) is the shortest edge of \(E_{i}\). As shown in Figure 3, the same length on \(e_{ij}\) is intercepted at point \(v_{a}^{\prime}\), and \(O\) is the midpoint of this length. Given any inserted vertex \(s\) on the line between \(O\) and \(v_{a}^{\prime}\), the intersection of the gray area with \(e_{ij}\) is the targeted range of \(s\). Considering the relation of \(l_{Az_{i}}=l_{sv_{i}}=l_{Bv_{i}}\), the suitable location can be determined by the following conditions:  
\[\angle v_{i}v_{k}s+\angle v_{i}v_{g}s\leq\angle v_{i}As+\angle v_{i}Bs=\frac{2 \pi-\angle v_{k}v_{i}v_{g}}{2}<\pi, \tag{2}\]  
Similarly, we can also obtain a vertex \(s^{{}^{\prime}}\) for the case of \(v_{j}\). If the regions of \(s\) and \(s^{{}^{\prime}}\) are overlapped, the inserted vertex is chosen as the midpoint in the regions. However, if these regions are not overlapped, the above process can be repeated and the convergence of it are acquired due to the monotonically of \(sum_{1}=\angle v_{i}v_{k}s+\angle v_{i}v_{g}s\) and \(sum_{2}=\angle sv_{k}v_{j}+\angle sv_{g}v_{j}\). As the region where \(s\) is taken gradually moves away from \(v_{i}\) to \(v_{j}\), \(sum_{1}\) monotonically increases and \(sum_{2}\) monotonically decreases. Both of them are less than \(\pi\), which means \(e_{is}\) and \(e_{ij}\) can fulfill the local Delaunay property. The improved vertex inserting operation can choose the suitable location for the newly inserted vertex \(s\), and then the local Delaunay property can be achieved. After the improved vertex inserting operation, the Delaunay property of the region consisting of four vertices \(v_{i},v_{g},v_{j}\) and \(v_{k}\) is satisfied. These new angles \(\angle v_{i}sv_{k},\angle v_{i}sv_{g}\) and \(\angle v_{j}sv_{g}\) destroy the local Delaunay property of the surrounding region, so the repeated vertex inserting is acceptable. However, in the case of narrow triangle appearance, it may repeat the vertex inserting operation endlessly. Therefore, a control parameter \(\delta\) should be designed to detect narrow triangles and avoid this kind of useless repetitive operation. For the original mesh \(M,l_{min}\) is the length of the shortest edge. \(\theta_{min}\) is the smallest angle. \(h\) is the distance between vertex \(v_{k}\) and bottom edge \(e_{ij}\) of triangle \(t_{ijk}\). \(d\) is the distance between vertex \(v_{k}\) and inserted vertex \(v_{s}\). For a Delaunay mesh \(DM\) complied with the local Delaunay property, all the edges of \(DM\) satisfy the following conditions:  
* Conditions 1: As shown in Figure 4a, for any triangle \(t_{ijk}\) in \(M\), this state is always satisfied: \[d\geq h=l\cdot\sin(\theta)\geq l_{min}\cdot\sin(\theta_{min}),\] (3)  
Figure 3: Choosing the position of newly insert vertex. For the original vertex \(v_{i}\), the newly inserted vertex \(s\) on the line segment between \(O\) and \(v_{a}^{\prime}\).