離散網(wǎng)格上曲率計算的_2016

1、可視化技術(shù)課程報告 離散網(wǎng)格上的曲率計算 姓 名 王 娜 學(xué) 號 201531491 院 系 信息科學(xué)與技術(shù)學(xué)院 專 業(yè) 軟件工程 年 級 2015級 離散網(wǎng)格上的曲率計算摘要：離散曲面形狀分析主要研究對各種離散形式曲面的進(jìn)行曲率估算，設(shè)計更準(zhǔn)確更有效率的曲率估算方法。本文主要綜述了離散網(wǎng)格上曲率的多種估算方法，展望了這些問題的發(fā)展趨勢。關(guān)鍵字：離散曲面；網(wǎng)格曲面；曲率 1.離散曲面發(fā)展背景隨著三維數(shù)據(jù)采樣技術(shù)和硬件設(shè)備的不斷改善，以及圖形工業(yè)對任意拓?fù)浣Y(jié)構(gòu)的光滑曲面造型的迫切需求，（這里的“任意拓?fù)洹本哂袃蓚€方面的含義：一是網(wǎng)格的虧格和相應(yīng)曲面的拓?fù)浣Y(jié)構(gòu)的任意的；二是由網(wǎng)格的頂點(diǎn)和邊法的特點(diǎn)

2、所構(gòu)成的圖形是任意的。）使得離散曲面日益成為計算機(jī)圖形學(xué)和幾何設(shè)計鄰域的寵兒。因此對離散曲面的估算微分量的研究逐漸成為一個新型課題。 將離散曲面估算得到的高斯曲率應(yīng)用于離散曲面形狀分析工具的設(shè)計，更加有效的提取其形狀和特征區(qū)域，利于特征區(qū)域邊界計算，區(qū)域分割。近年來，更是將離散曲面分析應(yīng)用到實(shí)際生活，在醫(yī)學(xué)領(lǐng)域，通過對大腦皮層的掃描，建立數(shù)字化模型，分析曲面形狀，來獲取大腦發(fā)育信息，甚至病變區(qū)域位等。成為病變檢測和獲取腦部發(fā)育信息的有力途徑。2.網(wǎng)格曲面上離散曲率的計算 三角網(wǎng)格模型在計算機(jī)圖形學(xué)、計算機(jī)輔助幾何設(shè)計中的使用日益廣泛，但是在三角網(wǎng)格上任意點(diǎn)處得到精確的法向量和曲率十分困難，主要

3、原因是離散三角網(wǎng)格曲面并不是用傳統(tǒng)微分幾何中熟知的參數(shù)方程和隱式方程來定義，而是由離散點(diǎn)云以及點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系定義的，這樣，傳統(tǒng)微分幾何中一階微分和二階微分的計算不能簡單地應(yīng)用于離散三角網(wǎng)格曲面上。 一般來說，曲面的一階微分量是指曲面的切平面方向和法向量，二階微分量是指曲面的曲率等有關(guān)量。隨著三維掃描技術(shù)的發(fā)展和逆向工程的興起，三角網(wǎng)格曲面日益成為三維圖形的一種通用表示方法，在計算機(jī)圖形學(xué)，計算機(jī)輔助幾何設(shè)計中的使用日益廣泛。但是由于三角網(wǎng)格曲面是由離散點(diǎn)云以及點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系定義的，缺少曲面確切的解析表示，所以不再適用傳統(tǒng)的解析曲面的曲率計算方法。 眾所周知，曲率是曲面曲線的重要不變

4、量，是傳統(tǒng)微分幾何中的重要基礎(chǔ)。同樣，三角網(wǎng)格的離散曲率也是離散曲面上應(yīng)用的基礎(chǔ)和前提。例如網(wǎng)格變形1，網(wǎng)格曲面的特征提取，網(wǎng)格光順2，網(wǎng)格簡化3，模型分塊4等等。在這些應(yīng)用中，通常需要首先估計離散曲面上某點(diǎn)的法向量和曲率，然后根據(jù)這些法向量或曲率定義一個范數(shù)，作為一個優(yōu)化的標(biāo)準(zhǔn)，利用這個關(guān)于曲率泛函的優(yōu)化標(biāo)準(zhǔn)再進(jìn)行離散網(wǎng)格曲面的進(jìn)一步處理。例如，在網(wǎng)格簡化應(yīng)用中，曲率的估計對確保優(yōu)化三角剖分起著至關(guān)重要的作用。在曲面建模中，許多技術(shù)是用來由原始粗糙網(wǎng)格來創(chuàng)建光滑曲面的，離散曲率是當(dāng)前近似情形的重要度量。精確的曲率和法向量也是網(wǎng)格去噪問題的基礎(chǔ)。好的平均曲率和法向量估計是無扭曲曲面光順技術(shù)的關(guān)

