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

汪春曉，路 游

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

汪春曉，路 游

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

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

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

0 引 言

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

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

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

1 算法基本原理

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

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

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

i=0

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

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

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

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

(1)

k>(4μ+1)/3

(2)

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

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

(3)

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

對(duì)各i=1,2,…,25，剖腔上的多項(xiàng)式可表示為：

根據(jù)對(duì)稱(chēng)性原則可以推出其他剖腔上的多項(xiàng)式。

記Β(x,y)為圖2中定義在Q上的分片多項(xiàng)式，在編號(hào)為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滿(mǎn)足：

(5)

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

(7)

(8)

(9)

(10)

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

(11)

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

由控制系數(shù)表達(dá)式(見(jiàn)式(10))可知，控制系數(shù)與每一個(gè)數(shù)據(jù)塊周?chē)乃膫€(gè)數(shù)據(jù)點(diǎn)以及中心點(diǎn)的值有關(guān)，如圖3所示。

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

(12)

由于初始控制系數(shù)矩陣是預(yù)估值，會(huì)存在偏差，所以要對(duì)其進(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。

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

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

(15)

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

這樣，?(x,y)∈2都有唯一的編號(hào)。可記為：{(?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)過(guò)程

輸入：給定數(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)計(jì)算其與給定數(shù)據(jù)點(diǎn)之間的最大距離ek，令e1=ek。

步驟6：輸出曲面W。

通過(guò)推導(dǎo)和分析可知，當(dāng)輸入點(diǎn)為m×n時(shí)，總計(jì)算時(shí)間為Θ(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的普通個(gè)人電腦上分別利用傳統(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é)束語(yǔ)

針對(duì)傳統(tǒng)的非張量積型二元樣條曲面重構(gòu)速度較慢、曲面精度不高等問(wèn)題，提出新的非張量積型二元樣條曲面重構(gòu)方法，通過(guò)重新構(gòu)造控制系數(shù)，并利用迭代公式不斷修正控制系數(shù)，進(jìn)而得到符合要求的最佳控制系數(shù)，使得重構(gòu)出的曲面質(zhì)量得到提高。在重構(gòu)過(guò)程中，劃分點(diǎn)與塊的歸屬關(guān)系，將原來(lái)計(jì)算點(diǎn)的過(guò)程轉(zhuǎn)化為計(jì)算塊的過(guò)程，并且降低邊界處點(diǎn)的重復(fù)運(yùn)算，減少了計(jì)算次數(shù)，降低了運(yùn)算量，從而提高了重構(gòu)曲面的速度。最后通過(guò)實(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é)報(bào),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ù)值流形方法與時(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ì)算機(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ì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條：CAGD&NURBS[M]．北京：北京航空航天大學(xué)出版社,1994.

[15] 王仁宏,崔錦泰.關(guān)于一個(gè)二元B樣條基[J]．中國(guó)科學(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ò)出版時(shí)間：2017-06-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(60873093)

汪春曉(1991-)，男，碩士生，研究方向?yàn)橛?jì)算機(jī)可視化、計(jì)算幾何；路 游,博士，副教授,研究方向?yàn)橛?jì)算幾何、圖形學(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