New approaches for Delaunay triangulation and optimisation

Abstract

New techniques are presented for Delaunay triangular mesh generation and element optimisation. Sample points for triangulation are generated through mapping (a new approach). These sample points are later triangulated by the conventional Delaunay method. Resulting triangular elements are optimised by addition, removal and relocation of mapped sample points (element nodes). The proposed techniques (generation of sample points through mapping for Delaunay triangulation and mesh optimisation) are demonstrated by using Mathematica software. Simulation results show that the proposed techniques are able to form meshes that consist of triangular elements with aspect ratio of less than 2 and minimum skewness of more than 45°.

Keywords: Aspect ratio; Computer simulation; Computing methodology; Delaunay triangulation; Element skewness; Finite element methods; Generalised equation; Geometry; Mapping; Mathematical modeling; Mechanical engineering; Mesh optimisation; Sample points.

Fig. 1

Examples of decomposed domains according to Fubini's theorem. From left: a domain with 4 constant lines, a domain with 3 constant lines and 1 curve, a domain with 2 constant lines and 1 curve, and a domain with 2 parallel constant lines and 2 curves.

Fig. 2

Reference square domains with sample points (a) SP13 (b) SP41 (c) ASP20 (d) ASP48.

Fig. 3

Three combinations of intersections within a triangular element (a) skewness corresponding to node 1 (b) skewness corresponding to node 2 (c) skewness corresponding to node 3.

Fig. 4

Framework for mesh optimisation.

Fig. 5

Determination of valid region. (a) defining initial boundaries based on isosceles triangles. (b) checking validity of sample points within the region bounded by the initial boundaries (c) finalised valid region.

Fig. 6

Optimisation of a flawed element through node relocation. (a) a mesh consisting of a flawed element 9-13-16. (b) formation of a polygonal structure based on the selected node. (c) formation of final valid area (greyed) based on the intersections of individual valid regions. (d) mesh after the optimisation.

Fig. 7

Optimisation of a flawed element through node insertion and relocation. (a) a mesh consisting of a flawed element 106-126-139. (b) insertion of a mid-node 291 along the longest edge of the element. (c) relocation of node 126.

Fig. 8

Displacement of boundary node of a mesh system to the domain boundary (a) inaccurate positioning of node 3 (b) optimised mesh.

Fig. 9

Displacement of boundary node based on the second approach. (a) inaccurate positioning of node 3 (b) optimised mesh.

Fig. 10

Sample point generation for quadrant of a circle. (a) problem domain. (b) Initial distribution of sample points by using SP13. (c) Initial distribution of sample points by using SP41.

Fig. 11

Triangulation by using SP13. (a) initial triangulation. (b) optimised mesh.

Fig. 12

Triangulation by using SP41. (a) initial triangulation. (b) redundant triangles inside the mesh with AR>100. (c) optimised mesh.

Fig. 13

Adaptive sample point generation for quadrant of a circle. (a) Initial distribution of sample points by using ASP20. (b) Initial distribution of sample points by using ASP48.

Fig. 14

Adaptive mesh generation for quadrant of a circle. (a) Adaptive mesh by using ASP20. (b) Adaptive mesh by using ASP48.

Fig. 15

Decomposition of a problem domain according to Fubini's theorem. (a) domain before decomposition (b) domain after decomposition into 2 sub-domains R1 and R2.

Fig. 16

Generation of sample points. (a) distribution of sample points for SP13 (b) distribution of sample points for SP41.

Fig. 17

Coarse mesh optimisation for quadrant of hollow cylinder. (a) initial triangulation for the coarse mesh associated with SP13 (b) final optimised mesh.

Fig. 18

Fine mesh optimisation for quadrant of hollow cylinder. (a) initial triangulation for the fine mesh associated with SP41 (b) final optimised mesh.

Fig. 19

Decomposition of a wrench domain according to Fubini's theorem.

Fig. 20

Initial mesh for the head.

Fig. 21

Initial mesh for the tip (close up view).

Fig. 22

Optimised mesh for the head.

Fig. 23

Optimised mesh for the tip (close up view).

Fig. 24

Initial mesh for the socket.

Fig. 25

Optimised mesh for the socket.

Fig. 26

Preparation of a domain for mesh generation (a) domain with free formed curves and a linear boundary. (b) partitioning of the domain.

Fig. 27

Meshing of free formed curves (a) initial mesh. (b) optimised mesh.

Fig. 28

Parameterisation of free formed curves (a) approximation of the curves by using Bezier curves. (b) resultant discretisation based on Bezier curves.