基于散亂數(shù)據(jù)的二元樣條)曲面重構(gòu)方法

汪春曉，路 游

(中國石油大學(xué)(北京),北京 102249)

汪春曉，路 游

(中國石油大學(xué)(北京),北京 102249)

在計算幾何領(lǐng)域中，利用曲面擬合散亂數(shù)據(jù)點(diǎn)集，是計算機(jī)圖形學(xué)以及計算機(jī)輔助幾何設(shè)計中一個困難的問題。傳統(tǒng)的基于均勻2-型三角剖分的二元樣條曲面重構(gòu)算法存在重構(gòu)速度較慢、曲面精度不高等問題。針對上述問題，提出了一種新的曲面重構(gòu)方法。該方法通過數(shù)據(jù)點(diǎn)構(gòu)造以卷積形式表示的控制系數(shù)，并構(gòu)造迭代公式，迭代計算數(shù)據(jù)點(diǎn)與曲面的距離，根據(jù)距離調(diào)整控制系數(shù)，直到前后兩次數(shù)據(jù)點(diǎn)到曲面的最大距離的差值小于適當(dāng)?shù)拈撝担M(jìn)而確定最佳的控制系數(shù)，通過將點(diǎn)置于數(shù)據(jù)塊中，以數(shù)據(jù)塊為單位進(jìn)行計算，采用取整的方式消除邊界處的重復(fù)計算，減少了重構(gòu)曲面的計算次數(shù)。實(shí)驗(yàn)結(jié)果表明，該方法提高了曲面重構(gòu)的速度和質(zhì)量，證明了此方法是可行、有效的。

二元樣條；卷積；曲面重構(gòu)；控制系數(shù)；迭代方法

0 引 言

樣條函數(shù)，是具有一定光滑性的分段或者分片定義的多項式函數(shù)。在計算機(jī)幾何領(lǐng)域與飛機(jī)、船舶制造等領(lǐng)域均有重要的應(yīng)用。一元樣條應(yīng)用最早、最廣泛，研究的最詳細(xì)的是3次樣條函數(shù)。1946年，數(shù)學(xué)家I．J．Schoenberg系統(tǒng)地建立了一元樣條函數(shù)的理論基礎(chǔ)[1]。從60年代開始，樣條函數(shù)有了迅速的發(fā)展和應(yīng)用。1966年，H.B.Curry和I.J.Schoenberg提出了一元B樣條函數(shù)，是一種定義B樣條函數(shù)的幾何直觀方法[2]。1975年，利用函數(shù)論和代數(shù)幾何方法，王仁宏教授構(gòu)建了多元樣條函數(shù)的基本理論框架，開創(chuàng)了一套研究多元樣條函數(shù)基本問題的新方法，即光滑余因子協(xié)調(diào)法[3]。目前在多元樣條的研究方法上大致可分為三類：光滑余因子協(xié)調(diào)法，以王仁宏為代表；B-網(wǎng)方法，以Farin[4]為代表；B-樣條方法，亦稱投影子法，以Schoenberg[2]、de Boor[5]和Micchelli[6]等為代表。最近一段時間，樣條函數(shù)方面也有許多研究成果。文獻(xiàn)[7-8]分別介紹了多元樣條的應(yīng)用研究，B樣條在模糊系統(tǒng)中的應(yīng)用，等等。在文獻(xiàn)[9-13]分別介紹了B樣條的圖像插值方法，B樣條的數(shù)值流形和時間積分方法。

曲線曲面造型是計算機(jī)圖形學(xué)、計算機(jī)輔助幾何設(shè)計和計算機(jī)輔助設(shè)計所研究的重要內(nèi)容，多元樣條在其中有重要的作用。到目前為止，曲線曲面造型以逐漸形成了以非均勻有理B樣條設(shè)計和隱式代數(shù)曲面為主體，以插值、擬合、逼近等方法為骨架的理論體系[3,14]。傳統(tǒng)的基于均勻2-型三角剖分二元樣條曲面重建方法構(gòu)造的曲面具有內(nèi)置的連續(xù)性，重建后的曲面整體次數(shù)低，控制頂點(diǎn)相對較少，曲面拼接時無需考慮拼接處的光滑問題，同時，曲面也具有良好的幾何和逼近性質(zhì)，如幾何不變性、變差縮減性等。但是，該方法也存在一些不足，比如重構(gòu)曲面的速度較慢，數(shù)據(jù)點(diǎn)與重構(gòu)曲面之間的距離過大等。

