苗蘭芳， 周廷方， 彭群生

（1. 浙江師范大學(xué)信息科學(xué)與工程學(xué)院，浙江 金華 321004； 2. 浙江大學(xué)CAD&CG國家重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310027）

現(xiàn)實(shí)世界中有許多應(yīng)用有賴于建立準(zhǔn)確的實(shí)體模型并進(jìn)行可視化，如雕像、考古藝術(shù)品、大規(guī)模地貌以及反求工程中的模型仿制、模具翻新等。由三維掃描儀對(duì)模型表面進(jìn)行掃描，會(huì)得到大量的三維采樣點(diǎn)，從這些點(diǎn)中重建出逼近于原始實(shí)體模型表面的曲面并進(jìn)行繪制是計(jì)算機(jī)圖形學(xué)中一個(gè)很重要的研究領(lǐng)域。近年來，隨著模型表面復(fù)雜度和表面采樣點(diǎn)數(shù)據(jù)的增加，形成了眾多大規(guī)模采樣點(diǎn)數(shù)據(jù)模型，從這樣的數(shù)據(jù)模型中快速地重建出曲面必然會(huì)出現(xiàn)以前小規(guī)模數(shù)據(jù)點(diǎn)模型所沒有的問題。

在曲面重建方法中，基于徑向基函數(shù)[1-3]（RBF： Radial Base Function）的曲面重建方法和幾何樣條曲面的最小二乘擬合[4]是一種基于全局的隱式曲面重建方法，其中RBF 對(duì)于不完整的光滑數(shù)據(jù)模型的修補(bǔ)特別有用，但它有磨光作用，因此很難重建像棱邊、尖角之類的明顯特征，并且在處理大規(guī)模數(shù)據(jù)點(diǎn)模型的速度很慢。基于Blinn[5]局部隱式曲面加權(quán)混合思想之上的曲面重建方法是一種局部的隱式曲面重建方法，如：Muraki等[6]用高斯球的線性組合擬合散亂點(diǎn)云的隱式曲面；Hoppe 等[7]通過估算局部區(qū)域內(nèi)的最近點(diǎn)切平面的有向距離進(jìn)行隱式曲面重建；Curless 等[8]提出了一種基于對(duì)預(yù)建的基礎(chǔ)表面模型上的距離函數(shù)的估算進(jìn)行隱式曲面重建；Alexa[9]等采用基于投影的形狀逼近方法在局部性和直接重采樣方面有所突破，但投影需要求解非線性MLS 問題，從而使大部分形狀操作非常費(fèi)時(shí)；Ohtake 等[10]對(duì)大規(guī)模數(shù)據(jù)點(diǎn)采用多層次剖分MPU 方法，首先對(duì)點(diǎn)模型根據(jù)其點(diǎn)數(shù)和法棱錐角進(jìn)行八叉樹自適應(yīng)剖分，繼而對(duì)每個(gè)單元重建的局部曲面進(jìn)行加權(quán)混合。

基于局部的隱式曲面重建方法和基于全局的隱式曲面重建方法相比，其最大優(yōu)勢(shì)在于：將大規(guī)模的數(shù)據(jù)點(diǎn)云分成小塊的數(shù)據(jù)點(diǎn)云后在小范圍內(nèi)進(jìn)行隱式曲面重建，然后通過對(duì)重建的局部曲面加權(quán)混合求得函數(shù)值。但該類方法在計(jì)算函數(shù)值時(shí)仍需求解線性或非線性系統(tǒng)方程。Nielson 提出一種基于徑向Hermite 基函數(shù)的加權(quán)對(duì)散亂數(shù)據(jù)點(diǎn)的位置和法向進(jìn)行插值的曲面重建方法[11]。該方法通過對(duì)點(diǎn)附近的最近的模型表面上K 個(gè)點(diǎn)的法向和位置信息直接求取函數(shù)值，其重建速度快于前面描述的任何一種曲面重建方法，但是該方法不能處理帶有噪聲的散亂點(diǎn)數(shù)據(jù)。

針對(duì)上述情況，本文提出了一種點(diǎn)模型的隱式曲面的快速重建方法，該方法以局部鄰域內(nèi)采樣點(diǎn)的雙邊濾波函數(shù)值為依據(jù)，其模型表面附近任意一點(diǎn)的函數(shù)值通過該點(diǎn)附近表面上最近的K個(gè)采樣數(shù)據(jù)直接估算所得，和以往的曲面重建方法相比，本文方法既不用曲面內(nèi)、外的支撐點(diǎn)，也不用求解線性或非線性系統(tǒng)方程，具有非?？斓闹亟ㄋ俣?。此外，由于該隱式曲面是基于雙邊濾波函數(shù)之上的，因此，還能對(duì)帶有噪聲的點(diǎn)模型進(jìn)行特征保持的曲面重建。

