[發(fā)明專(zhuān)利]一種基于距離加權(quán)最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310210453.2
• 申請(qǐng)日: 2013-05-31
• 公開(kāi)（公告）號(hào): CN103295266A
• 公開(kāi)（公告）日: 2013-09-11
• 發(fā)明（設(shè)計(jì)）人: 鄧龍騰;羅笑南;薛凱軍;肖劍
• 申請(qǐng)（專(zhuān)利權(quán)）人: 東莞中山大學(xué)研究院;中山大學(xué)
• 主分類(lèi)號(hào): G06T17/00
• 分類(lèi)號(hào): G06T17/00
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

技術(shù)領(lǐng)域

本發(fā)明涉及技術(shù)計(jì)算機(jī)領(lǐng)域，具體涉及一種基于距離加權(quán)最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化的方法。

背景技術(shù)

隨著當(dāng)今科學(xué)技術(shù)飛速的發(fā)展進(jìn)步，三維圖形由于其更生動(dòng)具體的立體效果，越來(lái)越傾向于取代二維圖形在人們生活、工作領(lǐng)域的地位。越來(lái)越多的三維圖形出現(xiàn)在數(shù)字電視、動(dòng)畫(huà)游戲、地圖繪制和醫(yī)療成像等領(lǐng)域中。隨著三維模型數(shù)據(jù)獲取技術(shù)的不斷提高，三維模型的精度也隨之增長(zhǎng)，這給處理能力有限的交互式設(shè)備帶來(lái)了巨大的壓力。然而有些場(chǎng)合下并不需要有如此高精度的三維模型，因此需要對(duì)三維模型進(jìn)行簡(jiǎn)化，從而加快交互終端的處理能力。

與二維圖片用圖像分辨率來(lái)表示圖像精度的方法一樣，三維圖形也用模型分辨率來(lái)對(duì)應(yīng)模型數(shù)據(jù)密度的大小。模型數(shù)據(jù)密度大意味著模型分辨率高，模型比較精確精細(xì)；模型數(shù)據(jù)密度小意味著模型分辨率低，模型比較粗糙簡(jiǎn)陋。因此三維圖形網(wǎng)格簡(jiǎn)化的實(shí)質(zhì)就是：對(duì)三維網(wǎng)格模型的點(diǎn)和三角面片進(jìn)行處理，在盡量保持原始模型特征的情況下，去除不影響原始模型特征的多余的點(diǎn)和面片，從而減低模型的數(shù)據(jù)密度，獲得能夠滿(mǎn)足需要的分辨率比較低的模型，使得三維圖形在設(shè)備終端的顯示和編輯變得容易并減少三維圖形數(shù)據(jù)在因特網(wǎng)上傳輸?shù)膲毫Α?/p>

早在1976年就有學(xué)者James?Clark提出了三維模型簡(jiǎn)化的思想，近些年，隨著計(jì)算機(jī)圖形學(xué)的發(fā)展進(jìn)步以及三維模型應(yīng)用范圍的拓展，越來(lái)越多的研究人員對(duì)三維模型簡(jiǎn)化進(jìn)行了深入全面的研究，特別是采用網(wǎng)格來(lái)表示三維模型成為主流之后，涌現(xiàn)眾多的三維模型簡(jiǎn)化算法。

現(xiàn)有的一個(gè)基于最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化算法，通過(guò)頂點(diǎn)對(duì)折疊代價(jià)的衡量，綜合考慮頂點(diǎn)對(duì)的選擇對(duì)三維模型拓?fù)浣Y(jié)構(gòu)的影響以及對(duì)被選擇的頂點(diǎn)對(duì)不同折疊操作對(duì)模型拓?fù)浣Y(jié)構(gòu)的影響，從而使得簡(jiǎn)化后的模型能夠保留更多原始模型的特征。

對(duì)于現(xiàn)有的技術(shù)，該算法雖然綜合考慮了頂點(diǎn)對(duì)的選擇對(duì)三維模型拓?fù)浣Y(jié)構(gòu)的影響以及對(duì)被選擇的頂點(diǎn)對(duì)不同折疊操作對(duì)模型拓?fù)浣Y(jié)構(gòu)的影響，使得簡(jiǎn)化后的模型能夠保留更多原始模型的特征。但是其對(duì)于存在狹長(zhǎng)三角面片的網(wǎng)格模型缺乏考慮。如圖1所示，點(diǎn)A和B為選擇的具有最小折疊代價(jià)的頂點(diǎn)對(duì)，如果將點(diǎn)B向點(diǎn)A合并，則對(duì)模型不會(huì)產(chǎn)生較大的影響。然而可能存在點(diǎn)A向點(diǎn)B合并，那么在合并后，就將產(chǎn)生如圖2所示的結(jié)果：產(chǎn)生了多個(gè)狹長(zhǎng)的小三角面片。

