Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 81
Edited by: B.H.V. Topping
Paper 65

A Modified Paving Algorithm

A. Dixit

Department of Civil Engineering, Georgia Institute of Technology, Georgia, United States of America

Full Bibliographic Reference for this paper
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 [3] 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 [4] 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.

Blacker T.D. and Stephenson M.B., "Paving: A new approach to automated quadrilateral mesh generation", IJNME, Vol 32, 811-847,(1991). doi:10.1002/nme.1620320410
White R.D. and Kinney P., "Redesign of paving algorithm: Robustness enhancements through element by element meshing", Proceedings, 6th International Meshing Roundtable, Sandia National Laboratories, pp.323-335, October 1997.
Ball M, Magazine M. "The design and analysis heuristics", Networks 1981; 11:215-9. doi:10.1002/net.3230110210
A. Dixit, "Simplifying Improvements to the Paving Algorithm", in Proceedings of the Fourth International Conference on Engineering Computational Technology, B.H.V. Topping and C.A. Mota Soares, (Editors), Civil-Comp Press, Stirling, United Kingdom, paper 21, 2004. doi:10.4203/ccp.80.21

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description