Applications Of Arbitrary Precision Floating-Point Arithmetic In Delaunay Mesh Generation

Mesh generation is widely and successfully used in many areas, such as computer graphics, computer vision, visualization, geographic information system, scientific computation and so on. The thesis focuses on mesh generation technology in scientific computation area. Mesh is classified to structured one and unstructured one according to whether the number of nodes incident to an interior node is similar or not. The Delaunay method is one of the most popular unstructured mesh generation methods.Many floating-point computations are involved in the Delaunay method. These computations may not be exact due to round-off errors of floating-point numbers, consequently, many unexpected robust problems appear. In order to resolve these problems, a scheme by using arbitrary precision floating-point arithmetic is presented.The structure of the thesis is shown as follows.Chapter 1 introduces the research background, the current status of unstructured mesh generation, and explains why the round-off errors of floating-point computations could introduce the robust problems of Delaunay mesh generation.Chapter 2 introduces the arbitrary precision floating-point arithmetic algorithm in detail. The algorithm is free of robust problems if the floating-point units in processors comply with the IEEE-754 floating-point standard. The idea is to exactly store an arithmetic result with the approximate result and the exact round-off error separated in floating-point numbers supported by hardware. The most important part of the algorithm is to guarantee the exactness of the round-off errors, and we will prove the exactness mathematically. Using the arbitrary precision floating-point arithmetic and adaptive technology, four exact computational geometry predicates are implemented.Chapter 3 applies the arithmetic algorithm and predicates introduced in Chapter 2 in an implementation of the Delaunay mesh generation method. Two exact algorithms are designed. One is to judge whether a segment and a triangle intersect or not, where the intersect point could be located exactly simultaneously. The other is to judge whether the two coplanar triangles have similar orientations. The two algorithms are key to guarantee robustness of boundary edge and boundary face recovery procedures. Chapter 4 presents some examples to show the effect of the improved Delaunay algorithm. Four mesh examples which could not be generated by the former algorithm are given firstly, and the unsuccessful reasons are analyzed. Some other mesh examples obtained from practical simulation projects are presented to demonstrate the capabilities of our meshing algorithm. Moreover, by integrating with a CAE system called HEDP developed by our lab, Center for Engineering and Scientific, Zhejiang University, a complete simulation process for structure vibration is performed.Chapter 5 concludes the thesis, and depicts some drawbacks of the current algorithm and their possible resolutions.