三角網格簡化與曲面細分研究摘要在計算機圖形學和虛擬現實，地理建模，衛(wèi)星圖片識別等領域，對于大型物體模型，幾何建模中為了表征物體的表面細節(jié)，相應的3D模型通常需要相當數量的三角形。龐大的數據量將給計算機的處理和存儲，網絡數據傳輸和實時顯示帶來很大的困難。因此，如何減少模型生成和計算的數據量，提高模型網格的質量一直是相關人員研究的重點和難點。網格簡化算法可以減少復雜網格中的冗余數據，在存儲和計算方面具有很大的優(yōu)勢。基于計算機圖形處理，圖形和顯示的新技術和新成果，本文研究了網格簡化和曲面細分的理論，應用問題和有效解決方案。通過對簡化方法的研究和分析，選擇二次誤差測度簡化算法是基本算法。然后結合模型特征，在經典簡化算法的基礎上，將三角網格模型頂點的sharpdegree引入到二次誤差測度的計算中。提出了一種改進的基于由劉曉麗提出的尖銳特征的網格簡化算法，以獲得較為良好的3D模型。簡化模型可以根據尖銳特征變化合理分配網格數，使網格更有效地保持更多的關鍵細節(jié)特征。在此基礎上，對初始控制網格進行Loop細分，得到生動逼真的模型。關鍵詞：三角網格簡化,三角網格優(yōu)化，QEM算法,sharpdegreeSummaryInthefieldsofcomputergraphicsandvirtualreality,geographicmodeling,satelliteimagerecognition,etc.,forlargeobjectmodels,inordertocharacterizethesurfacedetailsofobjects,thecorresponding3Dmodelsusuallyrequireaconsiderablenumberoftriangles.Thehugeamountofdatawillbringgreatdifficultiestotheprocessingandstorageofcomputers,networkdatatransmissionandreal-timedisplay.Therefore,howtoreducetheamountofdatageneratedandcalculatedbythemodelandimprovethequalityofthemodelgridhasalwaysbeenthefocusanddifficultyofrelevantpersonnelresearch.Themeshsimplificationalgorithmcanreduceredundantdataincomplexgridsandhasgreatadvantagesinstorageandcalculation.Basedoncomputergraphics,newtechniquesandnewresultsofgraphicsanddisplay,thispaperstudiesthetheory,applicationproblemsandeffectivesolutionsofmeshsimplificationandtessellation.Throughtheresearchandanalysisofthesimplifiedmethod,thequadraticerrormeasuresimplificationalgorithmisthebasicalgorithm.Thencombinedwiththemodelfeatures,basedontheclassicalsimplificationalgorithm,thesharpdegreeoftheverticesofthetriangularmeshmodelisintroducedintothecalculationofthequadraticerrormeasure.AnimprovedmeshsimplificationalgorithmbasedonthesharpfeaturesproposedbyLiuXiaoliisproposedtoobtainabetter3Dmodel.Thesimplifiedmodelcanreasonablyallocatethenumberofmeshesbasedonsharpfeaturechanges,allowingthemeshtomoreeffectivelymaintainmorecriticaldetailfeatures.Onthisbasis,Loopsegmentationisperformedontheinitialcontrolmeshtoobtainavividandrealisticmodel.Keywords:triangularmeshsimplification,triangularmeshoptimization,QEMalgorithm,sharpdegree

