快速計(jì)算平面與高精度細(xì)分曲面交線的方法

朱建寧，王敏杰，魏兆成，曹 斌

（大連理工大學(xué) 機(jī)械工程學(xué)院，遼寧 大連 116024）

0 引言

細(xì)分曲面建模法可以輕易構(gòu)造具有任意拓?fù)浣Y(jié)構(gòu)的光滑曲面，廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)、影視、動(dòng)畫等領(lǐng)域。曲面求交［1］是計(jì)算機(jī)輔助幾何設(shè)計(jì)領(lǐng)域中的關(guān)鍵問(wèn)題，其中平面與曲面求交是數(shù)控加工［2］、3D打印、快速原型［3］等領(lǐng)域中的基礎(chǔ)問(wèn)題?？焖?、穩(wěn)定和高精度的平面與細(xì)分曲面求交技術(shù)有利于細(xì)分曲面在工業(yè)領(lǐng)域更廣泛的應(yīng)用。

由于細(xì)分曲面沒有整體的解析表達(dá)式，在實(shí)際應(yīng)用中，常常采用一定細(xì)分次數(shù)的控制網(wǎng)格代替細(xì)分曲面進(jìn)行各種操作。理論上，一些平面與多邊形網(wǎng)格求交的方法也適用于解決平面與細(xì)分曲面求交的問(wèn)題。但在高精度細(xì)分曲面龐大的數(shù)據(jù)量和復(fù)雜拓?fù)浣Y(jié)構(gòu)的情況下，這種把細(xì)分曲面當(dāng)作一般多邊形網(wǎng)格的做法并不能獲得較好的計(jì)算性能。在細(xì)分曲面之間求交的研究中，一些學(xué)者［4－7］利用二部圖理論和局部細(xì)分技術(shù)，通過(guò)低層次控制網(wǎng)格之間相交區(qū)域的逐次求精，當(dāng)控制網(wǎng)格的細(xì)分次數(shù)達(dá)到預(yù)設(shè)值時(shí)才進(jìn)行細(xì)分曲面之間的求交。這類方法有效地控制了相交的網(wǎng)格邊和網(wǎng)格面的搜索范圍，提高了求交的效率。但這類方法也存在一定的局限性，由于控制網(wǎng)格的“收縮”特性，有可能會(huì)出現(xiàn)“多交”和“漏交”兩種情況：低層次控制網(wǎng)格之間相交而細(xì)分曲面之間并不相交；低層次控制網(wǎng)格之間不相交而細(xì)分曲面之間相交。還有一些學(xué)者［8－9］基于細(xì)分曲面的參數(shù)化表示，研究了細(xì)分曲面求交和裁剪問(wèn)題。在數(shù)控加工和快速原型等領(lǐng)域，為獲得加工軌跡，常常需要對(duì)同一細(xì)分曲面模型與大規(guī)模平面組進(jìn)行多次求交，顯然上述一些求交方法的效率有待提高。

對(duì)于基于網(wǎng)格模型的求交計(jì)算，如何快速、準(zhǔn)確和穩(wěn)定地搜索出相交的網(wǎng)格邊是最基礎(chǔ)也是最重要的問(wèn)題。高精度細(xì)分曲面龐大的數(shù)據(jù)量和復(fù)雜的拓?fù)浣Y(jié)構(gòu)，為高效搜索相交的網(wǎng)格邊增加了難度。與現(xiàn)有方法不同，本文并沒有把細(xì)分曲面當(dāng)作一般多邊形網(wǎng)格模型對(duì)待，而是利用細(xì)分曲面控制網(wǎng)格的拓?fù)浣Y(jié)構(gòu)特性，實(shí)現(xiàn)了 Catmull－Clark［10］細(xì)分曲面的分片表示，進(jìn)而將平面與復(fù)雜細(xì)分曲面模型的求交問(wèn)題轉(zhuǎn)化為平面與形狀簡(jiǎn)單的細(xì)分曲面面片的求交問(wèn)題。針對(duì)平面與細(xì)分曲面面片求交問(wèn)題，根據(jù)細(xì)分曲面面片規(guī)則的拓?fù)浣Y(jié)構(gòu)，分別建立細(xì)分曲面面片多級(jí)分割技術(shù)和交線追蹤策略，以此為基礎(chǔ)，快速、穩(wěn)定地實(shí)現(xiàn)了平面與細(xì)分曲面面片的相交性判斷和交線計(jì)算。

