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

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

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

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

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