Next: Example Up: Sequential Mesh Generation Previous: Region Discretization

Computational Complexity

The spatial localization, intersection checking and front management, in terms of edge or face selection and searching, are considered to be the general bottlenecks of the advancing front procedure. All aspects are addressed in the presented approach. The intersection check exploits the underlying parametric space if possible. Also the number of involved mesh entities is significantly reduced. The spatial localization is implemented using the octree. This exhibits the computational complexity which becomes nearly constant for reasonable octree depth . This is due to the fact that only negligible percentage of the total generation time is consumed by the octree traversal. Since gradual size variation is ensured (by the use of octree constrained at maximum to one level difference) no special algorithm for the edge or face selection strategy is required. Therefore the simplest approach was chosen which always uses the first available edge or face in the front. This obviously leads to the constant computational complexity. The remaining procedures are similar to the conventional advancing front method and thus the overall computational complexity approaches with being the number of elements, which makes the proposed methodology very competitive for practical use.



Next: Example Up: Sequential Mesh Generation Previous: Region Discretization

Daniel Rypl
2005-12-03