射線跟蹤技術(shù)中物體外形精確建模算法

周曉平，　柳朝陽

(1.鄭州大學(xué)信息工程學(xué)院，鄭州450001；　2.鄭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，鄭州450001)

?

射線跟蹤技術(shù)中物體外形精確建模算法

周曉平1，柳朝陽2

(1.鄭州大學(xué)信息工程學(xué)院，鄭州450001；2.鄭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，鄭州450001)

[摘要]為了對(duì)復(fù)雜物體外形進(jìn)行快速精確建模,利用多面體樣條方法進(jìn)行物體表面的設(shè)計(jì)及應(yīng)用研究.通過對(duì)樣條函數(shù)節(jié)點(diǎn)進(jìn)行分類，給出空間中任意拓?fù)浣Y(jié)構(gòu)網(wǎng)格上樣條函數(shù)組的具體構(gòu)造方法.研究曲線曲面控制點(diǎn)與生成樣條函數(shù)的節(jié)點(diǎn)的相互依賴關(guān)系,提出在無單位分解條件下構(gòu)造具有幾何不變性曲線曲面的合理化方法.通過構(gòu)造控制點(diǎn)處多面體樣條函數(shù)，生成了任意拓?fù)浣Y(jié)構(gòu)的連續(xù)多面體樣條曲面.這樣的多面體樣條曲面在同樣性質(zhì)要求下曲面次數(shù)低，只有張量積NURBS曲面的一半;并且與細(xì)分曲面相比，所獲取的物體外形表面具有坐標(biāo)計(jì)算準(zhǔn)確，中間數(shù)據(jù)較少等優(yōu)點(diǎn)，可以用于精確構(gòu)造電磁射線追蹤中物體的外形.

[關(guān)鍵詞]多面體樣條； 有理函數(shù)； 任意網(wǎng)格； 物體外形； 射線跟蹤

1引言

隨著移動(dòng)通信的發(fā)展, 射線跟蹤技術(shù)被廣泛的應(yīng)用于室內(nèi)定位[1]、無線網(wǎng)絡(luò)規(guī)劃[2]、電磁輻射評(píng)價(jià)[3]中.對(duì)射線跟蹤中所遇到形狀各異的物體，需要對(duì)其外形進(jìn)行快速精確建模.近幾年來，國(guó)內(nèi)外許多學(xué)者[4,5]運(yùn)用拓?fù)渚匦尉W(wǎng)格上的NURBS曲面對(duì)射線跟蹤技術(shù)中的物體外形進(jìn)行建模.

多元樣條函數(shù)曲面是另一種重要的曲面設(shè)計(jì)方法.用多元箱樣條函數(shù)可設(shè)計(jì)一種特定網(wǎng)格上的曲面[6].細(xì)分曲面適宜于任意拓?fù)渚W(wǎng)格上的曲面的設(shè)計(jì)，但是個(gè)極限過程的結(jié)果，不適宜于精確的坐標(biāo)計(jì)算，因此不適合電磁計(jì)算中物體外形快速精確建模.以光滑余因子協(xié)調(diào)方法[7]為核心的多元樣條的代數(shù)幾何方法,把任意剖分下的多元樣條歸結(jié)為方程組求解.但具體的解卻與多元樣條依賴的網(wǎng)格結(jié)構(gòu)有關(guān)，難以有通用曲面設(shè)計(jì)方法.包含不同類型的多元樣條的多面體條[8]進(jìn)行曲面設(shè)計(jì)是計(jì)算幾何中一個(gè)非常重要的課題，有待于進(jìn)一步研究，尋找突破.

本文通過對(duì)多面體樣條的節(jié)點(diǎn)進(jìn)行分類，構(gòu)造了控制點(diǎn)處多面體樣條，生成了任意拓?fù)浣Y(jié)構(gòu)的連續(xù)多面體樣條曲面.這樣的曲面次數(shù)低，坐標(biāo)計(jì)算準(zhǔn)確等，適合電磁計(jì)算中物體外形快速精確建模，有必要深入研究其在電磁計(jì)算中的應(yīng)用.

2多面體樣條

