VR04多細節(jié)層次模型生成和繪制課件

第4章多細節(jié)層次模型和繪制計算機科學(xué)系2009，51第4章多細節(jié)層次模型生成和繪制第4章多細節(jié)層次模型和繪制計算機科學(xué)系1第4章多細主要內(nèi)容4.1 簡介4.2 基本概念4.3網(wǎng)格簡化算法4.4多分辨率模型生成算法4.5實時連續(xù)LOD模型繪制4.6地形實時繪制2第4章多細節(jié)層次模型生成和繪制主要內(nèi)容4.1 簡介2第4章多細節(jié)層次模型生成和繪制4.1

簡介細節(jié)層次LOD（LevelofDetail）1976年Clark提出指對同一場景或場景中的物體，使用具有不同細節(jié)的描述方法得到一組模型，供繪制時選擇使用目的是減少模型的多邊形個數(shù)，提高繪制速度廣泛應(yīng)用于復(fù)雜場景快速繪制、飛行模擬器、3D動畫、虛擬現(xiàn)實等系統(tǒng)3第4章多細節(jié)層次模型生成和繪制4.1簡介細節(jié)層次LOD（LevelofDetail4.1

簡介LOD方法的基本思想不同的物體或物體的不同部分采用不同的細節(jié)繪制時，如果物體離視點比較遠，或者物體比較小，可以用較粗的LOD模型繪制，反之用較細的模型繪制同樣，對運動快的物體用較粗的LOD模型繪制，反之用較細的模型繪制4第4章多細節(jié)層次模型生成和繪制4.1簡介LOD方法的基本思想4第4章多細節(jié)層次模型4.2

基本概念誤差度量如何生成不同細節(jié)的模型局部誤差距離誤差計算曲率誤差計算5第4章多細節(jié)層次模型生成和繪制4.2基本概念誤差度量5第4章多細節(jié)層次模型生成和繪4.2

基本概念全局誤差計算法具有較好的近似效果，但計算量大一般用法簡化過程中，刪除的頂點具有盡量小的全局誤差精化過程中，增加的頂點具有盡量大的全局誤差6第4章多細節(jié)層次模型生成和繪制4.2基本概念全局誤差6第4章多細節(jié)層次模型生成和繪4.2

基本概念簡化操作指在網(wǎng)格模型簡化過程中使用到的基本操作包括頂點刪除：把三角形中不重要的頂點刪去三角形刪除：若三角形的面積小于某個值，移去頂點刪除三角形刪除7第4章多細節(jié)層次模型生成和繪制4.2基本概念簡化操作頂點刪除三角形刪除7第4章多細4.2

基本概念簡化操作包括（續(xù)）邊折疊：把邊折疊成一個新點，并把與邊相連的點連到新點三角形折疊：把三角形折疊成一個新點，并把與三角形相連的點連到新點邊折疊三角形折疊8第4章多細節(jié)層次模型生成和繪制4.2基本概念簡化操作邊折疊三角形折疊8第4章多細節(jié)4.3

網(wǎng)格簡化算法幾何元素刪除型算法幾何元素直接刪除型通過評價頂點或三角形的重要性，如果不重要則直接刪除，并對得到的空洞進行三角化近平面合并型把近似位于同一平面上的相鄰三角形合并邊折疊型搜索平面區(qū)域和特征邊，然后使用邊折疊操作簡化模型代表研究者Hoppe（微軟研究院）9第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法幾何元素刪除型算法9第4章多細4.3

網(wǎng)格簡化算法基于頂點聚類的模型簡化算法賦予各頂點權(quán)值，特征變化較大的點權(quán)值大根據(jù)物體復(fù)雜程度，相對大小等因素，把物體所占空間劃分為多個立方體單元計算出立方體里各頂點的代表點把位于立方體單元內(nèi)的點用代表點代替，把產(chǎn)生的退化多邊形移去10第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法基于頂點聚類的模型簡化算法10第44.3

