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

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

0 引言

細(xì)分曲面建模方法不僅具有非均勻有理B樣條（Non－Uniform Rational B－Spline，NURBS）方法的局部性和仿射不變性等良好性質(zhì)，還具有NURBS方法所不具有的拓?fù)淙我庑院驼w連續(xù)性，可以構(gòu)造具有任意拓?fù)浣Y(jié)構(gòu)的光滑曲面，因此廣泛應(yīng)用于影視、動(dòng)畫(huà)和虛擬現(xiàn)實(shí)等領(lǐng)域。然而，細(xì)分曲面建模方法中存在的一些關(guān)鍵問(wèn)題成為細(xì)分曲面在工業(yè)領(lǐng)域應(yīng)用的瓶頸，其中計(jì)算空間點(diǎn)到細(xì)分曲面有符號(hào)最近距離就是一個(gè)重要的問(wèn)題。同時(shí)，在機(jī)器人運(yùn)動(dòng)規(guī)劃和數(shù)控加工等領(lǐng)域，空間點(diǎn)到細(xì)分曲面有符號(hào)最近距離也是解決物體間運(yùn)動(dòng)干涉和碰撞檢測(cè)問(wèn)題的基礎(chǔ)。

有關(guān)計(jì)算點(diǎn)到參數(shù)曲面最近距離的研究比較廣泛，徐汝鋒等［1］首先在參數(shù)曲面上選取一個(gè)初始點(diǎn)，以該點(diǎn)為中心點(diǎn)，按給定步長(zhǎng)求取周?chē)乃膫€(gè)頂點(diǎn)，在上述五個(gè)頂點(diǎn)中，將距離空間點(diǎn)最近的頂點(diǎn)作為中心點(diǎn)，步長(zhǎng)減半再次求取其周?chē)乃膫€(gè)頂點(diǎn)，重復(fù)以上步驟，直到獲得滿足一定精度的最近距離。熊志剛等［2］采用雙向黃金分割法對(duì)參數(shù)曲面的參數(shù)空間進(jìn)行分割，通過(guò)計(jì)算和比較黃金分割點(diǎn)函數(shù)值，逐次縮小參數(shù)區(qū)間。當(dāng)參數(shù)區(qū)間縮小到一定程度時(shí)，以空間點(diǎn)到黃金分割點(diǎn)的最近距離作為近似最優(yōu)解。蘇智劍等［3］利用遺傳算法計(jì)算空間點(diǎn)到參數(shù)曲面的最近距離，首先將參數(shù)曲面離散成空間點(diǎn)，然后采用遺傳優(yōu)化方法初步判斷問(wèn)題解所在的區(qū)間，最后采用連續(xù)變量?jī)?yōu)化方法求得問(wèn)題的精確解。廖平［4］利用粒子群優(yōu)化算法計(jì)算空間點(diǎn)到參數(shù)曲面的最近距離，理論上能夠獲得全局最優(yōu)解，但計(jì)算速度較慢。由于細(xì)分曲面沒(méi)有整體的解析表達(dá)式，上述研究方法不能直接應(yīng)用于空間點(diǎn)到細(xì)分曲面最近距離的計(jì)算，在實(shí)際應(yīng)用中，常常采用一定細(xì)分次數(shù)的控制網(wǎng)格代替細(xì)分曲面進(jìn)行各種幾何操作。關(guān)于計(jì)算點(diǎn)到網(wǎng)格模型最近距離的研究，方向等［5］提出一個(gè)快速計(jì)算空間點(diǎn)到任意多面體的有符號(hào)距離的方法，該方法以空間點(diǎn)為中心，采用動(dòng)態(tài)球搜索技術(shù)，通過(guò)縮小三角面片的搜索范圍來(lái)提高搜索距離空間點(diǎn)最近的三角面片的搜索效率。但是細(xì)分曲面不同于一般的網(wǎng)格模型，為表示復(fù)雜形體的光滑曲面，細(xì)分曲面控制網(wǎng)格的數(shù)據(jù)量十分巨大，一般搜索技術(shù)的效率難以滿足應(yīng)用。目前，僅有TorstenUllrich等［6］對(duì)計(jì)算空間點(diǎn)到 Catmull－Clark［7］細(xì)分曲面的最近距離問(wèn)題進(jìn)行了研究。該研究通過(guò)將Catmull－Clark細(xì)分曲面離散成三角面片，以空間點(diǎn)到三角面片的最近距離作為空間點(diǎn)到細(xì)分曲面的最近距離；利用細(xì)分曲面分片表示和自適應(yīng)細(xì)分技術(shù)，使細(xì)分曲面的數(shù)據(jù)存儲(chǔ)和三角面片的數(shù)量減少到最低；通過(guò)建立Catmull－Clark細(xì)分曲面的距離場(chǎng)，提高了搜索三角面片的效率。然而，通過(guò)自適應(yīng)細(xì)分技術(shù)減少的三角面片數(shù)量有限，且容易產(chǎn)生數(shù)值誤差，同時(shí)建立距離場(chǎng)的代價(jià)也比較高。

