Next: Conclusions Up: Top Previous: Algorithm performance


To demonstrate the performance of the algorithm an academic example is presented. A set of uniform meshes1 over a unit hemisphere has been generated using 4 different uniform control grids. The control grids 1, 2, 3, and 4 contain 130, 504, 2094, and 8222 elements, respectively and have been created for target element size 0.35, 0.175, 0.0875, and 0.04375, respectively. For each control grid, three meshes have been generated with target element size 0.035, 0.05, and 0.07 using different selection algorithm (for point to surface projection). The difference between the ``simple'' and ``enhanced'' algorithm consists in the fact that ``simple'' algorithm is not using mid-nodes for sub-triangle selection. The convergence criterion for the projection has been set to 0.1 % of the target element size. The achieved results are summarized in Table 1. For each mesh, the number of generated elements (Elems) and the total computing time (T-tot) in seconds have been recorded. Since the algorithm seems to be quite slow (the same surface mesh generator working with tensor product polynomial surfaces is about 10 times faster) the total computing time has been split to a part corresponding strictly to the mesh generation process (T-mesh) and to a part related to the smoothing phase (T-opt) (only 2 cycles were considered). It is evident that the computing time is steadily decreasing with the decreasing size of the elements in the control grid. Each time the size of control triangles is halved the total computing time is reduced by a constant value (specific for a particular mesh size). This can be explained by reduction of the level of subdivision required by the convergence criterion by 1 whenever the control mesh size is halved. It can be also observed that the ``enhanced'' selection algorithm outperforms (although only slightly) the ``simple'' one on coarser control grids, where a higher probability of incorrect selection occurs. Note that this performance difference is increasing with the mesh density.

Since most of the smoothing time (over 85 %) is consumed by the projection algorithm it is be possible to estimate the overhead in the mesh generation phase caused by the projection. The key to an improved performance is to replace the ``accurate'' projection by an ``approximate'' one whenever possible and to reduce the number of ``accurate'' projections to the minimum, ideally to the number of nodes (or surface nodes). The ``approximate'' projection, however, must be accurate enough to guarantee correct behaviour of the mesh generation algorithm. A possible way may be to introduce a (rational) Bezier triangle over each triangle of the original control grid and to adjust its control polygon (and weights) to ``minimize'' its deviation from the limit surface. The parametric space of the (rational) Bezier triangle can be then efficiently used for the implementation of the ``approximate'' projection technique.

Table 1: Performance overview.


... meshes1
All meshes have been generated on a Dell notebook with Intel Pentium II 300 MHz processor and 128 MBytes RAM running under Linux Red Hat 5.2.

Next: Conclusions Up: Top Previous: Algorithm performance

Daniel Rypl