1 Catmull－Clark細(xì)分曲面的分片表示

Catmull－Clark細(xì)分曲面采用1～4面分裂的拓?fù)浞至岩?guī)則生成新網(wǎng)格，屬于四邊形網(wǎng)格的逼近型細(xì)分模式。作為雙三次均勻B樣條曲面的推廣，Catmull－Clark細(xì)分曲面具有良好的曲面連續(xù)性，除了在個(gè)別奇異頂點(diǎn)處為C1連續(xù)外，在其余各處均為C2連續(xù)。如果內(nèi)部頂點(diǎn)的價(jià)（共享此頂點(diǎn)的邊的數(shù)量）不等于4，則稱該頂點(diǎn)為奇異頂點(diǎn)。Catmull－Clark細(xì)分模式生成的新點(diǎn)可以分為新面點(diǎn)、新邊點(diǎn)和新頂點(diǎn)三個(gè)基本類型，對(duì)于邊界情況，還有邊界新邊點(diǎn)和邊界新頂點(diǎn)。圖1給出了Catmull－Clark細(xì)分算法的細(xì)分模板，圖中：新頂點(diǎn)由空心圓點(diǎn)表示，原網(wǎng)格頂點(diǎn)由圓點(diǎn)表示。

圖2中的初始控制網(wǎng)格經(jīng)過(guò)三次Catmull－Clark細(xì)分后，每個(gè)初始控制網(wǎng)格中的四邊形面片都轉(zhuǎn)變?yōu)槌史疥嚺帕械乃倪呅蚊嫫M，這樣的面片組稱為細(xì)分曲面面片（Subdivision Surface Patch，SSP）。不論拓?fù)浣Y(jié)構(gòu)多么復(fù)雜的Catmull－Clark細(xì)分曲面，都可以分解為若干個(gè)具有相同拓?fù)浣Y(jié)構(gòu)的SSP。這不僅是Catmull－Clark控制網(wǎng)格不同于一般多邊形網(wǎng)格的拓?fù)浣Y(jié)構(gòu)特性，也是分片表示Catmull－Clark細(xì)分曲面的理論基礎(chǔ)。

為獲得更高的平面與細(xì)分曲面求交的計(jì)算性能，本文采用元胞結(jié)構(gòu)［11］實(shí)現(xiàn)了細(xì)分曲面的分片表示。元胞內(nèi)層結(jié)構(gòu)由一個(gè)二維數(shù)組和若干個(gè)一維數(shù)組構(gòu)成。二維數(shù)組表示SSP，稱其為元胞數(shù)組（Ac）；一維數(shù)組表示SSP的鄰域結(jié)構(gòu)。根據(jù)鄰域結(jié)構(gòu)輔助細(xì)分作用的不同，可以將鄰域結(jié)構(gòu)分為輔助SSP邊界細(xì)分結(jié)構(gòu)（Ae）和輔助SSP角點(diǎn)細(xì)分結(jié)構(gòu)（Av）。元胞外層結(jié)構(gòu)可以采用半邊結(jié)構(gòu)，通過(guò)半邊結(jié)構(gòu)記錄初始控制網(wǎng)格的拓?fù)浣Y(jié)構(gòu)來(lái)表示SSP之間的拓?fù)潢P(guān)系。如圖3所示，圖3a為帶邊界的SSP及其鄰域結(jié)構(gòu)所組成的初始控制網(wǎng)格，圖3b表明了網(wǎng)格頂點(diǎn)與元胞內(nèi)層結(jié)構(gòu)的對(duì)應(yīng)關(guān)系。其中：Av1，Av2，Av3和Av4分別為輔助SSP角點(diǎn)細(xì)分的結(jié)構(gòu)，Ae1，Ae2和Ae3分別為輔助SSP邊界細(xì)分的結(jié)構(gòu)。應(yīng)用元胞結(jié)構(gòu)可以將Catmull－Clark細(xì)分曲面的整體細(xì)分轉(zhuǎn)化為各個(gè)元胞的局部細(xì)分。圖3c為初始元胞結(jié)構(gòu)細(xì)分一次后的結(jié)構(gòu)。這種分片實(shí)現(xiàn)Catmull－Clark細(xì)分曲面的方式并沒有改變基本的細(xì)分規(guī)則，其中正確判斷新點(diǎn)的類型并采用對(duì)應(yīng)的細(xì)分模板，是確保元胞局部細(xì)分順利進(jìn)行的關(guān)鍵。