為解決以上問(wèn)題，本文以Catmull－Clark細(xì)分曲面為例，研究快速計(jì)算空間點(diǎn)到細(xì)分曲面最近距離的方法。本文采用一定細(xì)分層次的極限網(wǎng)格表示細(xì)分曲面，以空間點(diǎn)到極限網(wǎng)格頂點(diǎn)的最近距離作為空間點(diǎn)到細(xì)分曲面的最近距離。通過(guò)改進(jìn)的Catmull－Clark細(xì)分曲面數(shù)據(jù)結(jié)構(gòu)，能夠更好地實(shí)現(xiàn)細(xì)分曲面的分片表示，進(jìn)而采用分治策略和包圍體技術(shù)縮小極限網(wǎng)格頂點(diǎn)的搜索范圍，而且采用較粗層次控制網(wǎng)格創(chuàng)建包圍體的代價(jià)要比建立距離場(chǎng)的代價(jià)低。根據(jù)細(xì)分曲面面片拓?fù)浣Y(jié)構(gòu)的特性創(chuàng)建多分辨率采樣技術(shù)，基于該技術(shù)可以顯著提高搜索最近頂點(diǎn)的效率。本文算法將計(jì)算空間點(diǎn)到細(xì)分曲面面片和空間點(diǎn)到細(xì)分曲面整體的最近距離問(wèn)題有機(jī)地統(tǒng)一起來(lái)，是一種理想的全局尋優(yōu)算法。

1 算法原理

當(dāng)細(xì)分曲面表示精度較高時(shí)，網(wǎng)格頂點(diǎn)的密度非常大，空間點(diǎn)到三角面片頂點(diǎn)的最近距離與空間點(diǎn)到三角面片的最近距離相差較小，而計(jì)算點(diǎn)與點(diǎn)的距離要比計(jì)算點(diǎn)與三角面片的距離更加穩(wěn)定和快速。因此，可以將計(jì)算空間點(diǎn)到細(xì)分曲面的最近距離問(wèn)題轉(zhuǎn)化為搜索距離空間點(diǎn)最近的細(xì)分曲面網(wǎng)格頂點(diǎn)問(wèn)題。首先，創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)細(xì)分曲面的分片表示，進(jìn)而采用分治策略，將在細(xì)分曲面全局范圍內(nèi)搜索最近頂點(diǎn)的問(wèn)題轉(zhuǎn)化為在各個(gè)細(xì)分曲面面片（Subdivision Surface Patch，SSP）局部范圍內(nèi)搜索最近頂點(diǎn)的問(wèn)題，搜索結(jié)果的全局最優(yōu)解理論上存在于局部最優(yōu)解中。然后，利用細(xì)分曲面控制網(wǎng)格的凸包性質(zhì)對(duì)每個(gè)SSP構(gòu)建包圍體；計(jì)算空間點(diǎn)和包圍體之間的最近距離Dpb，將SSP按照該距離由小到大進(jìn)行排序，以此順序分別計(jì)算空間點(diǎn)與SSP的最近距離Dpssp。將逐次計(jì)算得到的Dpssp進(jìn)行比較，獲得準(zhǔn)全局最近距離Dminq。在每次計(jì)算之前，對(duì)比Dpb和Dminq的大小，如果Dpb≥Dminq，則停止計(jì)算，該Dminq即為空間點(diǎn)到細(xì)分曲面的最近距離Dmin；否則繼續(xù)計(jì)算，直到獲得Dmin為止。

