Next: Example Up: Top Previous: Mesh generation

Algorithm performance

The spatial localization for the intersection check and the front management, in terms of the edge selection and searching, are considered to be general bottlenecks of the advancing front procedure. Both aspects are addressed in the presented approach. The spatial localization is implemented using the octree data structure. When searching for the most suitable candidate in the neighbourhood, the local Delaunay property is used as a criterion. This reduces the probability of consequent occurrence of an intersection. Since gradual variation of mesh size is ensured no special algorithm for the edge selection strategy is required. Therefore, the simplest approach has been chosen which always uses the first available edge in the front. This obviously leads to the constant computational complexity of the front management.

Another crucial aspect is related to the projection algorithm. To make the 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 only on a single triangle selected from the original control grid. The refinement of this triangle is accomplished progressively towards the current projection of the point being projected (Fig. 3). In order to enable fast setup of 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 (and then 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 and simultaneously it is traced to enable correction if an invalid selection has been detected (Fig. 3).



Next: Example Up: Top Previous: Mesh generation

Daniel Rypl
2005-12-03