三維空間內(nèi)凹多面體的Minkowski和的算法研究

1、學位論文三維空間內(nèi)凹多面體的minkowski和的算法研究2009年11月工學碩士學位論文三維空間內(nèi)凹多面體的minkowski和的算法研究碩士研究生：導師：申請學位級別：工學碩士學 科、專 業(yè)：計算機應用技術(shù)所 在 單 位：信息科學與工程學院授予學位單位：classified index: tp301.6u.d.c.: 654dissertation for the master degree in engineeringresearch on computing minkowski sum of non-convex polyhedral in thress demensioncandid

2、ate:supervisor:academic degree applied for:master of engineeringspeciality:computer application technologyuniversity:yanshan university碩士學位論文原創(chuàng)性聲明本人鄭重聲明：此處所提交的碩士學位論文三維空間內(nèi)凹多面體的minkowski和的算法研究，是本人在導師指導下，在攻讀碩士學位期間獨立進行研究工作所取得的成果。據(jù)本人所知，論文中除已注明部分外不包含他人已發(fā)表或撰寫過的研究成果。對本文的研究工作做出重要貢獻的個人和集體，均已在文中以明確方式注明。本聲明的法律結(jié)

3、果將完全由本人承擔。 作者簽字 日期： 年 月 日碩士學位論文使用授權(quán)書三維空間內(nèi)凹多面體的minkowski和的算法研究系本人在攻讀碩士學位期間在導師指導下完成的碩士學位論文。本論文的研究成果歸所有，本人如需發(fā)表將署名為第一完成單位及相關(guān)人員。本人完全了解關(guān)于保存、使用學位論文的規(guī)定，同意學校保留并向有關(guān)部門送交論文的復印件和電子版本，允許論文被查閱和借閱。本人授權(quán)，可以采用影印、縮印或其他復制手段保存論文，可以公布論文的全部或部分內(nèi)容。 保密，在 年解密后適用本授權(quán)書。本學位論文屬于不保密。（請在以上相應方框內(nèi)打“” ）作者簽名： 日期： 年 月 日導師簽名： 日期： 年 月 日摘要摘 要

4、計算幾何是計算機理論科學的一個重要分支，該學科已經(jīng)有了巨大的發(fā)展，產(chǎn)生了一系列的理論成果。minkowski和算法作為計算幾何研究領(lǐng)域中的一個分支，在理論和應用上都有著重要的意義，其研究成果已在機器人學、動態(tài)仿真、計算機圖形學等許多領(lǐng)域中得到了廣泛的應用，尤其在機器人學領(lǐng)域，它是計算無碰撞路徑的一個重要工具。因此，如何快速而準確地計算避障路徑，一直是國內(nèi)外學者研究的重要課題。首先，在對國內(nèi)外研究現(xiàn)狀進行綜合分析的基礎(chǔ)上，進一步研究了計算兩個凸多面體minkowski和的求和算法。本文脫離以往算法中基于傳統(tǒng)的高斯映射的算法，以減少計算平面劃分疊置的次數(shù)、提高算法的執(zhí)行效率為目標，提出了正四面體映

5、射和點投影的概念，通過計算凸多面體的正四面體映射和點投影，把三維空間的問題轉(zhuǎn)換到二維平面進行解決。其次，凸剖分是計算凹多面體的minkowski和的一個重要步驟。為了有效地計算凹多面體的minkowski和，在研究了國內(nèi)外許多凸剖分算法后，本文采用集合論和圖論的思想，提出了基于成功回路的凹多面體的剖分算法，同時對剖分算法的時間復雜度進行了分析。再次，給出了計算凹多面體的minkowski和算法的總體思想。采用成功回路的算法對凹多面體進行剖分，得到若干子凸多面體；利用正四面體映射和點投影的算法計算所有可能成對的子凸多面體的minkowski和；通過已改進的enhanced marching cu

6、bes算法合并子凸多面體的minkowski和多面體的邊界。最后，通過實驗驗證了上述的研究內(nèi)容，給出了實驗結(jié)果，并將結(jié)果與現(xiàn)有的算法進行了對比分析。關(guān)鍵詞 計算幾何；正四面體映射；點投影；凹多面體；成功回路；enhanced marching cubes；minkowski和iiiabstractabstractcomputational geometry is an important embranchment of computer theoretical science. the subject has already made a tremendous development and

7、produced a series of theoretical results. minkowski sum algorithm has the great significance in theory and application as an embranchment of computational geometry. it plays an important role in robotics, dynamic simulation, computer graphics, and so on, especially in the field of robotics, it is an

8、 important tool for computing collision-free path. therefore, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars.firstly, this paper researches the existed approach of minkowski sum of two convex polyhedral.

9、in order to reduce the amount of computing overlay of two planar subdivisions and improve the efficiency of the algorithm, this paper separates from the previous algorithm based on the traditional gaussian map and proposes the method of regular tetrahedron map and point projection to resolve this pr

10、oblem. through this method, it can reduce the problem in 3d to 2d. secondly, convex decomposition is an important step of computing minkowski sum of two non-convex polyhedral. so, for effectively computing the minkowski sum of non-convex polyhedral, the papers uses the idea of set theory and graph t

