任意精度浮點算術在Delaunay網格生成算法實現(xiàn)中的應用.pdf

1、網格生成技術在很多領域都有廣泛的應用，如計算機圖形學、計算機視覺、可視化、地理信息系統(tǒng)和科學計算。本文主要關注科學計算領域的網格生成技術。按包含內部節(jié)點的單元數(shù)目是否相同，網格分為結構化和非結構化兩類。Delaunay方法是目前最流行的非結構化網格生成方法之一。 Delaunay網格生成方法牽涉到很多浮點計算。由于計算機浮點數(shù)截斷誤差的影響，這些計算可能是不精確的，由此可能導致很多意想不到的算法健壯性問題。本文引入任意精度浮點算

2、術，部分解決了此類健壯性問題。 本文敘述結構如下： 第1章簡單介紹了研究背景和非結構化網格生成技術的研究現(xiàn)狀，解釋了浮點運算誤差影響Delaunay網格生成算法健壯性的機理。 第2章詳細介紹了軟件模擬任意精度浮點算術算法，它適用于符合IEEE-754標準的浮點運算部件。它的原理是將浮點算術計算的近似結果與誤差部分分別精確地保存在硬件支持的浮點數(shù)中，由多個浮點數(shù)共同精確地表示計算結果。算法的關鍵是保證誤差的精確性，

3、對此本章將給出詳細的證明。使用這些算術算法和自適應技術，我們實現(xiàn)了4個精確的計算幾何謂詞。 第3章則將第2章實現(xiàn)的算術算法和謂詞應用到Delaunay網格生成算法的邊界邊恢復和邊界面恢復環(huán)節(jié)。具體地，我們重新設計了線段和三角形單元相交及求解交點位置的精確算法，以及判斷兩個共面三角形單元繞向一致性的精確算法，它們是保證邊界邊和邊界面恢復過程健壯性的關鍵所在。 第4章則通過實際例子來展示本文算法的效果。首先利用改進后的Del