摘　要　介紹一種基于離散曲面的裁剪算法，該算法適用于注塑模CAD/CAE或其它產(chǎn)品設(shè)計(jì)和有限元分析的領(lǐng)域，實(shí)踐證明該算法自動(dòng)化程度高、速度快、穩(wěn)定可靠.
　　
關(guān)鍵詞　曲面裁剪，離散曲面，曲面求交，自動(dòng)搜索

　 1、引　言

　　在注塑模CAD/CAE中，自由曲面的設(shè)計(jì)與描述始終占有十分重要的地位.塑料制品種類繁多、形狀各異，而且注塑成形是一次成形，所以要求注塑模CAD/CAE軟件的幾何造型系統(tǒng)具有較強(qiáng)的曲面處理能力，能夠快速、方便地生成塑料制品圖和模具型腔圖.在實(shí)際工程中有許多產(chǎn)品的某些外表面不能或不便于用一張曲面表示，而用多張曲面構(gòu)造一個(gè)產(chǎn)品的曲面模型時(shí)，某些曲面又有多余部分.因此，利用曲面裁剪技術(shù)把單張曲面不需要的部分裁剪掉或?qū)⒍鄰埱嫫唇雍蟮亩嘤嗖糠植眉舻簦憧梢缘玫剿璧那婺Ｐ?曲面裁剪不僅是構(gòu)造產(chǎn)品曲面模型的重要手段，也是采用縫合技術(shù)構(gòu)造曲面實(shí)體模型必備的操作.
　　由于注塑模CAE分析要求盡可能方便、高效地構(gòu)造出產(chǎn)品的幾何模型，并且對(duì)裁剪曲面或曲面裁剪后拼接成的曲面進(jìn)行網(wǎng)格劃分時(shí)，要求能夠處理公共邊界的信息，即2個(gè)曲面在拼接處具有相同的離散邊界，便于注塑模CAE后續(xù)的流動(dòng)、保壓和翹曲等有限元模擬分析，而對(duì)于曲面的精度允許有一定的誤差，因此本文介紹一種基于離散曲面的裁剪方法.所謂離散曲面，是一類采用組成曲面多邊形網(wǎng)的點(diǎn)、線、面及其拓?fù)湫畔⑼暾拿枋銮?
　　根據(jù)作者的研究和實(shí)踐，認(rèn)為基于注塑模CAD/CAE的曲面裁剪主要涉及以下問題：（1）曲面分割；（2）曲面求交；（3）曲面片的裁剪；（4）生成裁剪曲面的自動(dòng)搜索算法.

2、曲面分割和離散曲面

　　曲面分割是將任意一自由曲面，按照某一給定的分割算法進(jìn)行不斷的分割加密而成，每一次分割均生成一個(gè)比原來的多邊形網(wǎng)更加致密的多邊形網(wǎng)，其極限曲面是一張光滑曲面.在本文中采用文獻(xiàn)［1，2］的分割算法，其中提出了平面度的概念，以平面度作為控制精度，當(dāng)分割的次數(shù)使得多邊形網(wǎng)與極限曲面之離差小于控制精度后，就不再細(xì)分，這時(shí)的多邊形網(wǎng)便是一張離散曲面.

3、離散曲面求交

　　離散曲面的求交實(shí)質(zhì)可歸于一些小的平面多邊形求交，對(duì)于控制精度高的曲面，相應(yīng)的離散網(wǎng)格便很致密，小的平面片就很多，因此提高求交效率對(duì)整個(gè)曲面裁剪的效率非常重要.

3.1　曲面數(shù)據(jù)的存儲(chǔ)