11、heory and propose a new algorithm to decompose non-convex polyhedron that based on successful loop after studying the convex decomposition algorithms. at the same time, the complexity of the algorithm is analyzed.thirdly, the paper gives the overall idea of computing the minkowski sum of non-convex

12、polyhedral. it uses successful loop to decompose non-convex polyhedral into convex pieces, then computes their pair wise minkowski sum that based on regular tetrahedron map and point projection, last, uses the reformative approach of the enhanced marching cubes to unite the boundary of polyhedral mi

13、nkowski sum of the sub polyhedral. finally, we validate the above algorithm and give the results. we also do some comparison and analysis with the existing algorithm.keywords computational geometry; regular tetrahedron map; point projection; non-convex polyhedron; successful loop; enhanced marching

14、cubes; minkowski sum目錄目錄摘 要iabstractii第1章 緒論11.1 課題研究意義11.2 minkowski和算法的研究現(xiàn)狀21.2.1 國外研究現(xiàn)狀31.2.2 國內(nèi)研究現(xiàn)狀41.3 minkowski和算法的應用61.3.1 機器人路徑規(guī)劃61.3.2 碰撞檢測61.4 本文研究內(nèi)容71.5 本文組織結(jié)構(gòu)8第2章 理論基礎(chǔ)92.1 相關(guān)的幾何定義92.1.1 歐幾里得空間92.1.2 點92.1.3 直線與線段92.1.4 多面體102.1.5 平面圖及平面劃分102.1.6 凸集與凸包102.2 基礎(chǔ)知識及內(nèi)容102.2.1 minkowski和的定義102

15、.2.2 minkowski和的性質(zhì)112.2.3 平面劃分的疊置122.2.4 邊界表示法132.2.5 移動立方體算法132.3 算法與數(shù)據(jù)結(jié)構(gòu)132.3.1 算法142.3.2 數(shù)據(jù)結(jié)構(gòu)152.4 本章小結(jié)18第3章 計算凸多面體的精確minkowski和193.1 引言193.2 現(xiàn)有的minkowski和求和算法193.3 相關(guān)定義213.4 正四面體映射213.4.1 正四面體映射的定義213.4.2 空間坐標轉(zhuǎn)換關(guān)系223.4.3 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息243.5 點投影253.5.1 點投影的定義253.5.2 空間坐標轉(zhuǎn)換關(guān)系263.5.3 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息283.6 基于正四

16、面體映射和點投影的minkowski和求和算法283.6.1 算法思想293.6.2 算法描述303.6.3 算法分析333.7 本章小結(jié)34第4章 計算凹多面體的minkowski和354.1 引言354.2 凹多面體minkowski和求和算法概述354.3 凹多面體凸剖分算法364.3.1 凸剖分算法的研究現(xiàn)狀364.3.2 相關(guān)定義與定理374.3.3 基于成功回路的凹多面體的剖分算法394.3.4 算法分析434.4 合并子minkowski和多面體434.4.1 相關(guān)定義434.4.2 合并子minkowski和多面體算法概述444.4.3 改進的合并算法454.4.4 算法分析4

17、74.5 計算簡單凹多面體的minkowski和算法總體思想474.6 本章小結(jié)48第5章 實驗與分析495.1 實驗環(huán)境設置495.2 leda簡介495.3 精確實數(shù)計算505.4 minkowski和求和算法的實驗驗證515.4.1 凸多面體minkowski和求和算法實現(xiàn)及分析525.4.2 簡單凹多面體minkowski和求和算法實現(xiàn)及分析565.5 本章小結(jié)61結(jié) 論63參考文獻65第1章 緒論第1章 緒論1.1 課題研究意義“計算幾何”這個術(shù)語最初是由minsky和papert作為模式識別的代用詞被提出來，到了a.r.forrost才有了正式的定義：“對幾何外形信息的計算機表示、

18、分析和綜合”。到了20世紀70年代末，shamos(沙莫斯)和hoey(霍伊)利用計算機有效地計算出平面點集的voronoi圖，并發(fā)表了一篇著名的論文，從此一門新的學科計算幾何從算法設計與分析中孕育而生1。該領(lǐng)域中的問題所帶來的挑戰(zhàn)性，也使得一大批科研人員為之嘔心瀝血、辛勤耕耘，從而使這一嶄新的研究領(lǐng)域在比較短的時間內(nèi)取得了輝煌的成果，對許多問題已經(jīng)有了一系列比較成熟的計算幾何算法。minkowski和算法作為計算幾何研究領(lǐng)域中的一個分支，在理論和應用上都有著重要的意義。它廣泛應用于機器人學、計算機圖形學、固體建模、計算機動畫和cad/cam等領(lǐng)域2。尤其在機器人學領(lǐng)域，minkowski和算