針對以上問題，提出了一種新的非張量積型二元樣條曲面重構(gòu)方法，通過卷積形式表示控制系數(shù)，結(jié)合數(shù)據(jù)點(diǎn)得到初始的控制系數(shù)，并構(gòu)造迭代公式，迭代計算數(shù)據(jù)點(diǎn)與擬合曲面的距離，根據(jù)距離重新調(diào)整控制系數(shù)，直到前后兩次數(shù)據(jù)點(diǎn)到曲面的最大距離的差值小于給定閾值，最后通過最佳的控制系數(shù)進(jìn)行曲面重構(gòu)。

1 算法基本原理

1.1 均勻2-型三角剖分上二元樣條函數(shù)空間

均勻2-型三角剖分是在矩形剖分的基礎(chǔ)上，連接其中各小矩形的兩條對角線而形成的三角剖分，如果矩形剖分是均勻剖分的，那么，形成的均勻2-型三角剖分也是貫穿剖分[15]。

mx-i=0,ny-i=0,ny-mx-i=0,ny-mx-

i=0

其中，i=…,-1,0,1,…。

圖1 區(qū)域D及其剖分

每個內(nèi)網(wǎng)點(diǎn)均由四條直線相交而成，如式(1)所示[16]：

Ni>(k+1)/(k-μ)

(1)

k>(4μ+1)/3

(2)

當(dāng)μ一定時，則要求多項式的次數(shù)盡可能低，那么可以得到如下若干個均勻2-型剖分上的樣條函數(shù)空間：

利用貫穿剖分上的樣條函數(shù)空間維數(shù)公式[16]：

(3)

圖2 區(qū)域Q及其剖分

對各i=1,2,…,25，剖腔上的多項式可表示為：

根據(jù)對稱性原則可以推出其他剖腔上的多項式。

記Β(x,y)為圖2中定義在Q上的分片多項式，在編號為i的剖腔上記為pi，那么顯然Β(x,y)C1(2)，并且在Q內(nèi)部Β(x,y)>0。因此，Β(x,y)是上的樣條函數(shù)，并且由文獻(xiàn)[17-18]可知，Β(x,y)的支集是最小的。

(4)

由式(4)定義的二元樣條函數(shù)A滿足：

(5)

對任意的i0,j0,0≤i0≤m+1,0≤j0≤n+1，集合Ai0,j0={Bi,j(x,y)A:(i,j)≠(i0,j0)}，構(gòu)成了樣條函數(shù)空間的一組基底。

A中的二元樣條函數(shù)具有如下性質(zhì)：

(6)

1.3 構(gòu)造擬插值算子

（1）港口岸線資源整合和港區(qū)功能布局優(yōu)化，推進(jìn)港口集約化發(fā)展。由于碼頭性質(zhì)、經(jīng)營等方面的原因，杭州港存在著泊位利用效率不高，岸線使用效益差，部分港區(qū)功能布局分散等現(xiàn)象。本次港口總體規(guī)劃的編制，將按照岸線資源利用集約化和港口發(fā)展規(guī)?；?、大型化和專業(yè)化的要求對岸線資源進(jìn)行整合利用，對港區(qū)和泊位功能進(jìn)行調(diào)整?？傮w規(guī)劃中處理好既有泊位與規(guī)劃新建泊位的關(guān)系，實(shí)現(xiàn)港口岸線資源整合和港區(qū)功能布局優(yōu)化將是杭州港總體規(guī)劃編制工作的難點(diǎn)之一。

(7)

(8)

(9)

(10)

對于以上兩種擬插值算子有以下結(jié)論[17]：

(11)

1.4 優(yōu)化控制系數(shù)

