王曉明， 劉吉曉

（山東交通學院數(shù)理系，山東 濟南 250023）

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

1 初始插值曲面的構(gòu)造

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

圖1 區(qū)域剖分以及局部插值示意

2 基于曲率和距離的抽樣三角網(wǎng)格

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

2.1 網(wǎng)格抽樣原理

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

圖2 質(zhì)點系

由此給出如下的網(wǎng)格抽樣原理。

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

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

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

它可以通過如下迭代求解

（2） 情形二：考慮距離

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

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

圖3 曲面10sin sin 局部

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

2.2 三角網(wǎng)格抽樣步驟

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

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

3 總 結(jié)

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

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

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

[3] 史利民, 王仁宏, 幾種基于散亂數(shù)據(jù)擬合的局部插值方法[J]. 數(shù)學研究與評論, 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 將本文方法用到人臉數(shù)據(jù)的結(jié)果