三維模型簡(jiǎn)化

《三維模型簡(jiǎn)化》由會(huì)員分享，可在線閱讀，更多相關(guān)《三維模型簡(jiǎn)化（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 基于 Garland 的邊收縮算法的一種實(shí)現(xiàn) 0 引言 隨著科學(xué)技術(shù)的進(jìn)步， 在計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)、地理信息系統(tǒng)、 醫(yī)學(xué)圖像系統(tǒng)等領(lǐng)域所構(gòu)造和使用的模型越來(lái)越精細(xì)、越來(lái)越復(fù)雜。這些復(fù)雜的模型不但對(duì)計(jì)算機(jī)的存儲(chǔ)容量、 處理速度提出了很高的要求、 而且成為實(shí)時(shí)繪制、 網(wǎng)絡(luò)傳輸?shù)钠款i。 因此模型簡(jiǎn)化成為非常 重要的研究課題。 模型簡(jiǎn)化是指在保持原模型幾何形狀基本不變的前提下， 采用適當(dāng)?shù)乃惴p少該模型的面片數(shù)、頂點(diǎn)數(shù)和邊數(shù)。 近年來(lái)，出現(xiàn)了很多有代表性的模型簡(jiǎn)化算法，其中 Galand 的基于二次誤差度量的邊收 縮算法是目前最常采用且有效的

2、算法。 其基本思想是以頂點(diǎn)到相關(guān)三角形平面的距離的平方和為誤差度量，通過(guò)重復(fù)的邊收縮操作對(duì)模型進(jìn)行簡(jiǎn)化。 1 算法分析與設(shè)計(jì) 1.1 基本概念 ： 定義 1 三角網(wǎng)格是由三位空間中的三角形通過(guò)邊和頂點(diǎn)連接而成的分段線性曲面。 三角網(wǎng)格 M 可由頂點(diǎn)集 V={v1,v2...vm} 和三角集合 F={f1.f2...fn} 組成的二元組 M=(V,F) 來(lái) 表示 定義 2 對(duì) M 種任一頂點(diǎn) vi ，與頂點(diǎn) vi 相關(guān)的三角形集合記作 Planes(i)，與邊 (vi,vj) 關(guān)聯(lián)的三角形集合記作 Planes(i,j) ，所有與 vi 關(guān)聯(lián)的邊構(gòu)成的集合 E

3、dge(i) 。 1.2 基于二次誤差度量的邊收縮算法 基于二次誤差度量的邊收縮算法是通過(guò)不斷選擇模型中的一條邊進(jìn)行收縮， 達(dá)到對(duì)模型 的簡(jiǎn)化。 每收縮一條非邊界邊， 模型減少 2 個(gè)三角形、 1 個(gè)頂點(diǎn)、 三條邊； 收縮一條邊界邊，模型減少 1 個(gè)三角形、 1 個(gè)頂點(diǎn)、倆條邊。 誤差度量 簡(jiǎn)化模型必須與原網(wǎng)格盡量相似，這取決于邊收縮的順序和邊收縮后生成的新點(diǎn)的位置。如何選擇合適的邊進(jìn)行收縮及如何生成新的頂點(diǎn)，有一個(gè)選擇誤差度量標(biāo)準(zhǔn)的問(wèn)題。 Garland 算法以點(diǎn)到平面的距離為誤差度量標(biāo)準(zhǔn)。 設(shè)對(duì)邊 (vi,vj) 進(jìn)行收縮，則與 (vi,v

4、j) 邊相關(guān)聯(lián)的三角形集合 Planes(i,j) 構(gòu)成了原模型上的 v 為 [x,y,z,1] T 一個(gè)區(qū)域，設(shè)邊收縮后生成的新位置 ，定義這次邊收縮帶來(lái)的新誤差 △ ( v ) 為 v 到三角形集合 Planes(i,j)中每個(gè)三角形所在面的距離的平方和 ，表示三角 形 集 合 Planes(i,j) 中 的 每 個(gè) 三 角 形 所 在 面 的 平 面 方 程 ax+by+cz+d=0 ， 且 有 a2 b2 c2 1。在根據(jù)點(diǎn)到平面 ax+by+cz+d=0 的 距 離 公 式 為 ax by cz d ( pT v

5、) 2 d a 2 b2 c2 v )= p Planes ( i , j ) 以及等式運(yùn)算 ,就有△( 其 中 ： T p=(a,b,c,d) 該式可變換如下： (v )  ([  x, y, z,1]T  )  v  T  ( ppT  )v p Planes( i , j ) v T  (

6、  Kp )v p Planes( i , j ) v T Qv K p 其中： 為 4*4 的對(duì)稱矩陣，稱為三角形的誤差矩陣，它的定義如下 Q 稱為該次收縮的誤差矩陣，定義如下 1.3 本小組關(guān)于 Garland 算法的一種實(shí)現(xiàn)。 為了簡(jiǎn)化算法實(shí)現(xiàn)的效率問(wèn)題 ,使用本組關(guān)于 Galand 算法的一種實(shí)現(xiàn) : 1、取邊收縮的誤差矩陣 Q 為邊的倆頂點(diǎn)收縮的誤差矩陣 Qi 和 Qj 之和，即 (Q=Qi+Qj) 。

7、 2、取新頂點(diǎn)位置為收縮邊 (i,j) 中的一個(gè)，誤差由公式 vT Qv 計(jì)算得到，具體的選擇由 i 收縮 到 j 的所產(chǎn)生的誤差和由 j 收縮到 i 所產(chǎn)生的誤差值做比較得到的較小值決定。 3、實(shí)際邊收縮帶來(lái)的結(jié)果是 刪除一個(gè)點(diǎn)， 刪除一條邊，刪除倆個(gè)與邊關(guān)聯(lián)的三角形，增加 新邊、三角形。 具體算法步驟如下： 步驟 1 根據(jù)給定的模型數(shù)據(jù)， 計(jì)算出所有頂點(diǎn)的頂點(diǎn)誤差矩陣 Qi ：為各平面對(duì)應(yīng)的 a、 K p b 、 c 關(guān) 聯(lián) 矩 陣 的 和 : 計(jì) 算 過(guò) 程 涉 及 求 面 的

8、a 、 b 、 c( 注 意 滿 足 a2 b2 c2 1)，即為面的單位法向量 ,單位法向量的求法可根據(jù)平面?zhèn)z點(diǎn)的叉乘在單位化即可。 步驟 2 差，代表從  設(shè)計(jì)一關(guān)于結(jié)構(gòu)體的優(yōu)先隊(duì)列來(lái)簡(jiǎn)化堆的操作，存放 i 折疊到 j 的誤差 ,并設(shè)計(jì)一哈希表用于判定是否新邊。  i， j，及其收縮帶來(lái)的誤 步驟 3 計(jì)算邊折疊誤差：根據(jù)步驟  2，取邊折疊從  i 到  j 和從  j 到  i 的教小者作為該邊 的誤差入隊(duì)并進(jìn)入哈希散