網(wǎng)格簡化算法基于折疊操作的模型簡化算法基于邊的折疊步驟計算原始模型中每個頂點的誤差矩陣Q選有效的可進行折疊的定點對為每個頂點對（v1，v2）計算最優(yōu)的用于代替V1，v2的新點v0把所有頂點按折疊順序放在堆中（V0T（Q1+Q2），v0為折疊代價），最小代價放在頂部重復(fù)地把頂點對（v1，v2）從堆中輸出，進行折疊，并修改受影響的頂點對的代價11第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法基于折疊操作的模型簡化算法11第44.4多分辨率模型生成算法簡介多分辨率模型是一種支持對同一場景中不同物體或同一物體的不同部分，使用具有不同的細節(jié)的描述方法的數(shù)據(jù)結(jié)構(gòu)控制場景復(fù)雜度、加速圖形繪制、提高交互性的一個非常有效的方法主要方法基于小波的多分辨率分析基于網(wǎng)格簡化或者網(wǎng)格細分的多分辨率模型12第4章多細節(jié)層次模型生成和繪制4.4多分辨率模型生成算法簡介12第4章多細節(jié)層4.4多分辨率模型生成算法MRM模型適用于任意網(wǎng)格簡化或精化操作具有高效的數(shù)據(jù)結(jié)構(gòu)，能快速遍歷所有數(shù)據(jù)不規(guī)則三角形網(wǎng)格，適用多種物體的多分辨率模型13第4章多細節(jié)層次模型生成和繪制4.4多分辨率模型生成算法MRM模型13第4章多4.5

實時連續(xù)LOD模型繪制LOD繪制技術(shù)分成與視點相關(guān)和無關(guān)兩類視點無關(guān)：根據(jù)不同的誤差標準預(yù)先生成不同精度的模型，繪制時根據(jù)視點的位置選擇相應(yīng)的模型繪制視點相關(guān)：根據(jù)視點動態(tài)生成簡化模型比較前者需要較多存儲空間，模型切換時會產(chǎn)生跳變計算量較大，模型能連續(xù)平滑過渡14第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制LOD繪制技術(shù)14第4章4.5

實時連續(xù)LOD模型繪制與視點無關(guān)的LOD預(yù)處理：存儲局部變化的模型，一般采用基于三角形折疊的算法繪制時：依據(jù)視點的距離，選擇局部細節(jié)變化大的模型特點：繪制速度快，但需要較多的存儲空間15第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制與視點無關(guān)的LOD15第4.5

實時連續(xù)LOD模型繪制與視點相關(guān)的LOD預(yù)處理：計算出每個頂點的誤差值（幾何誤差和屏幕誤差的綜合），根據(jù)視點、視見體等生成簡化模型輔助加速繪制視見體裁剪背面剔除幀間連貫性特點：不需要額外的外存，但計算細節(jié)的時間耗費較多16第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制與視點相關(guān)的LOD16第4.6地形實時繪制背景GIS地理信息系統(tǒng)、虛擬現(xiàn)實和軍事仿真等領(lǐng)域地形數(shù)據(jù)寵大，實時繪制和內(nèi)存管理能力有限1990s后期地形多分辨率繪制技術(shù)研究大量盛行，出現(xiàn)至少十種以上的典型算法多分辨率技術(shù)主要包括LOD數(shù)據(jù)組織方式、誤差計算、性能優(yōu)化1997年后基于規(guī)則三角形網(wǎng)成為主流的多分辨率建模繪制技術(shù)17第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制背景17第4章多細節(jié)層次模型生4.6地形實時繪制地形的表示不規(guī)則網(wǎng)格方法TIN(TriangulatedIrregularNetwork)多邊形少，地形表示精度低；數(shù)據(jù)結(jié)構(gòu)復(fù)雜；檢索面速度慢，不易于地形的碰撞檢測和變形處理。規(guī)則網(wǎng)格方法(UniformGridMethod)多邊形冗余大，易實時構(gòu)造多細節(jié)模型LOD；視點附近區(qū)域精度高。18第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制地形的表示18第4章多細節(jié)層4.6地形實時繪制規(guī)則網(wǎng)格方法LOD細節(jié)層次模型模型的動態(tài)抽取誤差評定方案19第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制規(guī)則網(wǎng)格方法19第4章多細節(jié)層4.6地形實時繪制LOD細節(jié)層次模型四叉樹二叉樹20第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制LOD細節(jié)層次模型20第4章4.6地形實時繪制LOD細節(jié)層次模型（續(xù)）問題：裂縫和T形交叉點四叉樹21第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制LOD細節(jié)層次模型（續(xù)）21第4章4.6地形實時繪制二叉樹模型ROAM算法最早提出二叉樹結(jié)構(gòu)和自頂向下構(gòu)建三角網(wǎng)格，幀間連貫性處理性能突出等腰直角三角形引入斜邊的中點后一分為二，遞歸分解后形成三角形二叉樹。子三角形替代父三角形時實現(xiàn)細化，反之實現(xiàn)粗化。22第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型22第4章多細節(jié)層次4.6地形實時繪制二叉樹模型（續(xù)）頂點間的依賴關(guān)系－DAG