2 細(xì)分曲面面片多級(jí)分割

經(jīng)過(guò)N次細(xì)分后，SSP網(wǎng)格的拓?fù)浣Y(jié)構(gòu)是一個(gè)大小為（2 N＋1）2的方陣，其中包含四邊形面的數(shù)量為4N。如果把細(xì)分N次的SSP均勻分割為4個(gè)子面片，則每個(gè)子面片網(wǎng)格的拓?fù)浣Y(jié)構(gòu)都是大小為（2N－1＋1）2的方陣，其中包含四邊形面的數(shù)量為4N－1，將這次分割定義為第一級(jí)分割。由此可見，細(xì)分N次的SSP進(jìn)行第一級(jí)分割后，所獲得的子面片網(wǎng)格的拓?fù)浣Y(jié)構(gòu)與細(xì)分N－1次的SSP網(wǎng)格的拓?fù)浣Y(jié)構(gòu)相同。同時(shí)，所獲得的子面片可以進(jìn)行下一級(jí)分割。對(duì)于細(xì)分N次的SSP可以進(jìn)行N級(jí)分割，第M級(jí)分割最多可以形成4M個(gè)大小為（2N－M＋1）2的方陣網(wǎng)格。SSP多級(jí)分割結(jié)合軸對(duì)稱包圍盒（Axis Aligned Bounding Box，AABB）干涉檢測(cè)技術(shù)，可以快速排除不與平面相交的分割子面片。通過(guò)相交子面片的逐級(jí)分割，不斷縮小相交網(wǎng)格面的搜索范圍。在該過(guò)程中，如果某一級(jí)分割后所有子面片的AABB與平面均不相交，則說(shuō)明該SSP與平面不相交。SSP多級(jí)分割并不是真正分割網(wǎng)格，而是為了提取特定范圍內(nèi)的網(wǎng)格頂點(diǎn)創(chuàng)建AABB。由于SSP頂點(diǎn)的坐標(biāo)存儲(chǔ)在Ac中，通過(guò)確定Ac行列索引的取值范圍就可以提取對(duì)應(yīng)的頂點(diǎn)。多級(jí)分割的子面片采用如下公式表示：式中：二維數(shù)組An1，An2，An3和An4分別表示由第n級(jí)分割獲得的四個(gè)子面片；in1，jn1，in2，jn2，in3，jn3，in4和jn4分別為對(duì)應(yīng)二維數(shù)組的起始行列索引；ln為第n級(jí)分割子面片的二維數(shù)組中終止行列索引與起始行列索引之差；in－1和jn－1分別為第n級(jí)被分割面片的二維數(shù)組的起始行列索引；i0和j0分別為Ac的起始行列索引。因此，只要確定第n級(jí)被分割面片的二維數(shù)組的起始行列索引，就可以提取由第n級(jí)分割獲得的四個(gè)子面片。圖4所示為細(xì)分三次的SSP多級(jí)分割的具體過(guò)程，深色的子面片表示被分割的面片。

3 平面與細(xì)分曲面面片求交

平面與SSP求交可以分為以下三個(gè)步驟：①計(jì)算交線的起始交點(diǎn)并確定交線類型；②計(jì)算交線的后續(xù)交點(diǎn)；③判定交線的終止交點(diǎn)。