附件3：目錄目錄圖清單 I表清單 Ⅱ緒論 11.1課題研究目的及意義 11.2研究現狀 11.2.1網格簡化研究現狀 11.2.2網格細分研究現狀 11.3本文主要內容 11.4本文主要結構安排 1第二章三角網格模型概述 32.1三角網格模型基本知識 32.1.1三角網格相關概念 32.1.2三角網格數據結構 32.2本章小結 4第三章網格簡化算法 53.1網格簡化原則 63.2網格簡化算法綜述 73.3二次誤差測度簡化算法 73.4本章小結 10第四章基于曲率的二次誤差測度簡化算法 114.1離散法向量和曲率概述 124.2離散法向量和曲率估計 134.3基于曲率的QEM算法 144.4實驗結果與分析 154.5本章小結 16第五章網格曲面細分 115.1細分曲面概述 125.1.1細分曲面概述 35.2曲面細分算法 135.2.1Loop細分 135.2.2改進的蝴蝶細分 135.3實驗結果與分析 155.4本章小結 16第六章總結與展望 56.1本文工作總結 66.2今后研究展望 7致謝 82參考文獻 83附錄 85圖清單圖2-1X 4圖2-2X 6圖3-1X 10表清單表2-1X 4表2-2X 6表3-1X 10緒論1.1研究背景及意義 隨著近年來虛擬現實技術的快速發(fā)展，三維模型掃描和重建技術被廣泛的應用在顯示物體的建模當中。在三維模型中，三角形網格是常用的表示方法，因此圖形處理器也一般會對三角網格渲染做一些加速和緩存優(yōu)化。但是初始網格一般存在以下問題：一方面，由于初始的三角網格常常由大量的三角形構成，所以此類網格對于計算機的處理能力和存儲有很大的要求，比如原始網格往往含有大量的頂點和三角面片數據不僅在存儲上占用很大的空間，而且模型的處理和顯示的計算量會急劇增長，因此對于復雜模型的三角網格的簡化非常重要；另一方面，原始的三角網格和簡化后的三角網格必然會出現一些畸形或狹長三角單元。在科學計算領域方面，畸形單元會造成數值計算誤差較大，對于數值求解的精度和計算效率以及穩(wěn)定性方面都有影響，更有可能造成運算不收斂。在模型渲染顯示領域，質量不好的三角形網格會影響視覺效果，如在網格的曲率變化比較大的地方，容易生成狹長劣質的三角面，此類三角較難表達出模型的局部特征，因此對于三角網格進行優(yōu)化也是一個重要的問題。在多媒體經歷了長足的發(fā)展之后，從最開始的數字音頻，到后來的數字圖像視頻，再到三維立體模型所展現的虛擬物體，極大地豐富了人們的生活。三維網格構造途徑一般有兩種思路三維網格構造途徑一般有兩種思路：首先是幾何建模，從一組較好精度的幾何面重構出三維模型；其次是三維點云重建，利用掃描儀器對現實世界采取掃描，得到物件面的點集，進而根據電暈集合構建三角網格。對于得到的網格一般采取離線處理，將其形態(tài)和數據進行優(yōu)化到預期的結果。在智能手機流行以前，三維模型處理只能在于高性能的主機上進行。伴隨著計算機中央處理器和圖形處理器性能的提高，三維模型不再是一個離人們很遠的技術。近些年以來，隨著移動設備計算性能的高速發(fā)展，復雜的三維模型顯示及處理更不僅僅存在于個人計算機上，更流行于人們的智能手機和一些移動設備。如近年來流行的刺激戰(zhàn)場，王者榮耀，游戲將三維模型和現實結合起來，給玩家增添了無窮的樂趣。盡管PC和移動設備的計算性能比起以往已經大大地增強，但是目前對于處理大型復雜網格來說仍然存在挑戰(zhàn)。由于掃描重建得到的網格往往含有大量的冗余數據，這些冗余的頂點和多邊形信息會耗費多余的資源，包括計算資源和存儲資源。比如在較平坦的地方，根據視覺效果并不需要大量的網格，因此對于這些地方可以適當減少三角形數量。另一方面，重建得到的網格可能存在一些退化的三角形，這種三角形一方面會影響網格計算的精度，另一方面也不能準確的表達模型的局部特征，因此對于這種三角形，應該進行一些優(yōu)化。因此如何進行網格簡化和優(yōu)化，使得網格模型更能適應理想的情況，并在簡化和優(yōu)化的過程中如何保持模型的細節(jié)特征，一直以來都是一個重要熱點問題。1.2研究現狀1.2.1網格簡化研究現狀關于重建生成的三角網格進行處理的過程中，簡化和優(yōu)化是必須要進行的處理步驟。由于處理后的網格，三角單元數量合理且質量好，不僅在在計算機中占用存儲空間減少，還可以減少處理器的運算量。形態(tài)較好的網格在計算方面會更加的精確，對于模型的細節(jié)特征也能更好的表現。近年來，研究者針對三角形網格的簡化和優(yōu)化做了大量的工作，并且取得了很好的成果。下面將對近年來三角網格簡化和三角網格優(yōu)化的研究現狀做出簡單的概述。早在20世紀70年代,由于科技的不斷發(fā)展，3D圖像開始進入人們世界，開始有學者關注模型網格簡化的探討和研究。但由于當時落后的計算機和不成熟的圖像處理功能,1990年前后,網格簡化才有了重大突破,涌現出了很多重要的算法,提高了網格簡化的效率,并在圖像處理，三維建模等許多領域得到了廣泛的應用。1992年后,國外研究人員相繼提出了多種多邊形網格簡化算法。Schroeder`等人提出了基于頂點刪除的模型簡化算法。'Hamann給出了一種基于三角形收縮的模型簡化算法,該算法根據三角形的曲率和角度計算簡化后的誤差,首先刪除網格模型中狹長的三角形。邊收縮簡化算法`是近年網格簡化算法研究中非常重要的一類算法,于1993年由Hoppe首先提出,通過對一個全局能量函數進行優(yōu)化控制實現簡化過程。這個方法是對通過模型邊線相連的頂點對進行操作,的其優(yōu)點不會破壞模型的拓撲結構。但當模型簡化到一定程度時,適度地破壞模型的拓撲結構反而會增強簡化的效果。而且這是一個非線性優(yōu)化過程,需要的數據量大,計算過于復雜,運行速度慢。因此Garland提出了一套以矩陣為基礎的反復收縮算法,任何頂點對之間的距離只要小于使用者所設定的閡值,就有可能被收縮。這就是后來網格簡化算法中經常被用到的經典的QEM算法。在國內近十年也開展了一些卓有成效的研究工作,其中有些是對已有的多邊形網格算法進行改進,有些是提出新的多邊形網格模型的簡化方法。都取得了相應不錯的簡化效果。有文獻簡單地引入了曲率和面積作為衡量誤差的因子,在算法的誤差矩陣中加入一項成為新的誤差矩陣,較好地取得了保留網格特征的效果,但是該方法過于簡單,而且在實現上開銷較大，運行效率較慢。也有文獻中提出了一種局部體積誤差的半邊收縮網格簡化方法,文中以半邊體積變化的絕對值并結合網格曲率信息定義誤差函數,但文中的曲率因子計算方法過于費時,并且邊收縮后新頂點的位置并沒有根據網格體積變化量來確定。1.2.2曲面細分的研究現狀1974年，Chaikin提出了一種細分算法，該算法在閉合控制多邊形上定義，通過細分限制過程生成表面。Reisenfeld發(fā)現Chaikin算法是一種具有均勻二次條帶的細分算法，即在一個循環(huán)節(jié)點序列的每個區(qū)間插入節(jié)點的遞歸過程。應用相同的原理，通過推廣雙二次和雙三次樣條曲面二分法，Doo/Sabin和Catmull/Clark分別提出了一種細分算法。然而，奇點處的細分曲面的連續(xù)性問題尚未解決。直到1995年，Reif解決了奇點處細分曲面的連續(xù)性問題，使得細分曲面在理論和實踐上得到了極大的發(fā)展。細分算法根據細分曲面與控制網格之間的關系進行分類，可分為兩類：近似細分算法和插值細分算法。在近似細分算法中，Doo/Sabin和Catmull/Clark技術概括了從四邊形控制網格生成雙二次和雙三次B樣條曲面的想法。Loop提出了一種類似的細分算法，即四次B樣條二分法算法的推廣。Loop算法與Doo/Sabin和Catmull/Clark細分算法的不同之處在于它基于三角形控制網格。插值細分算法首先由Dyn/Gregory研究，并于1990年給出了著名的蝶形插值細分算法。與其他細分算法一樣，蝴蝶細分算法使用一些鄰域點進行細分。所需的數據結構簡單且易于實現，但是為了實現C'連續(xù)極限曲面，該算法需要初始控制拓撲規(guī)律性。網格。1996年，Zorin提出了一種插值細分算法，該算法保留了蝴蝶算法的簡單性，并為非規(guī)則初始網格實現了良好的平滑性。這些插值細分算法廣泛用于小波和多邊形表面的多分辨率分解和多分辨率編輯。Kobbelt提出了一種變量插值細分算法，其中頂點位置是通過求解優(yōu)化問題得到的，因此該算法是全局的，它破壞了計算機圖形應用中的細分算法。