19、法起到了重要的作用，主要應用在機器人的運動規(guī)劃中。機器人學(robotics)是與機器人設計、制造和應用等相關(guān)的學科，主要研究機器人的控制與被處理物體之間的相互關(guān)系3。機器人學有著極其廣泛的研究和應用領(lǐng)域，這些領(lǐng)域體現(xiàn)出廣泛的學科交叉，涉及眾多的課題，如機器人控制、智能、傳感、機器人裝配以及機器語言等，在工業(yè)、農(nóng)業(yè)、空間和海洋以及國防等領(lǐng)域得到越來越普遍的應用。機器人學的最終目標之一，就是設計出一個獨立自主的機器人，它能夠接受高級任務并且在沒有人的干涉下自主執(zhí)行并完成任務4。路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當?shù)膹慕o定初始位姿到終止位姿的運動路徑，使機器人在運動過程中能安全、無碰

20、撞地繞過所有障礙物5。因此，能否對運動路徑進行快速而準確地規(guī)劃成為衡量機器人智能高低的一個重要標準。為了更好地解決機器人的路徑規(guī)劃問題，人們往往用多面體模型來模擬工作空間中的機器人與障礙物，其中多面體又可以分為凸多面體和凹多面體。這樣，檢測機器人與障礙物之間的碰撞情況就轉(zhuǎn)換為檢測多個幾何體之間的碰撞情況6。根據(jù)工作環(huán)境，機器人的路徑規(guī)劃可以分為動態(tài)路徑規(guī)劃和靜態(tài)路徑規(guī)劃。動態(tài)環(huán)境即時變環(huán)境，含有運動軌跡已知或未知的障礙物。對于軌跡已知的情況下的規(guī)劃可以將其轉(zhuǎn)化為若干靜態(tài)問題解決；但對于運動軌跡未知的情況，機器人需要在運動中不斷地檢測與障礙物之間的碰撞情況。在靜態(tài)環(huán)境下，機器人僅僅能夠做平移或翻

21、轉(zhuǎn)運動，通常障礙物為靜態(tài)的剛性物體，并且機器人與障礙物的幾何形狀和位置是已知的。在這種條件下，機器人可根據(jù)先驗環(huán)境模型找出從起始點到目標點的可行或最優(yōu)路徑，并沿著這條路徑順利地完成任務。這個看似簡單的問題在計算幾何學中卻成為具有挑戰(zhàn)性的問題，并且成為機器人研究領(lǐng)域中的一個研究熱點問題。minkowski和是計算無碰撞路徑的一個重要工具，可以定義為，在歐幾里得空間中，假設p和q為兩個封閉的幾何對象，那么p和q的minkowski和為幾何對象m，其中p和q分別是p和q上的點，p+q是p和q的位置矢量和7。也就是說若，則有。假設多面體p為工作空間中的任意一個障礙物，多面體r為沿平面做平移運動的機器人

22、，則p所對應的r障礙物為，其中-r與r關(guān)于坐標原點對稱。除此之外，minkowski和還可以用來計算兩個多面體之間的滲透深度、精確檢測物體之間的碰撞情況以及應用到機器人裝配仿真等等，有著很廣泛的應用8?？梢姡芯績蓚€幾何對象的minkowski和求和算法，對于解決機器人的路徑規(guī)劃問題有著十分重要的現(xiàn)實價值。1.2 minkowski和算法的研究現(xiàn)狀1983年，t.lozano-perez首次利用minkowski和來計算位姿空間障礙物(configuration space obstacle)，并應用到機器人的運動規(guī)劃中9。目前研究人員已經(jīng)提出了計算三維空間內(nèi)兩個多面體的minkowski和的

23、多種不同方法，主要目標都是計算minkowski和的邊界值，并提供一些方法來表示它10。其中，計算凸多面體的minkowski和的方法已經(jīng)有了成熟的算法，而凹多面體的minkowski和一直停留在獲得近似值。1.2.1 國外研究現(xiàn)狀1987年，l.j.guibas和r.seidel提出了計算簡單多胞體minkowski和多面體的敏感輸出(output-sensitive)算法，該算法定義了二維平面上的一個操作，稱作卷積(convolution)11。1996年，j.basch和l.guibas等人擴展了上述算法，提出了以定義在多面體運動軌跡上的卷積計算為基礎(chǔ)的方法來計算三維空間內(nèi)多面體的min

