## 3 Method
### The Delaunay Mesh Construction Algorithm
Similarly, for the \(v_{j}\), an inserted vertex \(s^{{}^{\prime}}\) is been obtained. * Conditions 2: For original edge \(e\) in \(M\), the condition is also found that: \[\min\{l_{e}|e\in\Omega(v_{i})\}\geq l_{min}\cdot\sin(\theta_{min}),\] (4)
* Conditions 3: As shown in Figure 4b, the distance of the newly inserted vertex from any vertex also satisfies that: \[l_{is}\geq l_{ig}\cdot\sin(\theta_{min})\geq l_{min}\cdot\sin(\theta_{min}),\] (5)  
Therefore, if a new edge \(e_{gg}\) is shown in Figure 4b, whose length is less than \(l_{min}\cdot\sin(\theta_{0})\), the triangle \(l_{ijg}\) could be considered as a narrow triangle. In the practical application, the \(l_{min}\) and \(\sin(\theta_{min})\) do not exist in the same triangle. Thus, a control factor \(\delta\) could be set as \(\delta=k\cdot l_{min}\cdot\sin(\theta_{0}),k\in Z^{+}\) to replace \(l_{min}\cdot\sin(\theta_{0})\). In other words, if the length of a new edge \(e_{gg}\) is less than \(\delta\), the triangle will be considered as a narrow triangle which is collapsible in the algorithm and shown in Figure 4c. This condition is considered as the case of volume destruction to the original mesh because it makes the final narrow triangle compressed into a single edge. A Delaunay mesh construction algorithm is designed and the pseudo code is shown in Algorithm 1. We try to implement the stack using the priority queue approach. Firstly, the control factor \(\delta\) is initialized. Then, we place all non-local Delaunay edges in a priority queue \(Q\) keyed on the sum of the diagonals corresponding to edge \(e\) with the largest sum at the top. The algorithm iterative inserts a newly vertex \(v_{s}\) to split the NLD edge from the queue, and updates the information about all elements in \(\Omega(v_{s})\) such as connectivity and normal vectors. Finally, the edges in the \(D(v_{s})\) should be determined if them are the NLD edges and all of the new NLD edges will be pushed in the priority queue \(Q\). The algorithm will repeat this procedure until the priority queue \(Q\) is empty. Figure 4: (a) Schematic diagram of Case 1; (b) schematic diagram of Case 3; (c) face collapsing. ```
Input: Arbitrary watertight triangle Mesh \(M=(V,E,F)\) Output: A Delaunay Mesh \(DM=(V_{D},E_{D},F_{D})\)
1 Initialization:;
2 First, initialize control factor \(\delta\);
3 Second, initialize the priority queue \(Q\) of the all NLD edges. 4 while\(Q\) is not emptydo
5 Pop the NLD edge \(e_{ij}\) with the largest diagonal sum from \(Q\);
6 /* Determine whether triangles are a narrow triangles */
7\(t_{ijk}\gets T(v_{i},v_{j},v_{k})\), \(t_{ijk}\gets T(v_{i},v_{j},v_{g})\);
8 if\(d_{k}\leq\delta\)then
9 collapseTriangle(\(t_{ijk}\));
10 end if
11 if\(d_{g}\leq\delta\)then
12 collapseTriangle(\(t_{ijk}\));
13
14 end if /* Splitting the NLD edges */
15\(e_{1}\gets e_{ik}\), \(e_{2}\gets e_{ig}\), \(e_{3}\gets e_{jk}\), \(e_{4}\gets e_{jg}\);
16\(r[4]\gets null\);
17 for\(m\gets 1\)to\(4\)do
18\(p_{m}\leftarrow\) FindCrossPoint(\(s_{m},e_{ij}\));
19 if\(m==1||m==2\)then
20\(r[m]\leftarrow\) FindOverlapRange(\(v_{i},p_{m}\));
21
22 end if
23 if\(m==3||m==4\)then
24\(r[m]\leftarrow\) FindOverlapRange(\(p_{m},v_{j}\));
25
26 end if
27
28 end if
29
30 end for
```  
**Algorithm 1**Delaunay mesh construction.