一種大規模散亂數據自適應壓縮與 曲面重建方法

王曉明， 劉吉曉

（山東交通學院數理系，山東 濟南 250023）

針對大規模散亂數據的曲面重建是反向工程，計算機輔助設計，計算機圖形學等領域的關鍵問題。目前以NURBS 為主的參數曲面和三角網格曲面是最常用的兩種方法。三角網格曲面在實際中有廣泛的應用，但由于實際中所測得的數據往往規模大，密度高，直接對其進行三角網格重建一般是困難的，而且也是不必要的。文獻[2]給出一種基于曲率抽樣網格的NURBS 曲面重建算法。該算法能將數據點云壓縮成一個由適合數量的點連成的四邊形網格，進而由網格直接進行NURBS 擬合。那么，能否利用上述算法設計一種三角網格生成算法。本文正是基于此，給出了一種自適應數據壓縮和三角網格重建算法。

1 初始插值曲面的構造

雖然徑向基插值曲面質量很好，但其也有一個弱點。當插值點數量增加時，運算時間也隨之急劇增加。故對于大規模的數據點集，采用文獻[5]中的分片插值策略。將曲面定義域F 剖分為若干小區域，每個小區域上的曲面由該區域中所有點以及相鄰區域中的若干點插值而成。如圖1 所示，小區域A上的曲面片由D中落在深色小矩形內的點插值而成。該方法雖然不能保證曲面整體的連續性，但由于曲面良好的光順性和光滑性，使其在分片交界處也不會太大差異。

圖1 區域剖分以及局部插值示意

2 基于曲率和距離的抽樣三角網格

由于直接對大規模高密度散亂數據三角化是非常耗時而且也是不必要的，故一般須先對散亂數據進行壓縮，然后再進行重建。本文給出一種基于曲率和距離的三角網格抽樣方法。將數據壓縮和曲面重建同時進行。

2.1 網格抽樣原理

現考察圖2 所示的質點系，若沿x 軸分布的質點1m 和 3m 分別位于1x 和3x 處，則質點系的質心2x 滿足

圖2 質點系

由此給出如下的網格抽樣原理。

（1） 情形一：考慮曲率。

若定義r ( x, y)為反映曲面 f ( x, y )曲率的形狀函數 (r ( x, y)＞0)，將其類比于式（3）中的質量，可得

顯然在形狀函數r ( x, y )較大的地方，所需的抽樣點較多。這里r ( x, y)可以采用文獻[1-2]中的定義

它可以通過如下迭代求解

（2） 情形二：考慮距離

（3） 情形三：綜合考慮曲率與距離

由于要生成三角網格，如果只考慮曲率，將會出現大量的狹長三角片，導致三角網格曲面質量不高，如圖4(a)。如果僅考慮距離，則沒有有效利用固定數量的點充分刻畫曲面細節，如圖4(b)。所以這里考慮將二者加權平均，令式(4)～式(8)中

圖3 曲面10sin sin 局部

圖4 對圖3 曲面分別用3 種方法抽樣的結果

2.2 三角網格抽樣步驟

下面結合一個實例給出本文算法。對所給散亂數據點（圖5(a)），首先利用第二節中所介紹的算法。得到一張插值曲面。然后在曲面上設計一張初始三角網格曲面。該初始網格約束在曲面定義域F 內。該網格可以隨機定義，如文獻[1-2]中的四邊形網格均為隨機定義。但考慮初始網格的好壞會直接影響到后面的迭代次數，故在這里 人為指定。首先將曲面定義域F 沿 yx, 方向分別等分為 m1,m2份，使 m1m2=m。這樣得到m 個 等分點。同時按照點的分布建立起點與點之間的拓撲關系，如圖5(b)所示。然后將這種拓撲關系對應到曲面上，就得到了初始的三角網格曲面圖5(c)。可以看出，由于點在定義域上均勻分布，使得初始三角網格不能很好地刻畫曲面的細節特征，如嘴巴，鼻子眼睛等部位。利用式(7)～式(9)進行迭代計算。在迭代過程中位于邊界曲面上的點只能在相應的邊界上滑動，而4 個角點位置保持不動。最終可得如圖5(e)的抽樣網格。圖5(d)是其在xoy 平面的投影。可以看到，在曲面細節處聚集了較多的點，故網格能很好刻畫曲面細節特征。

由于定義域的邊界一般不是數據點集的邊界，最后還需尋找真實邊界。將網格和數據點集均投影到xoy 平面（也就是只利用每個點的前兩個坐標）。分別稱其投影為投影網格和投影點集。從投影網格四邊向內，逐個刪除三角網格中的三角片，直到遇到其投影網格中包含投影點集中點的三角片。這樣就可以得到一張基本反映數據點集形狀的三角網格。更進一步還可以通過用離每個網格點最近的原始數據點代換該網格點得到實際的三角網格曲面，如圖5(f)所示。

3 總 結

本文給出一種針對大規模散亂數據的自適應壓縮術和曲面重建算法。算法簡單高效，另外，由于生成的三角網格中內點的度均為六，這對進一步生成高階光滑的細分曲面是十分有利的。

[1] Li S Z. Adaptive sampling and mesh generation [J]. Computer-Aided Design, 1995, 27(3)： 235-240.

[2] 來新民, 等. 基于NURBS 的散亂數據點自由曲面重構[J]. 計算機輔助設計與圖形學學報, 1999, 11(5)： 433-436.

[3] 史利民, 王仁宏, 幾種基于散亂數據擬合的局部插值方法[J]. 數學研究與評論, 2006, 26(2)： 283-291.

[4] Richard Franke. Scattered data interpolation tests of some methods [J]. Mathematics of Computation, 1982, 38(157)： 181-200.

[5] Bradley C, Vickers G W. Free-form surface reconstruction for machine vision rapid prototyping [J]. Optical Engineering, 1993, 32(9)： 2191-2199.

圖5 將本文方法用到人臉數據的結果