父三角形斜邊中點與子三角形直角頂點間的關(guān)系23第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）23第4章多細4.6地形實時繪制二叉樹模型（續(xù)）誤差計算依賴視點位置與地形的崎嶇程度有關(guān)投影方式有關(guān)保證地形不出現(xiàn)裂縫－嵌套誤差判據(jù)球24第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）24第4章多細4.6地形實時繪制二叉樹模型（續(xù)）視錐裁剪技術(shù)包圍球的視錐剔除方法：三角形與視錐外接球距離和半徑關(guān)系判斷三角形外接球：視錐外的快速判斷：25第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）25第4章多細4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—活躍幀（liveframes）依據(jù)前一幀所顯示的三角形而得到當(dāng)前幀應(yīng)顯示的三角形網(wǎng)格，減少計算ROAM算法采用按誤差值大小排序確定合并與分裂的三角形隊列，維護隊列增加了時間開銷，在一定程度上影響了繪制效率活躍幀：視點在當(dāng)前位置時，三角形狀態(tài)將不發(fā)生變化的幀數(shù)影響因素：視點位置和方向（是否在視錐內(nèi)）26第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）26第4章多細4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—活躍幀計算視點：視錐：活躍幀：27第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）視點：27第4章4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—隊列 分裂隊列Qs合并隊列Qm直繪隊列QrN是延遲處理次數(shù)的閾值：大小影響Qr中個數(shù)，影響

LOD生成時間與地形起伏程度有關(guān)

28第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）28第4章多細4.6地形實時繪制動態(tài)地形局部區(qū)域高度數(shù)據(jù)發(fā)生變化誤差重新計算（靜態(tài)地形在預(yù)處理階段生成）數(shù)據(jù)精度提高擴展精度方法（全局和局部）局部擴展時需要考慮不同精度數(shù)據(jù)的混合繪制變化區(qū)域內(nèi)的頂點誤差判據(jù)球半徑小區(qū)域被破壞形變區(qū)域精度高原始區(qū)域精度低29第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形形變區(qū)域精度高原始區(qū)域精度4.6地形實時繪制動態(tài)地形（續(xù)）邊界點性質(zhì)左邊界上引入頂點后，地形網(wǎng)格模型的右半塊中不會引入頂點30第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）30第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）局部擴展定理設(shè)單元格C的精度被擴大為原來的2k倍，為了保證不出現(xiàn)裂縫，不論k為多大的正整數(shù)，只需要擴大過渡區(qū)內(nèi)單元格的分辨率。擴展后過渡區(qū)31第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）擴展后過渡區(qū)31第44.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—問題利用視點和嵌套誤差判據(jù)球生成地形三角網(wǎng)精度會破壞區(qū)域的完整性陷入地形內(nèi)32第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）陷入地形內(nèi)32第4章4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—解決方法主要方法：（1）最大值法：Iwoa大學(xué)He將區(qū)域內(nèi)所有頂點誤差設(shè)置為最大值區(qū)域內(nèi)部沒有LOD，三角形過多（2）斜邊長度代替空間誤差國防大學(xué)王林旭提出，不能有效保證區(qū)域的完整性33第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）33第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—區(qū)域的三角形劃分