在徐汝鋒［1］和熊志剛［2］等的研究中，分別以不同的方式實(shí)現(xiàn)了參數(shù)曲面采樣。通過(guò)采樣點(diǎn)擇優(yōu)與采樣區(qū)域縮小的交替進(jìn)行，完成了最近頂點(diǎn)的搜索；在計(jì)算空間點(diǎn)到SSP最近距離的研究中，利用SSP網(wǎng)格的拓?fù)浣Y(jié)構(gòu)特性，發(fā)展了文獻(xiàn)［1－2］的理論；根據(jù)SSP網(wǎng)格的拓?fù)浣Y(jié)構(gòu)特性，制定多分辨率采樣規(guī)則；以相對(duì)較低層次的網(wǎng)格頂點(diǎn)作為低分辨率采樣點(diǎn)，以相對(duì)較高層次的網(wǎng)格頂點(diǎn)作為高分辨率采樣點(diǎn)；通過(guò)擇優(yōu)的低分辨率采樣點(diǎn)確定再次進(jìn)行高分辨率采樣的區(qū)域，重復(fù)此過(guò)程一定次數(shù)，就可以最終鎖定距離空間點(diǎn)最近的SSP網(wǎng)格頂點(diǎn)，此頂點(diǎn)與空間點(diǎn)的距離即為Dpssp；根據(jù)此頂點(diǎn)的坐標(biāo)和法向建立參數(shù)直線方程，計(jì)算直線中距離空間點(diǎn)最近的參數(shù)點(diǎn)；以參數(shù)點(diǎn)與空間點(diǎn)的距離為基礎(chǔ)，對(duì)計(jì)算結(jié)果進(jìn)行誤差分析，如果計(jì)算結(jié)果沒(méi)有滿足誤差要求，則結(jié)合局部細(xì)分技術(shù)，對(duì)SSP局部進(jìn)行高分辨率采樣，再次計(jì)算最小距離，直到計(jì)算結(jié)果滿足誤差要求為止；最后，以參數(shù)點(diǎn)的參數(shù)值確定Dpssp的符號(hào)。

2 算法描述

2．1 細(xì)分曲面生成

2．1．1 細(xì)分次數(shù)

細(xì)分曲面是控制網(wǎng)格不斷細(xì)分的極限狀態(tài)。在實(shí)際應(yīng)用中，通常用一定細(xì)分次數(shù)的控制網(wǎng)格代替細(xì)分曲面。理論上，細(xì)分次數(shù)越高，控制網(wǎng)格的表示精度越高，使細(xì)分曲面的數(shù)據(jù)量呈指數(shù)速率增長(zhǎng)，給細(xì)分曲面應(yīng)用于高精度的工業(yè)領(lǐng)域增加了困難。因此，一些學(xué)者［8－10］對(duì)控制網(wǎng)格與細(xì)分曲面之間的誤差分析以及細(xì)分次數(shù)與表示精度的映射關(guān)系進(jìn)行了深入研究。極限網(wǎng)格和控制網(wǎng)格具有相同的拓?fù)浣Y(jié)構(gòu)，極限網(wǎng)格頂點(diǎn)是控制網(wǎng)格對(duì)應(yīng)頂點(diǎn)的極限位置。對(duì)于逼近型細(xì)分曲面，相同細(xì)分次數(shù)的極限網(wǎng)格比控制網(wǎng)格具有更高的表示精度。本文應(yīng)用Catmull－Clark細(xì)分曲面極限網(wǎng)格計(jì)算空間點(diǎn)到Catmull－Clark細(xì)分曲面的最近距離，采用Huang等［11］的方法確定Catmull－Clark細(xì)分曲面極限網(wǎng)格的細(xì)分次數(shù)。

2．1．2 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是細(xì)分曲面實(shí)現(xiàn)和應(yīng)用算法開(kāi)發(fā)的基礎(chǔ)。目前，細(xì)分曲面常用的數(shù)據(jù)結(jié)構(gòu)分別為基于邊［12］和四叉樹(shù)［13］結(jié)構(gòu)，這兩種數(shù)據(jù)結(jié)構(gòu)在細(xì)分次數(shù)較高時(shí)，不但十分消耗計(jì)算機(jī)內(nèi)存，而且搜索和查詢(xún)的效率較低。Settgast等［14］在進(jìn)行 Catmull－Clark細(xì)分曲面自適應(yīng)細(xì)分的研究中，為解決細(xì)分曲面內(nèi)存消耗過(guò)大的問(wèn)題，提出用二維數(shù)組分片表示細(xì)分曲面的方法。但Settgast的做法有兩個(gè)缺陷：①規(guī)則的二維數(shù)組不能很好地表示SSP周?chē)灰?guī)則的鄰域結(jié)構(gòu)，不利于細(xì)分算法實(shí)現(xiàn)及數(shù)據(jù)結(jié)構(gòu)在多種細(xì)分模式中推廣；②二維數(shù)組中過(guò)多的鄰域結(jié)構(gòu)信息不利于細(xì)分曲面應(yīng)用算法的開(kāi)發(fā)。