3．1 計(jì)算起始交點(diǎn)并確定交線類型

將平面與SSP交線的第一個(gè)交點(diǎn)定義為起始交點(diǎn)，圖5所示的實(shí)心圓點(diǎn)即為起始交點(diǎn)。細(xì)分次數(shù)為N 的SSP中含有網(wǎng)格邊的數(shù)量為22N＋1＋2N＋1。若直接提取SSP的網(wǎng)格邊并與平面進(jìn)行相交測(cè)試，則效率較低，特別是當(dāng)SSP的細(xì)分次數(shù)較高時(shí)。在碰撞檢測(cè)中，常常采用包圍盒近似表示復(fù)雜物體，以提高碰撞檢測(cè)的效率。結(jié)合平面與AABB的相交檢測(cè)技術(shù)和SSP多級(jí)分割，計(jì)算起始交點(diǎn)的步驟如下：

步驟1 創(chuàng)建SSP的AABB，并與平面進(jìn)行相交檢測(cè)。如果平面與AABB不相交，則說(shuō)明平面與SSP不存在交線，結(jié)束程序。

步驟2 提取SSP的邊界網(wǎng)格邊，并與平面進(jìn)行相交檢測(cè)。如果檢測(cè)到與平面相交的網(wǎng)格邊，則計(jì)算起始交點(diǎn)并結(jié)束程序。

步驟3 設(shè)置n的初始值為1，將SSP進(jìn)行第n級(jí)分割。

步驟4 分別對(duì)獲得的分割子面片創(chuàng)建AABB，并與平面進(jìn)行相交檢測(cè)。如果所有第n級(jí)分割子面片的AABB與平面均不相交，則結(jié)束程序。

步驟5 提取與平面相交的AABB中子面片的邊界網(wǎng)格邊，并與平面進(jìn)行相交檢測(cè)。如果檢測(cè)到與平面相交的網(wǎng)格邊，則計(jì)算起始交點(diǎn)并結(jié)束程序。

步驟6 如果n＜N，則N為SSP的細(xì)分次數(shù)，n＝n＋1，轉(zhuǎn)步驟3。否則，結(jié)束程序。

根據(jù)起始交點(diǎn)位于SSP中的拓?fù)湮恢?，可以把平面與SSP的交線分為兩種類型：如果起始交點(diǎn)位于SSP的邊界，則將此時(shí)的交線定義為線型交線；如果起始交點(diǎn)位于SSP的內(nèi)部，則將此時(shí)的交線定義為環(huán)型交線。圖5a和圖5b所示分別為線型交線和環(huán)型交線。

3．2 計(jì)算后續(xù)交點(diǎn)

假設(shè)平面與四邊形網(wǎng)格面存在兩個(gè)交點(diǎn)，如果其中一個(gè)交點(diǎn)已知，則另一個(gè)待求交點(diǎn)可以稱為已知交點(diǎn)的后續(xù)交點(diǎn)。根據(jù)交點(diǎn)的拓?fù)湮恢?，可以將平面與四邊形網(wǎng)格面的交點(diǎn)分為兩種類型：①如果交點(diǎn)位于網(wǎng)格邊的內(nèi)部，則稱其為邊交點(diǎn)；②如果交點(diǎn)位于網(wǎng)格邊的端部，則稱其為點(diǎn)交點(diǎn)。為區(qū)分不同方位的交點(diǎn)，每種類型的交點(diǎn)還可以分為四種情況。當(dāng)已知交點(diǎn)的具體類型和情況確定后，在四邊形網(wǎng)格面中提取對(duì)應(yīng)的網(wǎng)格邊與平面進(jìn)行相交檢測(cè)，可以獲得后續(xù)交點(diǎn)。當(dāng)?shù)貌坏胶罄m(xù)交點(diǎn)時(shí)終止計(jì)算程序。如圖6所示，圓點(diǎn)表示已知交點(diǎn)，線段表示對(duì)應(yīng)的網(wǎng)格邊，圖6a～圖6d描述了四種邊交點(diǎn)對(duì)應(yīng)的網(wǎng)格邊的選取方法，圖6e～圖6f描述了四種點(diǎn)交點(diǎn)對(duì)應(yīng)的網(wǎng)格邊的選取方法。

