基于等值線法求取NURBS曲面與隱式曲面交線的原理，我們提出了一種局部加密的改進(jìn)算法。通過局部加密算法減少正則網(wǎng)格單元頂點處^值計算數(shù)目。采用擬牛頓迭代法求交點、B樣條曲線擬合參數(shù)域上的交線等改進(jìn)算法，提高了NURBS曲面與隱式曲面求交算法的效率和精度，并通過MATLAB編程進(jìn)行了驗證。

一、全網(wǎng)格遍歷法求解NURBS曲面與隱式曲面交線

1、基本原理

設(shè)NURBS曲面為x=g1(u，v），y=g2(u，v），z=g3(u，v），控制頂點Pij（i=0，1，…，n1；j=0，1，…，n1）呈拓?fù)渚匦侮嚵校纬梢粋€控制網(wǎng)格。ωij是與頂點Pij聯(lián)系的權(quán)因子。Bik1(u)和色，Bjk2(v)分別為u向k1次和v向k2次規(guī)范B樣條基。

設(shè)隱式曲面為f(x，y，Z）=0，其中廠的定義域為Ωf，則NURBS曲面與隱式曲面的交線方程為：f(g1，g2，g3）=h(u，v）=O的求解過程實際上就是曲面求交的過程。

2、全網(wǎng)格遍歷求解多項式方程

（1）正則化網(wǎng)格的生成

曲面參數(shù)化后，將參數(shù)域Ωg沿u、v方向分別分為nu,nv份。每一個矩形單元△i,j的四個頂點分別為(ui,vj)， (ui,vj+1），(ui+1，vj+1), (ui+1，vj), (i=0,1，…，nu-1；j=0，1，…，nv-1)。對應(yīng)的函數(shù)值為hij ，hi,j+1，hi+1J+1，hi+1J(i=0,1，…，nu-l;j=0,1，…，nv-1)。

(2)網(wǎng)格單元與等值線的交點計算

網(wǎng)格單元與等值線交點計算，主要是計算單元各邊與等值線的交點，可以采用頂點判斷和邊上插值的方法計算交點，具體步驟如下：

1)若hiJ≤0，則頂點(ui,uj）記為“-”，否則記為“+”；

2)若單元的4個頂點都為“+"，或全為“-”，則網(wǎng)格單元與等值線h(u,v）=O無交點，否則轉(zhuǎn)到3）；

3)對于兩個頂點異號的單元邊，采用擬牛頓迭代法計算等值線與這條邊的交點，如圖2中紅色圓點，設(shè)hi+1,J+1，為“+”，hi+1,j為“-”，則交點(ut，vt)為：

vt=Vi+l（i=2，3，…，n）。該單元其它邊上的交點可用相同方法求得。

3、等值線的生成

逐個計算出每一個網(wǎng)格單元與等值線的交點，用三次B樣條曲線按順序擬合這些交點，最終得到等值線h(u，v）=0。

需要注意的是，采用B樣條曲線擬合單元內(nèi)的交點，必須首先確定這些交點的先后次序。對于形狀比較簡單的等值線，可用其關(guān)鍵信息判斷交點的先后次序。例如與u向傳遞的波浪面相交時，交點可按照其u坐標(biāo)值的大小排序；與圓柱面相交時交點可按照交點和圓心的連線與水平線的夾角大小排序。對于形狀比較復(fù)雜的等值線，目前還未找到完美的解決方法，可采用蟻群算法保證各點之間的總距離最小，以此為原則對數(shù)據(jù)點進(jìn)行排序。

綜上所述，全網(wǎng)格遍歷法求解多項式方程h（u，v）=0的流程。

數(shù)據(jù)取自采用全網(wǎng)格遍歷法編制的matlab程序求解NURBS曲面與圓柱曲面交線過程。本文所用NURBS曲面由201×401個型值點擬合而成，程序運行平臺機型配置為AMD Athlon四核2.8GHz，8G內(nèi)存。

當(dāng)曲面曲率變化劇烈或者對交線精度要求較高時，往往需要較小的網(wǎng)格步長。全網(wǎng)格遍歷要求對每個單元都要求解，由表1可知，當(dāng)網(wǎng)格密度增加時，該算法計算量會成倍增加，導(dǎo)致其耗時也會成倍增加。在網(wǎng)格步長較小時，全網(wǎng)格遍歷求解多項式h（u，v）=O效率很低。

從表1中不難看出，隨著網(wǎng)格步長的減小，需要計算頂點處危值的數(shù)目也越多，而單獨計算各頂點處h值所耗時間占整個求交程序耗時的絕大部分。由此可知，想要提高求交算法的效率，就需要在相同精度要求下，盡量減少尼值的計算數(shù)目。因此在求交過程中引入局部加密算法，期望通過減少危值計算數(shù)目，提高求交算法的效率。

二局部加密算法在NURBS曲面與隱式曲面求交中的應(yīng)用

1、選定正則化基網(wǎng)格

局部加密算法首先需要選定一個網(wǎng)格密度較疏的正則化基網(wǎng)格，基網(wǎng)格的網(wǎng)格步長取△u=△v=△=O.1。求出每個網(wǎng)格單元四個頂點處的函數(shù)值h（u，v），運用全網(wǎng)格遍歷求解算法求出網(wǎng)格單元與等值線的交點，如圖4中紅色星號所示。將頂點處h值儲存在矩陣危。h0（i，j），(i=1，2，…，1/△+1)中。那么h0（i，j）=h((i- 1)△，(j-1）△)。

2、確定加密范圍

以網(wǎng)格步長等于△為例，確定加密范圍的方法如下：

1)將各單元與等值線的交點排序，排序方法與全網(wǎng)格遍歷法中擬合等值線時交點排序的方法相同，排好序的交點分別記為al，a2，…，ak，ak+l，…，an(k=1，…，n）。對于單元i，各頂點編號如圖5所示。以Ai為單元i的參考基點，則Ai的坐標(biāo)為：uAi=fix [min(uk,uk+l)/△]△；：uAi=fix [min(vk,vk+l)/△]△，其中fix為取整函數(shù)。單元中Bi，Ci，Di的坐標(biāo)可通過參考基點Ai的坐標(biāo)求得，例如uBi=uAi+△， VBi =VAi；

2)如圖6所示，按照交點順序依次找到單元參考基點Al，A2，…，Ai，Ai+i，…，Am(=l，…，m)，由單元參考基點依次確定包含交點的每一個單元。

所求等值線必定在這個加密范圍內(nèi)。

3、網(wǎng)格加密

確定需要加密的網(wǎng)格范圍后，將加密范圍內(nèi)的每個單元均分為四個小的單元。

4、數(shù)據(jù)處理

每一次加密網(wǎng)格后，需要更新頂點處h值，為避免重復(fù)計算，需要對數(shù)據(jù)做一些特殊處理：

1）確定加密區(qū)域所在的最小矩形域。

矩形域D1DZD3D4即為加密區(qū)域所在的最小矩形域。

2)生成判斷矩陣。加密最小矩形域，將矩形域內(nèi)每一個單元均分為四個小單元。

為便于后續(xù)計算，在加密后引入判斷矩陣判斷最小矩形域內(nèi)的頂點是否在加密區(qū)域內(nèi)。

3)更新網(wǎng)格頂點處h值，并將其儲存在矩陣hK中。當(dāng)K=1時，h1（i,j)=ho（i+VD1/△,j+VD1/△）。當(dāng)K=2，3時，計算hK。

5、網(wǎng)格加密后單元與等值線交點的計算

在每一次加密網(wǎng)格后，都需要重新計算單元與等值線的交點。

admin

收藏 海報分享