【正文】 93年，它以?xún)A斜圖(Slope Diagram)表示法為基礎(chǔ)[13]。計(jì)算兩個(gè)多面體的Minkowski和等同于分別計(jì)算兩個(gè)多面體的傾斜圖，然后合并它們的傾斜圖，并從合并的傾斜圖中提取Minkowski和的邊界值[14]。通過(guò)使用立體投影(Stereographic Projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問(wèn)題降低到較低維數(shù)的空間中進(jìn)行解決。1997年，：首先，對(duì)每個(gè)多邊形(或多面體)進(jìn)行凸剖分，得到若干個(gè)子凸多邊形(或多面體)；然后，計(jì)算取自不同多邊形(或多面體)的所有可能成對(duì)的子凸剖分的Minkowski和；最后，合并第二步中所有子Minkowski和多邊形(多面體)[15]?；谏厦娴钠史挚蚣?，2002年，并提出了多種不同的剖分方法[16]。由于凹多面體的Minkowski和求和算法過(guò)于復(fù)雜，目前，人們主要研究能夠得到滿(mǎn)足某些標(biāo)準(zhǔn)的近似值的求和算法，如文獻(xiàn)[17,18]。2000年，[19]中給出了計(jì)算普通多邊形的Minkowski和算法，該算法是基于CGAL(Computational Geometry Algorithm Library)[20]實(shí)現(xiàn)的。2001年，基于Ghosh在文獻(xiàn)[13]中提出的傾斜圖表示法，最終提出了在線(xiàn)性時(shí)間內(nèi)計(jì)算三維空間凸多面體Minkowski和的新方法，但是該方法只對(duì)非常簡(jiǎn)單的凸多面體適用[21]。2002年，E. ，提供了為建造平面集合的精確、有效的Minkowski和所使用的軟件包[22]。2003年，(Convex Hull)的凸多面體的Minkowski和求和算法與基于傾斜圖的凸多面體的Minkowski和求和算法進(jìn)行了優(yōu)化[23]。遵循文獻(xiàn)[13]提出的方法，2007年，(Cubical Gaussian Map)計(jì)算三維空間內(nèi)凸多面體的精確Minkowski和算法[24]，該算法也是基于CGAL實(shí)現(xiàn)的。 國(guó)內(nèi)研究現(xiàn)狀國(guó)內(nèi)對(duì)Minkowski和算法的研究起步較晚。其中，對(duì)凸多面體的Minkowski和算法的研究取得了一些很好的成果；對(duì)凹多面體的剖分和子Minkowski和多面體的合并的研究也有了一定的進(jìn)展。2007年，郭希娟和高艷麗提出了基于正四面體中心投影RTCP(Regular Tetrahedron Central Projection)和三角形內(nèi)簡(jiǎn)單平面凸劃分的疊置算法計(jì)算凸多面體精確Minkowski和的優(yōu)化算法[25]?；谡拿骟w中心投影算法，2008年，郭希娟和謝蕾又給出了進(jìn)一步優(yōu)化—基于正四面體高斯映射RTGM(Regular Tetrahedron Gaussian Map)的算法[26]。通過(guò)對(duì)國(guó)內(nèi)外研究現(xiàn)狀的分析，可以得出計(jì)算多邊形或者多面體的Minkowski和算法主要有六種，即基于凸包的求和算法、基于凸剖分的求和算法、基于傾斜圖的求和算法、基于立方體高斯映射的求和算法、基于正四面體中心投影的求和算法以及基于正四面體高斯映射的算法。其中，基于凸包的Minkowski和求和算法是非常著名的算法之一，該算法直接源于Minkowski和的定義，它可以表示為：，其中，CH表示凸包操作，、分別表示多面體P和Q中頂點(diǎn)的集合[15]。在計(jì)算Minkowski和多面體的過(guò)程中，該算法需要區(qū)分內(nèi)部點(diǎn)、外部點(diǎn)和邊界點(diǎn)，創(chuàng)建這些點(diǎn)集的凸包不但需要很高的計(jì)算費(fèi)用，并且該算法的計(jì)算結(jié)果不是圖而是一個(gè)點(diǎn)集?；趦A斜圖的Minkowski和求和算法，根據(jù)高斯映射的規(guī)則，把多面體的體元(包括多面體的頂點(diǎn)、棱、面)映射到單位球表面，并采用立體投影方法把每個(gè)多面體的傾斜圖轉(zhuǎn)化為平面圖形，然后計(jì)算平面圖形的疊置，從疊置的結(jié)果中抽取Minkowski和的邊界值。采用立體投影方法不僅會(huì)使算法在處理退化情況時(shí)存在著很大的局限性，而且會(huì)增加算法的實(shí)現(xiàn)難度，很難得到精確的計(jì)算結(jié)果。基于立方體高斯映射的Minkowski和求和算法，通過(guò)自定義的立方體高斯映射，把三維空間內(nèi)的凸多面體的體元映射到立方體表面，從而得到六個(gè)平面劃分面，計(jì)算兩個(gè)凸多面體的Minkowski和就等同于計(jì)算六對(duì)平面劃分的疊置。通過(guò)計(jì)算六對(duì)平面劃分中各面的附加信息，得到Minkowski和多面體的立方體高斯映射表示，最后求逆映射得到精確的Minkowski和多面體?；谡拿骟w中心投影的Minkowski和算法，首先按照高斯映射規(guī)則，將凸多面體映射到單位球面上，再取單位球面的外切正四面體，通過(guò)自定義的正四面體中心投影得到凸多面體在正四面體上的投影。求兩個(gè)凸多面體的Minkowski和等同于求四對(duì)平面劃分的疊置。通過(guò)計(jì)算四對(duì)平面劃分中各面的附加信息，得到新多面體的正四面體中心投影，最后求逆映射得到Minkowski和多面體?；谡拿骟w高斯映射的Minkowski和算法，為計(jì)算兩個(gè)給定位置和形態(tài)的凸多面體的Minkowski和表示，取凸多面體的外切正四面體，根據(jù)自定義的正四面體高斯映射把凸多面體映射到外切正四面體的四個(gè)表面上，求兩個(gè)凸多面體的Minkowski和等同于求四對(duì)平面劃分的疊置，通過(guò)計(jì)算平面劃分中各面的附加信息，得到新多面體的正四面體高斯映射，最后求逆映射得到Minkowski和多面體?；谕蛊史值腗inkowski和算法，是計(jì)算凹多邊形或凹多面體的Minkowski和的常用算法。對(duì)于二維空間內(nèi)的凹多邊形而言，常用的方法就是把凹多邊形剖分為若干個(gè)凸多邊形，通過(guò)計(jì)算凸多邊形Minkowski子和的并來(lái)得到凹多邊形的Minkowski和。理論上，剖分策略的選擇與求和速度無(wú)關(guān)，但實(shí)際上，它嚴(yán)重影響著整個(gè)求和算法的運(yùn)行時(shí)間，特別是計(jì)算三維空間內(nèi)的凹多面體的Minkowski和。因此，迫切需要尋找某種策略來(lái)降低計(jì)算凹多面體的Minkowski和的求和算法的時(shí)間復(fù)雜度，同時(shí)由于基于剖分法中的合并算法的復(fù)雜度很高，目前仍然沒(méi)有人提出計(jì)算凹多面體的精確Minkowski和的算法。因此研究凹多面體的精確Minkowski和求和算法是一項(xiàng)具有挑戰(zhàn)性及重要意義的課題。 Minkowski和算法的應(yīng)用Minkowski和算法在許多領(lǐng)域中有著廣泛的應(yīng)用，如機(jī)器人學(xué)、碰撞檢測(cè)、模擬仿真、計(jì)算機(jī)圖形學(xué)等等，下面重點(diǎn)介紹該算法在機(jī)器人路徑規(guī)劃和碰撞檢測(cè)中的應(yīng)用。 機(jī)器人路徑規(guī)劃?rùn)C(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計(jì)出獨(dú)立自主的機(jī)器人。在指揮這種機(jī)器人時(shí)，只需要告訴它去做什么，而不必告訴它如何去做，其中尤為重要的一個(gè)方面就是，機(jī)器人應(yīng)該懂得如何對(duì)自己的運(yùn)動(dòng)進(jìn)行規(guī)劃[27]。路徑規(guī)劃是機(jī)器人學(xué)算法中的一個(gè)重要問(wèn)題，其本質(zhì)是在眾多障礙物之間為機(jī)器人尋找一條最優(yōu)或近似最優(yōu)的無(wú)碰撞路徑，該問(wèn)題經(jīng)常用位姿空間方法來(lái)描述。所謂的位姿空間，也稱(chēng)C空間，是機(jī)器人的參數(shù)空間；機(jī)器人的工作空間是機(jī)器人在其中實(shí)際運(yùn)動(dòng)的那個(gè)空間，也就是真實(shí)的世界。自由C空間(Free Configuration Space)是機(jī)器人避免與障礙物發(fā)生碰撞的所有位置點(diǎn)的集合[27]。為了規(guī)劃路徑，需要擁有一個(gè)能夠捕捉自由位姿空間連通性的表示，而Minkowski和算法可以來(lái)計(jì)算所需的表示，并且能夠獲得一條精確的無(wú)碰撞路徑。假設(shè)多面體P為工作空間中的障礙物，多面體R為移動(dòng)機(jī)器人，那么通過(guò)計(jì)算位姿空間障礙物來(lái)確定一條無(wú)碰撞的路徑，這個(gè)問(wèn)題就轉(zhuǎn)變?yōu)橛?jì)算多面體P與R的Minkowski和，其中R與R關(guān)于坐標(biāo)原點(diǎn)對(duì)稱(chēng)。 碰撞檢測(cè)碰撞檢測(cè)是檢測(cè)兩個(gè)物體在空間中是否重疊或它們的邊界線(xiàn)是否至少共享一個(gè)點(diǎn)[17]。在虛擬環(huán)境中，由于用戶(hù)的交互，物體之間經(jīng)常發(fā)生碰撞，為保持虛擬環(huán)境的真實(shí)感和用戶(hù)的沉浸感，快速精確的碰撞檢測(cè)是必不可少的。傳統(tǒng)的碰撞檢測(cè)方法主要有空間分解法和層次包圍盒技術(shù)，這兩種算法都只能近似的檢測(cè)物體是否發(fā)生碰撞，Minkowski和算法能夠精確地檢測(cè)出物體之間是否發(fā)生碰撞。該問(wèn)題用滲透深度來(lái)描述，兩個(gè)多面體P和Q的滲透深度是指使得兩個(gè)多面體不相交，其中一個(gè)多面體必須移動(dòng)的最小距離[17]。通過(guò)計(jì)算原心到Minkowski和()表面上的最小距離來(lái)得到。若滲透深度大于等于零，說(shuō)明兩個(gè)多面體發(fā)生碰撞，反之，兩個(gè)多面體不會(huì)發(fā)生碰撞。 本文研究?jī)?nèi)容本文在對(duì)國(guó)內(nèi)外研究現(xiàn)狀全面分析的基礎(chǔ)上，完成對(duì)三維空間內(nèi)凹多面體Minkowski和求和算法的進(jìn)一步研究，主要包括下述內(nèi)容。(1)計(jì)算簡(jiǎn)單凸多面體的Minkowski和的求和算法 通過(guò)深入研究正四面體中心投影算法和正四面體高斯映射算法，發(fā)現(xiàn)這兩種算法都需要計(jì)算四次劃分平面疊置，并且都沒(méi)有給出具體的映射函數(shù)關(guān)系式。因此，本文提出了正四面體映射和點(diǎn)投影的概念，把三維空間的問(wèn)題轉(zhuǎn)換到二維空間進(jìn)行解決，且只需要計(jì)算一對(duì)平面劃分的疊置，更高效的計(jì)算凸多面體的精確Minkowski和。(2)簡(jiǎn)單凹多面體的剖分算法 通過(guò)深入研究國(guó)內(nèi)外凹多面體的剖分算法，發(fā)現(xiàn)大多數(shù)的剖分算法會(huì)生成大量新點(diǎn)，產(chǎn)生很多凸多面體。因此，本文采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法，該算法不僅不產(chǎn)生新的頂點(diǎn)，而且能夠處理有空洞的多面體。(3)計(jì)算簡(jiǎn)單凹多面體的Minkowski和求和算法 首先，根據(jù)(2)中提出的剖分算法對(duì)凹多面體進(jìn)行剖分，得到若干子凸多面體；其次，利用(1)中提出的求和算法計(jì)算所有可能成對(duì)的子凸多面體的Minkowski和；最后，在合并子凸Minkowski和多面體時(shí)，利用已改進(jìn)的Enhanced Marching Cubes算法獲得凹多面體的近似的Minkowski和多面體邊界。 本文組織結(jié)構(gòu)論文分為5章，其余部分組織如下。第2章介紹與本課題相關(guān)的基礎(chǔ)理論。首先，是對(duì)基本幾何定義的介紹；然后，闡述了Minkowski和的定義、性質(zhì)及相關(guān)的幾何操作；最后，介紹有關(guān)算法的基本知識(shí)，該部分為課題的研究打下了堅(jiān)實(shí)的理論基礎(chǔ)。第3章提出了一種新的計(jì)算凸多面體的Minkowski和的求和算法。首先，介紹現(xiàn)有的求和算法，分析它的主要思想；然后，以提高算法的執(zhí)行效率為目標(biāo)，提出正四面體映射和點(diǎn)投影的概念，給出正四面體映射和點(diǎn)投影的映射規(guī)則，并由此提出基于該映射的凸多面體的精確Minkowski和求和算法。最后，對(duì)算法的時(shí)間復(fù)雜度進(jìn)行了分析。第4章提出了一種新的凹多面體的剖分算法，并給出了計(jì)算凹多面體的Minkowski和求和算法思想。以提高算法的精確度和效率為目標(biāo)，首先，本章采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法；其次，在合并子凸多面體Minkowski和時(shí)，利用現(xiàn)有已改進(jìn)的Enhanced Marching Cubes算法，最終獲得近似的多面體Minkowski和邊界；最后，給出計(jì)算簡(jiǎn)單凹多面體Minkowski和的算法的總體思想。第5章是實(shí)驗(yàn)與分析，對(duì)所研究的內(nèi)容及算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證并給出實(shí)驗(yàn)結(jié)果。最后，對(duì)本課題進(jìn)行了全面總結(jié)，同時(shí)針對(duì)課題中存在的問(wèn)題提出了進(jìn)一步改進(jìn)的思路，并規(guī)劃了未來(lái)的研究方向。第2章 理論基礎(chǔ)下面給出一些本章中將要用到的幾何概念、定義和基礎(chǔ)知識(shí)。 相關(guān)的幾何定義本文考慮的對(duì)象是歐幾里得三維空間中的點(diǎn)集，假設(shè)有一個(gè)參考坐標(biāo)系，使得每個(gè)點(diǎn)表示為相應(yīng)維數(shù)的笛卡爾坐標(biāo)的向量。除了點(diǎn)之外，還將考慮包含兩個(gè)給定點(diǎn)的直線(xiàn)、直線(xiàn)上兩定點(diǎn)確定的直線(xiàn)段、三個(gè)給定點(diǎn)確定的平面等。下面給出本文所涉及到的基本幾何對(duì)象的定義。 歐幾里得空間若用(或)表示維歐幾里得空間，那么具有度量的實(shí)數(shù)的元組空間，稱(chēng)為歐幾里得空間[28]。 點(diǎn)中的點(diǎn)定義為一個(gè)元組。點(diǎn)也可以解釋為有個(gè)分量的向量，此向量的起點(diǎn)為坐標(biāo)原點(diǎn)，終點(diǎn)為點(diǎn)[28]。點(diǎn)是整個(gè)幾何學(xué)的基礎(chǔ)，它只有位置，沒(méi)有大小。 直線(xiàn)與線(xiàn)段在中給定兩個(gè)不同的點(diǎn)和，線(xiàn)性組合(是實(shí)數(shù)，即)是中的一條直線(xiàn)[28]。給定中兩個(gè)不同的點(diǎn)和，若在線(xiàn)性組合中加入條件，則得到點(diǎn)和的凸組合，即(，)，此凸組合描述了連接兩點(diǎn)和的直線(xiàn)段，并記為(無(wú)序?qū)?[28]。線(xiàn)段是直線(xiàn)的一部分，并以?xún)蓚€(gè)端點(diǎn)為界限。 多面體由若干平面多邊形圍成的封閉連通的空間區(qū)域稱(chēng)為多面體(允許有洞)[29]。一般說(shuō)來(lái)，多面體是指邊界和內(nèi)部域的并。多邊形的頂點(diǎn)和邊是多面體的頂點(diǎn)和邊，多邊形是多面體的小面。 平面圖及平面劃分假設(shè)圖G=(V，E)，其中V為頂點(diǎn)集，E為邊集，如果圖G能夠沒(méi)有交叉地嵌入平面，那么稱(chēng)圖G為平面圖。平面圖的直線(xiàn)平面嵌入確定平面的一個(gè)劃分，稱(chēng)為平面劃分(也稱(chēng)平面剖分)[28]。設(shè)平面圖的頂點(diǎn)數(shù)、邊數(shù)和區(qū)域數(shù)分別為v，e和f，則由歐拉公式有ve+f=2。 凸集與凸包假設(shè)S是二維平面上的非空點(diǎn)集，p1和p2是S中任意兩點(diǎn)，若存在一點(diǎn)p=tp1+(1t)p2，其中，則稱(chēng)S是凸集[30]。這就是說(shuō)，如果S中任意兩點(diǎn)所連線(xiàn)段全部位于S之中，那么S是凸的。此定義可以推廣到高維。平面中n個(gè)點(diǎn)的有限集合S的凸包CH(S)是一個(gè)凸多邊形[30]。在中，S的CH(S)是包含S的最小凸域的邊界，其頂點(diǎn)為S中的點(diǎn)，并且S中所有的點(diǎn)均包含在CH(S)內(nèi)。 基礎(chǔ)知識(shí)及內(nèi)容下面將給出Minkowski和的定義、性質(zhì)及相關(guān)的幾何操作。 Minkowski和的定義Minkowski和的定義是由德國(guó)數(shù)學(xué)家Hermann Minkowski最早提出的。在歐幾里得空間內(nèi)，假設(shè)P和Q為兩個(gè)封閉的幾何對(duì)象，它們的Minkowski和可以表示為：在不改變兩個(gè)操作數(shù)相對(duì)方位的情況下，一個(gè)操作數(shù)Q沿著另一個(gè)操作數(shù)P的外輪廓滑行，Q的參考點(diǎn)經(jīng)過(guò)的軌跡就是P和Q的Minkowski和。如圖21所示。圖21 P和Q的Minkowski和Fig. 21 The Minkowski Sum of P and Q另外，P和Q的Minkowski和也可以表示為幾何對(duì)象M，其中p和q分別為屬于幾何對(duì)象P和Q的點(diǎn)，為位置矢量與的矢量和。例如，在歐幾里得二維平面內(nèi)，假設(shè)并且，那么有。下面給出二維平面內(nèi)兩個(gè)三角形的Minkowski和，如圖22所示。PP圖22 三角形P和Q的Minkowski和Fig. 22 Minkowski Sum of triangle P and Q Minkowski和的性質(zhì)從上面的定義可知，計(jì)算兩個(gè)幾何對(duì)象S1與S2的Minkowski和具有下列性質(zhì)[31,32]。(1