本文構(gòu)建了一個(gè)雙層數(shù)據(jù)結(jié)構(gòu)，來(lái)更好地表示Catmull－Clark細(xì)分曲面，將該數(shù)據(jù)結(jié)構(gòu)命名為元胞數(shù)據(jù)結(jié)構(gòu)。內(nèi)層數(shù)據(jù)結(jié)構(gòu)主要包含一個(gè)二維數(shù)組和若干個(gè)一維數(shù)組，其中二維數(shù)組只表示SSP的信息，將其命名為元胞數(shù)組Ac，Ac＝（2N＋1）2，N為細(xì)分次數(shù)。若干個(gè)一維數(shù)組用來(lái)表示SSP的鄰域結(jié)構(gòu)信息，這些鄰域結(jié)構(gòu)信息主要輔助SSP進(jìn)行細(xì)分，分為兩類(lèi)：①輔助SSP的“角點(diǎn)”進(jìn)行細(xì)分，將其命名為輔助角點(diǎn)細(xì)分結(jié)構(gòu)Av，Av＝2Ne＋1，Ne為“角點(diǎn)”的價(jià)；②輔助SSP的“邊界”進(jìn)行細(xì)分，將其命名為輔助邊界細(xì)分結(jié)構(gòu)Ab，Ab＝2N＋1。外層數(shù)據(jù)結(jié)構(gòu)可以采用半邊數(shù)據(jù)結(jié)構(gòu)，通過(guò)細(xì)分曲面初始網(wǎng)格的拓?fù)浣Y(jié)構(gòu)來(lái)表達(dá)SSP之間的拓?fù)潢P(guān)系。圖1所示為SSP（頂點(diǎn)V1，V2，V3和V4組成）創(chuàng)建的元胞數(shù)據(jù)結(jié)構(gòu)示意圖。

2．1．3 細(xì)分算法實(shí)現(xiàn)

應(yīng)用元胞數(shù)據(jù)結(jié)構(gòu)，可以將Catmull－Clark細(xì)分曲面的整體更新轉(zhuǎn)化為各個(gè)元胞的局部更新，每個(gè)元胞的更新主要分為Ac的更新和輔助細(xì)分結(jié)構(gòu)的更新兩方面。Ac的更新分為三部分：①Ac“角點(diǎn)”的更新，由Av完成；②Ac“邊界”的更新，由Ab和Ac的邊界部分共同完成；③Ac內(nèi)部的更新，Ac的信息就可完成該部分的更新。輔助細(xì)分結(jié)構(gòu)的更新分為兩部分：①Av的更新，由Av獨(dú)自完成；②Ab的更新，由Ab和Ac的邊界部分共同完成。圖2所示為Catmull－Clark細(xì)分曲面元胞數(shù)據(jù)結(jié)構(gòu)的更新示意圖。極限網(wǎng)格同樣可以應(yīng)用元胞數(shù)據(jù)結(jié)構(gòu)進(jìn)行分片表示。當(dāng)細(xì)分N次的控制網(wǎng)格計(jì)算完成后，可以進(jìn)行細(xì)分N次的極限網(wǎng)格的計(jì)算。細(xì)分N次的極限網(wǎng)格頂點(diǎn)位置和法向的計(jì)算過(guò)程與細(xì)分N＋1次控制網(wǎng)格新頂點(diǎn)的計(jì)算過(guò)程類(lèi)似，具有相同的控制網(wǎng)格頂點(diǎn)搜索策略，僅僅是計(jì)算過(guò)程中控制網(wǎng)格頂點(diǎn)的加權(quán)系數(shù)不同。

2．2 分治策略與包圍體

2．2．1 分治策略

元胞數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素是由Ac表示的SSP，這為分治策略的實(shí)施提供了基礎(chǔ)。計(jì)算空間點(diǎn)到細(xì)分曲面最近距離的關(guān)鍵，是快速、準(zhǔn)確地搜索距離空間點(diǎn)最近的網(wǎng)格頂點(diǎn)，采用分治策略是為了提高搜索的效率。通過(guò)分治策略，將細(xì)分曲面整體范圍內(nèi)的搜索劃分為有限個(gè)SSP范圍內(nèi)的搜索。對(duì)每個(gè)SSP構(gòu)建包圍體并計(jì)算空間點(diǎn)和包圍體的最近距離，確定優(yōu)先計(jì)算最近距離的SSP。當(dāng)未搜索SSP的包圍體與空間點(diǎn)的最近距離大于當(dāng)前最優(yōu)結(jié)果時(shí)停止搜索，從而提高搜索的效率。

2．2．2 包圍體