　　曲面的數(shù)據(jù)存儲(chǔ)如圖1所示，分別用3個(gè)鏈表形成的網(wǎng)狀結(jié)構(gòu)存儲(chǔ)曲面（Surface）、網(wǎng)格平面片（Patch）和頂點(diǎn)（Vertex）的數(shù)據(jù)，這種結(jié)構(gòu)便于數(shù)據(jù)的查找，并且存儲(chǔ)冗余小.如圖2所示，一張曲面由n個(gè)Patch組成，如果分別存儲(chǔ)每一個(gè)Patch的頂點(diǎn)信息，則曲面中間的一個(gè)結(jié)點(diǎn)就會(huì)被存儲(chǔ)4次，邊界上的點(diǎn)也會(huì)被存儲(chǔ)2次（除角點(diǎn)外）.而采用圖1所示的存儲(chǔ)結(jié)構(gòu)，Vertex鏈表的結(jié)點(diǎn)與圖2所示的網(wǎng)格結(jié)點(diǎn)一一對(duì)應(yīng)，即只存儲(chǔ)一次，而每個(gè)Vertex表中的結(jié)點(diǎn)與Patch表中的結(jié)點(diǎn)則形成一對(duì)多的關(guān)系.

圖1　曲面的數(shù)據(jù)存儲(chǔ)方式

圖 2　離散曲面

3.2　求交算法

　　步驟1. 遍歷2個(gè)曲面的數(shù)據(jù)鏈，獲取幾何信息，如平面方程、直線方程等.記錄每個(gè)曲面中Patch之間的相鄰關(guān)系，供裁剪后自動(dòng)搜索時(shí)用.
　　步驟2. 由空間坐標(biāo)信息排除根本不可能相交的Patch對(duì)，避免不必要的求交運(yùn)算，求取有可能相交的Patch的交點(diǎn).
　　步驟3. 交點(diǎn)的有效性判斷.如圖3所示，交點(diǎn)必須同時(shí)在Patch1所表示的多邊形區(qū)域內(nèi)和 Patch2的一條邊界所在的線段內(nèi).后者判斷很簡(jiǎn)單，對(duì)前者處理本文采用射線法［3］.

圖3　兩平面片相交

步驟4. 交點(diǎn)排序.前面的Patch對(duì)相交時(shí)，記錄下相交線段，便可通過線段頂點(diǎn)比較法將每個(gè)Patch內(nèi)隨機(jī)求出的交線排序，如圖4所示.

圖4　平面片求交后交點(diǎn)排序

步驟5. 處理交線通過Patch的頂點(diǎn)或邊的特殊情況.
　　步驟6. 循環(huán)處理完2個(gè)曲面鏈表中的每個(gè)Patch.
4、曲面裁剪

　　為了使曲面裁剪具有自動(dòng)化的能力，即在求交結(jié)束后就能自動(dòng)分為要保留和要裁剪掉的2個(gè)部分，然后由用戶交互取舍，而且要滿足注塑模CAE中網(wǎng)格劃分對(duì)公共邊界的要求，作者設(shè)計(jì)了一種及時(shí)分片法，算法如下：
　　步驟1. 對(duì)裁剪曲面中每個(gè)Patch在求交完畢后隨即將其分割成2個(gè)或多個(gè)Patch，不論是2個(gè)或多個(gè)Patch，必須按一定規(guī)則將其分為2類，一類保留，另一類裁剪掉，因而稱為及時(shí)分片法.如圖5所示，一般情況下一個(gè)Patch被一分為二，則這2個(gè)新生成的Patch自然分為上述2類.但在某些情況下，也可能被分為多個(gè)Patch，如圖6所示.用逐次二分法將其分解為多個(gè)Patch后，本文采用交線包容法，同樣可將這多個(gè)Patch分為2類，如圖7所示.所謂交線包容法是將包含原Patch內(nèi)所有交線的多邊形作為一類，如圖7(a)所示，其它的作為另一類，如圖7(b)所示.

圖 5　1個(gè)平面片裁剪后生成2個(gè)平面片

圖 6　逐次二分法分解平面片

圖 7　交線包容法分類

步驟2. 將新生成的Patch加入到Patch鏈表中，去掉原Patch.
　　步驟3. 處理如圖8所示的特殊情況.一個(gè)Patch中出現(xiàn)內(nèi)環(huán)，無法用2個(gè)多邊形來描述分割后的圖形，對(duì)這種情況本文采取加密離散網(wǎng)格的方法，避免出現(xiàn)內(nèi)環(huán).

圖 8　平面片內(nèi)環(huán)情況

5、生成裁剪曲面的自動(dòng)搜索算法