9、列。 步驟 4 選擇隊(duì)列中的隊(duì)頭元素 q 出隊(duì) (即代表從 q.i 折疊到 q.j) 。 步驟 5 判斷 i， j 同時(shí)相關(guān)的三角形的個(gè)數(shù)：如果個(gè)數(shù)大于 1，那么刪除與 i， j 同時(shí)關(guān) 聯(lián)的三角形， 刪除點(diǎn) i，進(jìn)行邊收縮 (將剩余三角形中與 i 相關(guān)的三角形全部轉(zhuǎn)移到與 j 相關(guān) ), 并往隊(duì)列中增加由于折疊帶來(lái)的新邊 (做與步驟 3 相同的操作 )，否則轉(zhuǎn)步驟 4。 步驟  6  如果邊收縮達(dá)到給定的收縮哦邊的個(gè)數(shù)，則結(jié)束收縮，否則轉(zhuǎn)步驟  4。 2、實(shí)驗(yàn)分析 原始牛模型 : 5804 個(gè)三角片

10、 簡(jiǎn)化后，三角片 2804 簡(jiǎn)化時(shí)間 2578ms 進(jìn) 一 步 簡(jiǎn) 化 后 ， 三 角 片 1404 簡(jiǎn) 化 時(shí) 間

11、 3235ms, 更進(jìn)一步簡(jiǎn)化，三角片 704 簡(jiǎn)化時(shí)間 3500ms 2.2..1 原始兔子模型 19859 個(gè)三角片

12、 簡(jiǎn)化后 三角片 3859 簡(jiǎn)化時(shí)間 40375ms 進(jìn)一步簡(jiǎn)化 三角片 1859 簡(jiǎn)化時(shí)間 41359ms

13、 更進(jìn)一步簡(jiǎn)化 三角片 1159 簡(jiǎn)化時(shí)間 41219ms 3、結(jié)束語(yǔ) 本次簡(jiǎn)化，在簡(jiǎn)化達(dá)到一定程度后，并不能確保保持具體信息，與 存在著簡(jiǎn)化后的模型局部極大或極小的情況 . 參考文獻(xiàn)  Galand 算法同樣， Garland M ， Heckbert P S.Surface simplification  using quadric error metric[J].Computer Graphics,1997,31(3);209-216 高質(zhì)量保行三角形網(wǎng)格簡(jiǎn)化算法 其他相關(guān)僅作了解的文獻(xiàn) .  -- 南京航天航空大學(xué)