1.3本文主要內容本文主要研究了基本網格簡化算法（QEM算法），給出了相關概念并在VS2015+Opengl環(huán)境下完成了該算法的相關實驗,分析實驗結果，在查閱大量文獻資料對該簡化算法進行改進,經過反復試驗不斷調試,最終獲得一個能較好地保留原始模型重要幾何特征的控制網格。然后,在此基礎上,選擇Loop曲面細分算法,對該控制網格進行細分,得到不同分辨率下具有很好光順性和良好視覺效果的細分曲面,能夠較為真實的表達出模型。1.4本文結構安排本文主要研究了基于曲率和面積的二次誤差測度網格簡化和基于細分規(guī)則的曲面細分。按照網格模型的簡化原則,依次介紹了三角網格簡化算法,并在此基礎上,將離散曲率引入到邊收縮代價計算中,得到的控制網格簡化模型能合理地分配網格,更好地保持了原始模型的重要特征。在此基礎上,對控制網格進行細分,得到光滑的細分曲面。本文共分為六章,各章的主要內容如下第一章論述網格簡化和曲面細分研究的目的和意義,介紹網格模型簡化及細分技術的發(fā)展及其國內外的研究現狀,概括本文的研究內容、研究方法。第二章通過對不同的三角網格分析,確定選用三角網格模型和采取的數據結構,進而對與網格模型相關的基礎知識做詳細的闡述。第三章研究已有的網格簡化算法,對各個算法的特點進行深入分析,最后選定經典的二次誤差測度簡化算法作為基礎算法,詳細地介紹該算法,并提出算法改進的方向。第四章與QEM算法優(yōu)化，研究三角網格曲面上曲率的刻畫,并將離散曲率引入到邊收縮代價計算中,提出基于曲率二次誤差測度網格簡化算法,并通過試驗對算法進行驗證。第五章在對網格簡化的基礎上,采用Loop細分算法對簡化模型進行細分,通過試驗對細分算法進行驗證,得到相應的細分曲面。第六章總結全文的研究工作,并指出今后進一步研究方向。2. 三角網格概述2.1三維建模我們日常生活中事物是彼此相關聯(lián)的，任何一件事情都不可能孤立存在，因此，用計算機虛擬世界的事物反映現實世界事物之間的聯(lián)系必然復雜，為了更好地表達現實世界事物，方便計算機系統(tǒng)進行準確高效的映射，通常需要人類建立相應的規(guī)則（模型）來建立描述客觀實體本身及實體之間聯(lián)系。以空間信息模型為例，在基于對象的建模中，關鍵把空間信息抽象成明確的，可識別的和相關的事物或實體，例如，在二維GIS中，點（NODE）,面（face），線（Line）就是地理空間信息中的三類對象。在計算機中，表達一個真實世界的三維對象或虛擬模型就需要通過幾何建模的方式更好地表達。2.1.1幾何建模方法?線框模型，顧名思義，該模型只有“線”的概念，僅使用一些頂點和棱邊來表示物體?？杀磉_一些結構簡單的事物，如房屋、零件設計等結構信息。但這種方法有很明顯的短板，就是無法展現事物的整體（如紋理等相關信息），模型較為抽象，應用范圍十分有限。但操作簡單，技能要求不高，對顯示效果要求不高的（CAD）應用，線框模型得到了不錯的應用。?表面模型相對于線框模型來說，引入了“面”的概念，相比較而言能實現的效果就豐富了很多。對于大多數人來說，我們更關注于事物表面，因此，面模型通過使用一些參數化的面片（如多邊形網格）來模擬真實物體的表面，這樣能夠更加生動形象秒回事物表面特征。這種方式以其優(yōu)秀的視覺效果被廣泛應用于電影、游戲等行業(yè)中，也是我們平時接觸最多的。如最近比較火的《復聯(lián)》，我的世界等都使用了相關技術，給我們帶來了完美的視覺游戲體驗。Meshlab、Maya等工具也在這些方面有不錯的表現。而表面模型雖然豐富了物體表面的細節(jié)和特征，但是當我們在專業(yè)領域需要內部信息時，面模型就顯得捉襟見肘了。?實體模型相對于表面模型來說，又引入了“體”的概念，在構建了物體表面的同時，深入到物體內部，形成物體的“體模型”，這種建模方法被應用于醫(yī)學影像、科學數據可視化等專業(yè)應用中。2.2三角網格模型三角網格就是全部由三角形組成的多邊形網格。多邊形和三角網格在圖形學和建模中起著至關重要的作用，三角網格用來模擬復雜物體的表面。如下圖所示：圖2.2當然，任意多邊形網格都能用來模擬現實世界中的客觀事物表達，但三角網格以其結構簡單性，操作靈活性和表達準確性而吸引人，與其他多邊型相比，許多操作（如編程建模，模型優(yōu)化）對三角網格更容易。2.2.1表示網格三角網格需要存儲三類信息：

