付 彤，曲慧雁

（1.吉林工程技術(shù)師范學(xué)院，吉林 長(zhǎng)春 130052；

2.吉林農(nóng)業(yè)大學(xué)信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130037）

最小距離分裂算法在NURBS曲面間的改進(jìn)

付 彤1，曲慧雁2

（1.吉林工程技術(shù)師范學(xué)院，吉林 長(zhǎng)春 130052；

2.吉林農(nóng)業(yè)大學(xué)信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130037）

基于分裂算法中最小距離在NURBS曲面間的應(yīng)用研究，提出了以包圍體來(lái)代替包圍盒（AABB）的思想，在求凸包間距離時(shí)選取了GJK算法，并對(duì)分裂算法進(jìn)行了改進(jìn)，從而在算法精度以及算法速度方面實(shí)現(xiàn)了極大地提高.

凸包；分裂；GIK算法；NURBS曲面

0 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展，特別是虛擬現(xiàn)實(shí)技術(shù)的不斷發(fā)展，碰撞檢測(cè)已經(jīng)成為計(jì)算機(jī)動(dòng)畫(huà)、計(jì)算幾何等研究領(lǐng)域的重要組成部分.因用戶(hù)間交互以及物體運(yùn)動(dòng)，使得虛擬環(huán)境下，物體之間的碰撞時(shí)常發(fā)生，考慮到此環(huán)境下對(duì)真實(shí)性保護(hù)的要求，對(duì)兩物體間碰撞發(fā)生的可能性必須給出及時(shí)的判斷，因而需要計(jì)算兩物體之間的距離.

進(jìn)行精確的碰撞檢測(cè)，對(duì)于提高虛擬環(huán)境的沉浸感有著至關(guān)重要的作用，而虛擬環(huán)境自身的復(fù)雜性和實(shí)時(shí)性對(duì)碰撞檢測(cè)提出了更高的要求.碰撞檢測(cè)主要依據(jù)虛擬空間中的任意兩個(gè)不可刺穿的物體不能存在于相同位置的空間區(qū)域這一命題.目前碰撞檢測(cè)算法有三類(lèi)：包圍盒層次法、空間剖分法、距離向量法［1－4］.空間多面體間距離成為求解問(wèn)題的焦點(diǎn)，目前其對(duì)于凸多面體的空間距離研究較多.如：文獻(xiàn)［5-6］對(duì)于兩凸多面體間提出了距離求解的快速算法，分別是GJK算法和LC算法.在碰撞檢測(cè)中，作者以參數(shù)曲面為基礎(chǔ)進(jìn)行了研究，做出了一些成就.文獻(xiàn)［7］主要研究表面為自由曲面物體的應(yīng)用問(wèn)題.國(guó)際標(biāo)準(zhǔn)組織（ISO）于1991年對(duì)于工業(yè)用品制定了STEP標(biāo)準(zhǔn)，其中數(shù)學(xué)中唯一用以定義的自由型曲線(xiàn)和曲面的方法就是NURBS，而NURBS方法恰恰可以定義絕大多數(shù)的自由曲線(xiàn)和曲面.目前能見(jiàn)到的有關(guān)曲面間距離的研究關(guān)于自由型的還比較少，而關(guān)于有理Bezier，其有向曲面間距離算法的研究在文獻(xiàn)［8］中已經(jīng)給出，并且該研究成果是前所未有的.

本文采用增量算法對(duì)凸包圍多面體與曲面控制點(diǎn)進(jìn)行求解，將GJK算法應(yīng)用與凸多面體的距離求解綜合起來(lái)，用包圍體代替原來(lái)的包圍盒算法，改進(jìn)了原有的分裂算法.

1 理論背景

1.1 NURBS曲面簡(jiǎn)介

NURBS曲面的表達(dá)式

其中：Vi，j為控制頂點(diǎn)，Wi，j為權(quán)因子，Bi，k（u）和Bj，l（v）分別為沿u向具有k次和沿v向具有l(wèi)次的B樣條的基函數(shù).

遞推公式如下：

其中：k為冪的次數(shù)，ui（i＝0，1，…，m）為節(jié)點(diǎn).

此外，文中還約定：端節(jié)點(diǎn)重復(fù)度對(duì)于u向矢量與v向矢量分別為k＋1與1＋1，從而在幾何性質(zhì)上NURBS曲面由于端節(jié)點(diǎn)和Bezier曲面同次有理，有相同的角點(diǎn).

1.2 分裂曲面原理介紹