2.1　單個(gè)多面體樣條的構(gòu)造

設(shè)P是Rn+s中以n+s-1-維超平面為邊界的凸多面體，L為Rn+s到Rs的線性映射，則多元的多面體樣條B(x)可定義為

B(x)=voln(P∩L-1x),x∈Rs，

(1)

其中s≥1,n≥0.

若取L=Rs為n+s-維歐氏空間Rn+s中向量到其前s-維向量的投影

Rs(x1,x2,…,xs,xs+1,…,xn+s)=(x1,x2,…,xs),

則由Rn+s中的單純形V可定義s元n次樣條函數(shù)

B(x)=voln(V∩Rs-1x),x∈Rs,

(2)

其中voln表示n-維體積，在n=1時(shí)為長(zhǎng)度.

常見的樣條函數(shù)都是多面體樣條.圖1示出一元一次樣條B(x)的幾何構(gòu)造[6], 圖中節(jié)點(diǎn)滿足：t0

圖1　一元一次樣條函數(shù)的幾何構(gòu)造

2.2　多面體樣條性質(zhì)

由式(1)可推得多面體樣條函數(shù)支撐集為supp(B)=L(P)，并滿足

引理[8]多面體樣條B(x)是一個(gè)分片n-次多項(xiàng)式，并在經(jīng)過其支撐集L(P)的s-1維子區(qū)域L(F)上連續(xù)階為Cn+s-d-2，其中F為P的任意一個(gè)面，而d為L(zhǎng)-1(L(F))的實(shí)際維數(shù).

引理中連續(xù)階的結(jié)論類似于一元樣條的重節(jié)點(diǎn)處連續(xù)階的問題.由于L-1(L(F))?F，而F的維數(shù)為s-1，d≥s-1,n+s-d-2≤n-1.

多面體樣條重節(jié)點(diǎn)要求至少有s+1-個(gè)節(jié)點(diǎn)值在s-1-維子區(qū)域上.對(duì)s=2，等價(jià)于3個(gè)以上的節(jié)點(diǎn)共線.

3任意網(wǎng)格上多面體樣條算法

構(gòu)造多面體樣條函數(shù)的凸多面體P有不同的類型時(shí)就可以構(gòu)造出不同的多元樣條，如箱樣條、錐樣條.但這些傳統(tǒng)的多元樣條都是定義在特定的網(wǎng)格上.在射線追蹤技術(shù)中，必須對(duì)復(fù)雜的物體外形進(jìn)行精確地建模，利用樣條函數(shù)可以實(shí)現(xiàn)此功能，但需要找出在任意網(wǎng)格上構(gòu)造相互關(guān)聯(lián)的樣條組的算法.

3.1　任意網(wǎng)格上多面體樣條組的構(gòu)造

平面網(wǎng)格通常由相互交叉的直線段對(duì)平面分割形成，直線段的端點(diǎn)或交點(diǎn)稱為節(jié)點(diǎn)，兩節(jié)點(diǎn)間的直線段稱為邊.

如圖2所示,平面網(wǎng)格中包含節(jié)點(diǎn)ti的最小多邊形稱為節(jié)點(diǎn)ti的支撐集合，記為supp(ti).節(jié)點(diǎn)ti稱為supp(ti)的內(nèi)(節(jié))點(diǎn).作為多邊形supp(ti)頂點(diǎn)的n個(gè)節(jié)點(diǎn)ti,j(j=1,2,…,n)稱為supp(ti)的(邊)界(節(jié))點(diǎn).通過對(duì)節(jié)點(diǎn)添加分量，構(gòu)造三維空間中的n+1個(gè)加長(zhǎng)向量點(diǎn)(ti,j,0),j=1,2,…,n和(ti,1).如圖3所示，這n+1個(gè)點(diǎn)構(gòu)成了界點(diǎn)圍成的平面多邊形supp(ti)為底面，(ti,1)為頂點(diǎn)的立體錐形多面體pg(ti).

圖2　平面網(wǎng)格的節(jié)點(diǎn)ti及其支撐集　　　圖3 平面網(wǎng)格節(jié)點(diǎn)ti處多面體和樣條