頂點。每個三角網格都有頂點，確定三角網格形狀。

2.邊。連接兩個頂點的邊，每個三角形有三條邊。

3.面。每個三角形對應一個面，我們可以用頂點或邊列表表示面。2.3表示三角網格數據結構在計算機圖形學上，表達表面網格的數據結構有三種，分別是面列表、鄰接矩陣、半邊結構。面列表的典型代表是.obj格式文件和Unity。其優(yōu)點是，簡單而且能夠表達非流形網格，但網格查詢和處理能力差。當然還有一些不是利用索引，而是直接儲存整個頂點的信息，典型代表是OpenGL可編程管線和.stl格式文件。鄰接矩陣就是將網格視為鄰接圖，給定一個包含n個頂點的網格，構建一個n*n的矩陣來表達鄰接關系，優(yōu)點是支持非流型網格和高效查詢，缺點是沒有邊的顯示和表達。關于半邊數據結構，很好理解，就是把三角網格的每一條邊分成兩個方向相反的半邊，并且一條邊未分半邊之前一條邊是屬于兩個面，而每個半邊完全屬于一個面。綜合上述，得到半邊的數據結構為一條半邊的起始頂點origin，這條半邊指向的下一條半邊next，這條半邊對應的另外半邊opposite，和這條半邊所在的面IncFace。這就能解釋為什么半邊數據結構僅支持流形網格了。2.4本章小結本章內容主要介紹了三同的三維建模方法和三角網格建模的數據結構等信息，從多個角度進行對比，分析優(yōu)缺點，最終確定使用三角網格和半邊數據結構作為幾何建模的標準。3.網格簡化算法3.1網格簡化原則三角形網格簡化的原理是通過一定的規(guī)則來減少三維對象模型的表面的三角形網格，同時保持原來的三維模型的重要幾何特征。3.2網格簡化算法對于三角網格簡化的處理，一般有這幾種簡化方式：三角網格重新劃分，表面重采樣和網格幾何元素刪除。1.三角網格重新劃分三角形網格重新劃分指的是根據現有的三角網格信息，如局部曲率，三角片面積或局部密度在已有的網格上重新布點，最后加以調整生成新的三角網格。針對這種方法，國內外學者做了大量的研究。Turk等提出了新的簡化方法，即根據已有原始的三角網格創(chuàng)建新的多細節(jié)層次模型(LOD)，此方法將給定數量的定點散布到初始三角網格表面上，根據新的頂點和原始頂點生成中間網格，最后移除中間網格中的初始頂點，再對刪除過程中產生的多邊形重新進行三角化，最終再做一次網格優(yōu)化。這種方法也有一些缺陷，如網格曲率變化較大，重新劃分效果不是很好，新點分布計算量大等。Li[2]等人提出了針對非鈍角三角形的簡化方法，首先通過重新劃分網格將其轉化為非鈍角網格，然后通過約束將其擬合到原始網格，最后再通過二次誤差度量(QEM)將其冗余數據移除。Liu[4]等人提出了先使用原始頂點構造出Delaunaymeshes(DM)，然后通過QEM算法將構造的網格簡化，從而得到質量較好，數據冗余量小的網格。周昆等基于Turk等改進的重新劃分方法，使用了曲率特征和三角形面積表示的疏密特征來分布新點，該方法復雜度小，效果較好。2.網格表面重采樣通過網格表面重采樣的方式簡化網格，操作的自由度更大，可以得到形態(tài)更好的三角形單元，但是不可避免的帶來的較高的計算量。為了達到較為規(guī)則的重采樣，一般都要對原始網格執(zhí)行參數化。Eck等使用新的方法將初始網格進行參數化，得到了一個基準網格，再從基準網格的三角片中進行重采樣映射回初始的網格面。這種方法獲取到的三角網格，每個三角面片連通度都是較平均的。通過這種方法得到的新網格其實并不均勻，在這種方法中，參數化的質量決定著網格的質量。把不可以直接展開的三維模型參數化到平面中會導致扭曲誤差，因此在參數域中繼續(xù)進行重采樣將造成扭曲被擴大。因為每個面的映射函數不是相同的，在二維空間進行均等采樣后重建的三角網格可能并不是均等的，所以通過形拓撲結構優(yōu)化為目的的重采樣，即使網格的每個頂點的度比較均勻，但是單個三角形質量卻并不達標。總的來說，通過重采樣去簡化網格，要先根據初始網格求出基網格，然后從基網格映射到新的三維平面。這種方法不僅計算量大，而且在重新網格化時通過三維模型-位平面-三維模型這一映射過程，由于參數化的質量有可能導致新的網格出現扭曲，與原網格形成較大的誤差。3.幾何元素刪除幾何元素刪除指的是通過刪除三角形網格的面，頂點或者邊來達到簡化三角形網格的目的。這種簡化方法是通過定義一系列簡化元操作，使用這些簡化元對三角網格中的幾何元素按照某種優(yōu)先級進行操作，從而達到簡化的目的。簡化元操作包含頂點移除，三角面移除，三角形折疊和三角形頂點聚類等。頂點刪除的主要內容是在模型網格的但各頂點進行刪除操作。最簡單的方法就是判斷與該頂點鄰接面上的頂點是否共面，如果共面，則直接移除這個頂點不會對網格的局部結構造成影響，移除頂點和其鄰接面后需要對周圍所產生的空洞進行填補，重復上面的步驟，直至達到要求的簡化程度。Schroeder等首次提出了基于三角網格頂點元素刪除的簡化算法。此算法簡化效率高，網格的三角面質量好，在大型模型的三角網格上應用起來效果簡化較好，但是由于這種方法只能對流型網格進行操作，而不能對網格上的非流型頂點。后來其將方法改進后，可以通過改變拓撲結構去簡化出漸近的網格。還有一種頂點聚類方法，其基本思想為將原始網格均等劃分為多個規(guī)則小區(qū)域（一般為正方形），對于每個區(qū)域計算一個中心頂點（非幾何中心），將原始網格在該區(qū)域的點合并到區(qū)域中心點，若某三角形在該區(qū)域有大于一個頂點，則將三角形刪除，重復此步驟遍歷劃分的小區(qū)域，最終得到簡化后的網格。頂點聚類算法的優(yōu)點在于實現起來容易，算法效率也比較高，程序魯棒性好，因為其對于原始網格拓撲結構沒有限制。但是它也存在著一些問題，頂點聚類方法在簡化步驟中有可能會改變網格的拓撲結構由于在網格結構變化明顯處，簡化算法往往會對網格的拓撲結構造成該邊改變，因此會造成網格的細節(jié)特征退化，對于網格的外觀造成影響。小區(qū)域的大小決定了簡化的精度，由于區(qū)域是等分的，因此其對于密度不均勻的網格簡化效果不是很好（密度不同往往意味著不同的特征），因此可以針對這種方法將網格的密度作為參數加入到區(qū)域的大小中去，從而得到一種自適應區(qū)域大小的聚類方法，從而更好地保留網格的特征。因此該算法的核心在于如何選取聚類區(qū)域大小和聚類中心點。Rossignac等提出的頂點聚類算法使用均勻的柵格來劃分出區(qū)域，計算出每個頂點的優(yōu)先級，較大曲率或者面積較大出的頂點優(yōu)先級比較高，選取區(qū)域中優(yōu)先級最高的頂點作為中心點。Boubekeur等提出了一種快速的網格簡化算法，該算法采用了頂點隨機選擇和三角形重新索引兩種策略，頂點被選擇的概率取決一個網格局部特征估計算法，它可以優(yōu)先考慮曲率較高的區(qū)域，但是仍然可以在曲率較小的地方充分采樣。重新構造三角形是通過廣度優(yōu)先算法，從選擇的頂點開始，根據相鄰的三個面去確定該三角形。該網格簡化算法的時間復雜度在這兩個步驟中都是線性的，因此速度很快。Morigi等提出了基于聚類的多精度網格簡化算法，算法基于p-Laplacian流的表面演變，通過p-Laplaciand的空間效果去決定哪些區(qū)域適合簡化。具體方案是在每個簡化精度上通過空間擴散確定要簡化的候選點，然后通過增量式的簡化并且更新頂點的位置達到簡化目的。這種算法對于不同復雜度的模型均有效，并且對于具有尖銳特征和平坦部分的模型效果較好。在簡化算法中，最常用的是基于邊折疊的算法，Hoppe等首先提出了基于邊折疊的三角網格簡化算法。該算法選中兩個相鄰的頂點和，刪除邊以及該邊相鄰的面，將點和合并到一個計算出的新點，此時邊鄰接的兩個面則變成了兩個邊。這里的新點取值根據不同的算法會有不同的取法?；谶呎郫B的三角網格簡化算法一般有以下幾個特點：(1)算法魯棒性好，對于三角網格的拓撲結構沒有太多的要求和限制。(2)簡化的網格對于原網格的擬合度比較高。(3)對于有孔洞的模型，可以在簡化過程中將其修復，從而較高比率的簡化模型。(4)可以生成LOD模型，因為根據簡化的路徑，往往可以反推從而得到多種精度的網格。(5)算法的復雜度取決于網格誤差的計算方式和折疊新頂點的計算方式。例如對于要折疊的點和，如果簡單的取，或的中點作為新頂點，此時算法復雜度會較低，但是如果通過誤差測度去計算新頂點，算法復雜度會相應的增高。由于邊折疊算法的以上特點，研究者對其進行了廣泛的研究。最早的邊折疊算法是Hoppe等于1993年提出的，Hoppe使用了能量法來決定折疊的順序和折疊后頂點的位置，但是該算法能量計算方法復雜度較高，在實際應用中比較困難。因此Garland[3]等人提出了QEM(二次誤差度量，QuadricErrorMetrics)算法，該算法采用將折疊點到其鄰接面的距離表示為一個二次誤差矩陣，采用該矩陣來表示誤差。先求出每個頂點的誤差矩陣，然后選擇誤差最小的頂點對進行折疊直至達到要求。QEM簡化算法中的新頂點位置計算可以選取使得網格簡化前后誤差最小的位置，算法步驟簡單并且復雜度低，最終得到的網格質量較好。由于經典的網格簡化算法只關注初始網格和簡化結果之間的算數誤差，沒有考慮簡化后網格的視覺誤差，針對這一現象研究者們提出了一系列結構和特征保留的網格簡化算法。Salinas等針對特定的情境提出了結構敏感網格的簡化算法，該算法將三角形表面和一系列檢測到的代理平面作為輸入，接著使用貪心算法對邊界進行折疊，這樣可以盡可能的達到近似于原平面和代理平面的效果。該算法可以很好的擬合平面，并且過濾掉其他部分，能最大可能地保留模型的整體結構。Wang等提出了一種基于曲率的三角形網格簡化算法，由于基于邊折疊算法往往關注原始網格和簡化后網格之間的誤差，忽略了網格的幾何特征。此算法通過計算每個頂點的平均曲率并考慮了頂點鄰接面的曲率變化改進經典的邊折疊網格算法，簡化結果能夠保留原始模型的主要拓撲特征和幾何特征，并且不需要復雜的計算，也可以減少重建過程中噪聲和梯度的影響，從而使得網格表面平滑。由于三位模型往往也具有一些紋理色彩，因此考慮到模型的整體外觀，An等人提出了一種視角獨立的顯著性模型，這種模型綜合考慮了顏色信息和幾何形狀信息的影響。該算法首先對輸入網格的每個頂點計算視角獨立的顯著性值，考慮的因素包括曲率，網格顯著性，多視角圖像的最大，最小和平均顯著性等，接著根據每個頂點的誤差去決定簡化順序，保證每次簡化都損失的是較低的顯著性。Jiang等人結合基于曲率和距離誤差兩種算法提出了一種基于曲率和距離度量的新型網格簡化算法，很好的保持了模型的形狀特征并且降低了簡化后模型和原始模型的整體誤差。對于簡化算法速度方面的改進，有研究人員提出了基于GPU(GraphicsProcessingUnit，圖形處理器)和并行網格簡化算法。Papageorgiou等在GPU上實現了三角網格的簡化算法，該算法在組合的三角網格上進行基于二次誤差度量的邊折疊，利用了OpenCL提供的數據并行性，并且在其主要的迭代結構里面沒有連續(xù)的段，充分地利用了GPU的計算能力，結果顯示相比順序的折疊算法，該算法速度更快。Cabiddu等提出了一種對于任意規(guī)格三角形網格的簡化算法，并且利用了現代分布式環(huán)境的計算能力。算法利用了多臺計算機，結合了靈活的外存技術和精確的內存算法，算法運行快速。Lee等提出了一種新的基于內嵌樹折疊方式的網格簡化并行算法，為了并行化地在GPU上處理網格，首先打破了網格數據結構之前的依賴關系，將網格分解為多個部分，通過延遲更新簡化的結果，將簡化的路徑保存在臨時表中，可以在下一步全局性的進行一比較個更新。正是由于這種懶更新的方法，可以在網格中自由的選擇小的結構進行折疊，經過實驗對比，該算法比Papageorgiou等人基于GPU的簡化算法快十倍以上。Odaker[22]等人提出了基于GPU加速的并行半邊折疊實時網格簡化算法，使用基于半邊折疊來代替邊折疊，因此可以在多個頂點上并行進行操作，使用一系列頂點的邊界來解決拓撲不一致或者折疊過程中發(fā)生的邊交錯情況，這種方法可以并行地刪除網格中上千個頂點，借助于現代GPU的能力，算法可以達到實時的視覺上的簡化效果。3.3QEM（QuadricErrorMetrics）網格簡化算法在計算機圖形應用中，為了盡可能真實呈現虛擬物體，往往需要高精度的三維模型。然而，模型的復雜性直接關系到它的計算成本，因此高精度的模型在幾何運算時并不是必須的，取而代之的是一個相對簡化的三維模型，那么如何自動計算生成這些三維簡化模型就是網格精簡算法所關注的目標。Garland等人。1997]提出了基于二次誤差作為指標成本，這是快速且具有高品質的邊緣收縮算法。如下圖所示（截取自論文）：算法詳述：1.構造每個頂點的Q1.計算一個頂點的所有平面的方程ax+by+cz+d=0且a2+b2+c2=1保存參數a，b，c，d。

