稠密采樣點模型的快速隱式曲面重建

苗蘭芳， 周廷方， 彭群生

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

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

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

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

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

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

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

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

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

1.1 任意一點的雙邊濾波函數值的計算

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

1.2 任意一點的法向計算

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

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

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

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

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

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

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

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

2 基于雙邊濾波函數的隱式曲面重建的應用

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

2.1 去噪和特征保持

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

4(a)）。

圖 3 帶有噪聲的Bunny數據模型的表面重建結果

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

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

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

2.2 布爾操作

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

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

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

相應地距離場函數的并定義為

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

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

3 實驗結果及分析

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

圖 6 不完整數據模型Venus（72545）在不同小立方體邊長下重建的結果（括號內為點數）

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

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

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

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

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

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

4 小 結

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

[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.