1、離散數字幾何處置彭 群 生胡 國 飛浙江大學CAD&CG國家重點實驗室 2003年09月24日 長沙.內容提要一、離散數字幾何處置簡介二、三角網格的參數化 意義和目的 前人任務和我們的最新研討成果 參數化的例子及其運用三、三角網格的光順 意義和目的 前人任務和我們的最新研討成果 參數化的例子四、結論和未來的任務.一、數字幾何處置簡介幾何表示參數曲面隱式曲面體數據多邊形網格點數據網格變成主流的幾何表達方式.一、數字幾何處置簡介PositionNormalColorTextureBRDF 幾何信息: N維.三維數字幾何處置過程獲取處置存儲和傳輸運用(仿真,文娛)參數化光順/去噪簡化/緊縮多分辨率編

2、輯.三角網格參數化貓頭 (個頂點,257個三角形 )平面參數化球面參數化.網格光順和去噪3D網格模型的光順可視化劉新國2002. 兔子基網格(162 三角形) 原始網格和LOD表示三角網格的簡化.多分辨率編輯三角網格的編輯周昆2002.紋理映射球面凸組合參數化算法的紋理映射效果胡國飛2003.重網格化parameterizationresamplingABF參數化方法的Remeshing效果(Sheffer2000).重網格化parameterizationresamplingremeshingMIPS參數化方法的Remeshing效果Hormann1999.曲面擬合parameterizat

3、ionB-Spline Surface平面凸組合參數化方法曲面擬合效果(Floater1998).幾何外形過渡累進球面參數化方法的Morphing效果Praun2003. 問題的描畫 研討內容 前人任務 我們的最新研討成果 參數化的例子及其運用二、三角網格參數化.問題的描畫給定一個由空間點集組成的三角化網格和一個參數域，尋求一個參數域上的點到三角網格點的一一對應映射，并且在參數化域上堅持原始網格的拓撲信息。.意義曲面擬合: 經過參數化，把離散的3D數據點用一個光順的參數曲面來擬合。紋理映射: 利用外表網格參數化信息，把一幅紋理圖像映射到三維網格上，使得外表網格看上去更加生動逼真。重網格化: 利

4、用參數化把三角化曲面轉化成具有細分連通性的規那么網格，并且在此根底上進一步作多分辨率分析。幾何外形過渡: 經過參數化到一樣的參數域進展點對應，使得兩個不同物體之間的平滑過渡。.研討內容 1 保證參數化的有效性 三維網格 二維參數化結果.研討內容 2 尋求某種幾何度量的變形最小化不同的參數化方法下的紋理映射,具有不同的變形.研討內容保面積? 保角? 等距? 2 尋求某種幾何度量的變形最小化.研討內容 3 具有線性時間空間復雜度的算法全局參數化方法：求解整體約束非線性系統部分參數化方法：求解部分線性系統.前人任務基于松弛參數化方法： Graph Embedding(Tutte60) 平面凸組合(F

5、loater97) 球面松弛參數化(Alexa00) 球面凸組合(胡國飛和彭群生03)基于調和映射的方法 調和映射(Pinkall 93,Eck95) 累進球面參數化(周昆02,Praun03)分割展平法 整體Angle-Based-Flattening(Sheffer00) 部分Bounded-Distortion-Piecewise(Sorkine02).累進球面參數化 (周昆2002)根本思緒1 生成帶有部分參數化信息的累進網格表示。循環地執行邊收縮操作，直到當前簡化網格變成一個凸多面體基網格。對每次邊收縮操作，收縮邊的兩個頂點按簡化后生成的簡化網格外表作部分參數化。2 由于基網格是凸多

6、面體，從基網格的中心投影可以得到相應的球面網格。對每次頂點分裂操作，運用部分參數化信息把兩個分裂出來的頂點映射在單位球面上。3 一切的頂點分裂操作執行終了，球面參數化生成。.累進球面參數化流程edge collapsesMiSpn, , SpiM=MnM 0vertex splitsM nvertex splitsM jvertex splitsM iedge collapsesMjSpi+1, , Spjedge collapsesM0Spj-1, , Sp1.累進球面參數化實例.凸組合球面參數化 (胡國飛2003)根本思緒 1 球面投影：初始化 2 凸組合：松弛迭代求解球面新點 3 虛擬邊

7、境技術：改善邊境變形特征 1 參數化解存在且獨一，數值解收斂于真實解 2 權值可控，部分保形.凸組合參數化實例3D網格模型的球面參數化.三、網格光順和去噪 問題的描畫 研討內容 前人任務 我們的最新研討成果 參數化的例子及其運用.問題的描畫在數據獲取過程中，人為的擾動或者掃描儀本身的缺陷使得生成三維數據帶有噪聲(noise)。去噪是消除三維數據外表的部分幾何突變，并在部分范圍內堅持外形變化的銜接性。光順是在剔除噪聲獲取離散曲面更高階光滑性的同時，堅持網格模型的拓撲信息和幾何特征不變性。.問題的描畫重心約束的光順算法劉新國2001.目的1 體積堅持(volume-preserving)Lapla

