最小距離分裂算法在NURBS曲面間的改進

付 彤，曲慧雁

（1.吉林工程技術師范學院，吉林 長春 130052；

2.吉林農業大學信息技術學院，吉林 長春 130037）

最小距離分裂算法在NURBS曲面間的改進

付 彤1，曲慧雁2

（1.吉林工程技術師范學院，吉林 長春 130052；

2.吉林農業大學信息技術學院，吉林 長春 130037）

基于分裂算法中最小距離在NURBS曲面間的應用研究，提出了以包圍體來代替包圍盒（AABB）的思想，在求凸包間距離時選取了GJK算法，并對分裂算法進行了改進，從而在算法精度以及算法速度方面實現了極大地提高.

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

0 引言

隨著計算機技術的發展，特別是虛擬現實技術的不斷發展，碰撞檢測已經成為計算機動畫、計算幾何等研究領域的重要組成部分.因用戶間交互以及物體運動，使得虛擬環境下，物體之間的碰撞時常發生，考慮到此環境下對真實性保護的要求，對兩物體間碰撞發生的可能性必須給出及時的判斷，因而需要計算兩物體之間的距離.

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

本文采用增量算法對凸包圍多面體與曲面控制點進行求解，將GJK算法應用與凸多面體的距離求解綜合起來，用包圍體代替原來的包圍盒算法，改進了原有的分裂算法.

1 理論背景

1.1 NURBS曲面簡介

NURBS曲面的表達式

其中：Vi，j為控制頂點，Wi，j為權因子，Bi，k（u）和Bj，l（v）分別為沿u向具有k次和沿v向具有l次的B樣條的基函數.

遞推公式如下：

其中：k為冪的次數，ui（i＝0，1，…，m）為節點.

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

1.2 分裂曲面原理介紹

節點插入算法在分裂NURBS曲面中是核心環節.先給出節點插入在B樣條中的算法：

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

1.3 實現分裂算法的具體過程

需要對插入uknot和vkont的位置進行尋找，并對其重復度分別進行計算.節點插入后，賦值給分裂后的曲面控制頂點，并賦值給相應的權因子.給出分裂算法的流程如下：

NURBS曲面作為首次輸入，并輸入ukont和vkontu這兩個u和v向所插入的節點

（1）取得ui和vi，即uknot和vkont處插入所對應的位置.

（2）取得ukont和vkont節點分別的重復度ur，vr.

（3）對節點進行插入，k-節點重復度即作為NURBS曲面次數的插入個數.由此得m＋k－ur與m＋k－vr這兩個NURBS曲面1在插入節點沿控制頂點u向以及v向的個數.

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

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

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

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

（8）分別對各子曲面計算所生成的節點值.

以上的算法表明，對子曲面分裂后，控制頂點的數目不大于（等于只能取在控制頂點的數目恰好比NURBS曲面的次數多1這個條件下）原來曲面中控制頂點的個數.在插入節點計算中，不但要用到插入的節點，也要根據公式（1.2）—（1.5）來計算.

1.4 分裂算法應用于曲面NURBS的流程

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

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

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

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

2 改進算法

2.1 改進算法在包圍盒中的主要思想

計算曲面包圍盒相對來說較難.但如果控制頂點中，其權因子w比0大，凸包性上就顯現了NURBS曲面的優勢，此時由控制頂點所構造的凸包中必然包含了該曲面.因此就選取這些控制頂點，用形成的包圍體替代NURBS曲面上的點形成的包圍盒，對于兩個凸包的距離，凸多面體之間可以用計算最短距離的算法來求取，以此替代包圍盒之間距離算法和包圍盒算法.

定義2.1設S是空間中一個有限非空的點集，稱閉凸集中包含了S最小的那個集合為S的凸殼，記作CH（S），并記BCH（S）為此凸殼的邊界.

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

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

對于成熟空間點集而言有很多凸包算法，文中在構成凸多面體時引入了增量算法.構造一個空間四面體，將其認為是初始的凸多面體，并逐次添加剩余頂點.若添加的頂點已經位于凸多面體之內，那么這個頂點就不用再添加.若是位于凸多面體的外部，就在計算后生成一個新凸多面體.以下對此過程重復，所有頂點遍歷結束就生成了一個新的凸多面體.

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

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

co（S）是位于凸多面體內部且以S為頂點的點.

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

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

定義2.5對于凸多面體P，其支撐函數為

式中v為方向.該函數通過返回值形成P的一頂點.使用支撐函數，對點集P，便可找到v方向上的最大值的頂點.

對于P與Q的Minkowski差M，支撐函數為

（2.1）式表明，對于P和Q的Minkowski差M，其支撐函數差只要遍歷P和Q的所有頂點而不用遍歷整個Minkowski的差.

定義2.6在3維空間中仿射獨立的點集，以其為頂點的凸多面體即為一個簡單體（Simplex）.

借助P和Q的Minkowski差M的定義，計算凸多面體M到原點距離問題就是計算P與Q間的距離的最小值問題.

在對原點距離一個凸多面體的計算中，GJK算法給出了一簡單體序列W，它們與原點之間的距離依次遞減.而最初的W0，可以任意選取M中的一點充當.現在對于已存在的簡單體Wi，來計算Wi＋1，即下一個簡單體.先調用出支撐函數，返回頂點w，并添加到函數中，進而通過距離子算法來求得最近距離點v和W至原點的距離.與v無關的點刪除，就是下一個簡單體Wi＋1.

用該方法，一個與原點距離更短的簡單體由此產生，對這一過程進行重復，直至在支撐函數不再有新的定點返回.因為針對三維空間，故序列W中對于每個元素至多只能取3個頂點.

2.3 算法改進后的流程

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

（2）若曲面所分裂的層數已經到達hlevel，則進行點點比對以得到NURBS曲面1和NURBS曲面2，并以此控制頂點之間最短距離，若該距離比upper小，則記取pt1，pt2這兩個對應點，返回.

（3）對分裂算法進行調用，對兩NURBS曲面作分裂，得到nurbs1arr和nurbs2arr這兩個子曲面數組.（4）求取nurbs1arr與nurbs2arr的全部曲面片包圍盒.

（5）兩兩配對nurbs1arr與nurbs2arr的子曲面片，并在數組skarr內進行記錄.求取每個子曲面對對其最近角點的距離，并在數組mptdis中記錄.

（6）取得位于最近角點距離最小子曲面片對，同時記錄nurbs1和nurbs2這兩個對應的子曲面片對.

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

（8）按照最近角點距離對數組skarr進行排序.

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

3 實驗結果

π1，π2為兩個凸曲面，選取改進后的分裂算法（為方便起見，當分裂層次為7時，不再選用新算法），與原來的算法比較，計算兩曲面間的最小距離，其結果如表1.

表1 改進前后分裂算法計算的最小距離對比

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

［1］ 周云波，閆清東，李宏才.虛擬環境中碰撞檢測算法分析［J］.系統仿真學報，2006，18（1）：103-107.

［2］ NOBORIO H，FUKUDA 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］.南京：南京航空航天大學，2002.

［10］ 朱心雄.自由曲線曲面造型技術［M］.北京：科學出版社，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

國家自然科學基金資助項目（61106068）；吉林省科技發展計劃項目（201101115）.

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

陶 理）