基本劃分：由單元三角形及單元子三角形組成的集合最優(yōu)劃分：三角形合并后數(shù)目最少的劃分特點：基本劃分是區(qū)域內(nèi)部的最精細表示，而最優(yōu)劃分是最粗糙表示

生成最優(yōu)劃分算法：主要是任務(wù)是三角形與區(qū)域相交測試34第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）34第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域的LOD

為了生成區(qū)域的最優(yōu)劃分，也需要強迫較多三角形分裂（雖然比基本劃分減少了三角形數(shù)目）。根據(jù)人的視覺原理，遠離區(qū)域時，區(qū)域就越來越小，邊界也越來越模糊。因此，可以建立區(qū)域邊界的LOD，減少因確定邊界帶來較多的分裂操作考慮的因素：視點距離和視線方向35第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）考慮的因素：視點距離4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域的LOD—實現(xiàn)思路視角閾值化，動態(tài)調(diào)整頂點的誤差數(shù)據(jù)。含義：

當(dāng)視點接近區(qū)域時，Ri

擴大，保證視點在嵌套球內(nèi)；當(dāng)視點遠離區(qū)域時，Ri的擴大程度降低，視點落在嵌套球內(nèi)的可能性就越來越小，從而產(chǎn)生區(qū)域的細節(jié)層次36第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）36第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）實例—車轍和腳印37第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）37第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域保持采用區(qū)域的層次細節(jié)算法，保證了視點在近距離能觀察到區(qū)域完整形狀，而在遠距離處看到區(qū)域輪廓，三角形個數(shù)減少。沒有保持保持LOD38第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）沒有保持保持LOD34.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域保持實例——房屋、樹木近距離中等距離遠距離沒有區(qū)域保持區(qū)域保持房屋和樹木陷入地面內(nèi)39第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）近距離4.6地形實時繪制大規(guī)模地形的實時繪制重點和難點是海量地形數(shù)據(jù)的組織分塊繪制

根據(jù)視點位置，加載局部塊地形數(shù)據(jù)，每塊地形進行單獨繪制地形分塊每塊大小為（2k＋1）×（2k＋1），不足部分按邊界值進行延伸 整幅地形大小不再必須為（2n＋1）×（2n＋1）（n>k）40第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制整幅地形大小不4.6地形實時繪制大規(guī)模地形的實時繪制地形調(diào)度與裁剪按視點位置初步確定需要加載和卸載的子塊按視錐精確計算可見塊繪制每塊單獨繪制數(shù)據(jù)結(jié)構(gòu)只有一個三角形、二叉樹和DAG41第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制41第4章4.6地形實時繪制大規(guī)模地形的實時繪制塊間裂縫（邊界點在相鄰塊上的活躍狀態(tài)不同）子塊間子塊單元格間主要方法不規(guī)則法邊界處用不規(guī)則法生成三角形規(guī)則法根據(jù)公共邊頂點狀態(tài)強制分裂不規(guī)則法破壞了規(guī)則網(wǎng)格特性；規(guī)則法沒考慮邊界頂點狀態(tài)變化后對其它邊界的影響42第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制不規(guī)則法破壞了4.6地形實時繪制大規(guī)模地形的實時繪制無縫連接運算(處理裂縫)兩相鄰塊A和塊B，無縫連接U(A,B)公共邊界上頂點狀態(tài)一致其它邊界受影響，但影響范圍的有限相鄰子塊運算結(jié)果43第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制相鄰子塊4.6地形實時繪制大規(guī)模地形的實時繪制定理對子塊A，B，C，D，排列如下圖，則無縫連接操作∪(A,B,C,D)＝(A∪B＋B∪C+C∪D＋D∪A)n。其中塊的橫縱向點數(shù)N=2n+1k＝1k＝2k＝3……44第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制k＝14.6地形實時繪制大規(guī)模地形的實時繪制窗口掃描定理對空間上相鄰的塊組Aij(i＝0,…,m;j=0,…,n)，用22窗口對塊組按行（列）進行掃描處理，進行一遍處理后，相鄰塊間不存在裂縫。45第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制45第4章4.6地形實時繪制大規(guī)模地形的實時繪制單元格間裂縫處理塊內(nèi)單元格塊間單元格將單元格看作塊，利用窗口掃描定理掃描單元格子塊間的邊界線子塊間的邊界線塊間單元格塊內(nèi)單元格46第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制將單元格看作塊4.6地形實時繪制大規(guī)模地形的實時繪制實驗--驗證算法有效性地形大?。?193×8193子塊大?。?57×257

