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

（大連理工大學 機械工程學院，遼寧 大連 116024）

0 引言

細分曲面建模法可以輕易構造具有任意拓撲結構的光滑曲面，廣泛應用于計算機圖形學、影視、動畫等領域。曲面求交［1］是計算機輔助幾何設計領域中的關鍵問題，其中平面與曲面求交是數(shù)控加工［2］、3D打印、快速原型［3］等領域中的基礎問題?？焖佟⒎€(wěn)定和高精度的平面與細分曲面求交技術有利于細分曲面在工業(yè)領域更廣泛的應用。

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

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

1 Catmull－Clark細分曲面的分片表示

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

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

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

2 細分曲面面片多級分割

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

3 平面與細分曲面面片求交

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

3．1 計算起始交點并確定交線類型

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

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

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

步驟3 設置n的初始值為1，將SSP進行第n級分割。

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

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

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

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

3．2 計算后續(xù)交點

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

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

3．3 判定終止交點

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

3．4 算法復雜度分析

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

4 算法描述

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

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

步驟2 應用元胞結構實現(xiàn)Catmull－Clark細分曲面的分片表示。

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

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

步驟5 判斷第i個SSP的AABB是否與平面相交。如果不相交，則轉步驟4。

步驟6 結合SSP多級分割，計算第i個SSP與平面的起始交點并確定交線的類型。如果沒有獲得起始交點，則轉步驟4。

步驟7 計算后續(xù)交點。

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

步驟9 如果i＝＝n，則根據(jù)元胞外層結構描述的SSP之間的拓撲關系，合并平面與SSP的交線段，輸出平面與Catmull－Clark細分曲面的交線，否則轉步驟4。

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

5 算法測試與分析

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

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

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

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

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

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

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

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

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

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

6 結束語

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

［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）．［陳曉霞，雍俊海，陳玉健，等．基于坐標變換的曲線曲面求交算法［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ù)控加工二維輪廓的平滑處理技術［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］．計算機集成制造系統(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細分曲面求交研究［J］．機械科學與技術，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）．［鄭立垠，張 麗．基于凸包特征的細分曲面求交研究［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）．［李 濤，周來水．細分曲面求交裁剪算法研究［J］．計算機工程與應用，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］．計算機集成制造系統(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．