計(jì)算機(jī)圖形學(xué)第三章求交分類

計(jì)算機(jī)圖形學(xué)第三章求交分類第一頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.3.1 求交分類簡(jiǎn)介多面體模型這種模型的求交計(jì)算主要是線段和平面的求交，求交問題的解決相對(duì)簡(jiǎn)單。多面體模型的缺點(diǎn)是明顯的。它只能近似表示形體，同時(shí)，復(fù)雜形體表面的離散會(huì)帶來巨大的數(shù)據(jù)量。CSG模型在這種模型中，形體通過基本體素的組合來實(shí)現(xiàn)。二次曲面的求交是這些造型系統(tǒng)中必不可少的。第二頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

當(dāng)前的幾何造型系統(tǒng)，大多采用精確的邊界表示模型。在這種表示法中，形體的邊界元素和某類幾何元素相對(duì)應(yīng)，它們可以是直線、圓（圓?。⒍吻€、Bezier曲線、B樣條曲線等，也可以是平面、球面、二次曲面、Bezier曲面、B樣條曲面等，求交情況十分復(fù)雜。二次曲面與各種自由曲面并存的混合表示模型的采用，導(dǎo)致了歸類求交思想的產(chǎn)生。第三頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.3.2 求交分類策略在幾何造型系統(tǒng)中，用到的幾何元素主要有點(diǎn)：3D點(diǎn)。線：3D直線段、二次曲線(包括圓弧和整圓、橢圓弧和橢圓、拋物線段、雙曲線段)、Bezier曲線(有理和非有理)、B樣條曲線、NURBS曲線。面：平面、二次曲面(包括球面、圓柱面、圓錐/臺(tái)面、雙曲面、拋物面、橢球面和橢圓柱面)、Bezier曲面(有理和非有理)、B樣條曲面、NURBS曲面。第四頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

將幾何元素進(jìn)行歸類，利用同一元素之間的共性來研究求交算法。同時(shí)對(duì)每一類元素，在具體求交算法中要考慮它們的特性，以提高算法的效率，發(fā)揮混合表示方法的優(yōu)勢(shì)。求交方法可分為：點(diǎn)點(diǎn)、點(diǎn)線、點(diǎn)面、線線、線面六種。第五頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.3.3 基本的求交算法3.3.3.1線與線的求交計(jì)算二次曲線與二次曲線的求交。求交策略是將坐標(biāo)系變換到該圓錐曲線的局部坐標(biāo)系下，一個(gè)圓錐曲線用隱式方程的形式表示，而另一圓錐曲線采用參數(shù)方程的形式，代入即可獲得有關(guān)參數(shù)的四次方程，，因而可計(jì)算出二者的交點(diǎn)。二次曲線與NURBS曲線求交將NURBS曲線的參數(shù)方程代入圓錐曲線的隱式方程，得到參數(shù)的一元高次方程，然后，使用一元高次方程的求根方法解出交點(diǎn)參數(shù)?；虬褕A錐曲線也表示為參數(shù)形式，轉(zhuǎn)化為兩個(gè)NURBS曲線的求交問題。第六頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

NURBS曲線與NURBS曲線求交。采用離散法求初始交點(diǎn)，迭代求精確解的辦法，步驟如下：（1）初始化。依據(jù)離散精度，將NURBS曲線形成對(duì)應(yīng)的二叉樹表示，葉子結(jié)點(diǎn)是對(duì)應(yīng)于該曲線的某一離散子線段及其包圍盒，非葉子結(jié)點(diǎn)是對(duì)應(yīng)于該段NURBS曲線的包圍盒。（2）求初始交點(diǎn)。遍歷兩曲線的二叉樹，若其葉子結(jié)點(diǎn)的包圍盒相交，則將兩者的數(shù)據(jù)（曲線段中點(diǎn)的參數(shù)值，二者坐標(biāo)的平均值）存入初始交點(diǎn)隊(duì)列。（3）將初始交點(diǎn)迭代求精確交點(diǎn)。迭代方程可形象地用圖3.3.1表示。第七頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

第八頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.3.3.2線與面的求交計(jì)算二次曲線與二次曲面的求交的求交計(jì)算，可以把二次曲線的參數(shù)形式代入二次曲面的隱式方程，計(jì)算出交點(diǎn)的參數(shù)。NURBS曲線與二次曲面的求交計(jì)算，可以把NURBS曲線的參數(shù)形式代入二次曲面的隱式方程，得到關(guān)于參數(shù)的高次方程，然后求解。NURBS曲線與NURBS曲面的求交計(jì)算1．初始化。依據(jù)離散精度，將NURBS曲線離散成二叉樹的形式第九頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