　　圖9為求交后的結(jié)果，被裁剪曲面中有一部分Patch是將原Patch裁剪生成的，稱為新Patch，如Patch1，2，3，而有一部分是沒被裁剪到的，稱為原Patch，如Patch4，5，下面分別討論這2種Patch的搜索算法.

圖 9　曲面求交后的搜索

5.1　新Patch的搜索算法

　　步驟1.　由一個(gè)新Patch找到與之具有相鄰公共邊的新Patch，如圖9中由Patch3可找到Patch1，2.
　　步驟2. 排除不同類的Patch.這里的分類仍按照是裁剪部分或是保留部分來區(qū)分，如圖9中Patch1和Patch3是由同一個(gè)原Patch裁剪后得到的，顯然它們是不同類.從步驟1搜索結(jié)果中排除Patch1，即由Patch3搜索到Patch2，這樣可保證搜索到的Patch為同類，即同為需保留或同為需裁剪掉的部分.
　　步驟3. 遍歷Patch鏈表中新生成的Patch就能找出全部的同類新Patch.
　　步驟4. 處理特殊情況.
　　如圖10所示交線經(jīng)過Patch1，2，3，4的公共頂點(diǎn)，由Patch3按相鄰邊關(guān)系不能直接找到Patch5，對(duì)于這種情況，本文在求交過程記錄Patch1，4為新Patch，則可用步驟1中統(tǒng)一的相鄰邊搜索算法，由Patch3→Patch4→Patch5.對(duì)交線經(jīng)過Patch某一邊的特殊情況也可作類似處理.

圖10　交線通過公共頂點(diǎn)

5.2　原Patch的搜索

　　由5.1節(jié)中已找到的一個(gè)新Patch搜索與其有相鄰邊的原Patch，然后由該P(yáng)atch的相鄰關(guān)系即可高效地搜索出所有同類的原Patch，如圖9中由Patch3→Patch4→Patch5→….相鄰關(guān)系在求交過程中獲得，由相鄰關(guān)系搜索避免了循環(huán)遍歷整個(gè)Patch鏈表，大大提高了搜索效率.
　　將以上2個(gè)搜索過程的結(jié)果合并就得到了一類裁剪曲面，相應(yīng)的另一類裁剪曲面則由剩余的Patch構(gòu)成，裁剪過程完畢.以上算法對(duì)封閉交線仍然適用，如圖11所示.

圖 11　交線封閉情況的裁剪結(jié)果

6、算法評(píng)價(jià)和圖形實(shí)例

　　本算法是以離散曲面為基礎(chǔ)，針對(duì)兩串離散網(wǎng)格鏈表進(jìn)行的，因此對(duì)于任何曲面，只要經(jīng)過曲面分割得到離散曲面就可以用本算法進(jìn)行裁剪.裁剪的準(zhǔn)確度依賴于曲面分割的精度和密度.考慮到曲面裁剪的自動(dòng)性要求，本算法適合于兩曲面僅有一條交線的情況，如果交線多于一條，可先把曲面分為幾塊后再裁剪，如球面開通孔即為這種情況.
　　該算法應(yīng)用于注塑模CAD/CAE中的一個(gè)顯著的優(yōu)點(diǎn)是便于后續(xù)的有限元分析，裁剪后的拼合曲面直接滿足公共邊界處理的要求，可生成連通的有限元網(wǎng)格，該算法同樣也適合于其它產(chǎn)品設(shè)計(jì)和應(yīng)用有限元分析的領(lǐng)域.如圖12所示的鼠標(biāo)模型為兩曲面經(jīng)幾次裁剪后拼接而成的曲面，圖13為鼠標(biāo)模型的網(wǎng)格劃分結(jié)果，圖14為鼠標(biāo)模型的流動(dòng)分析結(jié)果（流動(dòng)前沿的等值線圖）.

圖 14　鼠標(biāo)模型的流動(dòng)模擬結(jié)果

應(yīng)用上述算法作者開發(fā)出的軟件已應(yīng)用于本實(shí)驗(yàn)室的注塑模CAD/CAM/CAE集成系統(tǒng)中，實(shí)踐證明該算法自動(dòng)化程度高、速度快，并且穩(wěn)定可靠.