24、kowski和12。1993年，p.k.ghosh為計算凸多面體和凹多面體的minkowski和提出了統(tǒng)一的算法，它以傾斜圖(slope diagram)表示法為基礎(chǔ)13。計算兩個多面體的minkowski和等同于分別計算兩個多面體的傾斜圖，然后合并它們的傾斜圖，并從合并的傾斜圖中提取minkowski和的邊界值14。通過使用立體投影(stereographic projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問題降低到較低維數(shù)的空間中進行解決。1997年，b.aronov和m.shair等人提出了計算普通多邊形或多面體的minkowski和的基本框架：首先，對每個多邊形(或

25、多面體)進行凸剖分，得到若干個子凸多邊形(或多面體)；然后，計算取自不同多邊形(或多面體)的所有可能成對的子凸剖分的minkowski和；最后，合并第二步中所有子minkowski和多邊形(多面體)15?；谏厦娴钠史挚蚣?，2002年，p.k.agarwal和e.flato等人給出了計算凹多邊形的minkowski和算法，并提出了多種不同的剖分方法16。由于凹多面體的minkowski和求和算法過于復雜，目前，人們主要研究能夠得到滿足某些標準的近似值的求和算法，如文獻17,18。2000年，e.flato和d.halperin在文獻19中給出了計算普通多邊形的minkowski和算法，該算法是

26、基于cgal(computational geometry algorithm library)20實現(xiàn)的。2001年，基于ghosh在文獻13中提出的傾斜圖表示法，h.bekker和j.b.t.m.roerdink比較了三種計算凸多面體minkowski和的方法，最終提出了在線性時間內(nèi)計算三維空間凸多面體minkowski和的新方法，但是該方法只對非常簡單的凸多面體適用21。2002年，e. flato和f.fogel等人給出了minkowski和算法的應用領(lǐng)域，提供了為建造平面集合的精確、有效的minkowski和所使用的軟件包22。2003年，y.y.wu和j.j.shah等人分別對基于

27、凸包(convex hull)的凸多面體的minkowski和求和算法與基于傾斜圖的凸多面體的minkowski和求和算法進行了優(yōu)化23。遵循文獻13提出的方法，2007年，e.fogel和d.halperin提出了基于立方體高斯映射cgm(cubical gaussian map)計算三維空間內(nèi)凸多面體的精確minkowski和算法24，該算法也是基于cgal實現(xiàn)的。1.2.2 國內(nèi)研究現(xiàn)狀國內(nèi)對minkowski和算法的研究起步較晚。其中，對凸多面體的minkowski和算法的研究取得了一些很好的成果；對凹多面體的剖分和子minkowski和多面體的合并的研究也有了一定的進展。2007年，

28、郭希娟和高艷麗提出了基于正四面體中心投影rtcp(regular tetrahedron central projection)和三角形內(nèi)簡單平面凸劃分的疊置算法計算凸多面體精確minkowski和的優(yōu)化算法25。基于正四面體中心投影算法，2008年，郭希娟和謝蕾又給出了進一步優(yōu)化基于正四面體高斯映射rtgm(regular tetrahedron gaussian map)的算法26。通過對國內(nèi)外研究現(xiàn)狀的分析，可以得出計算多邊形或者多面體的minkowski和算法主要有六種，即基于凸包的求和算法、基于凸剖分的求和算法、基于傾斜圖的求和算法、基于立方體高斯映射的求和算法、基于正四面體中心投影

29、的求和算法以及基于正四面體高斯映射的算法。其中，基于凸包的minkowski和求和算法是非常著名的算法之一，該算法直接源于minkowski和的定義，它可以表示為：，其中，ch表示凸包操作，、分別表示多面體p和q中頂點的集合15。在計算minkowski和多面體的過程中，該算法需要區(qū)分內(nèi)部點、外部點和邊界點，創(chuàng)建這些點集的凸包不但需要很高的計算費用，并且該算法的計算結(jié)果不是圖而是一個點集?；趦A斜圖的minkowski和求和算法，根據(jù)高斯映射的規(guī)則，把多面體的體元(包括多面體的頂點、棱、面)映射到單位球表面，并采用立體投影方法把每個多面體的傾斜圖轉(zhuǎn)化為平面圖形，然后計算平面圖形的疊置，從疊置的

30、結(jié)果中抽取minkowski和的邊界值。采用立體投影方法不僅會使算法在處理退化情況時存在著很大的局限性，而且會增加算法的實現(xiàn)難度，很難得到精確的計算結(jié)果?；诹⒎襟w高斯映射的minkowski和求和算法，通過自定義的立方體高斯映射，把三維空間內(nèi)的凸多面體的體元映射到立方體表面，從而得到六個平面劃分面，計算兩個凸多面體的minkowski和就等同于計算六對平面劃分的疊置。通過計算六對平面劃分中各面的附加信息，得到minkowski和多面體的立方體高斯映射表示，最后求逆映射得到精確的minkowski和多面體?；谡拿骟w中心投影的minkowski和算法，首先按照高斯映射規(guī)則，將凸多面體映射到單

31、位球面上，再取單位球面的外切正四面體，通過自定義的正四面體中心投影得到凸多面體在正四面體上的投影。求兩個凸多面體的minkowski和等同于求四對平面劃分的疊置。通過計算四對平面劃分中各面的附加信息，得到新多面體的正四面體中心投影，最后求逆映射得到minkowski和多面體?；谡拿骟w高斯映射的minkowski和算法，為計算兩個給定位置和形態(tài)的凸多面體的minkowski和表示，取凸多面體的外切正四面體，根據(jù)自定義的正四面體高斯映射把凸多面體映射到外切正四面體的四個表面上，求兩個凸多面體的minkowski和等同于求四對平面劃分的疊置，通過計算平面劃分中各面的附加信息，得到新多面體的正四面

32、體高斯映射，最后求逆映射得到minkowski和多面體?；谕蛊史值膍inkowski和算法，是計算凹多邊形或凹多面體的minkowski和的常用算法。對于二維空間內(nèi)的凹多邊形而言，常用的方法就是把凹多邊形剖分為若干個凸多邊形，通過計算凸多邊形minkowski子和的并來得到凹多邊形的minkowski和。理論上，剖分策略的選擇與求和速度無關(guān)，但實際上，它嚴重影響著整個求和算法的運行時間，特別是計算三維空間內(nèi)的凹多面體的minkowski和。因此，迫切需要尋找某種策略來降低計算凹多面體的minkowski和的求和算法的時間復雜度，同時由于基于剖分法中的合并算法的復雜度很高，目前仍然沒有人提出計

33、算凹多面體的精確minkowski和的算法。因此研究凹多面體的精確minkowski和求和算法是一項具有挑戰(zhàn)性及重要意義的課題。1.3 minkowski和算法的應用minkowski和算法在許多領(lǐng)域中有著廣泛的應用，如機器人學、碰撞檢測、模擬仿真、計算機圖形學等等，下面重點介紹該算法在機器人路徑規(guī)劃和碰撞檢測中的應用。1.3.1 機器人路徑規(guī)劃機器人學的最終目標之一，就是設計出獨立自主的機器人。在指揮這種機器人時，只需要告訴它去做什么，而不必告訴它如何去做，其中尤為重要的一個方面就是，機器人應該懂得如何對自己的運動進行規(guī)劃27。路徑規(guī)劃是機器人學算法中的一個重要問題，其本質(zhì)是在眾多障礙物之間

34、為機器人尋找一條最優(yōu)或近似最優(yōu)的無碰撞路徑，該問題經(jīng)常用位姿空間方法來描述。所謂的位姿空間，也稱c空間，是機器人的參數(shù)空間；機器人的工作空間是機器人在其中實際運動的那個空間，也就是真實的世界。自由c空間(free configuration space)是機器人避免與障礙物發(fā)生碰撞的所有位置點的集合27。為了規(guī)劃路徑，需要擁有一個能夠捕捉自由位姿空間連通性的表示，而minkowski和算法可以來計算所需的表示，并且能夠獲得一條精確的無碰撞路徑。假設多面體p為工作空間中的障礙物，多面體r為移動機器人，那么通過計算位姿空間障礙物來確定一條無碰撞的路徑，這個問題就轉(zhuǎn)變?yōu)橛嬎愣嗝骟wp與-r的minko

