Exact Surface Projection

In the presented approach, the control grid is subjected to the subdivision (temporarily during the projection) only on a single triangle localized from the original control grid (Fig. 51a). The refinement of this triangle is accomplished progressively towards the actual projection. This means that the next level refinement is applied only to that from the four hierarchical descendant sub-triangles of the localized triangle which ``contains'' the projected point (Fig. 51b). This approach enables almost unlimited number of refinements with minimum memory requirements.

The fast setup of the connectivity associated with the target triangle and utilized during the local subdivision is supported by the first level of the global refinement that is precomputed, prior to the actual mesh generation, typically during the initiation of the curvature-based mesh density control (see Subsection Discrete Surface Meshing).

An important aspect of the recursive subdivision consists in the fact
that the shape of the triangles of the control grid on any level of
the subdivision further evolves (the sides of the triangle become
curved) as midside nodes on higher levels are introduced (see Fig. 52).
A robust implementation of the projection therefore requires a reliable
algorithm for the initial triangle localization and consequent
sub-triangle selection (for the progressive refinement). Since the
evolution of the triangle shape during the refinement can be hardly
predicted, the implementation of a tool for the selection correction is of
primary importance. When using the AFT, the projected point is always
in the proximity of the generated mesh with nodes already projected to the
limit surface. The localization of a triangle in the initial control grid
can be therefore very efficiently performed by traversing through the initial
control grid from the target triangle of any of the already
projected nodes in the neighbourhood towards the point being projected
(Fig. 51a). The triangle
localization and sub-triangle selection is further enhanced by taking into account
the relevant midside nodes on the appropriate level of the subdivision
which determine approximately the bow of sides of triangles on that
level. Simultaneously, the sub-triangle selection is traced during the
refinement to enable a backtracking if an invalid selection
is detected. Note that the invalid selection is usually detected with
some delay.^{8} The
correction then consists in traversing the refinement
history in the opposite direction and detecting the highest level on
which a different selection (possibly leading to the correct projection) may
be made. Such a situation is demonstrated in Figure 53,
where the invalid selection (somewhere in
the refinement history) is discovered after four accomplished
refinements. Particularly, the projected point seems to ``fall'' into
neighbour 2 of sub-triangle 3 on the last level of the performed
refinement. Since the two previous selections (1 and 3 when going upwards) in the refinement
history do not allow to choose a better sub-triangle (this means on the side of
neighbour 2 of the last sub-triangle 3), the backtracking propagates to the
first level of refinement (selection of sub-triangle 4) that allows to
choose its neighbour 2. The progressive refinement is then restarted
from the modified entry in the refinement history. If the backtracking
fails in choosing an alternative selection up to the top of the
refinement history, the initially localized triangle must be modified
in a similar way and the progressive refinement is repeated from the
new target triangle.

- ... delay.
^{8} - A typical sign of the projected point being outside of the target triangle is that the distance of the projected point from the selected sub-triangle in its plane remains more or less constant while the size of the refined triangles is linearly decreasing.

*Daniel Rypl
2005-12-07*