當(dāng)獲得起始交點(diǎn)后，根據(jù)起始交點(diǎn)所屬的網(wǎng)格面和起始交點(diǎn)的具體類型和情況，可以搜索出與平面相交的網(wǎng)格邊并獲得后續(xù)交點(diǎn)。根據(jù)后續(xù)交點(diǎn)可以確定下一個(gè)與平面相交的四邊形網(wǎng)格面，而該后續(xù)交點(diǎn)成為求取下一個(gè)后續(xù)交點(diǎn)的已知交點(diǎn)。以此類推，可以采用遞歸的方式計(jì)算出平面與SSP交線中的所有后續(xù)交點(diǎn)，直到滿足終止求交條件時(shí)停止計(jì)算。

3．3 判定終止交點(diǎn)

將平面與SSP交線的最后一個(gè)交點(diǎn)定義為終止交點(diǎn)，圖5所示的空心方點(diǎn)即為終止交點(diǎn)。根據(jù)已知交點(diǎn)獲得后續(xù)交點(diǎn)后，需判斷后續(xù)交點(diǎn)是否為交線的終止交點(diǎn)。如果后續(xù)交點(diǎn)被判定為終止交點(diǎn)，就達(dá)到了終止求交條件，可以停止交線計(jì)算。根據(jù)交線的不同類型，采用不同的方法判定終止交點(diǎn)。對(duì)于線型交線，如果后續(xù)交點(diǎn)位于SSP的邊界，則該后續(xù)交點(diǎn)即為終止交點(diǎn)；對(duì)于環(huán)型交線，如果后續(xù)交點(diǎn)與起始交點(diǎn)相同，則該后續(xù)交點(diǎn)即為終止交點(diǎn)。

3．4 算法復(fù)雜度分析

對(duì)于細(xì)分N次的細(xì)分曲面面片，頂點(diǎn)的數(shù)量為（2N＋1）2個(gè)，邊界網(wǎng)格邊的數(shù)量為4×2N個(gè)。因此，細(xì)分曲面與平面求交算法的復(fù)雜度為O（m×（2N＋2＋3n））。其中：m表示與平面相交的細(xì)分曲面面片個(gè)數(shù)，n表示細(xì)分曲面面片中與平面相交的網(wǎng)格邊的數(shù)量。

4 算法描述

極限網(wǎng)格頂點(diǎn)是控制網(wǎng)格對(duì)應(yīng)頂點(diǎn)的極限位置。對(duì)于逼近型細(xì)分模式，相同細(xì)分次數(shù)的極限網(wǎng)格比控制網(wǎng)格具有更高的表示精度。因此，以一定細(xì)分次數(shù)的極限網(wǎng)格代替細(xì)分曲面與平面求交，有利于降低計(jì)算機(jī)內(nèi)存消耗和提高求交效率。由于相同細(xì)分次數(shù)的極限網(wǎng)格與控制網(wǎng)格具有相同的拓?fù)浣Y(jié)構(gòu)，極限網(wǎng)格同樣可以采用元胞結(jié)構(gòu)分片表示?？梢圆捎?Halstead等［12］的方法獲得Catmull－Clark細(xì)分曲面的極限網(wǎng)格，采用Huang［13］的方法計(jì)算滿足一定精度的極限網(wǎng)格的細(xì)分次數(shù)。計(jì)算平面與細(xì)分曲面交線的算法步驟如下：

步驟1 根據(jù)用戶指定的精度，計(jì)算Catmull－Clark細(xì)分曲面極限網(wǎng)格的細(xì)分次數(shù)。

步驟2 應(yīng)用元胞結(jié)構(gòu)實(shí)現(xiàn)Catmull－Clark細(xì)分曲面的分片表示。

步驟3 對(duì)每個(gè)SSP創(chuàng)建AABB。設(shè)置n為SSP的個(gè)數(shù)，i的初始值為0。