35、wski和，其中-r與r關(guān)于坐標原點對稱。1.3.2 碰撞檢測碰撞檢測是檢測兩個物體在空間中是否重疊或它們的邊界線是否至少共享一個點17。在虛擬環(huán)境中，由于用戶的交互，物體之間經(jīng)常發(fā)生碰撞，為保持虛擬環(huán)境的真實感和用戶的沉浸感，快速精確的碰撞檢測是必不可少的。傳統(tǒng)的碰撞檢測方法主要有空間分解法和層次包圍盒技術(shù)，這兩種算法都只能近似的檢測物體是否發(fā)生碰撞，minkowski和算法能夠精確地檢測出物體之間是否發(fā)生碰撞。該問題用滲透深度來描述，兩個多面體p和q的滲透深度是指使得兩個多面體不相交，其中一個多面體必須移動的最小距離17。通過計算原心到minkowski和()表面上的最小距離來得到。若滲透

36、深度大于等于零，說明兩個多面體發(fā)生碰撞，反之，兩個多面體不會發(fā)生碰撞。1.4 本文研究內(nèi)容本文在對國內(nèi)外研究現(xiàn)狀全面分析的基礎(chǔ)上，完成對三維空間內(nèi)凹多面體minkowski和求和算法的進一步研究，主要包括下述內(nèi)容。(1)計算簡單凸多面體的minkowski和的求和算法 通過深入研究正四面體中心投影算法和正四面體高斯映射算法，發(fā)現(xiàn)這兩種算法都需要計算四次劃分平面疊置，并且都沒有給出具體的映射函數(shù)關(guān)系式。因此，本文提出了正四面體映射和點投影的概念，把三維空間的問題轉(zhuǎn)換到二維空間進行解決，且只需要計算一對平面劃分的疊置，更高效的計算凸多面體的精確minkowski和。(2)簡單凹多面體的剖分算法 通

37、過深入研究國內(nèi)外凹多面體的剖分算法，發(fā)現(xiàn)大多數(shù)的剖分算法會生成大量新點，產(chǎn)生很多凸多面體。因此，本文采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法，該算法不僅不產(chǎn)生新的頂點，而且能夠處理有空洞的多面體。(3)計算簡單凹多面體的minkowski和求和算法 首先，根據(jù)(2)中提出的剖分算法對凹多面體進行剖分，得到若干子凸多面體；其次，利用(1)中提出的求和算法計算所有可能成對的子凸多面體的minkowski和；最后，在合并子凸minkowski和多面體時，利用已改進的enhanced marching cubes算法獲得凹多面體的近似的minkowski和多面體邊界。1.5 本文

