Next: Approximate Point-to-Surface Projection Up: Implementation Aspects Previous: Implementation Aspects


Exact Point-to-Surface Projection

In the presented approach, the control grid is refined (temporarily during the projection) only on a single triangle localized from the original control grid (Fig. 4a). 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. 4b). This approach enables unlimited number of refinements with constant memory requirements (of course, except the memory for variables on the stack, which is linearly increasing with the refinement level because of recursive call of the refinement function) given by the number of nodes (including midside nodes) in one-level neighbourhood of the localized triangle. To enable fast setup of the connectivity associated with that triangle and required during the local subdivision, the first level of refinement is precomputed, prior to the actual mesh generation, globally over the whole mesh and stored (permanently). Note that the refinement on the first level can be also utilized when assessing the curvature of the limit surface controlling the element size in order to ensure accurate representation of the limit surface by its discretization. The radius of the curvature can be then approximated using the normals at two neighbouring nodes of the control grid at the first level refinement. Note that there is no mask available for calculation of the curvature and that, as already mentioned, the modified Butterfly scheme is generally not continuous.

It is necessary to realize that the shape of the triangles of the control grid on any level of refinement further evolves (the sides of the triangle become curved) as midside nodes on higher levels are introduced (see Fig. 5). A robust implementation of the projection therefore requires a reliable algorithm for 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, implementation of a tool for selection correction is of primary importance. When using the advancing front technique the projected point is always in proximity of 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. 4a). The triangle localization and sub-triangle selection is further enhanced by taking into account the relevant midside nodes on 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 backtracking if an invalid selection is detected (usually with some delay, as the size of the refined triangles is linearly decreasing, while the distance of the projected point from the selected sub-triangle in its plane remains approximately constant, which is a sign that the projected point is outside of the triangle). The correction then consists in traversing the refinement history in the opposite direction and detecting the highest level on which different selection (possibly leading to correct projection) may be made. Such a situation is demonstrated in Figure 6, 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 the sub-triangle 3 on the last level of performed refinement. Since the two previous selections (1 and 3 when going upwards) in the refinement history do not allow to choose 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.



Next: Approximate Point-to-Surface Projection Up: Implementation Aspects Previous: Implementation Aspects

Daniel Rypl
2005-12-03