Next: Examples Up: Implementation Aspects Previous: Exact Point-to-Surface Projection

Approximate Point-to-Surface Projection

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 local element 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 to approximate the limit surface over individual elements of the initial control grid. The Bezier triangular patch of degree can be described by the following parametric formula [7]


where is the point on the patch, are Bezier control points, stand for bivariate Bernstein polynomials defined by


and , and are barycentric coordinates ().

The projection of a point to the Bezier triangular patch is performed 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. The projection algorithm is summarized in Table 1.

In the current implementation, the quadratic Bezier triangles have been employed. Their control polygon can be easily calculated using only nodes from 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. Therefore, 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 the derivative 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 the recursive subdivision has to be used in order to satisfy the constraint to the limit surface (unless it is planar).

Next: Examples Up: Implementation Aspects Previous: Exact Point-to-Surface Projection

Daniel Rypl