Next: Examples Up: Top Previous: Surface Mesh Smoothing

Algorithm Performance

As mentioned above, the computational complexity is important for the practical use of the algorithm. The spatial localization for the intersection checking and the front management, in terms of edge selection and searching, are considered to be the general bottlenecks of the advancing front procedure. Both aspects are addressed in the presented approach. The spatial localization is implemented using the octree, which exhibits the computational complexity with being the number of elements. However, the computational complexity is reduced nearly to a constant one for reasonable octree depth, which is the case for vast majority of triangulations. This is due to the fact that only negligible percentage of the total generation time is consumed by the octree traversal. Since the octree is also used to control the mesh gradation no special algorithms (as take the shortest edge first, etc.) are necessary to be employed to select an edge from the front. Therefore, the simplest approach was chosen which always uses the first edge 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 .



Next: Examples Up: Top Previous: Surface Mesh Smoothing

Daniel Rypl
2005-12-03