5、鍵。在計算機(jī)圖形學(xué)、圖像分析處理和幾何建模等研究領(lǐng)域中，如自由曲面、反求工程、圖像識別、三維醫(yī)療圖像重構(gòu)以及人臉識別等，經(jīng)常需要計算主曲率、平均曲率和高斯曲率等值，用于折痕、棱邊、隆起、溝壑等關(guān)鍵特征的提取、噪聲的過濾和曲面的修補(bǔ)等。這樣，三角網(wǎng)格曲面上離散曲率的各種估計方法應(yīng)運(yùn)而生。對于給定的描述一些光滑曲面的三角網(wǎng)格，有許多估算頂點(diǎn)法向量和曲率的方法"曲率估計算法多種多樣，例如，利用歐拉公式，采用最小二乘的估算方法(Chen and schmitt,1992)5;曲率張量的估計方法(Taubin,1995)6；法曲率積分公式的方法(Wa1Lanabe and Belyaev,20

6、01)7；曲率算子的方法(Meyer,2002)8估計頂點(diǎn)的法曲率，權(quán)值的選取在不斷革新，從最初Henri Gouraud(1971)的等加權(quán)平均，到角度權(quán)值以及面積權(quán)值，而后Max(l999)給出的與角度和邊長度相關(guān)的新權(quán)值，Sheng一GwoChen(2004)等又提出選擇點(diǎn)到相鄰三角形重心距離平方的倒數(shù)為權(quán)值。除此之外，還有比較不同算法估算精度的文章，Tatiana(2003)對三角網(wǎng)格上高斯曲率和平均曲率不同的估計方法作比較，ShuangthuangJin(2003)等對三角網(wǎng)格上點(diǎn)法向量的不同估計方法的比較。還有一些網(wǎng)格應(yīng)用的文章，Dyn和Hormann不但給出新的高斯曲率和平均曲率

7、估算定義，還應(yīng)用估算的曲率定義范數(shù)，進(jìn)行網(wǎng)格簡化。本文主要綜述了較為基礎(chǔ)的Chen 和Schmitt的方法，以及介紹了羅良峰和齊寶明針對該問題提出的基于Taubin方法的改進(jìn)，進(jìn)行離散三角網(wǎng)格的曲率計算。2.1 Chen 和 Schmitt 方法三角網(wǎng)格模型一般情況下可以由一對線性表表示，M=(V,F);其中，表示頂點(diǎn)集，表示三角片集。如下圖三角網(wǎng)格模型：三角片fk的法向量氣的計算式如下其中，表示由頂點(diǎn)指向頂點(diǎn)的邊向量；表示由頂點(diǎn)指向的邊向量。我們稱1-環(huán)鄰域是與點(diǎn)相鄰的三角形集合。圖中除頂點(diǎn)外的其它頂點(diǎn)組成的集合記為。如果頂點(diǎn)屬于，則是的相鄰點(diǎn)。中頂點(diǎn)個數(shù)稱為其頂點(diǎn)的度，記為。包含的三角形片

8、集合記為。如果三角形片記屬于，記為，記為三角形片的面積。包含點(diǎn)的三角片的面積之和記為。離散三角網(wǎng)格上法向量和法曲率也有一般的定義方法，這些幾何估算的準(zhǔn)確度對高斯曲率和平均曲率的準(zhǔn)確度影響很大。對于離散三角網(wǎng)格曲面M=(V,F)，任意點(diǎn)的法向量一般可定義為1-環(huán)三角形某些幾何的加權(quán)和。最簡單的加權(quán)方法1-環(huán)三角形的法向量平均值，定義如下： Taubin給出面積加權(quán)和的定義： 對于三角網(wǎng)格上任意點(diǎn)，法曲率通常使用公式 得到兩個主曲率（k1，k2）后，進(jìn)而計算平均曲率（H=（k1+k2）/2）和高斯曲率(K=k1*k2)。Chen 和 Schmitt 通過歐拉公式，給出了一種估計算法。他們的主要思想

9、是在切平面上選擇合適的坐標(biāo)。由歐拉公式可得 是選擇的坐標(biāo)系與主方向的夾角，上式可重寫為： C1，C2，C3是常數(shù)，是切向量與第一坐標(biāo)向量r1的夾角。然后，他們選擇，通過最小二乘的方法估計常數(shù)C1，C2，C3，其中，是與的夾角。曲率k1，k2可以由常數(shù)C1，C2，C3， 和以下關(guān)系求得 主方向可以由下列公式計算獲得 其中，r1，r2是選擇的坐標(biāo)系。仿真實(shí)現(xiàn)了三角網(wǎng)格上的曲率計算，便于實(shí)驗(yàn)的效果觀察，比較了三角網(wǎng)格上和矩形網(wǎng)格上的最大主曲率計算結(jié)果，如下圖顯示：三角網(wǎng)格與矩形網(wǎng)格上的曲率計算2.2改進(jìn)的Taubin方法羅良峰應(yīng)用重心加權(quán)和新的法曲率估計方法改進(jìn)原始的Taubin方法，使用重心權(quán)重相

