點(diǎn)模型的表面幾何建模和繪制.pdf

1、近年來，基于采樣點(diǎn)元的表面幾何建模與繪制的方法，在計(jì)算機(jī)圖形學(xué)領(lǐng)域內(nèi)受到越來越多的關(guān)注。許多應(yīng)用對(duì)幾何模型的精度和細(xì)節(jié)提出了越來越高的要求，各種高級(jí)造型工具和模型獲取技術(shù)不斷涌現(xiàn)，使得數(shù)據(jù)模型的規(guī)模和復(fù)雜程度急劇增長(zhǎng)。在處理如此高度復(fù)雜的數(shù)據(jù)模型時(shí)，傳統(tǒng)的基于網(wǎng)格的幾何表達(dá)方式已不再適合，取而代之的是基于點(diǎn)的表達(dá)方式。其原因有二方面：一方面，多邊形網(wǎng)格包含采樣點(diǎn)之間的連接關(guān)系，存貯和維護(hù)這些關(guān)系需要大量的內(nèi)存和計(jì)算方面的開銷，當(dāng)模型表面

2、復(fù)雜度進(jìn)一步增加時(shí)，這個(gè)問題變得更加嚴(yán)重；另一方面，基于點(diǎn)的幾何表達(dá)和處理無需維護(hù)其表面的全局一致的拓?fù)浣Y(jié)構(gòu)，而顯得特別靈活和簡(jiǎn)單。因此，研究基于點(diǎn)的表面幾何建模和繪制具有十分重要的意義。 我們所研究的三維模型一般地是實(shí)體表面的一組稠密采樣點(diǎn)，成為點(diǎn)模型。其中的每個(gè)采樣點(diǎn)記錄了采樣的位置坐標(biāo)，以及其它可能的附加屬性，如法向、顏色，和材質(zhì)等。在本文中，我們首先回顧基于點(diǎn)元表示的圖形學(xué)的發(fā)展歷史和相關(guān)工作.然后在已有的基于點(diǎn)的建模和

3、繪制方面的技術(shù)和算法基礎(chǔ)之上，提出了以下幾個(gè)有關(guān)點(diǎn)模型的表面幾何建模和繪制方面的新算法，用于處理這些廣泛使用和日益復(fù)雜的三維采樣點(diǎn)幾何模型。 首先我們提出了一個(gè)新的隱式曲面重建算法，實(shí)現(xiàn)了基于離散采樣點(diǎn)的表面快速重建。該算法以點(diǎn)模型表面附近局部區(qū)域內(nèi)雙向?yàn)V波函數(shù)值作為曲面重建函數(shù)，其函數(shù)值通過最近的K個(gè)模型表面上的采樣點(diǎn)直接計(jì)算所得，從而無需求解線性和非線性方程，也無需曲面內(nèi)部或外部的支撐點(diǎn)，具有非常快的計(jì)算速度；此外，由于采用

4、雙邊濾波函數(shù)，還能對(duì)含有噪聲的離散采樣點(diǎn)模型進(jìn)行特征保持的表面重建。實(shí)驗(yàn)表明我們的算法可以高質(zhì)量地重建復(fù)雜物體的表面模型。 光線跟蹤是計(jì)算機(jī)圖形的基本繪制方法，運(yùn)用光線跟蹤方法繪制高質(zhì)量的點(diǎn)模型圖像具有重要的意義。針對(duì)光線跟蹤繪制點(diǎn)模型時(shí)不能同時(shí)兼顧質(zhì)量和速度的問題，我們提出了一個(gè)點(diǎn)模型的局部幾何重建和光線跟蹤繪制的新的算法，該算法在每個(gè)采樣點(diǎn)元附近局部地重建一個(gè)二次多項(xiàng)式函數(shù)曲面逼近點(diǎn)模型，然后根據(jù)逼近誤差ε將每個(gè)重建曲面限制

