任意精度浮點(diǎn)算術(shù)在Delaunay網(wǎng)格生成算法實(shí)現(xiàn)中的應(yīng)用.pdf

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

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

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