若能保證此錐形多面體pg(ti)每個(gè)點(diǎn)的投影都在底面多邊形supp(ti)內(nèi)，則由pg(ti)各點(diǎn)向底面supp(ti)投影所定義的樣條Bi(t)稱為ti處的二元一階樣條函數(shù).

3.2　任意網(wǎng)格上的多面體樣條公式

節(jié)點(diǎn)ti處的二元一階樣條函數(shù)Bi(t)的值是多面體底面上各點(diǎn)的高程值，是個(gè)真正的一次曲面函數(shù).保證這個(gè)函數(shù)關(guān)系成立不需要supp(ti)為凸集.

設(shè)平面函數(shù)li,j(t)滿足

li,j(ti,j)=0,li,j(ti,j+1)=0,li,j(ti)=1,

(3)

即為一個(gè)過節(jié)點(diǎn)tij,tij+1直線方程函數(shù)，則有

定理任意網(wǎng)格中節(jié)點(diǎn)ti處的二元一階樣條函數(shù)Bi(t)可表示為

(4)

其中Δi,j表示三個(gè)節(jié)點(diǎn)ti,j,ti,j+1和ti給出的三角形.

4任意網(wǎng)格上連續(xù)性多元樣條曲面設(shè)計(jì)算法

4.1　樣條函數(shù)曲線及性質(zhì)

基于一元樣條函數(shù)的B樣條曲線具有如下表示形式和性質(zhì).

(i) (整體性)B樣條曲線存在于整個(gè)參數(shù)空間，具有無限的表示形式

(5)

而Bi,k(t)是相應(yīng)于參數(shù)空間中給定節(jié)點(diǎn)序列

-∞<…≤t-1≤t0≤t1≤…≤ti-1≤ti≤…<+∞

(6)

的k-階樣條函數(shù).

(ii) (局部性)式(5)中Bi,k(t)的有界支撐集使得單獨(dú)某個(gè)控制點(diǎn)Pi只對(duì)有限范圍的P(t)有影響，使得P(t)可定義在有限范圍內(nèi)，可定義在在相互分離的區(qū)間段上.P(t)的計(jì)算實(shí)際上只有有限項(xiàng).

(iii) (光滑性)Bi,k(t)的k-1-階光滑性保證了P(t)的k-1-階光滑性.因此，樣條函數(shù)階數(shù)的選取直接依據(jù)對(duì)最終生成曲線的光滑性的要求而定.

(iv) (非負(fù)單位分解性)式(5)中的所有k-階樣條函數(shù)Bi,k(t)滿足

(7)

使得曲線P(t)具有仿射不變性和凸包性質(zhì)[9].并且由于Bi,k(t)的有限支撐集，P(t)只是位于相關(guān)控制點(diǎn)，而非全體控制點(diǎn)的凸包之內(nèi)，這使得P(t)具有更緊湊的凸包性質(zhì).

(v) (易擴(kuò)展性)實(shí)際應(yīng)用中，常常給出有限個(gè)控制點(diǎn)Pi，并由此構(gòu)造有限范圍內(nèi)的P(t).同時(shí)，增加或減少一個(gè)控制點(diǎn)只是P(t)相應(yīng)地增加或減少了一段，但P(t)作為一條完整的曲線，整體性質(zhì)不變.

4.2　任意形狀物體外形曲面算法及性質(zhì)

將式(5)中的Bi,k(t)換成二元樣條Bi(t)，就可以構(gòu)造任意網(wǎng)格上物體外形曲面.控制點(diǎn)Pi分布在網(wǎng)格節(jié)點(diǎn)處，形成與節(jié)點(diǎn)、二元樣條Bi(t)的相互對(duì)應(yīng).

通過一個(gè)一個(gè)的多面體樣條函數(shù)的性質(zhì)保證網(wǎng)格上的所有多面體二元樣條函數(shù)與曲面滿足4.1小節(jié)中的性質(zhì)(ii)、(iii)及(iv).如箱樣條、基于單純形剖分的多元樣條基函數(shù)[9]、基于特定網(wǎng)格多面體區(qū)域的多元樣條基函數(shù)[8].但將網(wǎng)格上的所有多面體樣條應(yīng)用于任意形狀物體外形曲面設(shè)計(jì)時(shí)，要使性質(zhì)(iv)成立必然會(huì)引進(jìn)過多的樣條函數(shù)；要使性質(zhì)(v)成立，在增減一個(gè)控制點(diǎn)時(shí)會(huì)增減太多基函數(shù).另外，式(7)也不能保證必然成立.