1 基于雙邊濾波函數(shù)的隱式曲面重建

雙邊濾波函數(shù)最早被用于圖像處理領(lǐng)域的輪廓特征保持的去噪中[12]，后來被拓展用于三維數(shù)據(jù)的網(wǎng)格模型表面去噪，效果相當(dāng)好[13-14]。盡管這些文獻(xiàn)中描述的去噪方法是針對(duì)網(wǎng)格模型表面，但同樣也適合于點(diǎn)模型表面。

式中 K 為參與函數(shù)值計(jì)算的離iP 點(diǎn)最近的模型表面上的采樣點(diǎn)數(shù)，cW 、sW 在圖像去噪處理 中，分別作為雙邊濾波函數(shù)的空域和頻域高斯濾 波，現(xiàn)分別作為三維模型表面采樣點(diǎn)iP 所在的局 部鄰域內(nèi)切平面上和法向高度場(chǎng)的高斯濾波，具體形式如下

其中sσ 、cσ 分別為其切平面（空域）和法向 高度場(chǎng)（頻域）上的高斯濾波系數(shù)，它們反映了 計(jì)算任意一個(gè)采樣點(diǎn)P 的雙邊濾波函數(shù)值時(shí)的 切向和法向影響范圍。采用這個(gè)雙邊濾波函數(shù)，可以對(duì)模型表面數(shù)據(jù)進(jìn)行去噪的同時(shí)也能進(jìn)行特征保持[13-14]。

1.1 任意一點(diǎn)的雙邊濾波函數(shù)值的計(jì)算

對(duì)于模型表面上任一采樣點(diǎn)iP 及其法向Ni，都可得到一個(gè)由公式（2）計(jì)算所得的雙邊濾波函數(shù)值；而對(duì)于模型表面附近任一點(diǎn)P ( x, y , z )，在根據(jù)公式（2）計(jì)算其雙邊濾波函數(shù)值時(shí)，發(fā)現(xiàn)還需要先計(jì)算該點(diǎn)的法向N ( x, y , z )。

1.2 任意一點(diǎn)的法向計(jì)算

Amenta等指出，采樣點(diǎn)模型的MLS隱式曲面函數(shù)可以表示成二個(gè)分量：一個(gè)能量場(chǎng)和一個(gè)法矢量場(chǎng)[15]。對(duì)于采樣點(diǎn)模型表面附近任意一點(diǎn)，用MLS表面能量最小法可求出該點(diǎn)的法向。但運(yùn)用該方法在某些地方會(huì)產(chǎn)生不理想的法向（如：距離表面較遠(yuǎn)的地方和表面附近有明顯特征的地方）[16]。為此，他們又提出另外兩種表面能量定義方式改進(jìn)法向場(chǎng)的分布，即：通過鄰域采樣點(diǎn)加權(quán)重心的能量函數(shù)以及利用線積分計(jì)算的能量函數(shù)，但這兩種方法都是針對(duì)沒有法向的采樣點(diǎn)模型，而且需求解費(fèi)時(shí)的非線性方程。

對(duì)于帶有法向的采樣點(diǎn)模型，在表面附近任意一點(diǎn)的法向可以估算為與該點(diǎn)最近的模型表面上的K 個(gè)點(diǎn)法向的加權(quán)和[17]，即

式中 K 為距離P 點(diǎn)最近的模型表面的鄰域點(diǎn)數(shù)， WNi(|P ? Pi|)可以為任意一個(gè)關(guān)于距離|P ? Pi|單調(diào)遞減的正值權(quán)函數(shù)，如：可以選擇Sheperd反距離函數(shù) WNi(| x |) = 1/x及高斯濾波 函數(shù)。用這種計(jì)算方式估算的模型表面法向場(chǎng)，如圖1所示。

圖 1 點(diǎn)模型表面的法向場(chǎng)流線

上述法向估算方法簡單、快速，并且可以保證在表面附近的法向場(chǎng)的正確性。但在遠(yuǎn)離采樣點(diǎn)模型表面時(shí)，法向場(chǎng)與表面垂直方向會(huì)有一定的偏移。在下面將要描述的等值面抽取算法中，由于只是利用了采樣點(diǎn)模型表面附近的函數(shù)值及其相應(yīng)的法向場(chǎng)，因此，可以保證重建曲面的正確性。