節(jié)點(diǎn)插入算法在分裂NURBS曲面中是核心環(huán)節(jié).先給出節(jié)點(diǎn)插入在B樣條中的算法：

由算法容易得出，在新節(jié)點(diǎn)插入后，其矢量就會(huì)增加一個(gè)新區(qū)間；并且控制點(diǎn)每增加一個(gè)，對(duì)新控制頂點(diǎn)必須重新計(jì)算全因子.對(duì)同一節(jié)點(diǎn)而言，若節(jié)點(diǎn)有k次重復(fù)（B樣條中基函數(shù)冪次為k），在相應(yīng)節(jié)點(diǎn)處對(duì)NURBS曲線(xiàn)進(jìn)行分段，具體算法見(jiàn)文獻(xiàn)［9-10］.該分割算法基于NURBS曲面進(jìn)行了拓展.NURBS曲面中，要求分別插入u和v方向節(jié)點(diǎn)，對(duì)控制頂點(diǎn)進(jìn)行計(jì)算，要把曲面分成4份，并對(duì)生成的新拆分的子曲面片重新分配控制頂點(diǎn).

1.3 實(shí)現(xiàn)分裂算法的具體過(guò)程

需要對(duì)插入uknot和vkont的位置進(jìn)行尋找，并對(duì)其重復(fù)度分別進(jìn)行計(jì)算.節(jié)點(diǎn)插入后，賦值給分裂后的曲面控制頂點(diǎn)，并賦值給相應(yīng)的權(quán)因子.給出分裂算法的流程如下：

NURBS曲面作為首次輸入，并輸入ukont和vkontu這兩個(gè)u和v向所插入的節(jié)點(diǎn)

（1）取得ui和vi，即uknot和vkont處插入所對(duì)應(yīng)的位置.

（2）取得ukont和vkont節(jié)點(diǎn)分別的重復(fù)度ur，vr.

（3）對(duì)節(jié)點(diǎn)進(jìn)行插入，k-節(jié)點(diǎn)重復(fù)度即作為NURBS曲面次數(shù)的插入個(gè)數(shù).由此得m＋k－ur與m＋k－vr這兩個(gè)NURBS曲面1在插入節(jié)點(diǎn)沿控制頂點(diǎn)u向以及v向的個(gè)數(shù).

（4）對(duì)于nurbs1這個(gè)子曲面，曲面1NURBS中控制頂點(diǎn)分別為［l，…，ui－ur］和［l，…，vi－vr］，即沿u和v向.

（5）對(duì)于nurbs2這個(gè)子曲面，其控制頂點(diǎn)分別為［ui－ur，…，m＋k－ur］和［l，…，vi－vr］，也為曲面1NURBS沿u和v向.

（6）對(duì)于nurbs3這個(gè)子曲面，其控制頂點(diǎn)為［l，…，ui－ur］和［vi－vr，…，n＋k＋vr］，也為曲面1 NURBS中沿u和v兩個(gè)方向.

（7）對(duì)于nurbs4這個(gè)子曲面，得到控制頂點(diǎn)［ui－ur，…，m＋k－ur］和［vi－vr，…，n＋k＋vr］，也為曲面1NURBS中u和v方向.

（8）分別對(duì)各子曲面計(jì)算所生成的節(jié)點(diǎn)值.

以上的算法表明，對(duì)子曲面分裂后，控制頂點(diǎn)的數(shù)目不大于（等于只能取在控制頂點(diǎn)的數(shù)目恰好比NURBS曲面的次數(shù)多1這個(gè)條件下）原來(lái)曲面中控制頂點(diǎn)的個(gè)數(shù).在插入節(jié)點(diǎn)計(jì)算中，不但要用到插入的節(jié)點(diǎn)，也要根據(jù)公式（1.2）—（1.5）來(lái)計(jì)算.

1.4 分裂算法應(yīng)用于曲面NURBS的流程

先針對(duì)給出曲面間的最短距離，給出其上界的計(jì)算方法.在本文中的NURBS曲面的u向矢量和v向矢量中端節(jié)點(diǎn)的重復(fù)度分別取為k＋1和l＋1，故對(duì)NURBS曲面而言，也能有角點(diǎn)的相關(guān)幾何性質(zhì)，如果有角點(diǎn)，就必定在該曲面上.由此，在兩曲面間，其角點(diǎn)間的距離最小值就必不小于曲面間距離的最小值.故把角點(diǎn)之間距離的最小值暫時(shí)當(dāng)做是曲面之間距離最小值的上界，記為upper.