步驟4 i＝i＋1，如果i＞n，則中止計(jì)算程序并輸出計(jì)算結(jié)果。

步驟5 判斷第i個(gè)SSP的AABB是否與平面相交。如果不相交，則轉(zhuǎn)步驟4。

步驟6 結(jié)合SSP多級(jí)分割，計(jì)算第i個(gè)SSP與平面的起始交點(diǎn)并確定交線的類型。如果沒有獲得起始交點(diǎn)，則轉(zhuǎn)步驟4。

步驟7 計(jì)算后續(xù)交點(diǎn)。

步驟8 判斷是否滿足終止求交條件。如果不滿足條件，則轉(zhuǎn)步驟7。

步驟9 如果i＝＝n，則根據(jù)元胞外層結(jié)構(gòu)描述的SSP之間的拓?fù)潢P(guān)系，合并平面與SSP的交線段，輸出平面與Catmull－Clark細(xì)分曲面的交線，否則轉(zhuǎn)步驟4。

平面與Catmull－Clark細(xì)分曲面求交的算法流程如圖7所示。

5 算法測(cè)試與分析

算法測(cè)試共分為三部分：①主要測(cè)試平面與SSP求交的穩(wěn)定性；②主要測(cè)試平面與復(fù)雜細(xì)分曲面模型求交的效率；③主要測(cè)試大規(guī)模平面組與復(fù)雜細(xì)分曲面模型求交的性能。算法測(cè)試的軟、硬件環(huán)境分別為：Windows 7 64－bit操作系統(tǒng)和 MATLAB 2012b軟件；CPU i5－3570k，RAM 4G。

第①部分算法測(cè)試的測(cè)試模型是一個(gè)細(xì)分10次的Catmull－Clark細(xì)分曲面面片。以圖8所示的平面和SSP作為測(cè)試樣本，各個(gè)測(cè)試樣本中的平面與SSP的相交情況、交線類型、交點(diǎn)個(gè)數(shù)和算法耗時(shí)等測(cè)試數(shù)據(jù)如表1所示。

表1 測(cè)試平面與SSP求交的數(shù)據(jù)

從表1中的數(shù)據(jù)可以看出，對(duì)于圖8所示的平面與SSP的相交、相切和相離的情況，算法均能給出正確的結(jié)果，測(cè)試結(jié)果表明了平面與SSP求交的穩(wěn)定性較強(qiáng)。SSP是構(gòu)成細(xì)分曲面模型的基本數(shù)據(jù)元素，理論上，平面與細(xì)分曲面模型在全局范圍內(nèi)的交線必然存在于局部SSP之中，因此將平面與復(fù)雜細(xì)分曲面模型的求交問(wèn)題轉(zhuǎn)化為平面與拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單的SSP的求交問(wèn)題，有利于提高平面與復(fù)雜細(xì)分曲面模型求交的穩(wěn)定性。

第②部分算法測(cè)試的測(cè)試模型是細(xì)分9次的復(fù)雜細(xì)分曲面模型。以圖9所示的平面和復(fù)雜細(xì)分曲面模型作為測(cè)試樣本，各個(gè)測(cè)試樣本的SSP個(gè)數(shù)、交點(diǎn)個(gè)數(shù)、SSP的AABB與平面相交的數(shù)量、與平面相交的SSP的數(shù)量和算法耗時(shí)等測(cè)試數(shù)據(jù)如表2所示。

表2 測(cè)試平面與復(fù)雜細(xì)分曲面模型求交的數(shù)據(jù)