(8)

如果想適當(dāng)調(diào)整各個(gè)控制點(diǎn)的貢獻(xiàn)大小的似然比例值，則可定義

(9)

對(duì)于有限多個(gè)控制點(diǎn)Pi,i∈I，可定義

(10)

但參數(shù)t的取值范圍不是∪i∈Isupp(Bi,k)，而是∪i?Isupp(Bi,k)的補(bǔ)集.這保證了在增加控制點(diǎn)時(shí)新增加的曲線段、曲面片與已定義的部分既能合理拼接(保持必要的光滑性)，又互不影響.

4.3　不同類型網(wǎng)格物體外形曲面構(gòu)造算法

下面給出不同網(wǎng)格上曲面的構(gòu)造模型.

(i) 三角網(wǎng)格中的二元一階樣條函數(shù)及曲面:若所有數(shù)據(jù)已經(jīng)三角化，利用此三角網(wǎng)格上二元一階樣條函數(shù)定義的曲面就是每個(gè)三角形的三個(gè)節(jié)點(diǎn)處的三個(gè)控制點(diǎn)為一組定義的平面三角形塊組成的多面體曲面.若所有的supp(Pi)覆蓋每個(gè)三角形網(wǎng)格恰好三次，則所有數(shù)據(jù)點(diǎn)處樣條的和恒為1，即4.1小節(jié)的性質(zhì)(iv)成立.否則，不成立.

(ii) 四邊形網(wǎng)格的二元一階樣條函數(shù)及曲面:若所有數(shù)據(jù)具有四邊形剖分，則此網(wǎng)格二元一階樣條函數(shù)定義的曲面就是四邊形每一點(diǎn)與其它頂點(diǎn)相連的平面三角形片為一組聯(lián)合組成的多面體曲面，是分片連續(xù)的一次曲面.四邊形剖分中網(wǎng)格大小可以不一致.對(duì)網(wǎng)格大小一致的矩形剖分?jǐn)?shù)據(jù)，此曲面不同于矩形網(wǎng)格上笛卡爾乘積型的雙一次曲面.雙一次曲面是二次曲面.

(iii) 任意網(wǎng)格的二元一階樣條函數(shù)及曲面:若所有數(shù)據(jù)具有一般的多邊形剖分，則此二元一階樣條函數(shù)定義的曲面在多邊形剖分內(nèi)為分片連續(xù)的一次曲面組成.一次曲面的片數(shù)與描述的對(duì)角線剖分多邊形區(qū)域數(shù)目相同，是隨多邊形邊數(shù)快速增加的很大的值[10].任意網(wǎng)格可以包含三角、四邊形，甚至其他類型的混合網(wǎng)格.樣條函數(shù)是根據(jù)控制點(diǎn)定義的，不同的控制點(diǎn)處的樣條函數(shù)網(wǎng)格形式是不一樣的，求解結(jié)果也不一樣.但依據(jù)多面體樣條的定義不難統(tǒng)一求得.

5結(jié)論

本文提出的算法可以用于構(gòu)造控制點(diǎn)處二元一階樣條函數(shù)，生成任意拓?fù)浣Y(jié)構(gòu)上連續(xù)的二元一次樣條曲面；這樣的多元樣條函數(shù)曲面具有曲面次數(shù)低，坐標(biāo)計(jì)算準(zhǔn)確，中間數(shù)據(jù)較少等優(yōu)點(diǎn)，非常適合電磁射線跟蹤中物體外形精確構(gòu)造及應(yīng)用.由此可見，二階，甚至更高階光滑度的多面體樣條，以及相應(yīng)的多元樣條曲面的構(gòu)造方法及在工程中的應(yīng)用是值得進(jìn)一步研究的問題.