詳細論述見：《計算機輔助設(shè)計與圖形學(xué)學(xué)報》2006，10“地形分塊繪制中的邊界裂縫處理算法”47第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制地形大?。涸敿?.6地形實時繪制大規(guī)模地形的實時繪制實驗—性能裂縫處理時間增加的三角形數(shù)裂縫處理時間不到1ms，對整體的實時性影響很??；加入活躍點造成的邊界提升的深度很小，裂縫處理后增加的三角形數(shù)目在20～100個左右48第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制裂縫處理時間不4.6地形實時繪制大規(guī)模地形的實時繪制實例49第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制49第4章4.6地形實時繪制發(fā)展動向基于硬件（GPU）的加速技術(shù)Vertex和FragmentShading基于LOD的合成地形環(huán)境建模繪制50第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制發(fā)展動向50第4章多細節(jié)層次模第4章多細節(jié)層次模型和繪制計算機科學(xué)系2009，551第4章多細節(jié)層次模型生成和繪制第4章多細節(jié)層次模型和繪制計算機科學(xué)系1第4章多細主要內(nèi)容4.1 簡介4.2 基本概念4.3網(wǎng)格簡化算法4.4多分辨率模型生成算法4.5實時連續(xù)LOD模型繪制4.6地形實時繪制52第4章多細節(jié)層次模型生成和繪制主要內(nèi)容4.1 簡介2第4章多細節(jié)層次模型生成和繪制4.1

簡介細節(jié)層次LOD（LevelofDetail）1976年Clark提出指對同一場景或場景中的物體，使用具有不同細節(jié)的描述方法得到一組模型，供繪制時選擇使用目的是減少模型的多邊形個數(shù)，提高繪制速度廣泛應(yīng)用于復(fù)雜場景快速繪制、飛行模擬器、3D動畫、虛擬現(xiàn)實等系統(tǒng)53第4章多細節(jié)層次模型生成和繪制4.1簡介細節(jié)層次LOD（LevelofDetail4.1

簡介LOD方法的基本思想不同的物體或物體的不同部分采用不同的細節(jié)繪制時，如果物體離視點比較遠，或者物體比較小，可以用較粗的LOD模型繪制，反之用較細的模型繪制同樣，對運動快的物體用較粗的LOD模型繪制，反之用較細的模型繪制54第4章多細節(jié)層次模型生成和繪制4.1簡介LOD方法的基本思想4第4章多細節(jié)層次模型4.2

基本概念誤差度量如何生成不同細節(jié)的模型局部誤差距離誤差計算曲率誤差計算55第4章多細節(jié)層次模型生成和繪制4.2基本概念誤差度量5第4章多細節(jié)層次模型生成和繪4.2

基本概念全局誤差計算法具有較好的近似效果，但計算量大一般用法簡化過程中，刪除的頂點具有盡量小的全局誤差精化過程中，增加的頂點具有盡量大的全局誤差56第4章多細節(jié)層次模型生成和繪制4.2基本概念全局誤差6第4章多細節(jié)層次模型生成和繪4.2

基本概念簡化操作指在網(wǎng)格模型簡化過程中使用到的基本操作包括頂點刪除：把三角形中不重要的頂點刪去三角形刪除：若三角形的面積小于某個值，移去頂點刪除三角形刪除57第4章多細節(jié)層次模型生成和繪制4.2基本概念簡化操作頂點刪除三角形刪除7第4章多細4.2

基本概念簡化操作包括（續(xù)）邊折疊：把邊折疊成一個新點，并把與邊相連的點連到新點三角形折疊：把三角形折疊成一個新點，并把與三角形相連的點連到新點邊折疊三角形折疊58第4章多細節(jié)層次模型生成和繪制4.2基本概念簡化操作邊折疊三角形折疊8第4章多細節(jié)4.3