從表2的數(shù)據(jù)可以看出，對(duì)于圖9所示的平面與復(fù)雜細(xì)分曲面模型的相交情況，算法均能給出正確的結(jié)果。對(duì)于測(cè)試樣本1和2，在測(cè)試模型的頂點(diǎn)個(gè)數(shù)達(dá)到五千萬(wàn)級(jí)的情況下，計(jì)算耗時(shí)為1．3s左右。測(cè)試結(jié)果表明平面與復(fù)雜細(xì)分曲面模型求交的效率較高?；谠Y(jié)構(gòu)分片表示Catmull－Clark細(xì)分曲面主要是為了在交線計(jì)算的過(guò)程中實(shí)施分治策略。以SSP的AABB與平面相交檢測(cè)為基礎(chǔ)的第一級(jí)分治可以快速排除絕大多數(shù)與平面不相交的SSP，顯著降低了求交的規(guī)模，如表2所示，與平面相交的SSP的數(shù)量?jī)H占測(cè)試模型SSP總數(shù)的一小部分。以SSP多級(jí)分割為基礎(chǔ)的第二級(jí)分治可以快速計(jì)算起始交點(diǎn)，同時(shí)，針對(duì)SSP拓?fù)浣Y(jié)構(gòu)特性的后續(xù)交點(diǎn)計(jì)算方法在根本上提高了求交的效率。

第③部分算法測(cè)試的測(cè)試模型是一個(gè)由29個(gè)SSP構(gòu)成的細(xì)分8次的復(fù)雜細(xì)分曲面模型。分別以圖10a所示的飛機(jī)模型和垂直于X，Y，Z坐標(biāo)軸的大規(guī)模平面組作為測(cè)試樣本，針對(duì)平面垂直于坐標(biāo)軸，在任意平面與細(xì)分曲面求交的基礎(chǔ)上對(duì)算法進(jìn)行了優(yōu)化。各個(gè)測(cè)試樣本的平面間距、平面?zhèn)€數(shù)、交點(diǎn)個(gè)數(shù)和算法耗時(shí)等測(cè)試數(shù)據(jù)如表3所示。

表3 測(cè)試平面與復(fù)雜細(xì)分曲面模型求交的數(shù)據(jù)

如圖10b～圖10d所示，算法均能給出正確的結(jié)果，從表3的數(shù)據(jù)可以看出，在測(cè)試模型的頂點(diǎn)個(gè)數(shù)近百萬(wàn)級(jí)和截平面的數(shù)量過(guò)百的情況下計(jì)算耗時(shí)均較低，測(cè)試結(jié)果表明以本文算法為基礎(chǔ)的大規(guī)模平面組與復(fù)雜細(xì)分曲面模型求交的性能較高。這為細(xì)分曲面在數(shù)控加工、快速原型和3D打印等領(lǐng)域的應(yīng)用提供了基礎(chǔ)。

6 結(jié)束語(yǔ)

應(yīng)用元胞結(jié)構(gòu)分片表示Catmull－Clark細(xì)分曲面，不但有利于降低高精度細(xì)分曲面的計(jì)算機(jī)內(nèi)存消耗，而且可為分治策略的實(shí)施提供基礎(chǔ)。分治策略的實(shí)施將復(fù)雜細(xì)分曲面模型與平面求交的問(wèn)題轉(zhuǎn)化為簡(jiǎn)單細(xì)分曲面面片與平面求交的問(wèn)題，不僅降低了求交的規(guī)模，還提高了交點(diǎn)計(jì)算的穩(wěn)定性和效率。細(xì)分曲面面片多級(jí)分割結(jié)合軸對(duì)稱包圍盒干涉檢測(cè)技術(shù)，可以快速判定平面與細(xì)分曲面面片的相交性和獲得交線的起始交點(diǎn)。以起始交點(diǎn)為基礎(chǔ)，針對(duì)細(xì)分曲面面片拓?fù)浣Y(jié)構(gòu)特性的后續(xù)交點(diǎn)計(jì)算方法，在根本上提高了平面與細(xì)分曲面面片求交的效率。通過(guò)實(shí)例測(cè)試了算法的穩(wěn)定性和效率，測(cè)試結(jié)果表明本文提出的平面與Catmull－Clark細(xì)分曲面求交的算法實(shí)用、高效。如何將本文算法的核心理論和方法擴(kuò)展到Catmull－Clark細(xì)分曲面之間求交的研究中，是未來(lái)的研究方向。