包圍體的基本思想是使用體積略大而幾何特征簡(jiǎn)單的幾何體（球體、長(zhǎng)方體等）來(lái)近似表示復(fù)雜的幾何對(duì)象。目前，常用的包圍體有包圍球、軸向包圍盒、固定方向包圍盒、方向包圍盒和離散方向包圍盒等。為方便計(jì)算空間點(diǎn)到包圍體的最近距離，本文采用包圍球來(lái)近似表示SSP。對(duì)于逼近型細(xì)分模式，可以根據(jù)控制網(wǎng)格的凸包性質(zhì)構(gòu)建包圍球。為提高構(gòu)建包圍球的效率，可以采用較低層次的控制網(wǎng)格頂點(diǎn)構(gòu)建包圍球，構(gòu)建方法如下：

式中：Cbs表示包圍球的球心點(diǎn)，Rbs表示包圍球的半徑，P1，P2，…，Pn表示控制網(wǎng)格頂點(diǎn)。

2．2．3 計(jì)算空間點(diǎn)與包圍球的最近距離

設(shè)空間點(diǎn)到包圍球的最近距離為Dpb，

式中Dpc表示空間點(diǎn)到包圍球球心的距離。當(dāng)計(jì)算結(jié)果為負(fù)值時(shí)，說(shuō)明空間點(diǎn)在包圍球的內(nèi)部。將SSP按照其Dpb由小到大進(jìn)行排序，以該順序開(kāi)始計(jì)算空間點(diǎn)到SSP的有符號(hào)最近距離。

2．3 計(jì)算空間點(diǎn)到SSP的有符號(hào)最近距離

2．3．1 搜索策略

細(xì)分曲面通過(guò)多邊形網(wǎng)格表示造型曲面。細(xì)分曲面的極限網(wǎng)格不斷加密逼近造型曲面，每次細(xì)分增加的極限網(wǎng)格頂點(diǎn)可以認(rèn)為是對(duì)極限曲面的高分辨率采樣。利用遞歸細(xì)分過(guò)程中極限網(wǎng)格由粗到精的特性，擴(kuò)展了文獻(xiàn)［1－2］的搜索策略。具體的搜索策略如下：當(dāng)Catmull－Clark細(xì)分曲面面片進(jìn)行第一次細(xì)分后，搜索區(qū)域被自然地分割為四個(gè)子區(qū)域。第二次細(xì)分后，每個(gè)子區(qū)域內(nèi)生成對(duì)應(yīng)的采樣點(diǎn)，鎖定距離空間點(diǎn)最近的采樣點(diǎn)的子區(qū)域。再次細(xì)分后，鎖定的子區(qū)域被分割為四個(gè)區(qū)域，且每個(gè)區(qū)域中都生成一個(gè)采樣點(diǎn)。每次細(xì)分完成后都伴隨著采樣點(diǎn)擇優(yōu)和搜索區(qū)域分割的過(guò)程。當(dāng)最后一次細(xì)分完成后，對(duì)鎖定搜索區(qū)域內(nèi)的所有頂點(diǎn)進(jìn)行采樣，選取距離空間點(diǎn)最近的頂點(diǎn)。

2．3．2 多分辨率采樣

上述搜索策略中所需要的采樣點(diǎn)，可以通過(guò)多分辨率采樣技術(shù)從極限網(wǎng)格中獲取。對(duì)于SSP，極限網(wǎng)格頂點(diǎn)的數(shù)值存儲(chǔ)在對(duì)應(yīng)的元胞數(shù)組Ac中，Ac的行列索引實(shí)現(xiàn)了SSP的自然參數(shù)化。不同細(xì)分層次極限網(wǎng)格頂點(diǎn)的行列索引遵循如下定理和推論：

定理1 對(duì)于細(xì)分次數(shù)為N的Catmull－Clark細(xì)分曲面面片，Ac＝（2N＋1）2。在該Ac中，以2N－m為索引間距，提取第m次細(xì)分（m≤N）的極限網(wǎng)格頂點(diǎn)。

推論1 第m1次細(xì)分與第m2次細(xì)分（m1＜m2）的極限網(wǎng)格頂點(diǎn)的索引間距為（2N－m1－2N－m2）。

推論2 相鄰細(xì)分層次（m2－m1＝1）的極限網(wǎng)格頂點(diǎn)索引間距為2N－m2。

基于上述定理與推論，在SSP中搜索對(duì)應(yīng)的頂點(diǎn)，可以實(shí)現(xiàn)SSP的多分辨率采樣。具體做法是在第二次細(xì)分的極限網(wǎng)格中提取初始的四個(gè)采樣點(diǎn)，分別為：

式中：P11，P12，P13和P14分別表示初始的四個(gè)采樣點(diǎn)，N為細(xì)分次數(shù)。將四個(gè)采樣點(diǎn)中距離空間點(diǎn)最近的點(diǎn)設(shè)為擇優(yōu)點(diǎn)，擇優(yōu)點(diǎn)所在的區(qū)域即為下次采樣的區(qū)域。擇優(yōu)點(diǎn)的表達(dá)式為

