Next: Singularities Up: Indirect Triangulation of 3D Surfaces Previous: Surface Metric Tensor

## Parametric Space Meshing

The meshing of the parametric space is performed by a planar mesh generator, that must be able to produce anisotropic meshes and to accept arbitrarily subdivided boundary (on input). The first requirement stems from the generally anisotropic nature of the principal surface metric tensor, the second one ensures the conformity of the compound mesh consisting of several meshes on adjacent surfaces. Therefore, the advancing front technique was chosen as an appropriate candidate.

The general scheme of a planar AFT is described by the following basic steps:

• setup the initial front consisting of boundary edges,
• while the front is not empty, do
• select an edge from the front,
• calculate the position of the ideal'' point (forming a tentative equilateral triangle ),
• search the neighbourhood of point for the most suitable candidate to form a new ,
• perform the intersection check to avoid overlapping of with any already existing edge in the neighbourhood,
• if the intersection check fails, go to the previous step and search for the next most suitable candidate or increase the neighbourhood if there are no more candidates (including point ),
• update the front (remove already existing edges forming from the front and insert the newly created edges in the front).
The formulation of the AFT for the generation of anisotropic meshes requires a proper attention to be paid especially to the computation of the location of the ideal'' point and consequently also to the shape of its neighbourhood. Clearly, the point should be equally distant in the proper anisotropic metric from both ends of edge and this distance should be equal to the size of edge measured in the same metric (i.e. of the same type). Then the tentative would be of the equilateral shape in the real space if a constant target element size was used. Similarly, the neighbourhood of the ideal'' point is a locus of points in the parametric space, distance of which measured again in the same metric is not larger than a certain threshold value, typically related to the locally required element size. However, if the metric is variable, which is usually the case, the lengths in the parametric space should be calculated according to Eq. (29), which makes the computation of the position of the ideal'' point non-trivial and computationally demanding. It may be therefore convenient to use a more intuitive approach based on the ellipse of stretches. This ellipse can be constructed at each point of the parametric space from the surface metric tensor as was described in Subsection Surface Metric Tensor. The ideal'' point is then located on this ellipse, centered in the middle of the selected edge , using heuristic rules ensuring that the tentative triangle follows the stretch. This is demonstrated in Figure 3 that shows edge and the ellipse of stretches built at the center of that edge. Let is the ratio of the lengths of the minor and major half-axes of the ellipse . Then the location of point should be somewhere between point , which is ideal location for equal to , and point , which is appropriate for approaching zero. This can be achieved by using the heuristic interpolation function

 (31)

To ensure that the interpolation is done along the ellipse, it is better to rewrite Eq. (31) in terms of the angle that is zero for point

 (32)

Note that is the real angle between the major half-axis and the line connecting a particular point on the ellipse with the ellipse center. The movement of point along the ellipse is demonstrated for various ratios in Figure 4 and for various angles of edge in Figure 5.

Next: Singularities Up: Indirect Triangulation of 3D Surfaces Previous: Surface Metric Tensor

Daniel Rypl
2005-12-07