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 nontrivial 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 halfaxes 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 halfaxis 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
20051207