苗蘭芳， 周廷方， 彭群生

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

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

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

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

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

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

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

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

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

1.1 任意一點的雙邊濾波函數(shù)值的計算

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

1.2 任意一點的法向計算

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

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

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

圖 1 點模型表面的法向場流線

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

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

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

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

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

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

2.1 去噪和特征保持

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

4(a)）。

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

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

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

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

2.2 布爾操作

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

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

則很容易定義上述兩個模型的并

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

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

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

3 實驗結(jié)果及分析

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

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

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

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

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

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

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

圖 9 基于雙向濾波函數(shù)的隱式曲面的布爾運算

4 小 結(jié)

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