5、在稱為ε置信鄰域的范圍內(nèi)，形成一個(gè)ε面元。采樣點(diǎn)模型上的所有面元以其中心位置及面元半徑為依據(jù)，構(gòu)造層次BSP樹，用來加速計(jì)算光線和點(diǎn)模型的交點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法能有效地兼顧點(diǎn)模型繪制算法中的效率和質(zhì)量。我們發(fā)現(xiàn)，上面點(diǎn)模型的光線跟蹤算法中的BSP樹結(jié)構(gòu)也可以用于光線跟蹤繪制稠密采樣的網(wǎng)格模型。它的一個(gè)優(yōu)點(diǎn)是避免了常規(guī)BSP樹構(gòu)造方法中因分割與剖分平面相交的面片所引起的場(chǎng)景復(fù)雜度的增加，大大簡(jiǎn)化了BSP樹的構(gòu)建過程。于是我們提出了一種

6、基于面片中心點(diǎn)索引的新的場(chǎng)景BSP樹結(jié)構(gòu)，用于加速三角網(wǎng)格模型的處理。其核心思想是以面片中心點(diǎn)位置作為場(chǎng)景中各面片二叉分類的依據(jù)，進(jìn)行BSP樹的構(gòu)建。 一個(gè)復(fù)雜的點(diǎn)模型可能包含成千上萬、幾十萬乃至上億的采樣點(diǎn)。直接處理那些大規(guī)模的點(diǎn)模型無疑將十分困難。因此我們進(jìn)一步增強(qiáng)了上面的ε面元重建方法，并基于它提出了一個(gè)新的點(diǎn)模型幾何簡(jiǎn)化方法。它包含兩個(gè)主要步驟：(1)我們首先提出鄰域?qū)哟螖U(kuò)展的優(yōu)化方法，使得重建的面元在一定誤差下能在更大

7、的范圍內(nèi)更好地逼近原模型，從而使該面元成為一個(gè)具有最大置信鄰域的面元。(2)基于上述面元表示的稠密采樣點(diǎn)模型由于面元間的相互重疊，很多信息是冗余的，于是我們提出了一個(gè)新的面元簡(jiǎn)化算法，將冗余的面元簡(jiǎn)化掉。不同于傳統(tǒng)的簡(jiǎn)化算法，我們從一個(gè)空的簡(jiǎn)化面元集合開始，不斷地在原模型的面元中挑選一個(gè)最優(yōu)的面元加入到簡(jiǎn)化面元集合，直到原點(diǎn)模型被完全覆蓋為止。實(shí)驗(yàn)結(jié)果表明：該算法能夠根據(jù)不同的預(yù)定誤差，削減表示稠密采樣點(diǎn)模型的面元數(shù)，同時(shí)能很好地表達(dá)原

8、來的幾何形狀。 布爾運(yùn)算是傳統(tǒng)造型系統(tǒng)一個(gè)關(guān)鍵重要的造型手段，如何對(duì)點(diǎn)模型進(jìn)行布爾運(yùn)算對(duì)于基于點(diǎn)的造型系統(tǒng)至關(guān)重要。本文我們提出了一個(gè)新的布爾運(yùn)算方法。它首先判斷每個(gè)采樣點(diǎn)面元相對(duì)于另一個(gè)實(shí)體模型表面的內(nèi)外及相交關(guān)系，然后對(duì)相交面元在置信鄰域內(nèi)進(jìn)行全局誤差控制下的交線求取和自適應(yīng)加密重采樣，從而一方面使細(xì)分后的面元可以更好地逼近布爾運(yùn)算結(jié)果在交線處的實(shí)體表面，另一方面使布爾運(yùn)算可以在具有不同分辨率的非均勻采樣點(diǎn)模型之間進(jìn)行。該算

9、法的主要貢獻(xiàn)在于：(1)為了加速采樣點(diǎn)的內(nèi)外測(cè)試，分別對(duì)參與布爾運(yùn)算的采樣點(diǎn)元模型建立了簡(jiǎn)單和有效的層次結(jié)構(gòu)K-D樹，而不是復(fù)雜的三色八叉樹；(2)能在全局誤差控制下對(duì)具有不同分辨率的非均勻采樣點(diǎn)模型之間做穩(wěn)定可靠的布爾運(yùn)算。 三維模型上另一類主要的幾何處理任務(wù)是去噪聲，以及表面細(xì)節(jié)光順和增強(qiáng)。我們將在最后一章提出一種全新的點(diǎn)模型譜分析和處理方法。我們首先提出一個(gè)方法計(jì)算模型表面變化模式，即形狀基函數(shù)。然后把點(diǎn)模型表示成這些變化