下面就將兩曲面進(jìn)行分裂，得到的新的子曲面片，我們對(duì)其兩兩配對(duì).針對(duì)任意兩個(gè)子曲面片位于每個(gè)子曲面對(duì)，以包圍盒來(lái)計(jì)算控制頂點(diǎn)間的距離.若包圍體間，其距離比upper大，那么一定找不到一個(gè)在曲面上的最短距離點(diǎn)存在于此子曲面對(duì)間，也就不需要再對(duì)這個(gè)子曲面對(duì)進(jìn)行下一步的對(duì)比.否則，需要對(duì)已得到的子曲面對(duì)計(jì)算位于兩子曲面中，角點(diǎn)之間的最短距離，并用它替代之前的upper，繼續(xù)進(jìn)行遞歸調(diào)用，達(dá)到分裂的層次hlevel為止.

由于分裂曲面后，都是在很靠近NURBS曲面得到的控制頂點(diǎn)，故對(duì)余下的節(jié)點(diǎn)逐一比對(duì)，找出可能有最短距離的那些子曲面上的控制點(diǎn)，并認(rèn)為兩NURBS曲面的最短距離即為控制頂點(diǎn)之間此前求出的最短距離，然后選取兩個(gè)距離最近的控制頂點(diǎn)，在兩NURBS曲面中，以其為近點(diǎn)對(duì)，對(duì)結(jié)果進(jìn)行輸出.

以上分裂算法中容易看出，搜索節(jié)點(diǎn)數(shù)過(guò)大主要是由于包圍盒過(guò)大，并且求解曲面間距離時(shí)采取的遞歸算法，其本質(zhì)就是搜索算法中的深度優(yōu)先.盡管分裂算法裁剪了搜索樹(shù)，但選擇擴(kuò)展節(jié)點(diǎn)卻非常盲目，因而對(duì)于子曲面片，即使不大可能存在近點(diǎn)對(duì)，也極易引起擴(kuò)展.

2 改進(jìn)算法

2.1 改進(jìn)算法在包圍盒中的主要思想

計(jì)算曲面包圍盒相對(duì)來(lái)說(shuō)較難.但如果控制頂點(diǎn)中，其權(quán)因子w比0大，凸包性上就顯現(xiàn)了NURBS曲面的優(yōu)勢(shì)，此時(shí)由控制頂點(diǎn)所構(gòu)造的凸包中必然包含了該曲面.因此就選取這些控制頂點(diǎn)，用形成的包圍體替代NURBS曲面上的點(diǎn)形成的包圍盒，對(duì)于兩個(gè)凸包的距離，凸多面體之間可以用計(jì)算最短距離的算法來(lái)求取，以此替代包圍盒之間距離算法和包圍盒算法.

定義2.1設(shè)S是空間中一個(gè)有限非空的點(diǎn)集，稱(chēng)閉凸集中包含了S最小的那個(gè)集合為S的凸殼，記作CH（S），并記BCH（S）為此凸殼的邊界.

定義2.2設(shè)多面體為P，若表面都是平面圖多邊形圍成的，每一對(duì)相交的面，其二面角在此多面體中都不大于π，那么稱(chēng)之為凸多面體.

因CH（S）是點(diǎn)集S的交，且包含了S的全體閉凸集，故BCH（S）作為空間點(diǎn)集S的邊界，也為凸多面體.

對(duì)于成熟空間點(diǎn)集而言有很多凸包算法，文中在構(gòu)成凸多面體時(shí)引入了增量算法.構(gòu)造一個(gè)空間四面體，將其認(rèn)為是初始的凸多面體，并逐次添加剩余頂點(diǎn).若添加的頂點(diǎn)已經(jīng)位于凸多面體之內(nèi)，那么這個(gè)頂點(diǎn)就不用再添加.若是位于凸多面體的外部，就在計(jì)算后生成一個(gè)新凸多面體.以下對(duì)此過(guò)程重復(fù)，所有頂點(diǎn)遍歷結(jié)束就生成了一個(gè)新的凸多面體.

2.2 位于凸多面體間的距離算法

在計(jì)算凸多面體之間的距離時(shí)，我們選取GJK算法.給出基本概念如下：

co（S）是位于凸多面體內(nèi)部且以S為頂點(diǎn)的點(diǎn).

定義2.4設(shè)凸多面體P與Q的 Minkowski差M＝｛x－y：x∈P，y∈Q｝.

