Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE TENTH INTERNATIONAL CONFERENCE ON CIVIL, STRUCTURAL AND ENVIRONMENTAL ENGINEERING COMPUTING
Edited by: B.H.V. Topping
A Modified Paving Algorithm
Department of Civil Engineering, Georgia Institute of Technology, Georgia, United States of America
A. Dixit, "A Modified Paving Algorithm", in B.H.V. Topping, (Editor), "Proceedings of the Tenth International Conference on Civil, Structural and Environmental Engineering Computing", Civil-Comp Press, Stirlingshire, UK, Paper 65, 2005. doi:10.4203/ccp.81.65
Keywords: mesh generation, advancing front, paving, quadrilateral elements, intersection handling, control sequence, convergence criteria, structural analysis software.
The paper comes as an outcome of implementing the paving algorithm [1,2] for finite element analysis (FEA) for civil engineering applications. Paving is a mesh generation method, for meshing a general three-dimensional surface, with quadrilateral elements. Although the paving method produces high quality elements, its implementation tends to be a tedious and difficult endeavor. For practical use an algorithm has to be fast and accurate, as well as easy to implement, test and maintain. Ball and Magazine  listed criteria for comparison of heuristic algorithms that, in addition to execution time, included ease of implementation.
This paper gives a modified paving algorithm, which is simpler compared to the previous algorithm. The first step towards the modified paving algorithm was taken when Dixit  suggested a few simple techniques to simplify the algorithm. These techniques ranged from tackling the intersection to the way the meshing progresses to fill elements in the domain. Based on those techniques the different modules of paving algorithm are changed. The advantages of using the changed modules over the modules as suggested originally are listed. Next the modules are arranged in a control sequence different from the one suggested in the original algorithm.
During the process of mesh generation several scenarios may arise when more than one paving operations can be used to proceed with meshing. To help resolve the conflict paving operations like row generation, intersection handling, closure, and mesh rectification techniques are prioritized. The modified modules are arranged in a logical control sequence based on the priority assigned to the different paving operations. The advantages of the new control sequence over the one suggested in the original algorithm are shown by comparing the modified control sequence to the control sequence of the previous versions of the algorithm.
Meshing is a tool used in various FEA applications. The quality of mesh is hence judged on the basis of the finite element results that are obtained. The mesh refinement that is required for different applications is different. Hence the same mesh can give very good results for one application while those results may not be very useful for another application. For example if the user is interested in displacement contours the level of mesh refinement required for same degree of accuracy is less than if the user was interested in stress contours. This disparity in interests was not tackled in the original paving algorithm or even by other meshing algorithms today. An attempt to tackle this disparity of interests is made in the modified algorithm based on a concept of convergence criteria.
The convergence criterion is a condition, which should be met to proceed to the next step of the mesh generation. This condition can be a simple condition or a complex condition. This is a generic tool to control the mesh quality and the time required to achieve that quality. Each step of the mesh generation, the row generation, intersection detection and tackling and closure should be preceded by as many operations of mesh rectification as is required to meet the convergence criteria. Meeting of convergence criteria results in the attainment of a stable mesh. If the convergence criterion tends to improve the quality of results, the processing time will increase. Here rather than suggesting the convergence criteria its importance and utility are emphasized. The convergence criterion will give the algorithm the control over both time and the quality of the results. This concept is discussed and elaborated in the paper.
The paving algorithm, as found in literature, is at a very high level of abstraction. This paper not only describes the modified algorithm but also provides enlightening details about the previous versions of the algorithm. This is done to simplify the understanding and implementation of the algorithm as well as encourage its evolution.
purchase the full-text of this paper (price £20)