Keywords: mesh generation, advancing front, paving, quadrilateral elements, surface meshing, intersection handling.

This paper describes new techniques developed to simplify paving [1] algorithm and to increase its robustness. The Paving algorithm is an advancing front meshing method for generating quadrilateral or hexahedral elements on general two- dimensional or three-dimensional domains. Although the paving method produces high quality elements, its implementation tends to be a tedious and difficult endeavour. For practical use an algorithm has to be fast accurate as well as easy to implement, test and maintain. Ball and Magazine [2] listed criteria for comparison of heuristic algorithms that, in addition to execution time, included ease of implementation. Two simple techniques have been suggested which, decrease the computational complexity and increase robustness, without adversely effecting the speed and memory requirements for paving algorithm. This paper also describes methods to mesh point boundaries. Point boundaries are points inside the domain which must be included in the mesh as nodes. These nodes, like nodes on fixed boundary, cannot move. Two approaches to mesh point boundaries are given in this paper and their relative advantages are described.

The paving method proceeds by placing elements over a boundary on which, nodes have already been planted depending upon the density requirements set by the user. After each element is added, a check is made whether the edges intersect the boundary for which elements are being put (self Intersection) [3], or edges intersect with another boundary (external intersection). An intersection is deemed unfeasible, if the number of nodes resulting on the boundary formed due to the intersection is odd. It is impossible to fill an odd numbered boundary with quadrilateral elements. The modified paving algorithm suggested by White [4] proposed that element generation be stopped at this stage and, the added elements for this row be removed. The mesh generation is then again started from another place on the boundary. This decreases the chances of successful completion of the meshing procedure. Also it may so happen that none of the nodes give acceptable intersection. To avert this, it is suggested to shift the intersection, so that, one of the boundaries gains one node and other one loses one node, thereby making the number of nodes in both the boundaries even and, allowing the mesh generation to proceed without the need to back track. The algorithm used to achieve this shift is described in this paper. This process along with increasing robustness, simplifies the algorithm considerably.

The advantages of paving algorithm are orientation independence, boundary sensitivity and strong transitioning ability. One characteristic of mesh generation, which is eluding paving algorithm, is geometric independence [5]. If the order of the boundaries supplied to the paving algorithm is changed, the mesh generated may be very different than that produced with a different order of boundaries. Also paving algorithm may give very high values of locality [5], as small change in a boundary may result in intersections happening at different places and, hence the mesh generated is different, sometimes this difference is very drastic. It is therefore suggested to lay the elements on the external boundary only, till an internal fixed boundary is encountered. As a result geometric independence is achieved. The locality property becomes predictable due to this change. Approaches to minimize degradation of boundary elements, due to this approach are also described in this paper. By paving the external boundary only there is tremendous reduction in complexity of external intersection module.

For certain applications, it may be necessary to have a point boundary in the inside of the meshing domain. A point boundary is node, which must be included during the process of meshing. An example of such a requirement is a floor slab intersected by columns. If the columns intersect somewhere on the inside of the slab, then, a finite element node at the point becomes a necessity. Determining the starting conditions such that a specified point is always included as a node is impossible. It is suggested that elements connected to the node at minimum distance from the point boundary be connected to the point boundary. This replacement can take place at different times during mesh generation process. The computational cost associated with the process is directly related to the suitability of the exchange node.

1

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

2

Ball M, Magazine M. "The design and analysis heuristics", Networks; 11:215-9, 1981. doi:10.1002/net.3230110210

3

Cass R.J., Benzeley S.E., Meyers R.J. and Blacker T.D., "Generalized Paving: And automated quadrilateral surface mesh generation algorithm", IJNME, Vol 39, No 9, 1475-1490, May 1996. doi:10.1002/(SICI)1097-0207(19960515)39:9<1475::AID-NME913>3.0.CO;2-W

4

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.

5

Sabin M., "Criteria for comparison of automatic mesh generation methods", Adv. in Eng. Software; 13, No. 5/6, 220-225, 1991. doi:10.1016/0961-3552(91)90028-3

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
purchase this book (price £95 +P&P)