［1］ CHEN Xiaoxia，YONG Junhai，CHEN Yujian，et al．Intersection algorithm based on coordinate transformation［J］．Computer Integrated Manufacturing Systems，2005，11（9）：1327－1332（in Chinese）．［陳曉霞，雍俊海，陳玉健，等．基于坐標(biāo)變換的曲線曲面求交算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2005，11（9）：1327－1332．］

［2］ LI Min，ZHANG Lichao，MO Jianhua，et al．Smoothing technique for 2Dcontour in numerical control plasma cutting［J］．Computer Integrated Manufacturing Systems，2011，17（12）：2623－2629（in Chinese）．［李 敏，張李超，莫健華，等．一種數(shù)控加工二維輪廓的平滑處理技術(shù)［J］．計(jì)算機(jī)集成制造系統(tǒng)，2011，17（12）：2623－2629．］

［3］ GAO Xinrui，ZHANG Shusheng，HOU Zengxuan．Three direction DEXEL model of polyhedrons and virtual rapid prototyping procedure simulation［J］．Computer Integrated Manufacturing Systems，2007，13（12）：2415－2420（in Chinese）．［高 新瑞，張樹生，侯增選．多面體三向DEXEL模型與虛擬快速原型［J］．計(jì)算機(jī)集成制造系統(tǒng)，2007，13（12）：2415－2420．］

［4］ YUAN Hong，LIAO Wenhe．On Catmull－Clark subdivision surface intersection with a given precision［J］．Mechanical Science and Technology，2008，27（4）：486－489（in Chinese）．［袁

鴻，廖文和．給定精度條件下的Catmull－Clark細(xì)分曲面求交研究［J］．機(jī)械科學(xué)與技術(shù)，2008，27（4）：486－489．］

［5］ ZHENG Liyin，ZHANG Li．Study of intersections for subdivision surface with convex hull［J］．Computer Engineering and Design，2008，29（1）：102－104（in Chinese）．［鄭立垠，張 麗．基于凸包特征的細(xì)分曲面求交研究［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（1）：102－104．］

［6］ NASRI A．Polyhedral subdivision methods for free form surfaces［J］．ACM Transactions on Graphics，1987，6（1）：29－73．

［7］ LANQUETIN S，F(xiàn)OUFOU S，KHEDDOUCI H，et al．A graph based algorithm for intersection of subdivision surfaces［C］//Proceedings of the 2003International Conference on Computational Science and Its Applications．Berlin，Germany：Springer－Verlag，2003：387－396．

［8］ LI Tao，ZHOU Laishui．Research on intersection and trim－ming algorithms for subdivision surfaces［J］．Computer Engineering and Applications，2009，45（30）：177－184（in Chinese）．［李 濤，周來(lái)水．細(xì)分曲面求交裁剪算法研究［J］．計(jì)算機(jī)工程與應(yīng)用，2009，45（30）：177－184．］

［9］ ZHU X P，HU S M，TAI C L，et al．A marching method for computing intersection curves of two subdivision solids［C］//Proceedings of the 11th IMA International Conference on Mathematics of Surfaces．Berlin，Germany：Springer－Verlag，2005：458－471．

［10］ CATMULL E，CLARK J．Recursively generated B－spline surface on arbitrary topological meshes［J］．Computer－Aided Design，1978，10（6）：350－355．

［11］ ZHU Jianning，WANG Minjie，WEI Zhaocheng，et al．An algorithm for quickly calculating the signed distance between apoint and a subdivision surface［J］．Computer Integrated Manufacturing Systems，2013，19（4）：687－694（in Chinese）．［朱建寧，王敏杰，魏兆成，等．快速計(jì)算空間點(diǎn)到細(xì)分曲面有符號(hào)最近距離的方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2013，19（4）：687－694．］

［12］ HALSTEAD M，KASS M，DEROSE T．Efficient，fair interpolation using Catmull－Clark surfaces［C］//Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques．New York，N．Y．，USA：ACM Press，1993：35－44．

［13］ HUANG Z，DENG J，WANG G．A bound on the approximation of a Catmull–Clark subdivision surface by its limit mesh［J］．Computer Aided Geometric Design，2008，25（7）：457－469．