式中：Pon表示第n次搜索時(shí)的擇優(yōu)點(diǎn)，iPon和jPon分別表示擇優(yōu)點(diǎn)的行列索引值。從第二次到第N－1次獲得采樣點(diǎn)的過(guò)程，可以用如下關(guān)系表示：

式中：Pn1，Pn2，Pn3和Pn4分別表示第n次搜索的四個(gè)采樣點(diǎn)，iPon－1和jPon－1分別表示第n－1次擇優(yōu)點(diǎn)的行列索引值。第N次采樣點(diǎn)由PoN－1的1－鄰域頂點(diǎn)構(gòu)成，從中選取距離空間點(diǎn)最近的頂點(diǎn)。應(yīng)用多分辨率采樣技術(shù)，在細(xì)分五次的SSP中搜索最近點(diǎn)的過(guò)程如圖3所示，圓形點(diǎn)為每次的多分辨率采樣點(diǎn)，方形點(diǎn)為擇優(yōu)點(diǎn)，最近點(diǎn)在圖中的深色區(qū)域頂點(diǎn)中擇優(yōu)獲得。

2．3．3 最近距離的誤差分析與符號(hào)判斷

以搜索的最近頂點(diǎn)的位置和法向建立參數(shù)直線方程，

式中：Po表示最近頂點(diǎn)的位置；No表示最近頂點(diǎn)的法向，可由Halstead等［15］的極限點(diǎn)法向公式計(jì)算。建立如下空間點(diǎn)與直線上參數(shù)點(diǎn)的距離表達(dá)式：

式中：Dpl（t）表示空間點(diǎn)與直線上參數(shù)點(diǎn)的距離，XP，YP和ZP分別表示空間點(diǎn)的坐標(biāo)分量，Xop，Yop和Zop分別表示最近頂點(diǎn)的坐標(biāo)分量，Nopx，Nopy和Nopz分別表示最近頂點(diǎn)法向的分量。令a＝Xp－，可以證明當(dāng)參數(shù)時(shí)，Dpl（T）的值最小，最小值

以Dpop表示空間點(diǎn)和最近頂點(diǎn)的距離，設(shè)精度評(píng)價(jià)系數(shù)，當(dāng)λ值足夠小時(shí)，認(rèn)為計(jì)算結(jié)果滿足精度要求。通過(guò)參數(shù)T的正負(fù)來(lái)判別最近距離的符號(hào)，當(dāng)T＞0時(shí)，說(shuō)明空間點(diǎn)在細(xì)分曲面的外部，則最近距離符號(hào)取為正；當(dāng)T＜0時(shí)，說(shuō)明空間點(diǎn)在細(xì)分曲面的內(nèi)部，則最近距離符號(hào)取為負(fù)。

2．3．4 算法描述

下面以Catmull－Clark細(xì)分曲面為例，描述計(jì)算空間點(diǎn)到Catmull－Clark細(xì)分曲面面片有符號(hào)最近距離的算法。

步驟1 提取采樣點(diǎn)P11，P12，P13和P14。

步驟2 分別計(jì)算空間點(diǎn)到P11，P12，P13和P14的距離。

步驟3 根據(jù)擇優(yōu)采樣點(diǎn)和索引間距提取采樣點(diǎn)P21，P22，P23和P24。

步驟4 交替進(jìn)行采樣點(diǎn)擇優(yōu)和搜索區(qū)域分割，直到確定第N－1次的擇優(yōu)采樣點(diǎn)PoN－1。

步驟5 在PoN－1的1－鄰域點(diǎn)中確定距離空間點(diǎn)最近的頂點(diǎn)。

步驟6 以最近頂點(diǎn)的位置和法向建立參數(shù)直線方程，以此為基礎(chǔ)對(duì)計(jì)算結(jié)果進(jìn)行誤差分析。若計(jì)算結(jié)果沒(méi)有滿足精度要求，則對(duì)相應(yīng)區(qū)域進(jìn)行局部細(xì)分，然后返回步驟4，直到所得計(jì)算結(jié)果滿足精度要求。

步驟7 根據(jù)參數(shù)T判別Dpssp的符號(hào)。

2．4 計(jì)算空間點(diǎn)到細(xì)分曲面有符號(hào)最近距離的算法描述

下面以Catmull－Clark細(xì)分曲面為例，描述計(jì)算空間點(diǎn)到Catmull－Clark細(xì)分曲面有符號(hào)最近距離的算法。

步驟1 根據(jù)細(xì)分曲面表示精度確定極限網(wǎng)格的細(xì)分次數(shù)。