2.計算每個平面的fundamentalerrorquadricKp3.將一個頂點的所有Kp求和構成該點的Q。2.選擇合并的點對合并的點對有以下兩種：兩點之間存在邊連接兩點之間距離小于閾值t計算合并后點的位置計算合并后點的Q=Q1+Q2，Q1，Q2為合并的兩個點的Q

2.計算新點坐標可以用下面的式子，q11表示新的Q的第一行的第一個元素的值。3.如果右式左面的矩陣不可逆則例如取k=0.1，0.2，。。。。分別計算cost，其中cost計算方法如下：取cost最小的位置即可。效果展示3.4本章小結本章主要簡單介紹了網格簡化的幾種主要核心基礎算法,然后系統(tǒng)地介紹了各種網格模型簡化方法,詳細地展示了各個簡化算法的優(yōu)缺點，最后確定以經典的QEM簡化算法為本文網格簡化的基本算法,并詳細介紹了QEM算法內容和最后給出實驗結果?？梢钥闯鯭EM簡化算法很好的保留了模型特征，但簡化程度過大，盡管算法效率較高，但是我們需要提高模型精度，接下來就是對QEM算法優(yōu)化，達到我們預期效果。4.基于曲率的QEM算法優(yōu)化在三維模型網格完成簡化后，網格中往往會引入狹長三角形。狹長三角形的數量往往表示著三角形網格的質量。因為這種畸形三角單元一方面會影響網格計算的精度，另一方面也不能準確的表達模型的局部特征。因此對于這種三角形，應該進行一些優(yōu)化，在不改變模型網格外觀的條件下，盡可能的將其轉化為符合Delaunay準則的或者等邊三角形。對于三角形網格優(yōu)化，常用的算法有兩大類：基于拓撲結構優(yōu)化算法和頂點位置調整優(yōu)化算法兩種。拓撲結構優(yōu)化算法指的是通過改變三角形網格的局部結構來減少網格中的狹長三角形，從而提高網格的整體質量。頂點位置調整優(yōu)化算法是通過調整網格中頂點的位置來優(yōu)化三角形網格的質量，通常會定義一些能量公式，通過最小化該能量值這種引導式的步驟，修正網格中的劣質三角形單元。4.1QEM優(yōu)化算法簡介為了在簡化過程中能保留三角形網格的重要特征，劉曉利[46]等定義了一個尖征度(sharpdegree)。特征邊：給定一個閾值角度θ，如果與改邊鄰接的兩個面法向夾角大于或等于θ，則稱該邊是特征邊，為了更好的保留網格邊界。定義所有邊界邊均是特征邊。頂點的尖銳特征：鄰近于頂點在頂點尖銳特征的邊的數量。的最小值是零和最大值為頂點的相鄰的邊的數量。上述概念需要補充的是，對于三角形網格邊界邊，默認其為尖特征邊，這樣可以促使邊界邊延遲折疊，從而盡可能保留模型邊界這一重要特征。將尖特征度和QEM算法結合起來，得到以下公式對于折疊時尖特征度的改變，算法采用了和QEM更新誤差矩陣同樣的方式，即將兩個端點的誤差項簡單相加作為新頂點的尖特征度。這種方法將QEM算法和尖特征度的更新統(tǒng)一起來了，因此復雜度和原始的QEM沒有差別。這種估算方式比較接近采用重新計算的方法求出的新頂點的尖特征度。4.2算法流程結合QEM算法和尖特征度概念，新的三角形網格簡化算法步驟如下圖：4.3實驗結果采用本章中改進的優(yōu)化算法對bunny模型進行簡化，bunny模型的原始頂點有34384個，下圖分別是簡化后剩余10000，5000和2000個頂點的網格模型。可以明顯看到網格變稀疏且模型特征保留較好。4.4本章小結本章討論了QEM算法在這折疊中的具體實現和不足之處。針對QEM算法在簡化三角形網格過程中不能保留模型有價值的特征，結合了角點征度概念實現了改進后的QEM算法，實驗結果分析顯示該算法對三角形網格中細節(jié)特征保留情況較理想。針對開放型三角網格邊界處的折疊，提出了改進的方法，使得折疊后的模型邊界能盡可能地接近原始邊界。5.網格曲面細分5.1細分曲面概述3D模型的網格細化是基于網格的離散表面的表示，它可以從任何拓撲網格構造光滑的表面。細化方法的基本思想是定義一個網格序列，其采用了某些細分規(guī)則（通常加權平均）在給定的初始網格插入新頂點，從而連續(xù)精制一個新的網格使用的限制，和細分規(guī)則重復。在極限，網格收斂的平滑曲線或表面上。3D模型網格的細化是在圖形算法和游戲領域的一個比較普遍的和有價值的算法。網格細分是由細分規(guī)則作用在初始網格得到的。細分規(guī)則可以分為兩個部分：一是拓撲分裂規(guī)則，主要用來描述網格每次細分之后所有頂點之間的連接關系，該過程也稱為分裂；另一個是幾何規(guī)則，用來計算新頂點的幾何位置信息，這一過程也稱為平均。通常有兩種基本的分裂方法：頂點分裂和面分裂，其區(qū)別主要在于所作用的基本幾何體元。圖示如下：5.1.1頂點分裂5.1.2面分裂5.2曲面細分算法在實踐中經常使用的三種細分模式主要有三種：Loop細分模式，Butterfly細分模式，√3細分模式，這三種方法的主要區(qū)別即在于它們的細分規(guī)則不同。這里主要介紹LOOP細分算法。Loop細分Loop細分模式采用1-4三角形分裂，只生成E-頂點和V-頂點。頂點的計算如下：a.若內部邊有兩個頂點v0和v1，共享此邊的兩個三角形（v0,v1,v2）和（v0,v1,v3），則新生成的E-頂點為:若內部頂點v的1-鄰域頂點為vi(i=0,1,2,…,n-1)，則新生的V-頂點為：即是頂點本身與其所有相鄰頂點的加權和，它本身的權值為，而鄰點權值為：b.若邊界邊的兩個頂點為v0和v1，則新生成的E-頂點為：c.若邊界頂點v在邊界上的兩相鄰頂點為v0和v1，則新生成的V-頂點為：圖5.2.1頂點位置5.3實驗結果與分析5.3.1實驗步驟1.確定插入頂點的位置（由公式計算插入的頂點坐標，生成一個新的頂點集合，并將其與舊的halfedge關聯(lián)）。2.確定原來頂點的位置（loop算法中需要重新調整舊的頂點，所以需要舊頂點位置）。3.更新頂點信息（將現有的halfedge和頂點集合起來構成新的face和grids）。具體執(zhí)行第一步如下圖所示以halfedge(vo,v1)為例，讓HalfEdge_halfedge*找到指向halfedge的點，將被find指向的halfedge的下一個原點添加到v0的鄰居上，即v1，檢查被find指向的halfedge的下一個孿生兄弟是否存在。然后我們發(fā)現指向它，并繼續(xù)循環(huán)，直到它返回halfedge(v0,v1)。在這個過程中，如果被find指向的halfedge的下一個孿生兄弟不存在，它就會到達一個終點，您可以選擇它是否僅僅是out/Indegree。相鄰點計算原子價。然后使用類似于find的find指向halfedge(v1,v0)并從另一個方向計算。第二步重構網格。生成插入點并移動原始頂點的過程與插入的新頂點和舊的halfedge相關聯(lián)，所以它實際移動情況可以和下圖相關聯(lián)。然后根據顯示的順序將原始face分成四個，并按照顯示的順序生成新的face和halfedge。5.3.2實驗結果本算法采用半邊數據結構的網格細分，己經在vs2015+opengl環(huán)境實現,并對來源于網 絡的三維網格模型進行細分試驗實驗,對算法得到的細分結果如圖一所示。圖一為cube模型的細分結果,圖二是T-shape模型的細分結果。從圖中可以看出,經過細分之后的模型光順性更好,很好地提高了模型的視覺效果（分別細分0次，1次，5次）。5.3.2圖一cube5.3.2圖二T-shape5.4本章小結本章首先對細分曲面進行概述重點對Loop細分方法進行深入研究,并實現該算法。6.總結與展望6.1工作總結在深入研究網格簡化和細分曲面技術的基礎上,提出了一種改進的基于曲率和面積的二次誤差測度簡化算法,并在此基礎上對簡化網格進行細分曲面擬合,提高模型的視覺效果。本文的主要研究內容如下在討論各種網格簡化算法并分析各自的優(yōu)缺點之后,深入分析并實現了網格簡化領域比較經典的算法。算法只是將頂點到平面的距離的平方和作為其簡化的誤差準則,衡量標準單一,在簡化時忽略了模型簡化邊周圍的曲率,邊長和三角形形狀等因素,因而簡化后模型網格的頂點會均勻分布,甚至一些重要的幾何特征會發(fā)生形變或者丟失等。在此基礎上,本文提出了一種基于曲率和面積的改進的二次誤差測度網格簡化算法,該算法實現快速,并且能夠較好地保持模型的尖銳特征,在解決模型的邊界問題上也有較好的表現。在網格簡化的基礎上,利用規(guī)則實現了對模型的細分,使得細分曲面不斷地逼近原始模型,得到的模型的細分曲面具有很好的光順性。6.2今后研究展望對算法模型進一步優(yōu)化，與深度學習相結合，實現生成的簡化三角網格的網格質量達到最優(yōu)效果，同時降低計算機資源使用。參考文獻郝娟兒.網格簡化和曲面細分的研究[D].東華大學,2012.

[2]郭力真吳恩華.多邊形模型簡化算法綜述[D].計算機應用研究,2005.

[3]祁田宇.虛擬水電仿真