[參考文獻(xiàn)]

[1]袁正午，王丹丹.基于射線跟蹤和Voronoi圖的室內(nèi)定位算法[J].計(jì)算機(jī)應(yīng)用研究, 2013, 30(2): 399-401.

[2]霍羽, 徐釗,劉逢雪.融合波模和射線理論的礦井電波傳播模型[J].電子學(xué)報(bào), 2013, 41(1): 110-115.

[3]周曉平，譚鳳杰，柳朝陽，等.射線跟蹤技術(shù)的一種加速算法[J].電波科學(xué)學(xué)報(bào)，2013，28(3):491-497.

[4]PerezJ，CatedraMF.ApplicationofphysicalopticstotheRCScomputationofbodiesmodeledwithNURBSsurfaces[J].IEEETransactionsonAntennasandPropagation, 1994, 42(10): 1404-1411.

[5]王楠,袁浩波,梁昌洪.應(yīng)用NURBS-UTD方法分析受擾方向圖[J].電子學(xué)報(bào)，2010,38(6): 1323-327.

[6]ZhangYong-Chun,DaFei-Peng,SongWen-Zhong.PiecewiseC1surfacesbasedonbivariatequarticbox-Splinesforarbitrarytriangularmeshes[J].JournalofSoftware, 2006, 17(10): 2211-2220.

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

[8]GoodmanT.Polyhedralsplines[C]∥DahmenW,GascaM,MicchelliCA.Computationofcurvesandsurfaces.Kluwer,Dordrecht,SpringerNetherlands,1990:347-382.

[9]TraasC.Practiceofbivariatequadraticsimplicialsplines[C]∥DahmenW,GascaM,MicchelliCA.Computationofcurvesandsurfaces.Kluwer,Dordrecht,SpringerNetherlands, 1990:383-422.

[10]LiuChao-yang.TheoryandapplicationofconvexcurvesandsurfacesinCAGD[M].ISBN90-365-1577-7，PressofUniversityofTwente, 2001.

AlgorithmofPrecisionModelingBodySurfaces

inElectronicRay-TracingTechnique

Zhou Xiao-ping1，Liu Chao-yang2

(1.SchoolofInformationEngineering，ZhengzhouUniversity，Zhengzhou450001，China;

2.SchoolofMathematics&Statistics，ZhengzhouUniversity，Zhengzhou450001，China)

Abstract:Inordertomodelthecomplexbodysurfacesinelectronicray-tracingquicklyandaccurately,thepolyhedronsplinemethodisemployedintheresearchonbodysurfacedesigningandapplication.Byclassifyingknotsrelatedtosplinefunctions,amethodispresentedforgeneratecertainsplinefunctionsoverameshwitharbitrarytopologicalstructureinspace.Theinterdependentrelationshipbetweencontrolpointsforacurveorsurfaceandthemeshknotsforsplinefunctionsisdiscussed.Thecurveorsurfacewithblendingfunctionsofnon-unitdecompositionpropertyisdesigned,withgeometricalinvarianceandconvexhullproperty.Byconstructingcontrolpolyhedronsplinefunctionsatcontrolpointsdistributedinameshwitharbitrarytopology,acontinuouspolyhedronsplinebodysurfaceoverarbitrarytopologyisgenerated.AsonlyhalforderofthecontinuoustensorproducttypeNURBSsurface,orderforthecontinuouspolyhedronsplinesurfaceislow.Comparingtosubdivisionsurfacewhichislimitingresult,thissurfacecanbeobtainedexactly,withlessprocessingdata,and,canbeusedforprecisioncomplexbodysurfacesinelectromagneticraytracing.

Keywords:polyhedralspline;rationalfunction;arbitrarymeshes;bodysurface;electromagneticraytracing

[基金項(xiàng)目]河南省重點(diǎn)科技攻關(guān)項(xiàng)目(142102210492，132102210194)

[收稿日期]2014-05-08;[修改日期] 2014-11-08

[中圖分類號(hào)]TP391.72;O241.3

[文獻(xiàn)標(biāo)識(shí)碼]B

[文章編號(hào)]1672-1454(2015)01-0021-05