由控制系數(shù)表達(dá)式(見式(10))可知，控制系數(shù)與每一個數(shù)據(jù)塊周圍的四個數(shù)據(jù)點(diǎn)以及中心點(diǎn)的值有關(guān)，如圖3所示。

圖3 四個數(shù)據(jù)點(diǎn)及中心點(diǎn)

(12)

由于初始控制系數(shù)矩陣是預(yù)估值，會存在偏差，所以要對其進(jìn)行修正。

E:=S-F

(13)

(14)

1.5 劃分邊界點(diǎn)

由式(9)可知，曲面W(f)由λi,j(f)和Bi,j(x,y)決定，由式(4)可知，Bi,j(x,y)是由B(x,y)在水平和垂直方向上進(jìn)行平移得到，并且最終得到的曲面的定義域I?2。

需要對?(x,y)2定義其所屬的塊編號(i,j)，(i,j)∈2，如圖4所示。令：

(?x」,?y」)=(i,j)，(x,y)(?x」,?y」)

(15)

圖4 邊界處點(diǎn)劃分方法

這樣，?(x,y)∈2都有唯一的編號?？捎洖椋簕(?x」,?y」)|?(x,y)∈[1,m+1)×[1,n+1),m,n∈}={(?x」,?y」)|?(x,y)∈[1,m]×[1,n],m,n∈}。

2 算法實(shí)現(xiàn)過程

輸入：給定數(shù)據(jù)點(diǎn)集F，閾值τ，數(shù)據(jù)點(diǎn)距離曲面最大距離e1，前一次的數(shù)據(jù)點(diǎn)距離曲面最大距離e0。

步驟4：在曲面上取與給定數(shù)據(jù)點(diǎn)坐標(biāo)相同的點(diǎn)，根據(jù)式(13)計算其與給定數(shù)據(jù)點(diǎn)之間的最大距離ek，令e1=ek。

步驟6：輸出曲面W。

通過推導(dǎo)和分析可知，當(dāng)輸入點(diǎn)為m×n時，總計算時間為Θ(l×m×n)，其中l(wèi)為迭代次數(shù)，與曲面結(jié)構(gòu)有關(guān)。

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

用Matlab軟件在處理器為Intel-1.80 GHz，內(nèi)存為4.0 GB的普通個人電腦上分別利用傳統(tǒng)非張量積型曲面重構(gòu)方法和文中提出方法進(jìn)行曲面重構(gòu)，結(jié)果如圖5所示。

(a)原始曲面

(b)在原始曲面上獲取的數(shù)據(jù)點(diǎn)

(c)傳統(tǒng))方法重構(gòu)出的曲面

(d)利用文中方法重構(gòu)出的曲面

曲面重構(gòu)各參數(shù)如表1所示。

表1 曲面重構(gòu)數(shù)據(jù)參數(shù)表

4 結(jié)束語

針對傳統(tǒng)的非張量積型二元樣條曲面重構(gòu)速度較慢、曲面精度不高等問題，提出新的非張量積型二元樣條曲面重構(gòu)方法，通過重新構(gòu)造控制系數(shù)，并利用迭代公式不斷修正控制系數(shù)，進(jìn)而得到符合要求的最佳控制系數(shù)，使得重構(gòu)出的曲面質(zhì)量得到提高。在重構(gòu)過程中，劃分點(diǎn)與塊的歸屬關(guān)系，將原來計算點(diǎn)的過程轉(zhuǎn)化為計算塊的過程，并且降低邊界處點(diǎn)的重復(fù)運(yùn)算，減少了計算次數(shù)，降低了運(yùn)算量，從而提高了重構(gòu)曲面的速度。最后通過實(shí)驗(yàn)證明了文中方法的可行性。

[1] Schoenberg I J.Contribution to the problem of application of equidistant data by analytic functions[J].Quart. Appl. Math,1946,4:45-99.

[2] Curry H B，Schoenberg I J．On Polya frequency functions IV:the fundamental spline functions and their limits[J]．J. Analyse Math,1996,17:71-107.