發(fā)明內(nèi)容

本發(fā)明是對(duì)一種基于距離加權(quán)最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化算法的改進(jìn)，其主要目標(biāo)是處理存在狹長(zhǎng)三角面片的三維模型。使用本發(fā)明的基于距離加權(quán)最小折疊代價(jià)的邊折疊簡(jiǎn)化算法，能夠盡量減少簡(jiǎn)化模型產(chǎn)生狹長(zhǎng)三角面片的出現(xiàn)，從而盡量保持了原始模型的拓?fù)浣Y(jié)構(gòu)和特征點(diǎn)。

本發(fā)明是一種基于距離加權(quán)最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化的方法。該算法以基于最小折疊代價(jià)的邊折疊算法為基礎(chǔ)，在選擇頂點(diǎn)對(duì)上進(jìn)行了改進(jìn)。首先計(jì)算出所有頂點(diǎn)與其所有相鄰頂點(diǎn)的平均距離，然后將頂點(diǎn)與相鄰頂點(diǎn)的距離與平均距離的比值作為折疊代價(jià)的一個(gè)系數(shù)，距離比值與折疊代價(jià)兩者的乘積作為新的折疊代價(jià)參與評(píng)估，該方法包括如下步驟：

步驟一：讀取三維模型的obj文件，求出平均起伏權(quán)值，確定參考閾值；

步驟二：根據(jù)模型文件中點(diǎn)的次序循環(huán)遍歷模型中的頂點(diǎn)v，全部遍歷完則進(jìn)入步驟八，否則進(jìn)入步驟三；

步驟三：通過(guò)將v的頂點(diǎn)起伏權(quán)值與參考閾值進(jìn)行比較，判斷該點(diǎn)是否是特征點(diǎn)，是則進(jìn)入步驟二；否則進(jìn)入步驟四；

步驟四：遍歷該頂點(diǎn)v的所有相鄰頂點(diǎn)，識(shí)別出未處理過(guò)的非特征頂點(diǎn)，并將該頂點(diǎn)與所有這些相鄰非特征頂點(diǎn)均配對(duì)作為邊折疊操作的候選頂點(diǎn)對(duì)；

步驟五：計(jì)算出該頂點(diǎn)與所有相鄰非特征頂點(diǎn)之間的距離，求和并算出平均距離以及每個(gè)相鄰頂點(diǎn)的距離比值；

步驟六：對(duì)每一對(duì)頂點(diǎn)都模擬進(jìn)行邊折疊操作，計(jì)算邊折疊之后產(chǎn)生的折疊代價(jià)，將其與相應(yīng)頂點(diǎn)的距離比值的乘積作為新的折疊代價(jià)。進(jìn)入步驟七；

步驟七：選擇折疊代價(jià)最小的那對(duì)候選頂點(diǎn)對(duì)作為進(jìn)行邊折疊操作的輸入，如果有多個(gè)這樣的頂點(diǎn)對(duì)存在，選擇距離最近的頂點(diǎn)對(duì)。此時(shí)模型頂點(diǎn)數(shù)減少一個(gè)。然后轉(zhuǎn)入步驟二，繼續(xù)進(jìn)行簡(jiǎn)化；

步驟八：將簡(jiǎn)化后保留的頂點(diǎn)及面片信息保存到新的obj文件中，以供下一次簡(jiǎn)化使用。

通過(guò)本發(fā)明提供的方法，本發(fā)明首先保持了基于最小折疊代價(jià)的三維模型邊折疊簡(jiǎn)化算法的簡(jiǎn)化有效性，即簡(jiǎn)化后能夠達(dá)到同樣的保持原始模型拓?fù)浣Y(jié)構(gòu)和特征的效果。其次，本發(fā)明創(chuàng)造性的將頂點(diǎn)間的距離與折疊代價(jià)相結(jié)合進(jìn)行了考慮，這使得在簡(jiǎn)化過(guò)程中降低了狹長(zhǎng)三角面片出現(xiàn)的可能。