Next: Approximate Surface Projection Up: Surface Projection Previous: Surface Projection


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.



Footnotes

... 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.


Next: Approximate Surface Projection Up: Surface Projection Previous: Surface Projection

Daniel Rypl
2005-12-07