[3] 王仁宏.多元齒的結(jié)構(gòu)與插值[J].數(shù)學(xué)學(xué)報,1975,18(2):91-106.

[4] Farin G.Bezier polynomials over triangles and the construction of piecewise Cr polynomials[R]．Brunel:University of Uxbridge,Middlesex,1980.

[5] de Boor C.Spline as linear combination of B-spline[M]//Approximation theory II.New York:Academic Press,1976:1-47.

[6] Dahmen W，Micchelli C A．Recent progress in multivariate splines[M]//Approximation Theory IV.New York:Academic Press,1983.

[7] 郭慶杰．多元樣條若干理論與應(yīng)用研究[D]．大連:大連理工大學(xué),2015.

[8] 譚彥華，李洪興，馬秀娟，等．B樣條函數(shù)在模糊系統(tǒng)中的應(yīng)用[J]．控制理論與應(yīng)用,2013,30(11):1445-1456.

[9] 魏曉靜．基于B樣條函數(shù)的圖像插值方法研究[D]．大慶:東北石油大學(xué),2014.

[10] 溫偉斌．基于B樣條插值的數(shù)值流形方法與時間積分方法的研究[D]．重慶:重慶大學(xué),2014.

[11] Zeng Xiaoming,Zhou Guorong,Yang Lianqiang.Best bounds on the distance between 3-direction quartic box spline surface and its control net[J]．Applied Mathematics:A Journal of Chinese Universities,2013,28(2):147-157.

[12] 楊聯(lián)強(qiáng)，王 東．三向四次箱樣條曲面與Bezier曲面的光滑拼接[J]．計算機(jī)工程與應(yīng)用,2013,49(23):119-121.

[13] Fang Meie,Lu Jia,Peng Qunsheng．Volumetric data modeling and analysis based on seven-directional box spline[J]．Science China:Information Science,2014,57(6):1-14.

[14] 施法中．計算機(jī)輔助幾何設(shè)計與非均勻有理B樣條：CAGD&NURBS[M]．北京：北京航空航天大學(xué)出版社,1994.

[15] 王仁宏,崔錦泰.關(guān)于一個二元B樣條基[J]．中國科學(xué),1984(9):12-23.

[16] Chui C K,Wang R H.Multivariate spline spaces[J].Jour. Math.Anal. Appl.,1983,94:197-221.

[17] 王仁宏，施錫泉，羅鐘鉉，等．多元樣條函數(shù)及其應(yīng)用[M]．北京：科學(xué)出版社,1994.

[18] Wang R H.The dimension and basis of spaces of multivariate splines[J].Journal of Computational and Applied Mathematics,1985,12(85):163-177.

WANG Chun-xiao，LU You

(China University of Petroleum，Beijing 102249，China)

In the field of computation geometry,the use of surface fitting scattered data points is a difficult problem for CG and CAGD.The traditional bivariate spline surface reconstruction algorithm based on uniform type-2 triangulation exists shortcomings of slow speed and poor accuracy.Aiming at these problems above,a new surface reconstruction method is developed successfully.The convolution type control coefficient is offered through the data points,and the distance between data points and surface is obtained by iterative method.Then according to the distance,control coefficient is adjusted until the difference is less than the appropriate threshold before and after the maximum distance of data points and surface,so the optimum control coefficient is determined.Then blocks are selected as basic calculation unit,eliminating repeated calculation at the boundary reduced computation times.The results show that the method improves the speed and quality of surface reconstruction and is proved to be feasible and effective.

bivariate spline；convolution；surface reconstruction；control coefficient；iteration method

2016-08-27

2016-11-30 網(wǎng)絡(luò)出版時間：2017-06-05

國家自然科學(xué)基金資助項目(60873093)

汪春曉(1991-)，男，碩士生，研究方向?yàn)橛嬎銠C(jī)可視化、計算幾何；路 游,博士，副教授,研究方向?yàn)橛嬎銕缀?、圖形學(xué)、虛擬現(xiàn)實(shí)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1508.052.html

TP391

A

1673-629X(2017)08-0025-05

10.3969/j.issn.1673-629X.2017.08.006