38、組織結(jié)構(gòu)論文分為5章，其余部分組織如下。第2章介紹與本課題相關(guān)的基礎(chǔ)理論。首先，是對基本幾何定義的介紹；然后，闡述了minkowski和的定義、性質(zhì)及相關(guān)的幾何操作；最后，介紹有關(guān)算法的基本知識，該部分為課題的研究打下了堅實的理論基礎(chǔ)。第3章提出了一種新的計算凸多面體的minkowski和的求和算法。首先，介紹現(xiàn)有的求和算法，分析它的主要思想；然后，以提高算法的執(zhí)行效率為目標，提出正四面體映射和點投影的概念，給出正四面體映射和點投影的映射規(guī)則，并由此提出基于該映射的凸多面體的精確minkowski和求和算法。最后，對算法的時間復雜度進行了分析。第4章提出了一種新的凹多面體的剖分算法，并給出了計

39、算凹多面體的minkowski和求和算法思想。以提高算法的精確度和效率為目標，首先，本章采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法；其次，在合并子凸多面體minkowski和時，利用現(xiàn)有已改進的enhanced marching cubes算法，最終獲得近似的多面體minkowski和邊界；最后，給出計算簡單凹多面體minkowski和的算法的總體思想。第5章是實驗與分析，對所研究的內(nèi)容及算法進行了實驗驗證并給出實驗結(jié)果。最后，對本課題進行了全面總結(jié)，同時針對課題中存在的問題提出了進一步改進的思路，并規(guī)劃了未來的研究方向。7第2章 理論基礎(chǔ)第2章 理論基礎(chǔ)下面給出一些本章中

40、將要用到的幾何概念、定義和基礎(chǔ)知識。2.1 相關(guān)的幾何定義本文考慮的對象是歐幾里得三維空間中的點集，假設有一個參考坐標系，使得每個點表示為相應維數(shù)的笛卡爾坐標的向量。除了點之外，還將考慮包含兩個給定點的直線、直線上兩定點確定的直線段、三個給定點確定的平面等。下面給出本文所涉及到的基本幾何對象的定義。2.1.1 歐幾里得空間若用(或)表示維歐幾里得空間，那么具有度量的實數(shù)的元組空間，稱為歐幾里得空間28。2.1.2 點中的點定義為一個元組。點也可以解釋為有個分量的向量，此向量的起點為坐標原點，終點為點28。點是整個幾何學的基礎(chǔ)，它只有位置，沒有大小。2.1.3 直線與線段在中給定兩個不同的點和，

41、線性組合(是實數(shù)，即)是中的一條直線28。給定中兩個不同的點和，若在線性組合中加入條件，則得到點和的凸組合，即(，)，35第3章 計算凸多面體的精確minkowski和此凸組合描述了連接兩點和的直線段，并記為(無序?qū)?28。線段是直線的一部分，并以兩個端點為界限。2.1.4 多面體由若干平面多邊形圍成的封閉連通的空間區(qū)域稱為多面體(允許有洞)29。一般說來，多面體是指邊界和內(nèi)部域的并。多邊形的頂點和邊是多面體的頂點和邊，多邊形是多面體的小面。2.1.5 平面圖及平面劃分假設圖g=(v，e)，其中v為頂點集，e為邊集，如果圖g能夠沒有交叉地嵌入平面，那么稱圖g為平面圖。平面圖的直線平面嵌入確定平

42、面的一個劃分，稱為平面劃分(也稱平面剖分)28。設平面圖的頂點數(shù)、邊數(shù)和區(qū)域數(shù)分別為v，e和f，則由歐拉公式有v-e+f=2。2.1.6 凸集與凸包假設s是二維平面上的非空點集，p1和p2是s中任意兩點，若存在一點p=tp1+(1-t)p2，其中，則稱s是凸集30。這就是說，如果s中任意兩點所連線段全部位于s之中，那么s是凸的。此定義可以推廣到高維。平面中n個點的有限集合s的凸包ch(s)是一個凸多邊形30。在中，s的ch(s)是包含s的最小凸域的邊界，其頂點為s中的點，并且s中所有的點均包含在ch(s)內(nèi)。2.2 基礎(chǔ)知識及內(nèi)容下面將給出minkowski和的定義、性質(zhì)及相關(guān)的幾何操作。2.

43、2.1 minkowski和的定義minkowski和的定義是由德國數(shù)學家hermann minkowski最早提出的。在歐幾里得空間內(nèi)，假設p和q為兩個封閉的幾何對象，它們的minkowski和可以表示為：在不改變兩個操作數(shù)相對方位的情況下，一個操作數(shù)q沿著另一個操作數(shù)p的外輪廓滑行，q的參考點經(jīng)過的軌跡就是p和q的minkowski和。如圖2-1所示。圖2-1 p和q的minkowski和fig. 2-1 the minkowski sum of p and q另外，p和q的minkowski和也可以表示為幾何對象m，其中p和q分別為屬于幾何對象p和q的點，為位置矢量與的矢量和。例如，在歐

44、幾里得二維平面內(nèi)，假設并且，那么有。下面給出二維平面內(nèi)兩個三角形的minkowski和，如圖2-2所示。pqqp圖2-2 三角形p和q的minkowski和fig. 2-2 minkowski sum of triangle p and q2.2.2 minkowski和的性質(zhì)從上面的定義可知，計算兩個幾何對象s1與s2的minkowski和具有下列性質(zhì)31,32。(1)與實數(shù)運算相似，求兩個幾何對象的minkowski和滿足交換規(guī)則和分配規(guī)則，即式子s1s2=s2s1與s1(s2s3)=(s1s2)(s1s3)成立。(2)設幾何對象s1與s2為兩個凸多邊形，分別含有n和m條邊，則minkow