容易得出，計(jì)算復(fù)雜度是P與Q的Minkowski差O（nm），其中P，Q的頂點(diǎn)數(shù)目分別為n，m.事實(shí)上，GJK算法中，完整的 Minkowski差不是必要的.特別需說(shuō)明的是，對(duì)于兩個(gè)凸多面體，它們的Minkowski差仍然為凸多面體.若兩個(gè)凸多面體相交，則M中必然能找到原點(diǎn).給出了Minkowski差的定義，那么從原點(diǎn)到M的最短距離便是P與Q之間最近的點(diǎn)的距離.故可通過(guò)求由原點(diǎn)至凸多面體M之間的距離作為P與Q間最短距離.

定義2.5對(duì)于凸多面體P，其支撐函數(shù)為

式中v為方向.該函數(shù)通過(guò)返回值形成P的一頂點(diǎn).使用支撐函數(shù)，對(duì)點(diǎn)集P，便可找到v方向上的最大值的頂點(diǎn).

對(duì)于P與Q的Minkowski差M，支撐函數(shù)為

（2.1）式表明，對(duì)于P和Q的Minkowski差M，其支撐函數(shù)差只要遍歷P和Q的所有頂點(diǎn)而不用遍歷整個(gè)Minkowski的差.

定義2.6在3維空間中仿射獨(dú)立的點(diǎn)集，以其為頂點(diǎn)的凸多面體即為一個(gè)簡(jiǎn)單體（Simplex）.

借助P和Q的Minkowski差M的定義，計(jì)算凸多面體M到原點(diǎn)距離問(wèn)題就是計(jì)算P與Q間的距離的最小值問(wèn)題.

在對(duì)原點(diǎn)距離一個(gè)凸多面體的計(jì)算中，GJK算法給出了一簡(jiǎn)單體序列W，它們與原點(diǎn)之間的距離依次遞減.而最初的W0，可以任意選取M中的一點(diǎn)充當(dāng).現(xiàn)在對(duì)于已存在的簡(jiǎn)單體Wi，來(lái)計(jì)算Wi＋1，即下一個(gè)簡(jiǎn)單體.先調(diào)用出支撐函數(shù)，返回頂點(diǎn)w，并添加到函數(shù)中，進(jìn)而通過(guò)距離子算法來(lái)求得最近距離點(diǎn)v和W至原點(diǎn)的距離.與v無(wú)關(guān)的點(diǎn)刪除，就是下一個(gè)簡(jiǎn)單體Wi＋1.

用該方法，一個(gè)與原點(diǎn)距離更短的簡(jiǎn)單體由此產(chǎn)生，對(duì)這一過(guò)程進(jìn)行重復(fù)，直至在支撐函數(shù)不再有新的定點(diǎn)返回.因?yàn)獒槍?duì)三維空間，故序列W中對(duì)于每個(gè)元素至多只能取3個(gè)頂點(diǎn).

2.3 算法改進(jìn)后的流程

（1）首先對(duì)曲面1NURBS和曲面2NURBS這兩個(gè)參數(shù)曲面進(jìn)行輸入，并輸入上界upper，即兩曲面間最短距離的邊界，在本程序中，這里upper為全局變量.

（2）若曲面所分裂的層數(shù)已經(jīng)到達(dá)hlevel，則進(jìn)行點(diǎn)點(diǎn)比對(duì)以得到NURBS曲面1和NURBS曲面2，并以此控制頂點(diǎn)之間最短距離，若該距離比upper小，則記取pt1，pt2這兩個(gè)對(duì)應(yīng)點(diǎn)，返回.

（3）對(duì)分裂算法進(jìn)行調(diào)用，對(duì)兩NURBS曲面作分裂，得到nurbs1arr和nurbs2arr這兩個(gè)子曲面數(shù)組.（4）求取nurbs1arr與nurbs2arr的全部曲面片包圍盒.

（5）兩兩配對(duì)nurbs1arr與nurbs2arr的子曲面片，并在數(shù)組skarr內(nèi)進(jìn)行記錄.求取每個(gè)子曲面對(duì)對(duì)其最近角點(diǎn)的距離，并在數(shù)組mptdis中記錄.

（6）取得位于最近角點(diǎn)距離最小子曲面片對(duì)，同時(shí)記錄nurbs1和nurbs2這兩個(gè)對(duì)應(yīng)的子曲面片對(duì).

（7）若nurbs1，nurbs2子曲面對(duì)的最近角點(diǎn)對(duì)距離比upper小，那么upper用該距離代替.