8、ce光順算子使得體積收縮.目的2 特征堅持(feature-preserving)牙齒，脊背等特征在光順后得到堅持(胡國飛2003).目的3 線性時間和空間復雜度 求解非線性系統 求解線性系統(多次) 求解線性系統(單步).前人的任務1 能量最小化方法(求解非線性系統) 薄膜能量(Morton92)： 薄板能量(Welch92)： 重心約束的磨光算法(劉新國02)優點: 基于能量方程去除外表噪聲，經過引入約束條件，可有效控制體積收縮和模型變形。缺陷: 非線性系統，運算時間長.前人的任務2 基于Laplace的光順算子(求解線性系統) 優點: 線性系統，算法簡單，運算速度快 缺陷: 需求多次迭代

9、才干到達光順效果，容易導致過光順，體積收縮的情況 改良算法： |方法(Taubin95) HC算法(Vollmer99) .HC算法.前人的任務3 魯棒的頂點預測方法網格的雙邊濾波器(Freishman03, Jones03) 圖像的雙邊濾波器是把象素到鄰域點的間隔以及該象素的亮度值與鄰域點的亮度值之差作為兩個參數。 Freishman網格雙邊濾波把點與周圍鄰域點的間隔以及該間隔向量與該點的法向的內積作為雙邊濾波器兩個參數。 Jones把點與周圍鄰域三角形重心的間隔以及與該點到周圍鄰域三角形的間隔作為雙邊濾波器的兩個參數。 優點: 無需迭代,算法簡單,運算速度快. 缺陷: 鄰域難確定，鄰域過小

10、，容易導致過光順和特征加強等。鄰域過大導致運算時間增大。.重心約束的磨光算法(劉新國02)網格曲面能量離散曲面的磨光能量最小化 .重心約束.能量最小化.部分迭代求解.結果.結果.三步頂點預測濾波器(胡國飛03)算法特征： 1 三步預測：利用兩次雙邊濾波器SOT和FOV和一次 準Laplacian 濾波來三步預測頂點。 2 限于部分鄰域：根據頂點的二階鄰域三角形，一階鄰域頂點以及頂點本身預測新點。 3 區分特征和噪聲：有效排除了二階鄰域以外噪聲對它的干擾，經過頂點部分鄰域的幾何信息來預測頂點的方法既能有效地剔除噪聲又能堅持網格的凹凸特征。.鄰域SOT: 二階鄰域三角形 FOV: 一階鄰域頂點.特

11、征和噪聲噪聲: 孤立的頂點擾動是噪聲，由于它只牽涉到一階鄰域三角形的部分幾何變形，我們予以剔除。特征: 頂點及其一階鄰域頂點沿同一方向上的動搖，且與其二階鄰域三角形的外形變化趨勢一致，我們以為它是一種三角網格的部分特征，給予堅持甚至加強。.SOT光順將頂點投影到其二階鄰域三角形所在平面上，再把所得投影點的加權平均作為該頂點的估計，對于變化平滑的特征，將產生過估計，對于突變的噪聲，會導致欠估計。最后使得凹凸特征被放大，而噪聲被減弱。.SOT光順利用點和二階鄰域三角形的幾何關系，進展雙邊濾波.準Laplacian光順噪聲點對于原始網格數據來講畢竟只占小部分，為了減小第一步處置對大部分正常頂點位置的

12、估計誤差，我們取原頂點和第一次預測位置的加權平均作第二次估計，稱之為準Laplacian光順：.基于FOV預測頂點沿頂點的法線方向，以平均曲率為權值，挪動各頂點，使得模型外表趨于最小曲面。FOV預測將使得噪聲點快速調整到符合部分鄰域變化趨勢的曲面上。.基于FOV預測頂點.優點: 經過魯棒的頂點預測進展光順，無需迭代； 防止過光順和特征加強等； 算法簡單，運算速度快. (a)原始網格 (b)噪聲網格 (c)一次光順 (d)二次光順三步頂點預測濾波器光順效果結果.結果三步頂點預測算法：恐龍的光順結果.結果 三步頂點預測算法：小噪聲和大噪聲的剔除效果Laplace20 Taubin20 Freishman Jones Our Method.結果 三步預測非迭代算法噪聲網格 80次Laplace 40次Taubin 三步預測.數據對比.今后的任務1 拓展到點模型和體數據模型。2 自順應特征識別，使得光順模型具有特征