45、ski和是由不超過n+m條邊構(gòu)成的凸多邊形。(3)設s1與s2為兩個多邊形，分別含有n和m個頂點，s1與s2的minkowski和的時間復雜度上界分為下列幾種情況。若s1與s2均為凸多邊形，則計算的時間復雜度上界為o(n+m)。若s1與s2中一個為凸多邊形，另外一個為非凸多邊形，則計算的時間復雜度上界為o(nm)。若s1與s2均為非凸多邊形，則計算的時間復雜度上界為o(n2m2)。(4)設s1與s2為兩個多面體，分別含有n和m個頂點，s1與s2的minkowski和所需要的時間分為下列幾種情況。若s1與s2均為凸多面體，則計算所需要的時間為o(n2m2)。若s1與s2均為非凸多面體，則計算所需

46、要的時間為o(n3m3)。2.2.3 平面劃分的疊置求平面劃分的疊置是將兩個或者多個平面劃分圖層進行疊加，并產(chǎn)生一個新平面劃分圖層的操作，其結(jié)果是將原來平面劃分中的圖元分割成新圖元，新圖元綜合了原來兩個圖層或者多個圖層的屬性33。給定兩個平面劃分d1和d2，它們的疊置是一個新的平面劃分，記作overlay(d1,d2)。如果在overlay(d1,d2)中存在一張面f，在d1和d2中分別存在面和，那么面f是的一個極大連通子集27。簡單的說是由來自d1和d2的邊共同在平面上導出一個子區(qū)域劃分，如圖2-3所示，黃色點為新的交點。圖2-3 平面劃分的疊置fig. 2-3 overlay of pla

47、nar subdivisions一般的疊置問題，首先給出分別對應于d1和d2的兩個雙向鏈接邊表，然后計算出對應于overlay(d1,d2)的雙向鏈接邊表，同時要求對overlay(d1,d2)中的每張平面劃分面加上標注，以指明在d1和d2中它分別屬于哪張平面劃分面，這樣能夠直接訪問存儲在這些面記錄中的附加信息。雙向鏈接邊表的定義將在2.3節(jié)中給出。2.2.4 邊界表示法物體可以通過描述它的邊界來表示，稱為邊界表示法34。邊界就是物體內(nèi)部點與外部點的分界面。定義了物體的邊界，該物體也就被唯一的定義了。邊界表示法的一個很重要的特點是描述了物體的信息，包括幾何信息與拓撲信息兩個方面。物體的幾何信息

48、是指頂點、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓撲信息是指物體上所有的頂點、棱邊、面間的連接情況35。2.2.5 移動立方體算法移動立方體mc(marching cubes)算法是基于規(guī)則體數(shù)據(jù)抽取等值面的經(jīng)典算法36。傳統(tǒng)的mc算法的基本思想是逐個處理數(shù)據(jù)場中的立方體(體單元)，分類出與等值面相交的立方體，采用插值計算出等值面與立方體的交點。根據(jù)立方體每一頂點與等值面的相對位置，將等值面與立方體的交點按一定方式連接生成等值面，作為等值面在該立方體內(nèi)的一個逼近。該算法對體數(shù)據(jù)中的體素逐個進行處理，每個被處理的體素，以三角面片表示其內(nèi)部的等值面。2.3 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)專門研究從解決

49、非數(shù)值計算的現(xiàn)實問題中抽象出來的數(shù)據(jù)在計算機中如何表示、快速存取和處理的方法。計算幾何與計算機科學中的算法設計與分析、數(shù)據(jù)結(jié)構(gòu)等學科的關(guān)系非常密切，它常常要用到這些學科的知識。設計求解幾何問題的算法首先應該具備兩個條件，一是分析并理解問題的幾何特征，二是掌握計算幾何中的幾何結(jié)構(gòu)、特殊的算法設計方法及相應的數(shù)據(jù)結(jié)構(gòu)。由于本文的研究內(nèi)容與幾何算法的設計與分析相關(guān)，因此就必須介紹一下關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的基本知識。2.3.1 算法算法是對特定問題求解步驟的一種描述，是指令的有限序列，是求解一個問題類的無二義性的有窮過程28。這里的求解過程是指求解問題執(zhí)行的一步一步動作的集合，每一步動作只需要有限的存儲

50、單元和有限的操作時間。簡單的說，算法就是解決特定問題的方法。描述一個算法可以采用文字敘述，也可以采用傳統(tǒng)流程圖、n-s圖或pad圖等等。一個算法具有下列重要特性。(1)有窮性 算法只執(zhí)行有限步，并且每步應該在有限的時間內(nèi)完成。(2)確定性 算法中的每一條指令必須有確切的含義，無二義性。(3)可行性 算法中描述的操作都必須足夠基本，即都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。(4)輸入 算法具有零個或多個輸入。(5)輸出 算法具有一個或多個輸出，沒有輸出的算法沒有任何意義。算法的復雜度是衡量算法效率的方法，其中包括算法的時間復雜度和算法的空間復雜度。為了說明復雜度的概念，先介紹問題規(guī)模的概

