凸包構(gòu)造與碰撞檢測(cè)的優(yōu)化研究.pdf

1、碰撞檢測(cè)是物理仿真、路徑規(guī)劃、虛擬裝配及觸覺渲染等諸多計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)的一類基礎(chǔ)問題，至今已有許多解決該問題的算法被提出，然而這些算法各有優(yōu)劣。例如V-Clip算法、Lin-Canny算法、GJK算法都將多面體視為凸體對(duì)象，因此對(duì)于凹多面體，需要通過構(gòu)造凸包來轉(zhuǎn)化為凸體對(duì)象。而且當(dāng)具體到實(shí)際應(yīng)用中時(shí)，還會(huì)遇到一些其他挑戰(zhàn):例如觸覺渲染要求極高的刷新率;精密零件的虛擬裝配不但需要算法能夠快速得到結(jié)果，而且對(duì)結(jié)果的準(zhǔn)確性要求也很高，因此根據(jù)

2、實(shí)際應(yīng)用環(huán)境對(duì)已有的凸包構(gòu)造算法和碰撞檢測(cè)算法進(jìn)行優(yōu)化改進(jìn)是一個(gè)值得研究的領(lǐng)域，具有理論意義與實(shí)際工程價(jià)值。
　　本論文以剛性的基于三角形圖元的機(jī)械表精密零件模型作為研究對(duì)象，論述了凸包構(gòu)造和碰撞檢測(cè)兩個(gè)階段的相關(guān)問題。本文主要進(jìn)行的工作及成果如下:
　　1.研究了凸包的性質(zhì)，并在此基礎(chǔ)上對(duì)三維空間的卷包裹(Gift-Wrapping)算法和快速凸包(QuickHull)算法的基本思想和計(jì)算復(fù)雜度進(jìn)行了論述，重點(diǎn)討論了快包法

3、的優(yōu)缺點(diǎn)，并由此提出了一種改進(jìn)的三維點(diǎn)集凸包構(gòu)造算法，該算法通過優(yōu)先考慮與凸包頂點(diǎn)共面的其他頂點(diǎn)，避免中間面的產(chǎn)生，減少最終構(gòu)成凸包的圖元數(shù)量。本文使用該算法構(gòu)造零件模型的凸包，利用凸包加快包圍體的構(gòu)造，并實(shí)現(xiàn)機(jī)械表零件與夾具及環(huán)境的快速碰撞檢測(cè)和仿真。
　　2.研究了碰撞檢測(cè)全局階段的N-體剔除方法:包圍體樹、空間剖分以及拓?fù)浞?，并討論了各自的適用場(chǎng)景。在拓?fù)浞ㄖ?，我們重點(diǎn)分析了最著名的掃掠剪除(SaP)算法以及其各類變種的優(yōu)缺

4、點(diǎn)和執(zhí)行效率，并提出一種基于樣本估計(jì)的SaP優(yōu)化算法，該算法通過樣本估計(jì)動(dòng)態(tài)選擇離散排序軸，降低了大型場(chǎng)景中模型積聚和模型規(guī)模變化對(duì)實(shí)時(shí)性的負(fù)面影響。實(shí)驗(yàn)結(jié)果表明新算法的性能優(yōu)于其他同類算法，且能夠適應(yīng)各種場(chǎng)景環(huán)境，其適用性更廣。
　　3.研究了碰撞檢測(cè)局部階段的精確相交測(cè)試方法，針對(duì)現(xiàn)有包圍體樹算法的實(shí)時(shí)性不足、對(duì)機(jī)械表裝配場(chǎng)景的適用性不佳的問題，本文提出一種改進(jìn)的混合包圍體樹算法，該算法在創(chuàng)建樹節(jié)點(diǎn)時(shí)使用了多個(gè)相關(guān)包圍體，并對(duì)