2．求初始交點(diǎn)。遍歷該二叉樹和四叉樹，如果曲線二叉樹葉子結(jié)點(diǎn)的包圍盒與曲面四叉樹的葉子結(jié)點(diǎn)的包圍盒有交點(diǎn)，則將子曲線段中點(diǎn)的參數(shù)值、子曲面片的中心點(diǎn)的坐標(biāo)值與參數(shù)值作為初始交點(diǎn)，記錄到初始交點(diǎn)點(diǎn)列中去。3．對(duì)初始交點(diǎn)進(jìn)行迭代，形成精確交點(diǎn)?？捎门ｎD迭代法求解精確交點(diǎn)。設(shè)NURBS曲線為C(t)，NURBS曲面為S(u,v)，則在交點(diǎn)處應(yīng)滿足：

C(t)-S(u,v)=0設(shè)f(u,v,t)=C(t)-S(u,v)第十頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

可得到：令,則可建立迭代方程：設(shè)初值為，一般迭代3~5次，便可達(dá)到要求的精度。第十一頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.3.3.3曲面與曲面的求交曲面與曲面之間的求交是最為復(fù)雜的一種曲面與曲面求交的基本方法主要有:代數(shù)方法幾何方法離散方法跟蹤方法第十二頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

1．代數(shù)方法利用代數(shù)運(yùn)算，特別是求解代數(shù)方程的方法求出曲面的交線。根據(jù)參與求交的兩曲面的表示形式的不同，可以把求交分為三種情況。隱式表示和參數(shù)表示的曲面求交，通過把參數(shù)方程代入隱式方程的方法，可以將交線表示為g(u,v)=0的形式。此時(shí)得到的交線方程是平面代數(shù)曲線方程，可根據(jù)平面代數(shù)曲線理論的方法求解交線。第十三頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

兩個(gè)曲面都是參數(shù)表示的情形，只需要將其中之一隱式化，然后用前面的方法求解。而參數(shù)多項(xiàng)式或有理多項(xiàng)式曲面的隱式化通過消元來實(shí)現(xiàn)。兩個(gè)曲面都是隱式曲面。一種方法是將其中一個(gè)曲面參數(shù)化，然后用第一種情況來求解。但是，一般情況下這種參數(shù)化很困難，對(duì)于某些情況可以采用另外的方法計(jì)算參數(shù)化的曲面。代數(shù)法的弱點(diǎn)是對(duì)誤差很敏感這是因?yàn)榇鷶?shù)法經(jīng)常需要判別某些量是否大于零、等于零或小于零，而在計(jì)算機(jī)中的浮點(diǎn)數(shù)近似表示的誤差常常會(huì)使這種判別出現(xiàn)錯(cuò)誤。第十四頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

2．幾何方法利用幾何的方法，對(duì)參與求交的曲面的形狀大小、相互位置以及方向等進(jìn)行計(jì)算和判斷，識(shí)別出交線的形狀和類型，從而可精確求出交線。幾何求交適應(yīng)性不是很廣，一般僅用于平面以及二次曲面等簡(jiǎn)單曲面的求交第十五頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

對(duì)于一些交線退化或相切的情形，交線往往是點(diǎn)、直線或圓錐曲線，用幾何方法求交可以更加迅速和可靠。第十六頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3．離散方法離散方法求交是利用分割的方法，將曲面不斷離散成較小的曲面片，直到每一子曲面片均可用比較簡(jiǎn)單的面片，然后用這些簡(jiǎn)單面片求交得一系列交線段，連接這些交線段即得到精確交線的近似結(jié)果。離散求交一般包括下面的過程：用包圍盒作分離性檢查排除無交區(qū)域；根據(jù)平坦性檢查判斷是否終止離散過程；連接求出的交線段作為求交結(jié)果。第十七頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

由于Bezier曲面，B樣條曲面具有離散性質(zhì)，使得它們最適合于離散法求交。缺點(diǎn)：離散法求出的交線逼近精度不高。如果要求的精度較高，需要增加離散層數(shù)。這將大大增加了數(shù)據(jù)儲(chǔ)存量和計(jì)算量。處于不同離散層數(shù)的相鄰子曲面片，由它們產(chǎn)生的交線段可能會(huì)出現(xiàn)裂縫。第十八頁，共二十頁，編輯于2023年，星期五清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 計(jì)算機(jī)圖形學(xué)基礎(chǔ)

4．跟蹤方法通過先求出初始交點(diǎn)，然后從已知的初始交點(diǎn)出發(fā)，相繼跟蹤計(jì)算出下一交點(diǎn)，從而求出整條交線的方法。跟蹤法的本質(zhì)是構(gòu)造交線滿足的微分方程組，先求出滿足方程組的某個(gè)某個(gè)初值解，通過數(shù)值求解微分方程組的方法來計(jì)算整個(gè)交線。跟蹤方法在計(jì)算相繼交點(diǎn)的時(shí)候，利用了曲面的