步驟2 應(yīng)用元胞數(shù)據(jù)結(jié)構(gòu)生成極限網(wǎng)格。

步驟3 對(duì)每個(gè)SSP構(gòu)建包圍球。

步驟4 計(jì)算Dpb，并以此距離對(duì)SSP的排序。

步驟5 逐次計(jì)算空間點(diǎn)到排序SSP的最近距離。如果Dpb≥Dminp，則停止計(jì)算，該Dminp即為空間點(diǎn)到細(xì)分曲面的最近距離；否則繼續(xù)計(jì)算，直到獲得Dmin為止。

3 算法測(cè)試及討論

上 述 算 法 在 Pentium （R）Dual－Core CPU E5200 2．5GHz、1G 內(nèi)存的硬 件平 臺(tái)上，應(yīng) 用MATLAB 7．10．0軟件實(shí)現(xiàn)，并進(jìn)行實(shí)例測(cè)試。

3．1 計(jì)算空間點(diǎn)到SSP有符號(hào)最近距離

本部分主要測(cè)試算法的計(jì)算精度。理論上，如果距離空間點(diǎn)的最近點(diǎn)存在于曲面的內(nèi)部，則空間點(diǎn)應(yīng)該在最近點(diǎn)的法線上。如圖4所示，測(cè)試模型是細(xì)分10次的Catmull－Clark細(xì)分曲面面片的極限網(wǎng)格。在該SSP中，均勻采樣25個(gè)頂點(diǎn)，將采樣點(diǎn)沿其法矢的正向和反向分別等距，把獲得的50個(gè)等距頂點(diǎn)作為此部分算法測(cè)試的測(cè)試點(diǎn)。如果等距測(cè)試點(diǎn)的最近點(diǎn)搜索結(jié)果為其對(duì)應(yīng)的采樣點(diǎn)，則說(shuō)明該算法的搜索結(jié)果是準(zhǔn)確的。如表1所示，50個(gè)測(cè)試點(diǎn)搜索最近頂點(diǎn)的準(zhǔn)確率為100%，這說(shuō)明測(cè)試點(diǎn)不論在曲面的“內(nèi)部”還是“外部”，算法都能準(zhǔn)確搜索到空間點(diǎn)的最近頂點(diǎn)。在測(cè)試模型的頂點(diǎn)數(shù)目達(dá)到百萬(wàn)級(jí)的情況下，單次測(cè)試平均耗時(shí)僅為0．228ms，測(cè)試結(jié)果也表明算法的搜索速度較快。

表1 計(jì)算50個(gè)測(cè)試點(diǎn)到SSP最近距離的測(cè)試結(jié)果

3．2 計(jì)算空間點(diǎn)到Catmull－Clark細(xì)分曲面有符號(hào)最近距離

本部分主要測(cè)試算法的計(jì)算效率。如圖5所示，測(cè)試模型是細(xì)分9次的Catmull－Clark細(xì)分曲面的極限網(wǎng)格，模型共有196片SSP。圖5中的散亂點(diǎn)（由圓點(diǎn)表示）為該部分算法測(cè)試的測(cè)試點(diǎn)。測(cè)試指標(biāo)分別為：搜索最近頂點(diǎn)所涉及的SSP個(gè)數(shù)，計(jì)算最近距離的耗時(shí)及最近距離的數(shù)值、誤差因子和距離符號(hào)。從測(cè)試結(jié)果可以看出，誤差因子的數(shù)值都非常小，可以認(rèn)為計(jì)算結(jié)果滿足精度要求，同時(shí)算法也能正確判斷出最近距離的符號(hào)。如圖6所示，計(jì)算耗時(shí)與算法需要搜索的SSP個(gè)數(shù)呈線性關(guān)系。分治策略的實(shí)施使搜索SSP的個(gè)數(shù)只占測(cè)試模型SSP總數(shù)的一小部分，降低了算法的計(jì)算規(guī)模。同時(shí)，對(duì)于細(xì)分次數(shù)為N的SSP，計(jì)算空間點(diǎn)到SSP的最近距離僅需要搜索4 N＋4個(gè)網(wǎng)格頂點(diǎn)即可完成。如表2所示，在測(cè)試模型的頂點(diǎn)數(shù)目達(dá)到千萬(wàn)級(jí)的情況下，計(jì)算耗時(shí)仍很小。其中，最大耗時(shí)為0．626ms，最小耗時(shí)僅為0．129ms。測(cè)試結(jié)果表明算法的計(jì)算效率較高。

表2 計(jì)算10個(gè)測(cè)試點(diǎn)到Catmull－Clark細(xì)分曲面的有符號(hào)最近距離的測(cè)試結(jié)果

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