網(wǎng)格簡化算法幾何元素刪除型算法幾何元素直接刪除型通過評價頂點或三角形的重要性，如果不重要則直接刪除，并對得到的空洞進行三角化近平面合并型把近似位于同一平面上的相鄰三角形合并邊折疊型搜索平面區(qū)域和特征邊，然后使用邊折疊操作簡化模型代表研究者Hoppe（微軟研究院）59第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法幾何元素刪除型算法9第4章多細4.3

網(wǎng)格簡化算法基于頂點聚類的模型簡化算法賦予各頂點權(quán)值，特征變化較大的點權(quán)值大根據(jù)物體復(fù)雜程度，相對大小等因素，把物體所占空間劃分為多個立方體單元計算出立方體里各頂點的代表點把位于立方體單元內(nèi)的點用代表點代替，把產(chǎn)生的退化多邊形移去60第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法基于頂點聚類的模型簡化算法10第44.3

網(wǎng)格簡化算法基于折疊操作的模型簡化算法基于邊的折疊步驟計算原始模型中每個頂點的誤差矩陣Q選有效的可進行折疊的定點對為每個頂點對（v1，v2）計算最優(yōu)的用于代替V1，v2的新點v0把所有頂點按折疊順序放在堆中（V0T（Q1+Q2），v0為折疊代價），最小代價放在頂部重復(fù)地把頂點對（v1，v2）從堆中輸出，進行折疊，并修改受影響的頂點對的代價61第4章多細節(jié)層次模型生成和繪制4.3網(wǎng)格簡化算法基于折疊操作的模型簡化算法11第44.4多分辨率模型生成算法簡介多分辨率模型是一種支持對同一場景中不同物體或同一物體的不同部分，使用具有不同的細節(jié)的描述方法的數(shù)據(jù)結(jié)構(gòu)控制場景復(fù)雜度、加速圖形繪制、提高交互性的一個非常有效的方法主要方法基于小波的多分辨率分析基于網(wǎng)格簡化或者網(wǎng)格細分的多分辨率模型62第4章多細節(jié)層次模型生成和繪制4.4多分辨率模型生成算法簡介12第4章多細節(jié)層4.4多分辨率模型生成算法MRM模型適用于任意網(wǎng)格簡化或精化操作具有高效的數(shù)據(jù)結(jié)構(gòu)，能快速遍歷所有數(shù)據(jù)不規(guī)則三角形網(wǎng)格，適用多種物體的多分辨率模型63第4章多細節(jié)層次模型生成和繪制4.4多分辨率模型生成算法MRM模型13第4章多4.5

實時連續(xù)LOD模型繪制LOD繪制技術(shù)分成與視點相關(guān)和無關(guān)兩類視點無關(guān)：根據(jù)不同的誤差標準預(yù)先生成不同精度的模型，繪制時根據(jù)視點的位置選擇相應(yīng)的模型繪制視點相關(guān)：根據(jù)視點動態(tài)生成簡化模型比較前者需要較多存儲空間，模型切換時會產(chǎn)生跳變計算量較大，模型能連續(xù)平滑過渡64第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制LOD繪制技術(shù)14第4章4.5

實時連續(xù)LOD模型繪制與視點無關(guān)的LOD預(yù)處理：存儲局部變化的模型，一般采用基于三角形折疊的算法繪制時：依據(jù)視點的距離，選擇局部細節(jié)變化大的模型特點：繪制速度快，但需要較多的存儲空間65第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制與視點無關(guān)的LOD15第4.5

