6.4.4 Boundary Refinement Algorithm



next up previous contents index
Next: 6.5 Triangulation Up: 6.4 Boundary Refinement Previous: 6.4.3 Boundary Grid Point

6.4.4 Boundary Refinement Algorithm

 

Combining the refinement criterion with the grid point insertion in a loop over all boundary elements yields the refinement algorithm. The refinement of an edge creates two new edges and one additional boundary grid point. These changes are immediately applied to the global graph data which in turn affect the loops that are performed over all edges and over all nodes in the vicinity of the current edge. Due to proper functional interfaces this does not pose an implementation problem, but a global variable is needed to indicate whether a refinement took place during the last scan of all edges and the algorithm terminates when the final scan of all edges did not reveal an edge to be refined.

 

This algorithm is simplified and reflects only the basic flow of the real implementation.

  
Figure 6.20: The interface edge and its selected quadtree buckets.

To determine all nodes in vicinity of the boundary edge efficiently, the quadtree structure can be utilized as shown in Figure 6.20. A selection quadrangle is constructed for the edge which contains the circle . This selection quadrangle (dashed lines in Figure 6.20) intersects only the shaded buckets and hence only the points are subject to further investigation. One can easily argue that this bucket selection method will cause the refinement algorithm to show an overall average complexity , where is the number of boundary edges (after refinement) and is the number of points (also after refinement). Examples and applications of the boundary refinement algorithm can be found in Section 6.7.


Martin Stiftinger
Thu Oct 13 13:51:43 MET 1994