層次包圍盒碰撞檢測(cè)算法的優(yōu)化及其并行化.pdf

1、隨著虛擬現(xiàn)實(shí)的發(fā)展和人們對(duì)體驗(yàn)要求的提高，碰撞檢測(cè)算法實(shí)時(shí)性與準(zhǔn)確性的要求也隨之提高。層次包圍盒碰撞檢測(cè)算法將物體分為粒度不同的包圍盒進(jìn)行測(cè)試，具有較高的準(zhǔn)確性，但是實(shí)時(shí)性較差。本文優(yōu)化了傳統(tǒng)的層次包圍盒碰撞檢測(cè)算法，并使用GPU并行計(jì)算，進(jìn)一步加快了碰撞檢測(cè)算法的速度。本文主要研究?jī)?nèi)容如下：
　?。?）以現(xiàn)有碰撞檢測(cè)算法為基礎(chǔ)，歸納總結(jié)了基于空間分解的碰撞檢測(cè)算法和基于層次包圍盒的碰撞檢測(cè)算法，分析并比較各類碰撞檢測(cè)算法的優(yōu)缺點(diǎn)

2、。
　?。?）對(duì)構(gòu)造層次包圍盒樹算法進(jìn)行優(yōu)化。分析哈夫曼法構(gòu)造層次包圍盒樹的實(shí)現(xiàn)方式，提出使用平衡二叉樹法對(duì)構(gòu)造層次包圍盒樹的優(yōu)化方案，節(jié)省了構(gòu)造層次包圍盒樹的耗時(shí)。
　?。?）實(shí)現(xiàn)優(yōu)化后的構(gòu)造層次包圍盒樹算法的并行化。對(duì)優(yōu)化后的構(gòu)造層次包圍盒算法進(jìn)行可行性分析，并在CUDA平臺(tái)上對(duì)其進(jìn)行并行化，進(jìn)一步節(jié)省了構(gòu)造層次包圍盒樹的耗時(shí)。
　?。?）實(shí)現(xiàn)層次包圍盒碰撞檢測(cè)算法的并行化。分析串行碰撞檢測(cè)算法中雙重遍歷層次包圍盒