實時連續(xù)LOD模型繪制與視點相關(guān)的LOD預(yù)處理：計算出每個頂點的誤差值（幾何誤差和屏幕誤差的綜合），根據(jù)視點、視見體等生成簡化模型輔助加速繪制視見體裁剪背面剔除幀間連貫性特點：不需要額外的外存，但計算細節(jié)的時間耗費較多66第4章多細節(jié)層次模型生成和繪制4.5實時連續(xù)LOD模型繪制與視點相關(guān)的LOD16第4.6地形實時繪制背景GIS地理信息系統(tǒng)、虛擬現(xiàn)實和軍事仿真等領(lǐng)域地形數(shù)據(jù)寵大，實時繪制和內(nèi)存管理能力有限1990s后期地形多分辨率繪制技術(shù)研究大量盛行，出現(xiàn)至少十種以上的典型算法多分辨率技術(shù)主要包括LOD數(shù)據(jù)組織方式、誤差計算、性能優(yōu)化1997年后基于規(guī)則三角形網(wǎng)成為主流的多分辨率建模繪制技術(shù)67第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制背景17第4章多細節(jié)層次模型生4.6地形實時繪制地形的表示不規(guī)則網(wǎng)格方法TIN(TriangulatedIrregularNetwork)多邊形少，地形表示精度低；數(shù)據(jù)結(jié)構(gòu)復(fù)雜；檢索面速度慢，不易于地形的碰撞檢測和變形處理。規(guī)則網(wǎng)格方法(UniformGridMethod)多邊形冗余大，易實時構(gòu)造多細節(jié)模型LOD；視點附近區(qū)域精度高。68第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制地形的表示18第4章多細節(jié)層4.6地形實時繪制規(guī)則網(wǎng)格方法LOD細節(jié)層次模型模型的動態(tài)抽取誤差評定方案69第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制規(guī)則網(wǎng)格方法19第4章多細節(jié)層4.6地形實時繪制LOD細節(jié)層次模型四叉樹二叉樹70第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制LOD細節(jié)層次模型20第4章4.6地形實時繪制LOD細節(jié)層次模型（續(xù)）問題：裂縫和T形交叉點四叉樹71第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制LOD細節(jié)層次模型（續(xù)）21第4章4.6地形實時繪制二叉樹模型ROAM算法最早提出二叉樹結(jié)構(gòu)和自頂向下構(gòu)建三角網(wǎng)格，幀間連貫性處理性能突出等腰直角三角形引入斜邊的中點后一分為二，遞歸分解后形成三角形二叉樹。子三角形替代父三角形時實現(xiàn)細化，反之實現(xiàn)粗化。72第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型22第4章多細節(jié)層次4.6地形實時繪制二叉樹模型（續(xù)）頂點間的依賴關(guān)系－DAG

父三角形斜邊中點與子三角形直角頂點間的關(guān)系73第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）23第4章多細4.6地形實時繪制二叉樹模型（續(xù)）誤差計算依賴視點位置與地形的崎嶇程度有關(guān)投影方式有關(guān)保證地形不出現(xiàn)裂縫－嵌套誤差判據(jù)球74第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）24第4章多細4.6地形實時繪制二叉樹模型（續(xù)）視錐裁剪技術(shù)包圍球的視錐剔除方法：三角形與視錐外接球距離和半徑關(guān)系判斷三角形外接球：視錐外的快速判斷：75第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）25第4章多細4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—活躍幀（liveframes）依據(jù)前一幀所顯示的三角形而得到當(dāng)前幀應(yīng)顯示的三角形網(wǎng)格，減少計算ROAM算法采用按誤差值大小排序確定合并與分裂的三角形隊列，維護隊列增加了時間開銷，在一定程度上影響了繪制效率活躍幀：視點在當(dāng)前位置時，三角形狀態(tài)將不發(fā)生變化的幀數(shù)影響因素：視點位置和方向（是否在視錐內(nèi)）76第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）26第4章多細4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—活躍幀計算視點：視錐：活躍幀：77第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）視點：27第4章4.6地形實時繪制二叉樹模型（續(xù)）幀間連貫性—隊列 分裂隊列Qs合并隊列Qm直繪隊列QrN是延遲處理次數(shù)的閾值：大小影響Qr中個數(shù)，影響

LOD生成時間與地形起伏程度有關(guān)

