Next: Examples Up: Surface Projection Previous: Exact Surface Projection


Approximate Surface Projection

Since the stopping criterion of the progressive refinement is typically related to the target element size, it is evident that the surface projection is computationally sensitive to the local element size. By increasing the 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 is described by the following parametric formula

(112)


where is the positional vector of a point on the patch, are Bezier control points, stand for bivariate Bernstein polynomials9 defined by

(113)


and , and are barycentric coordinates.

In the current implementation, the quadratic Bezier triangles have been employed. Their control polygons can be easily calculated using only nodes from the the first level of the global subdivision without the necessity to proceed to further levels of the subdivision. Also keeping the order of the patch low increases the computational performance of the projection. Moreover, the quadratic degree ensures the convergence of the projection to the ``expected'' solution. However, the quadratic patch is not capable to properly capture the change of the curvature from convex to concave and vice versa. In such a case, the projection gives quite unsatisfactory results. Therefore, the criterion whether to use the ``approximate'' projection is based on the match of the patch normal with the ``exact'' subdivision based normal at corner nodes of the patch. Should the normals deviate by more than degrees at least at one of the nodes, the recursive subdivision based projection algorithm is used.

The projection itself is accomplished using a similar algorithm as described in Subsection Surface Projection of Section Direct Triangulation of 3D Surfaces. It is performed in an iterative manner starting from the barycenter as the first approximation of the projection. This is affordable even if the generated elements are much smaller than the target triangle of the initial control grid because of the assumed quadratic degree of the patch. In each iteration, the point is firstly projected to the tangent plane constructed at the most recent approximation of using the patch normal at defined by

(114)


The tangent vectors in directions and are calculated as

(115)


where the components of the patch gradient are given by

(116)


(117)


(118)


The first derivative of the bivariate Bernstein polynomial with respect to the barycentric coordinate yields

(119)


Similar expressions may be derived for the first derivation with respect to and . The position of point projected to plane is expressed as

(120)


The increments of barycentric coordinates , , and , obtained from

(121)


are then subjected to a normalization to avoid running , , and out of the range of the parametric space and consequently to ensure . The approximation of point is then improved by incrementing its barycentric coordinates by normalized , , and . The whole process is repeated until the desired accuracy is achieved. The projection algorithm is summarized in Table 3.

Note that the ``approximate'' projection cannot be used for the evaluation of the final location of a node (typically in the last cycle of the mesh smoothing). In this case, the ``exact'' projection technique based on the recursive subdivision has to be employed in order to satisfy the constraint to the limit surface (unless the surface is planar).



Footnotes

... polynomials9
Keep in mind that although looks trivariate, it is not, since .


Next: Examples Up: Surface Projection Previous: Exact Surface Projection

Daniel Rypl
2005-12-07