自碰撞检测高层剔除算法研究与实现
发布时间：2018-08-25 19:47
【摘要】：近年来,碰撞检测作为物理仿真、虚拟现实、机器人路径规划等技术的重要组成部分受到广泛的关注。随着柔性体仿真的兴起,碰撞检测过程中的自碰撞检测问题日益凸显,传统的包围体技术、空间剖分算法等方法用于自碰撞检测不足以满足人们对速度的需求。本文首先对传统的自碰撞检测算法展开系统性的研究,通过实验分析得到自碰撞检测过程中的性能瓶颈,然后总结前人的方法,有针对性的进行算法修改,提出了新的高层剔除算法。本文的主要工作内容概括如下:1.总结了碰撞检测的一般过程,并分析了过程中的相关算法。同时构建实验系统并通过实验分析自碰撞检测过程,清晰定位自碰撞检测过程的瓶颈,为后续算法提供实验框架和优化方向。2.提出了法向锥指导的BVTT(层次包围体遍历树)前线算法。算法结合曲率启发式算法的高层剔除能力和BVTT前线算法减少包围体测试次数的能力,获得了更快的碰撞对收集过程,并且通过使用BVTT前线使检测过程得以快速的并行化。最终实验结果显示,该算法相较于仅使用包围体剔除的自碰撞检测算法,速度提升最高达到8倍。3.提出了快速的形变能量计算算法,通过形变能量剔除算法解决法向锥算法不能剔除非平坦区域的问题,并利用快速的形变能量计算算法优化剔除过程。最终实验结果显示本算法运行时能量计算过程的速度最高可达原方法计算能量的速度的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.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：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.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.9;TP242
【相似文献】
相关期刊论文 前10条
1 涂超;虚拟空间中的碰撞检测[J];武汉理工大学学报;2001年11期
2 黄金敢,沈斐敏;碰撞检测在交通事故模拟中的应用[J];交通与计算机;2004年01期
3 车念;;浅谈手机游戏中的碰撞检测[J];技术与市场;2009年11期
4 曾俊武,郭齐胜,李斌;车辆碰撞检测的一种简化数学模型[J];计算机仿真;2000年06期
5 陈e，
本文编号：2203918
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2203918.html