1.3 采用雙邊濾波函數(shù)進(jìn)行隱式曲面重建

由公式（2）計(jì)算的雙向?yàn)V波函數(shù)值D，在采樣點(diǎn)模型表面附近構(gòu)造了一個(gè)距離場(chǎng)，該距離場(chǎng)可以采用某種等值面抽取方法（如：移動(dòng)立方體方法MC：Moving Cube）抽取出任意函數(shù)值的等值面，其中距離值為零的等值面即為點(diǎn)模型表面。圖2是分別利用MC等值面抽取方法對(duì)兔子點(diǎn)模型表面附近函數(shù)值為零、+0.2和-0.1的等值面進(jìn)行抽取的結(jié)果。在用MC方法對(duì)等值面進(jìn)行抽取時(shí)，被剖分的移動(dòng)小立方體已足夠小，所抽取的等值面與模型表面的距離最大也不會(huì)超過小立方體的對(duì)角線，這一點(diǎn)為采樣點(diǎn)模型隱式曲面的正確重建提供了保證。

圖 2 采用本文方法重建的Bunny模型結(jié)果（圖中繪制模型在顯示時(shí)作了一定比例的縮放）

2 基于雙邊濾波函數(shù)的隱式曲面重建的應(yīng)用

由于雙邊濾波函數(shù)的去噪保特征的性質(zhì)，因此，利用雙邊波濾函數(shù)進(jìn)行隱式曲面重建時(shí)，對(duì)帶有一定噪聲和失真的采樣點(diǎn)模型能進(jìn)行去噪保特征的隱式曲面重建，此外，基于雙邊濾波函數(shù)的隱式曲面重建方法還可以方便地進(jìn)行實(shí)體幾何造型。

2.1 去噪和特征保持

去噪采用Nielson方法重建不含噪聲的稠密采樣點(diǎn)模型時(shí)，一般不會(huì)遇到問題，這是因?yàn)镹ielson方法是直接對(duì)點(diǎn)的位置和法向的插值進(jìn)行隱式曲面重建的[11]，但該方法應(yīng)用于帶有噪聲的稠密采樣點(diǎn)數(shù)據(jù)模型時(shí)，就會(huì)得到很不理想的結(jié)果，如圖3(b)所示。本文提出基于雙邊濾波函數(shù)對(duì)稠密采樣點(diǎn)數(shù)據(jù)模型進(jìn)行隱式曲面重建的方法，具有比較好的重建效果。如圖3(c)所示。無論是用Nielson的方法，還是用本文提出的方法，當(dāng)?shù)玫降哪Ｐ捅砻娴牟蓸狱c(diǎn)數(shù)據(jù)比較稠密且又比較準(zhǔn)確時(shí)，都會(huì)得到相當(dāng)好的結(jié)果，如圖4所示，盡管仍可從圖中看出某些細(xì)微的差別，如：采用后者的方法所重建的模型表面（如圖4(b)）光滑于采用前者方法所重建的模型表面（如圖

4(a)）。

圖 3 帶有噪聲的Bunny數(shù)據(jù)模型的表面重建結(jié)果

圖 4 無噪聲的稠密采樣點(diǎn)模型的隱式曲面重建結(jié)果

顯著特征的保持雖然基于雙邊濾波函數(shù)的隱式曲面重建能對(duì)采樣點(diǎn)模型進(jìn)行特征保持的表面重建，但對(duì)于比較明顯的模型表面特征（如CAD模型的邊、角等），如果只用上述重建方法，則會(huì)不同程度地削弱邊角特征的銳度。對(duì)此，在計(jì)算函數(shù)值時(shí)，首先對(duì)搜索到的模型表面上最近的K個(gè)采樣點(diǎn)進(jìn)行關(guān)于其法向的分類（具體方法可參看MPU有關(guān)明顯特征重建方法[10]），如圖5所示，然后，取最近的一類點(diǎn)計(jì)算函數(shù)值；更精確一點(diǎn)的方法還可以先把這些點(diǎn)按其特征所對(duì)應(yīng)的法向分成幾簇，再采用布爾交運(yùn)算求交的方法。

圖 5 采樣點(diǎn)模型附近任意一點(diǎn)P的最近采樣點(diǎn) 鄰域的明顯特征示意圖

2.2 布爾操作

為了下面描述方便，將FA記為與采樣點(diǎn)集A相對(duì)應(yīng)的體模型或距離場(chǎng)函數(shù)，A的外側(cè)可表示為

