[發明專利]一種基于距離加權最小折疊代價的三維模型邊折疊簡化的方法

有效

• 申請號: 201310210453.2
• 申請日: 2013-05-31
• 公開（公告）號: CN103295266A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 鄧龍騰;羅笑南;薛凱軍;肖劍
• 申請（專利權）人: 東莞中山大學研究院;中山大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及技術計算機領域，具體涉及一種基于距離加權最小折疊代價的三維模型邊折疊簡化的方法。

背景技術

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

與二維圖片用圖像分辨率來表示圖像精度的方法一樣，三維圖形也用模型分辨率來對應模型數據密度的大小。模型數據密度大意味著模型分辨率高，模型比較精確精細；模型數據密度小意味著模型分辨率低，模型比較粗糙簡陋。因此三維圖形網格簡化的實質就是：對三維網格模型的點和三角面片進行處理，在盡量保持原始模型特征的情況下，去除不影響原始模型特征的多余的點和面片，從而減低模型的數據密度，獲得能夠滿足需要的分辨率比較低的模型，使得三維圖形在設備終端的顯示和編輯變得容易并減少三維圖形數據在因特網上傳輸的壓力。

早在1976年就有學者James?Clark提出了三維模型簡化的思想，近些年，隨著計算機圖形學的發展進步以及三維模型應用范圍的拓展，越來越多的研究人員對三維模型簡化進行了深入全面的研究，特別是采用網格來表示三維模型成為主流之后，涌現眾多的三維模型簡化算法。

現有的一個基于最小折疊代價的三維模型邊折疊簡化算法，通過頂點對折疊代價的衡量，綜合考慮頂點對的選擇對三維模型拓撲結構的影響以及對被選擇的頂點對不同折疊操作對模型拓撲結構的影響，從而使得簡化后的模型能夠保留更多原始模型的特征。

對于現有的技術，該算法雖然綜合考慮了頂點對的選擇對三維模型拓撲結構的影響以及對被選擇的頂點對不同折疊操作對模型拓撲結構的影響，使得簡化后的模型能夠保留更多原始模型的特征。但是其對于存在狹長三角面片的網格模型缺乏考慮。如圖1所示，點A和B為選擇的具有最小折疊代價的頂點對，如果將點B向點A合并，則對模型不會產生較大的影響。然而可能存在點A向點B合并，那么在合并后，就將產生如圖2所示的結果：產生了多個狹長的小三角面片。

發明內容

本發明是對一種基于距離加權最小折疊代價的三維模型邊折疊簡化算法的改進，其主要目標是處理存在狹長三角面片的三維模型。使用本發明的基于距離加權最小折疊代價的邊折疊簡化算法，能夠盡量減少簡化模型產生狹長三角面片的出現，從而盡量保持了原始模型的拓撲結構和特征點。

本發明是一種基于距離加權最小折疊代價的三維模型邊折疊簡化的方法。該算法以基于最小折疊代價的邊折疊算法為基礎，在選擇頂點對上進行了改進。首先計算出所有頂點與其所有相鄰頂點的平均距離，然后將頂點與相鄰頂點的距離與平均距離的比值作為折疊代價的一個系數，距離比值與折疊代價兩者的乘積作為新的折疊代價參與評估，該方法包括如下步驟：

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

步驟二：根據模型文件中點的次序循環遍歷模型中的頂點v，全部遍歷完則進入步驟八，否則進入步驟三；

步驟三：通過將v的頂點起伏權值與參考閾值進行比較，判斷該點是否是特征點，是則進入步驟二；否則進入步驟四；

步驟四：遍歷該頂點v的所有相鄰頂點，識別出未處理過的非特征頂點，并將該頂點與所有這些相鄰非特征頂點均配對作為邊折疊操作的候選頂點對；

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

步驟六：對每一對頂點都模擬進行邊折疊操作，計算邊折疊之后產生的折疊代價，將其與相應頂點的距離比值的乘積作為新的折疊代價。進入步驟七；

步驟七：選擇折疊代價最小的那對候選頂點對作為進行邊折疊操作的輸入，如果有多個這樣的頂點對存在，選擇距離最近的頂點對。此時模型頂點數減少一個。然后轉入步驟二，繼續進行簡化；

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

通過本發明提供的方法，本發明首先保持了基于最小折疊代價的三維模型邊折疊簡化算法的簡化有效性，即簡化后能夠達到同樣的保持原始模型拓撲結構和特征的效果。其次，本發明創造性的將頂點間的距離與折疊代價相結合進行了考慮，這使得在簡化過程中降低了狹長三角面片出現的可能。