（8）按照最近角點(diǎn)距離對(duì)數(shù)組skarr進(jìn)行排序.

（9）對(duì)曲面片數(shù)組skarr進(jìn)行遍歷，若子曲面片對(duì)之間包圍盒的距離小于upper，則以子曲面nurbs1和nurbs2為參數(shù)，對(duì)本程序遞歸調(diào)用；否則返回.

3 實(shí)驗(yàn)結(jié)果

π1，π2為兩個(gè)凸曲面，選取改進(jìn)后的分裂算法（為方便起見(jiàn)，當(dāng)分裂層次為7時(shí)，不再選用新算法），與原來(lái)的算法比較，計(jì)算兩曲面間的最小距離，其結(jié)果如表1.

表1 改進(jìn)前后分裂算法計(jì)算的最小距離對(duì)比

表中l(wèi)代表分裂的層數(shù)，n是搜索節(jié)點(diǎn)的數(shù)目，t是計(jì)算所用的時(shí)間.明顯看出，搜索節(jié)點(diǎn)數(shù)大量減少，改進(jìn)包圍盒算法后，大大提高了算法效率.根據(jù)表1的結(jié)果，分裂層數(shù)增加一層，就增加大約2倍搜索節(jié)點(diǎn)數(shù).相對(duì)于包圍盒，由于包圍多面體最短距離更貼近曲面真實(shí)值，很大程度上減少了搜索節(jié)點(diǎn)的數(shù)目，算法速度得到了提高.當(dāng)分裂層次為7時(shí)，由于不再選取包圍體而是選取包圍盒使搜索節(jié)點(diǎn)突然增加.

［1］ 周云波，閆清東，李宏才.虛擬環(huán)境中碰撞檢測(cè)算法分析［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18（1）：103-107.

［2］ NOBORIO H，F(xiàn)UKUDA S，ARIMOTO S.Fast interference check method using octree［J］.Advanced Robotics，1989，3（3）：193-212.

［3］ LIN M C，MANOCHA D，CANNY J F.Fast collision detection between geometric models technical report TR93-004［R］.North Carolina：Chapel Hill，1993.

［4］ GINO VAN DEN BER GEN.A fast and robust GJK implementation for collison detection of convex objects［EB／OR］.［1999-12-04］.http：／／www.win.tue.nl／cs／tt／gino／solid／index.html.

［5］ GIBERT E G，JOHNSON D W，KEERTHI S S.A fast procedure for computing the distance between complex objects in threedimensional space［J］.IEEETrans Robotics＆Automation，1988，4（2）：79-85.

［6］ MING C LIN，JOHN F CANNY.A fast algorithm for incremental distance caculation［C］／／Proceeding of the 1991IEEE International Conference on Robotics and Automation，California：Sacramento，1991：276-283.

［7］ TURNBULL C，CAMERON S.Computing distances between NURBS-defined convex objects［C］／／In Proceedings of IEEE International Conference on Robotics and Automation，Piscataway：1998.

［8］ FEDERICO THOMAS，CONLIN TURNBULL，STEPHEN.Computing signed distance between free-form objects［C］／／Procceding of the 2000IEEE International Conference On Robotics ＆ Automation，San Francisco，CA：2000：3713-3718.

［9］ 劉浩.NURBS曲面間的最短距離［D］.南京：南京航空航天大學(xué)，2002.

［10］ 朱心雄.自由曲線(xiàn)曲面造型技術(shù)［M］.北京：科學(xué)出版社，2000：65-72.

Improved algorithm on minimum distance splitting between the NURBS surfaces

FU Tong1，QU Hui-yan2

（1.Jilin Teachers Institute of Engineering and Technology，Changchun 130052，China；
2.College of Information Technology，Jilin Agricultural University，Changchun 130037，China）

Collision detection is the key technology of VR.And the distance of convex geometric is the important fact of collision detection.The proposed method based upon the technique of splitting the NURBS surfaces consists of the convex hull displaced of the convex box（AABB）and GJK algorithm are employed to improve the spilt algorithm's performance.The implement shows that the improved spilt algorithm is more precisely and quickly.

convex hull；spilt of NURBS surfaces；GJK algorithm；NURBS surfaces

TP 301.6

520·1040

A

1000-1832（2011）04-0049-05

2011-07-25

國(guó)家自然科學(xué)基金資助項(xiàng)目（61106068）；吉林省科技發(fā)展計(jì)劃項(xiàng)目（201101115）.

付彤（1965—），女，副教授，主要從事計(jì)算方法研究.

陶 理）