本文的距離場(chǎng)函數(shù)是采樣點(diǎn)模型表面的雙邊濾波函數(shù)，而其外表面隱式地逼近于由其采樣點(diǎn)集所定義的表面。設(shè)B是另一個(gè)三維采樣點(diǎn)模型，其所對(duì)應(yīng)的體模型或距離場(chǎng)函數(shù)為FB，其外側(cè)為

則很容易定義上述兩個(gè)模型的并

相應(yīng)地距離場(chǎng)函數(shù)的并定義為

同樣的，可定義兩距離場(chǎng)函數(shù)的交和差為

甚至還可以定義一些混合（Blend）距離場(chǎng)函數(shù)，如雙曲線混合

3 實(shí)驗(yàn)結(jié)果及分析

本文所有實(shí)驗(yàn)結(jié)果均采用MC方法進(jìn)行隱式曲面三角化。在繪制時(shí)，發(fā)現(xiàn)MC方法在不同精度的小立方體下對(duì)采樣點(diǎn)模型細(xì)節(jié)有著不同程度的保留效果。圖6是對(duì)于右半邊數(shù)據(jù)不完整模型Venus頭像的重建結(jié)果，其中圖6(a)原始數(shù)據(jù)模型，圖6(b)、圖(c)、圖(d)為不同小立方體邊長（分別為：0.7，0.5，0.3）下的重建結(jié)果，圖6(b)的點(diǎn)數(shù)為28582，比原始模型的點(diǎn)數(shù)（72545）少了幾倍，這意味著其分辨率比原始模型降低了幾倍，因此在其繪制結(jié)果中丟失了好多細(xì)節(jié)；圖6(c)的點(diǎn)數(shù)為87536，該點(diǎn)數(shù)略多于原始模型的點(diǎn)數(shù)，其重建結(jié)果圖像保留了細(xì)節(jié)，但由于原始模型中左一半采樣稠密，而右一半采樣較稀，因此，重建后左邊的實(shí)際分辨率還是低于原始模型；圖6(d)的點(diǎn)數(shù)為155708，自然分辨率已高出原始點(diǎn)模型一倍，但繪制結(jié)果相對(duì)于圖6(c)沒有特別明顯的改進(jìn)。因此，在用移動(dòng)立方體方法進(jìn)行模型的等值面抽取時(shí)，對(duì)小立方體的邊長應(yīng)進(jìn)行自適應(yīng)的調(diào)整。這樣，既能避免不必要的冗余，又能避免細(xì)節(jié)丟失。

圖 6 不完整數(shù)據(jù)模型Venus（72545）在不同小立方體邊長下重建的結(jié)果（括號(hào)內(nèi)為點(diǎn)數(shù)）

圖7顯示了對(duì)Buuny模型（點(diǎn)數(shù)為35283）取不同分辨率并施加不同次數(shù)的雙邊濾波函數(shù)進(jìn)行重建的結(jié)果。左圖為對(duì)原始點(diǎn)模型使用一次雙邊濾波函數(shù)后重建的結(jié)果，中圖和右圖分別為對(duì)左圖結(jié)果（即：頂點(diǎn)及其法向）施加雙邊濾波函數(shù)一次、二次進(jìn)行重建的結(jié)果；上、下二排的小立方體邊長分別為：0.007和0.003；點(diǎn)數(shù)分別為：27114、26916、26726；148130、144312、145728?？梢钥闯觯湟?，分辨率越高，重建的細(xì)節(jié)越明顯；其二，增加使用雙邊濾波函數(shù)進(jìn)行重建的次數(shù)，可以使分辨率低的模型表面趨向于光滑，而對(duì)于分辨率較高的模型的影響甚少。

圖7 對(duì)Buuny 模型（點(diǎn)數(shù)為35283）在不同小立方體邊長（上： 0.007,下： 0.003）時(shí)施加1 次（左），2 次（中） 和3 次（右）的雙邊濾波函數(shù)進(jìn)行重建的結(jié)果（上排逐漸光滑，下排光滑很少。圖中右下角為點(diǎn)數(shù)）

圖8從左到右分別為點(diǎn)模型venus采用不同小立方體邊長的MC算法進(jìn)行連續(xù)六次等值面抽取的結(jié)果。小立方體邊長越大，其細(xì)節(jié)磨損程度越大，其重建模型表面也就越光滑。而在與圖7中相對(duì)應(yīng)的重建結(jié)果比較中，可以看出，在分辨率較高（小立方體邊長較小）的重建中，其細(xì)節(jié)隨著重建次數(shù)的增加，其磨光程度較低，但相對(duì)于原始模型，還是變得光滑了。