78第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制二叉樹模型（續(xù)）28第4章多細4.6地形實時繪制動態(tài)地形局部區(qū)域高度數(shù)據(jù)發(fā)生變化誤差重新計算（靜態(tài)地形在預(yù)處理階段生成）數(shù)據(jù)精度提高擴展精度方法（全局和局部）局部擴展時需要考慮不同精度數(shù)據(jù)的混合繪制變化區(qū)域內(nèi)的頂點誤差判據(jù)球半徑小區(qū)域被破壞形變區(qū)域精度高原始區(qū)域精度低79第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形形變區(qū)域精度高原始區(qū)域精度4.6地形實時繪制動態(tài)地形（續(xù)）邊界點性質(zhì)左邊界上引入頂點后，地形網(wǎng)格模型的右半塊中不會引入頂點80第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）30第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）局部擴展定理設(shè)單元格C的精度被擴大為原來的2k倍，為了保證不出現(xiàn)裂縫，不論k為多大的正整數(shù)，只需要擴大過渡區(qū)內(nèi)單元格的分辨率。擴展后過渡區(qū)81第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）擴展后過渡區(qū)31第44.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—問題利用視點和嵌套誤差判據(jù)球生成地形三角網(wǎng)精度會破壞區(qū)域的完整性陷入地形內(nèi)82第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）陷入地形內(nèi)32第4章4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—解決方法主要方法：（1）最大值法：Iwoa大學(xué)He將區(qū)域內(nèi)所有頂點誤差設(shè)置為最大值區(qū)域內(nèi)部沒有LOD，三角形過多（2）斜邊長度代替空間誤差國防大學(xué)王林旭提出，不能有效保證區(qū)域的完整性83第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）33第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域完整性—區(qū)域的三角形劃分

基本劃分：由單元三角形及單元子三角形組成的集合最優(yōu)劃分：三角形合并后數(shù)目最少的劃分特點：基本劃分是區(qū)域內(nèi)部的最精細表示，而最優(yōu)劃分是最粗糙表示

生成最優(yōu)劃分算法：主要是任務(wù)是三角形與區(qū)域相交測試84第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）34第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域的LOD

為了生成區(qū)域的最優(yōu)劃分，也需要強迫較多三角形分裂（雖然比基本劃分減少了三角形數(shù)目）。根據(jù)人的視覺原理，遠離區(qū)域時，區(qū)域就越來越小，邊界也越來越模糊。因此，可以建立區(qū)域邊界的LOD，減少因確定邊界帶來較多的分裂操作考慮的因素：視點距離和視線方向85第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）考慮的因素：視點距離4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域的LOD—實現(xiàn)思路視角閾值化，動態(tài)調(diào)整頂點的誤差數(shù)據(jù)。含義：

當(dāng)視點接近區(qū)域時，Ri

擴大，保證視點在嵌套球內(nèi)；當(dāng)視點遠離區(qū)域時，Ri的擴大程度降低，視點落在嵌套球內(nèi)的可能性就越來越小，從而產(chǎn)生區(qū)域的細節(jié)層次86第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）36第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）實例—車轍和腳印87第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）37第4章多細節(jié)4.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域保持采用區(qū)域的層次細節(jié)算法，保證了視點在近距離能觀察到區(qū)域完整形狀，而在遠距離處看到區(qū)域輪廓，三角形個數(shù)減少。沒有保持保持LOD88第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）沒有保持保持LOD34.6地形實時繪制動態(tài)地形（續(xù)）區(qū)域保持實例——房屋、樹木近距離中等距離遠距離沒有區(qū)域保持區(qū)域保持房屋和樹木陷入地面內(nèi)89第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制動態(tài)地形（續(xù)）近距離4.6地形實時繪制大規(guī)模地形的實時繪制重點和難點是海量地形數(shù)據(jù)的組織分塊繪制

根據(jù)視點位置，加載局部塊地形數(shù)據(jù)，每塊地形進行單獨繪制地形分塊每塊大小為（2k＋1）×（2k＋1），不足部分按邊界值進行延伸 整幅地形大小不再必須為（2n＋1）×（2n＋1）（n>k）90第4章多細節(jié)層次模型生成和繪制4.6地形實時繪制大規(guī)模地形的實時繪制整幅地形大小不4.6地形實時繪制大規(guī)模地形的實時繪制地形調(diào)