本文通過(guò)創(chuàng)建元胞數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了Catmull－Clark細(xì)分曲面的分片表示。在此基礎(chǔ)上，結(jié)合分治策略和多分辨率采樣技術(shù)，提出一種計(jì)算空間點(diǎn)到細(xì)分曲面有符號(hào)最近距離的算法。詳細(xì)描述了該算法的原理和實(shí)現(xiàn)步驟，并通過(guò)實(shí)例驗(yàn)證了算法的正確性和有效性。測(cè)試結(jié)果表明該算法穩(wěn)定性強(qiáng)，計(jì)算效率高，計(jì)算結(jié)果準(zhǔn)確。以本算法為基礎(chǔ)，計(jì)算細(xì)分曲面之間的最近距離，將是未來(lái)的研究方向。

［1］XU Rufeng，CHEN Zhitong，CHEN Wuyi．Grid algorithm for calculating the shortest distance from spatial point to free－form surface［J］．Computer Integrated Manufacturing Systems，2011，17（1）：95－100（in Chinese）．［徐汝鋒，陳志同，陳五一．計(jì)算點(diǎn)到曲面最短距離的網(wǎng)格法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2011，17（1）：95－100．］

［2］XIONG Zhigang，ZHANG Guankang．The algorithm research of minimum distance between two sculptured surfaces［J］．Journal of Engineering Graphics，1990，10（2）：27－31（in Chinese）．［熊志剛，張關(guān)康．雕塑曲面間最小距離的研究［J］．工程圖學(xué)學(xué)報(bào)，1990，10（2）：27－31．］

［3］SU Zhijian，WU Xutang，MAO Shimin．Genetic algorithms for solving the minimum distance between bezier curves and surfaces［J］．Machinery Design ＆ Manufacture，2003（6）：56－57（in Chinese）．［蘇智劍，吳序堂，毛世民．遺傳算法在求解空間曲線與曲面間最短距離中的應(yīng)用［J］．機(jī)械設(shè)計(jì)與制造，2003（6）：56－57．］

［4］LIAO Ping．Using particle swarm optimization algorithm to calculate the minimum distance from point to complex surface［J］．Computer Simulation，2009，26（8）：176－178（in Chinese）．［廖 平．用粒子群優(yōu)化算法計(jì)算點(diǎn)到復(fù)雜曲面最短距離［J］．計(jì)算機(jī)仿真，2009，26（8）：176－178．］

［5］FANG Xiang，BAO Hujun，WANG Ping'an，et al．Algorithm for fast calculating the nearest distance between space point and arbitrary polyhedron［J］．Journal of Computer Aided Design ＆ Computer Graphics，2001，13（9）：788－792（in Chinese）．［方 向，鮑虎軍，王平安，等．點(diǎn)到任意多面體距離的快速計(jì)算方法［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（9）：788－792．］

［6］ULLRICH T，SETTGAST V，KRISPEL U，et al．Distance calculation between a point and a subdivision surface［C］／／Proceedings of Vision，Modeling，and Visualization．Saarbrücken，Germany：MPII，2007：161－169．

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

［8］ZHANG J H，WANG G P．Improved error estimate for extraordinary Catmull－Clark subdivision surface patches［J］．The Visual Computer，2007，23（12）：1005－1014．

［9］CHENG F，YONG J．Subdivision depth computation for Catmull－Clark subdivision surfaces［J］．Computer Aided Design ＆Applications，2006，3（1／2／3／4）：485－494．

［10］MUSTAFA G，CHEN Falai，DENG Jiansong．Estimating error bounds for binary subdivision curves／surfaces［J］．Journal of Computational and Applied Mathematics，2006，193（2）：596－613．

［11］HUANG Zhangjin，DENG Jiansong，WANG Guoping．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．

［12］KRABMER P，CAZIER D，BECHMANN D．Extension of half－edges for the representation of multi－resolution subdivision surfaces［J］．The Visual Computer，2009，25（2）：149－163．

［13］DEFLORIANI L，KOBBELT L，PUPPO E．A survey on data structures for level－of－detail models［J］．Advances in Multi－resolution for Geometric Modelling，Series in Mathematics and Visualization，2004：49－74．DOI：10．1007／3－540－26808－1＿3．

［14］SETTGAST V，MüLLER K，F(xiàn)üNFZIG C，et al．Adaptive tesselation of subdivision surfaces［J］．Computers and Graphics，2004，28（1）：73－78．

［15］HALSTEAD M，KASS M，DEROSE T．Efficient fair interpolation using Catmull－Clark surfaces［C］／／Proceedings of SIGGRAPH 93．New York，N．Y．，USA：ACM，1993：35－44．