51、念。隨著處理問題的數(shù)據(jù)增大，處理會越來越困難復雜，把描述數(shù)據(jù)增大程度的量叫做問題規(guī)模37。規(guī)模越大，消耗的時間越多。利用某算法處理一個問題規(guī)模為n的輸入所需要的時間，稱為該算法的時間復雜度，它是規(guī)模n的函數(shù)，記為t(n)。算法的空間復雜度是指解決問題的算在執(zhí)行時所占用的存儲空間，記作s(n)28。下面主要討論算法的時間復雜度。由于一般不需要知道精確的時間耗費，只要知道時間耗費的增長率大體在什么范圍內(nèi)即可，因此引入算法復雜度階的概念。如果對某一個正常數(shù)c，一個算法能在時間cn2內(nèi)處理規(guī)模是n的輸入，則稱此算法的時間復雜度是o(n2)，讀作“n2階”。一般情況下，都是取一個簡單形式的函數(shù)作為階數(shù)的

52、規(guī)范，如，。一個算法的時間復雜度，如果是o(2n)，則稱算法需要指數(shù)時間；如果是o(nk)(k為有理數(shù))，則稱此算法為多項式時間算法。當n很大時，指數(shù)時間算法和多項式時間算法存在很大的差別。以多項式時間為限界的算法稱為有效算法。因此應該盡可能選用多項式階o(nk)的算法，而不希望用指數(shù)階的算法。算法的時間復雜度可分為最壞情況的時間復雜性和平均情況的時間復雜性30。對于給定規(guī)模為n的各種輸入，某算法執(zhí)行每條指令所需要的時間之和的最大值，稱為該算法的最壞情況的時間復雜性；對于給定規(guī)模為n的各種輸入，執(zhí)行每條指令所需要的時間之和的平均值，稱為平均情況的時間復雜性(或期望復雜性或平均特性)。由于規(guī)模為

53、n的輸入出現(xiàn)的概率不同，所以有時要考慮加權(quán)平均特性。2.3.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，簡言之是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合37。由于算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系非常緊密，因此在進行算法設計時首先要確定相應的數(shù)據(jù)結(jié)構(gòu)。本文除了用到通用的數(shù)據(jù)結(jié)構(gòu)鄰接表、隊列以外，還用到一種特殊的結(jié)構(gòu)：雙向鏈接邊表dcel(doubly connected edge list)27。雙向鏈接邊表適于表示嵌入到平面的平面劃分，它是一種簡單而有效的數(shù)據(jù)結(jié)構(gòu)，并且是一種基于邊的表示方法，同時包含頂點和面(平面劃分面)的信息。也就是說，對于任一個子區(qū)域，與之相對應的雙向鏈接邊表為其中的每個頂

54、點，每條半邊和每張面都設置了一個記錄，即頂點記錄、半邊記錄和面記錄，在這些記錄中，分別存有幾何信息、拓撲信息和附加信息。在雙向鏈接邊表數(shù)據(jù)結(jié)構(gòu)中，規(guī)定每條無向邊都由兩條具有相對方向的半邊(half edge)表示，這兩條半邊互稱為孿生半邊，并且都與它左側(cè)的面相關(guān)聯(lián)；對于任何一條半邊，都有唯一的一條后繼半邊，以及唯一的一條前驅(qū)半邊；每條有向半邊都有起點和終點。下面給出dcel結(jié)構(gòu)的各組成部分，如圖2-4所示。一般情況下，在對應頂點的頂點記錄中，設有一個名為coordinates(v)的域，用來存放頂點的坐標。此外，還有一個名為incidentedge(v)的指針，指向以頂點為起點的某一條半邊。在

55、對應于面的面記錄中，設有一名為outercomponent(f )的指針，指向該面的外邊界(outer boundary)上的任意一條半邊。若是無界面(unbouned face)，則此指針為null。此外，還有一個名為innercomponent(f )的列表，其中設有多個指針，分別對應于該面的各個空洞；每個指針所指的，是其對應空洞的邊界上的某一條半邊。在對應于半邊的半邊記錄中，設有一個名為origin(e)的指針，指向該半邊的起點；另有一個名為twin(e)的指針，指向其孿生半邊；還有一個名為incidentface(e)的指針，指向位于半邊左邊的面，即半邊參與圍成的那張面。半邊的終點無需

56、存儲，因為它等于origin(twin(e)。半邊起點的選取，要使得從半邊的起點走向終點的過程中，incidentface(e)位于的左側(cè)。此外，半邊記錄中還設有兩個指針next(e)和prev(e)，分別指向沿著incidentface(e)邊界的半邊的后繼半邊與前驅(qū)半邊。這樣，沿著incidentface(e)的邊界，以的終點為起點的半邊只有next(e)一條，而以的起點為終點的半邊也只有prev(e)一條。origin(e)next(e)incidentface(e)twine(e)eprev(e)圖2-4 dcel結(jié)構(gòu)的各組成部分fig. 2-4 component of dcel structure