圖8 從左到右圖分別為點(diǎn)模型venus 采用不同小立方體邊長的MC 算法進(jìn)行連續(xù)六次等值面抽取的 結(jié)果（小立方體邊長越大，其細(xì)節(jié)磨損程度越大，重建模型表面就越光滑）

圖9所示為采用本文提出的基于雙邊濾波函數(shù)進(jìn)行隱式曲面重建的方法對(duì)采樣點(diǎn)模型進(jìn)行布爾運(yùn)算的結(jié)果。圖中所用模型的點(diǎn)數(shù)分別為：兔子10k，圓環(huán)32k，vase68k，venus50k，球10k以及dinosaur56k。由此結(jié)果可知，采用雙邊濾波函數(shù)進(jìn)行隱式曲面重建可以很容易很魯棒地實(shí)現(xiàn)實(shí)體幾何造型中的布爾運(yùn)算。

圖 9 基于雙向?yàn)V波函數(shù)的隱式曲面的布爾運(yùn)算

4 小 結(jié)

本文提出了一種基于雙邊濾波函數(shù)的隱式曲面重建方法。在計(jì)算函數(shù)值時(shí)，只需將模型表面上最近的K個(gè)點(diǎn)的位置和法向信息代入公式（2）進(jìn)行直接計(jì)算，無須求解線性或非線性系統(tǒng)方程，與采用RBF、MLS及MPU的重建方法相比，新方法在時(shí)間上的優(yōu)勢(shì)是最為明顯的；此外，該方法還能對(duì)帶有噪聲的數(shù)據(jù)模型進(jìn)行表面重建，且具有很好的去噪保特征的重建效果。實(shí)驗(yàn)結(jié)果表明，基于雙邊濾波器的隱式曲面是一種非常有效的曲面表達(dá)形式。

[1] Carr J C, Beatson R K, Cherrie J B, et al. Reconstruction and representation of 3D objects with radial basis functions [C]//Proceedings of ACMSIGGRAPH 2001, 2001： 67-76.

[2] Turk G, O’Brien J. Modelling with implicit surfaces that interpolate [J]. ACM Transactions on Graphics, 2002, 21(4)： 855-873.

[3] Ohtake Y, Belyaev A G, Seidel H P. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions [C]//Shape Modeling International 2003, 2003： 153-161.

[4] Jüttler B, Felis A. Least-squares fitting of algebraic spline surfaces [J]. Advances in Computational Mathematics, 2002, 17： 135-152.

[5] Blinn J F. A generalization of algebraic surface drawing [J]. ACM Transactions on Graphics, 1982, 1(3)： 235-256.

[6] Muraki S. Volumetric shape description of range data using “Blobby Model” [C]//Proceedings of ACMSIGGRAPH 1991. Computer Graphics, 1991： 227-235.

[7] Hoppe H, DeRose T, Duchamp T. Surface reconstruction from unorganized points [C]// Proceeding of Siggraph 1992, 1992： 71-78.

[8] Curless B, Levoy M. A volumetric method for building complex models from range images [C]// Proceedings of SIGGRAPH 1996, 1996： 303-312.

[9] Alexa M, Behr J, Cohen-Or D, et al. Point set surfaces [C]//IEEE Visualization 2001, 2001： 21-28.

[10] Ohtake Y, Belyaev A, Alexa M, et al. Multi-level partition of unity implicits [C]//Siggraph 2003 Proceeding, San Diego, 2003： 463-470.

[11] Nielson G M. Radial hermite operators for scattered point cloud data with normal vectors and applications to implicitizing polygon mesh surfaces for generalized CSG operations and smoothing [C]//IEEE Visualization 2004, 2004： 203-210.

[12] Smith S M, Brady J M. SUSAN： a new approach to low level image processing [R]. Technical Report, 1995.

[13] Fleishman S, Drori I, Cohen-Or D. Bilateral mesh denoising [J]. ACM Trans. Graph, 2003, 22(3)： 950-953.

[14] Jones T, Durand F, Desbrun M. Non-iterative, feature preserving mesh smoothing [J]. ACM Trans. Graph, 2003, 22(3)： 943–949.

[15] Amenta N, Kil Y J. Defining point-set surfaces [J]. ACM Trans. Graph, 2004, 23(3)： 264-270.

[16] Amenta N, Kil Y J. The domain of a point set surface [C]//Proc. of Eurographics Symposium on Point-Based Graphics 2004, 2004： 139-147.

[17] Alexa M, Adamson A. On normals and projection operators for surfaces defined by point sets [C]//Proc. of Symp. on Point-Based Graphics 2004, 2004： 149-155.