10、比于使用面積加權(quán)的方式而言，更加充分的考慮到了三角網(wǎng)格形狀多實(shí)驗(yàn)結(jié)果的影響。但是估算法向量和法曲率這兩個幾何量，仍然是改進(jìn)后的Taubin方法對于三角網(wǎng)格中任意一點(diǎn)曲率計算的首要任務(wù)。采用重心加權(quán)和的方法估計法向量，利用任意一點(diǎn)的1-環(huán)三角面片的法向信息來估計曲率，得到局部曲率張量矩陣，此后對該矩陣進(jìn)行Householder變換和Givens變換，計算出對應(yīng)的特征矩陣和特征向量，最后通過主曲率與矩陣特征值的關(guān)系得出兩個主曲率，進(jìn)而得到平均曲率和高斯曲率。將改進(jìn)Taubin方法與原始Taubin方法和Meyer方法作了比較。對于隱式曲面和參數(shù)曲面，給出詳細(xì)的誤差分析；對于自由曲面，根據(jù)曲率確定三

11、角網(wǎng)格頂點(diǎn)顏色，從視覺上分析曲率估算結(jié)果。使用多組測試用例，不論是單位球面的測試用例、環(huán)面的測試用例還是自由三角網(wǎng)格曲面測試用例，測試結(jié)果均表明改進(jìn)的Taubin方法無論是在穩(wěn)定性上，還是在精確度上，較原始Taubin方法都有明顯改善。齊寶明采用面積質(zhì)心夾角的三角網(wǎng)格頂點(diǎn)向量法和三角片質(zhì)心權(quán)值來改進(jìn)Taubin離散曲率方法，同樣忽略了三角面片的形狀。但是如果只使用質(zhì)心或者面積夾角的估計方法，也不能反應(yīng)三角面片形狀的影響。所以作者提出了新的加權(quán)方法，面積質(zhì)心夾角的三角網(wǎng)格頂點(diǎn)向量法。相比較重心加權(quán)和面積夾角加權(quán)，更加明確的反映了三角片形狀的影響。 不論是哪一種離散網(wǎng)格曲率計算方式，都相較于未改進(jìn)

12、之前的方法有很大的提高，通過誤差分析，很明顯，同一物體的測量數(shù)據(jù)重建而得到的兩個三角網(wǎng)格中，頂點(diǎn)密度不同，曲率計算亦不同。頂點(diǎn)密度越大，計算結(jié)果越精密?？梢缘贸銮收`差是和點(diǎn)的密度以及此點(diǎn)的曲面彎曲程度是有密切關(guān)系的。誤差分析，可以直接找出誤差最大點(diǎn)，而不必計算每個點(diǎn)的曲率誤差。對誤差最大點(diǎn)進(jìn)行分析，減小誤差，提高算法精度。3.發(fā)展趨勢未來的工作,除了進(jìn)一步提高計算精度以及算法的穩(wěn)定性和適應(yīng)性外,在該領(lǐng)域里有許多重要方向值得研究探索。如網(wǎng)格光順、網(wǎng)格簡化、網(wǎng)格分割、特征識別等等，這些方向都是以離散網(wǎng)格上曲率估計為基礎(chǔ)而展開的。在不同場合，計算曲率的方法效率會有所不同，并非某一個特定的方法會占有

13、絕對優(yōu)勢，尋找一種更加快速、準(zhǔn)確地對海量數(shù)據(jù)的離散曲面的曲率計算，將成為這個研究課題不斷發(fā)展的源源動力。參考文獻(xiàn)：1 Warren J, Schaefer S, Hirani A N, Desbrun M.Barycentric coordinates for convexsets. Technical report, Rice University, 2003.2 Taubin G. A signal processing approach to fair surface design. In:Proc. of the SIGGRAPH' 95. New York: ACM Pres

14、s, 1995. p.351-358.3 Garland M, Heckbert P S. Surface simplification using quadric error metricsA.In:Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles,1997. p.209-216.4 G.Lavoue, F.Dupont and A.Baskurt, Constant. Curvature Region Decomposition of 3D-Meshes by a Mixed

15、. Approach Vertex-Triangle. Journal of WSCG, 2004, vol. 12, no.2, p. 245-252.5Chen,X.,Sehmitt,F.,1992.IntrinsieSurfaeePropertiesfromSurfaeeTrian即lation.ProeeedingsoftheEuroPeanConfereneeonComPuterVersion,P.739一743.6Taubin,G.,1995.EstimatingtheTensorofCurvatureofaSurfaeefromaPolyhedral ApproximationProeeedingsoftheFifthInternationalConfereneeonComputerVision,P.902一907.7K.WatanabeandA.GBelyaev.Deteetionofsalieuteurvaturefeaturesonpolygonalsurfaees.In:EUROGRAPHICS2001,volume20,2001.8MeyerM,DesbrunM,SehloderP,BarrAH.Diseretedifferential一geo