自碰撞檢測高層剔除算法研究與實現(xiàn)
發(fā)布時間：2018-08-25 19:47
【摘要】：近年來,碰撞檢測作為物理仿真、虛擬現(xiàn)實、機器人路徑規(guī)劃等技術(shù)的重要組成部分受到廣泛的關(guān)注。隨著柔性體仿真的興起,碰撞檢測過程中的自碰撞檢測問題日益凸顯,傳統(tǒng)的包圍體技術(shù)、空間剖分算法等方法用于自碰撞檢測不足以滿足人們對速度的需求。本文首先對傳統(tǒng)的自碰撞檢測算法展開系統(tǒng)性的研究,通過實驗分析得到自碰撞檢測過程中的性能瓶頸,然后總結(jié)前人的方法,有針對性的進(jìn)行算法修改,提出了新的高層剔除算法。本文的主要工作內(nèi)容概括如下:1.總結(jié)了碰撞檢測的一般過程,并分析了過程中的相關(guān)算法。同時構(gòu)建實驗系統(tǒng)并通過實驗分析自碰撞檢測過程,清晰定位自碰撞檢測過程的瓶頸,為后續(xù)算法提供實驗框架和優(yōu)化方向。2.提出了法向錐指導(dǎo)的BVTT(層次包圍體遍歷樹)前線算法。算法結(jié)合曲率啟發(fā)式算法的高層剔除能力和BVTT前線算法減少包圍體測試次數(shù)的能力,獲得了更快的碰撞對收集過程,并且通過使用BVTT前線使檢測過程得以快速的并行化。最終實驗結(jié)果顯示,該算法相較于僅使用包圍體剔除的自碰撞檢測算法,速度提升最高達(dá)到8倍。3.提出了快速的形變能量計算算法,通過形變能量剔除算法解決法向錐算法不能剔除非平坦區(qū)域的問題,并利用快速的形變能量計算算法優(yōu)化剔除過程。最終實驗結(jié)果顯示本算法運行時能量計算過程的速度最高可達(dá)原方法計算能量的速度的2倍,碰撞檢測整體性能提升至1.3倍。
[Abstract]:In recent years, collision detection as an important part of physical simulation, virtual reality, robot path planning and other technologies has attracted wide attention. With the rise of flexible body simulation, the problem of self-collision detection in the process of collision detection has become increasingly prominent. Traditional enclosure technology, space partition algorithm and other methods for self-collision detection are inadequate. In this paper, the traditional self-collision detection algorithm is studied systematically, and the performance bottleneck in the process of self-collision detection is obtained by experimental analysis. Then the predecessors'methods are summarized and the corresponding algorithm is modified, and a new high-level culling algorithm is proposed. The following: 1. Summarize the general process of collision detection, and analyze the relevant algorithms in the process. At the same time, build the experimental system and analyze the process of self-collision detection through experiments, clearly locate the bottleneck of the self-collision detection process, provide the experimental framework and optimization direction for the follow-up algorithm. 2. Propose a normal cone-guided BVTT (Hierarchical Bounding Body Traversal Tree) The algorithm combines the high-level culling ability of the curvature heuristic algorithm with the ability of BVTT front-line algorithm to reduce the number of tests on bounding bodies, and obtains a faster collision pair collection process. The detection process can be quickly parallelized by using BVTT front-line. Finally, the experimental results show that the algorithm is better than only using bounding bodies culling. Self-collision detection algorithm, speed up to 8 times. 3. A fast deformation energy calculation algorithm is proposed. Deformation energy elimination algorithm is used to solve the problem that normal cone algorithm can not eliminate unless flat area, and a fast deformation energy calculation algorithm is used to optimize the culling process. The experimental results show that the algorithm runs with energy meter. The speed of calculation is up to 2 times that of the original method, and the overall performance of collision detection is improved to 1.3 times.
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.9;TP242
[Abstract]:In recent years, collision detection as an important part of physical simulation, virtual reality, robot path planning and other technologies has attracted wide attention. With the rise of flexible body simulation, the problem of self-collision detection in the process of collision detection has become increasingly prominent. Traditional enclosure technology, space partition algorithm and other methods for self-collision detection are inadequate. In this paper, the traditional self-collision detection algorithm is studied systematically, and the performance bottleneck in the process of self-collision detection is obtained by experimental analysis. Then the predecessors'methods are summarized and the corresponding algorithm is modified, and a new high-level culling algorithm is proposed. The following: 1. Summarize the general process of collision detection, and analyze the relevant algorithms in the process. At the same time, build the experimental system and analyze the process of self-collision detection through experiments, clearly locate the bottleneck of the self-collision detection process, provide the experimental framework and optimization direction for the follow-up algorithm. 2. Propose a normal cone-guided BVTT (Hierarchical Bounding Body Traversal Tree) The algorithm combines the high-level culling ability of the curvature heuristic algorithm with the ability of BVTT front-line algorithm to reduce the number of tests on bounding bodies, and obtains a faster collision pair collection process. The detection process can be quickly parallelized by using BVTT front-line. Finally, the experimental results show that the algorithm is better than only using bounding bodies culling. Self-collision detection algorithm, speed up to 8 times. 3. A fast deformation energy calculation algorithm is proposed. Deformation energy elimination algorithm is used to solve the problem that normal cone algorithm can not eliminate unless flat area, and a fast deformation energy calculation algorithm is used to optimize the culling process. The experimental results show that the algorithm runs with energy meter. The speed of calculation is up to 2 times that of the original method, and the overall performance of collision detection is improved to 1.3 times.
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.9;TP242
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 涂超;虛擬空間中的碰撞檢測[J];武漢理工大學(xué)學(xué)報;2001年11期
2 黃金敢,沈斐敏;碰撞檢測在交通事故模擬中的應(yīng)用[J];交通與計算機;2004年01期
3 車念;;淺談手機游戲中的碰撞檢測[J];技術(shù)與市場;2009年11期
4 曾俊武,郭齊勝,李斌;車輛碰撞檢測的一種簡化數(shù)學(xué)模型[J];計算機仿真;2000年06期
5 陳e，
本文編號：2203918
本文鏈接：http://www.sikaile.net/kejilunwen/ruanjiangongchenglunwen/2203918.html
最近更新
教材專著
