Next: Example Up: Top Previous: Mesh Generation

Implementation

To make the point-to-surface projection accurate (in terms of the distance from the limit surface) it is necessary to subdivide the control grid up to a sufficiently high level. This results in a huge amount of data to be stored, which is not acceptable. In the presented approach, the grid is refined (temporarily) only on a single triangle localized from the original control grid (Fig. 3a). The refinement of this triangle is accomplished progressively towards the current projection of the point being projected (Fig. 3b). In order to enable fast setup of the connectivity associated with that triangle and required during the local subdivision, one level of subdivision is computed globally (and stored) prior to the actual mesh generation. A robust implementation of the projection requires a reliable algorithm for triangle localization (including its sub-triangles selection) and a tool for selection correction. Currently, the selection algorithm is 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 has been detected. Since the stopping criterion of the progressive refinement is typically related to the target element size, it is evident that the point-to-surface projection is computationally sensitive to the mesh size. With the increasing mesh density the costs of the projection algorithm become strongly prohibitive. The remedy to this problem consists in the implementation of an ``approximate'' projection with much lower computational demands. This may be accomplished by using Bezier triangular patches [5] to approximate the limit surface over individual elements of the control grid. The projection of a point to the Bezier triangular patch is accomplished in an iterative manner starting from the barycenter as the first approximation. In each iteration, the point is projected to the tangential plane (constructed at the most recent approximation) and then the increments of barycentric coordinates and , calculated using the patch gradients, are used to get better approximation of the projection. The whole process is repeated until the desired accuracy is achieved. In the current implementation, the quadratic Bezier triangles have been employed. Their control polygon can be easily calculated using only nodes from the the first level of global subdivision without the necessity to proceed to further levels of subdivision. Note that keeping the order of the patch low increases the computational performance. On the other hand, quadratic patch is not capable to properly capture the change of the curvature from convex to concave. In such a case, the projection gives very unsatisfactory results. The criterion whether to use a patch is based on the match between the patch normal and the normal calculated on the control grid using normal evaluation masks. Should the normals deviate by more than degrees at least at one of the patch vertices, the recursive subdivision based projection algorithm is used. However it is important to realize that for the final location of a node (typically in the last cycle of the mesh smoothing) the ``exact'' projection technique based on recursive subdivision has to be used in order to satisfy the constraint to the limit surface (unless it is planar).

Next: Example Up: Top Previous: Mesh Generation

Daniel Rypl
2005-12-03