凸包构造与碰撞检测的优化研究
发布时间：2018-07-20 09:14
【摘要】：碰撞检测是物理仿真、路径规划、虚拟装配及触觉渲染等诸多计算机科学领域内的一类基础问题,至今已有许多解决该问题的算法被提出,然而这些算法各有优劣。例如V-Clip算法、Lin-Canny算法、GJK算法都将多面体视为凸体对象,因此对于凹多面体,需要通过构造凸包来转化为凸体对象。而且当具体到实际应用中时,还会遇到一些其他挑战:例如触觉渲染要求极高的刷新率;精密零件的虚拟装配不但需要算法能够快速得到结果,而且对结果的准确性要求也很高,因此根据实际应用环境对已有的凸包构造算法和碰撞检测算法进行优化改进是一个值得研究的领域,具有理论意义与实际工程价值。本论文以刚性的基于三角形图元的机械表精密零件模型作为研究对象,论述了凸包构造和碰撞检测两个阶段的相关问题。本文主要进行的工作及成果如下:1.研究了凸包的性质,并在此基础上对三维空间的卷包裹(Gift-Wrapping)算法和快速凸包(QuickHull)算法的基本思想和计算复杂度进行了论述,重点讨论了快包法的优缺点,并由此提出了一种改进的三维点集凸包构造算法,该算法通过优先考虑与凸包顶点共面的其他顶点,避免中间面的产生,减少最终构成凸包的图元数量。本文使用该算法构造零件模型的凸包,利用凸包加快包围体的构造,并实现机械表零件与夹具及环境的快速碰撞检测和仿真。2.研究了碰撞检测全局阶段的N-体剔除方法:包围体树、空间剖分以及拓扑法,并讨论了各自的适用场景。在拓扑法中,我们重点分析了最著名的扫掠剪除(SaP)算法以及其各类变种的优缺点和执行效率,并提出一种基于样本估计的SaP优化算法,该算法通过样本估计动态选择离散排序轴,降低了大型场景中模型积聚和模型规模变化对实时性的负面影响。实验结果表明新算法的性能优于其他同类算法,且能够适应各种场景环境,其适用性更广。3.研究了碰撞检测局部阶段的精确相交测试方法,针对现有包围体树算法的实时性不足、对机械表装配场景的适用性不佳的问题,本文提出一种改进的混合包围体树算法,该算法在创建树节点时使用了多个相关包围体,并对树的构造方式进行修改,从而对零件模型间的相交状态可以更加精确高效的检测。我们还对如何优化内存占用进行了讨论。4.利用Unity3D引擎实现了机械表虚拟装配系统,并以系统的场景为模板构造实验环境,以碰撞检测算法的运行时间、准确性以及综合性能几个方面为考察目标,设计了两个算法对比实验。通过分析与传统算法的对比实验结果,验证了本文提出的SSVs混合包围体树算法在性能上优于传统算法。
[Abstract]:Collision detection is a basic problem in many fields of computer science, such as physical simulation, path planning, virtual assembly and tactile rendering. So far, many algorithms have been proposed to solve the problem, but these algorithms have their own advantages and disadvantages. For example, V-Clip algorithm / Lin-Canny algorithm / GJK algorithm regards polyhedron as convex object, so concave polyhedron needs to be transformed into convex object by constructing convex hull. And when it comes to practical applications, there are other challenges: for example, tactile rendering requires a very high refresh rate, and virtual assembly of precision parts requires not only fast algorithms to get results, Moreover, the accuracy of the results is very high. Therefore, the optimization and improvement of the existing convex hull construction algorithm and collision detection algorithm according to the practical application environment is an area worthy of study, which has theoretical significance and practical engineering value. In this paper, the rigid precision part model of mechanical watch based on triangular graph element is taken as the research object, and the problems related to the construction of convex hull and collision detection are discussed. The main work and results of this paper are as follows: 1. The properties of convex hull are studied, and the basic ideas and computational complexity of Gift-Wrapping algorithm and Quick Hull algorithm in 3D space are discussed, and the advantages and disadvantages of fast packet algorithm are discussed. An improved algorithm for constructing convex hull of three dimensional point set is proposed. The algorithm can avoid the generation of intermediate surface by giving priority to other vertices coplanar with convex hull vertices and reduce the number of graph elements that ultimately form convex hull. In this paper, the algorithm is used to construct the convex hull of the part model, the convex hull is used to accelerate the construction of the bounding body, and the rapid collision detection and simulation of mechanical watch parts, fixture and environment are realized. In this paper, the methods of N-Bounding in the global phase of collision detection, including bounding body tree, space partition and topological method, are studied, and their applicable scenarios are discussed. In the topological method, we focus on analyzing the advantages and disadvantages of the most famous sweep cut (SAP) algorithm and its various variants, and propose a sample estimation based SAP optimization algorithm. The algorithm dynamically selects discrete sorting axes by sample estimation, which reduces the negative effects of model accumulation and model size change on real-time performance in large scale scenarios. Experimental results show that the performance of the new algorithm is better than other similar algorithms, and it can adapt to various scene environments, and its applicability is wider. 3. In this paper, the accurate intersecting testing method in local phase of collision detection is studied. In view of the shortage of real-time performance of existing bounding tree algorithms and the poor applicability to the assembly scene of mechanical table, an improved hybrid bounding tree algorithm is proposed in this paper. In order to detect the intersecting state of part models more accurately and efficiently, the algorithm uses several related bounding bodies to create tree nodes and modifies the construction of the tree. We also discussed how to optimize memory usage. The virtual assembly system of mechanical table is realized by using the Unity3D engine, and the experimental environment is constructed with the system scene as the template. The object is the running time, accuracy and comprehensive performance of the collision detection algorithm. Two algorithm contrast experiments are designed. The performance of the SSVs hybrid bounding tree algorithm is proved to be superior to that of the traditional algorithm by analyzing the experimental results compared with the traditional algorithm.
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6
本文编号：2133066
[Abstract]:Collision detection is a basic problem in many fields of computer science, such as physical simulation, path planning, virtual assembly and tactile rendering. So far, many algorithms have been proposed to solve the problem, but these algorithms have their own advantages and disadvantages. For example, V-Clip algorithm / Lin-Canny algorithm / GJK algorithm regards polyhedron as convex object, so concave polyhedron needs to be transformed into convex object by constructing convex hull. And when it comes to practical applications, there are other challenges: for example, tactile rendering requires a very high refresh rate, and virtual assembly of precision parts requires not only fast algorithms to get results, Moreover, the accuracy of the results is very high. Therefore, the optimization and improvement of the existing convex hull construction algorithm and collision detection algorithm according to the practical application environment is an area worthy of study, which has theoretical significance and practical engineering value. In this paper, the rigid precision part model of mechanical watch based on triangular graph element is taken as the research object, and the problems related to the construction of convex hull and collision detection are discussed. The main work and results of this paper are as follows: 1. The properties of convex hull are studied, and the basic ideas and computational complexity of Gift-Wrapping algorithm and Quick Hull algorithm in 3D space are discussed, and the advantages and disadvantages of fast packet algorithm are discussed. An improved algorithm for constructing convex hull of three dimensional point set is proposed. The algorithm can avoid the generation of intermediate surface by giving priority to other vertices coplanar with convex hull vertices and reduce the number of graph elements that ultimately form convex hull. In this paper, the algorithm is used to construct the convex hull of the part model, the convex hull is used to accelerate the construction of the bounding body, and the rapid collision detection and simulation of mechanical watch parts, fixture and environment are realized. In this paper, the methods of N-Bounding in the global phase of collision detection, including bounding body tree, space partition and topological method, are studied, and their applicable scenarios are discussed. In the topological method, we focus on analyzing the advantages and disadvantages of the most famous sweep cut (SAP) algorithm and its various variants, and propose a sample estimation based SAP optimization algorithm. The algorithm dynamically selects discrete sorting axes by sample estimation, which reduces the negative effects of model accumulation and model size change on real-time performance in large scale scenarios. Experimental results show that the performance of the new algorithm is better than other similar algorithms, and it can adapt to various scene environments, and its applicability is wider. 3. In this paper, the accurate intersecting testing method in local phase of collision detection is studied. In view of the shortage of real-time performance of existing bounding tree algorithms and the poor applicability to the assembly scene of mechanical table, an improved hybrid bounding tree algorithm is proposed in this paper. In order to detect the intersecting state of part models more accurately and efficiently, the algorithm uses several related bounding bodies to create tree nodes and modifies the construction of the tree. We also discussed how to optimize memory usage. The virtual assembly system of mechanical table is realized by using the Unity3D engine, and the experimental environment is constructed with the system scene as the template. The object is the running time, accuracy and comprehensive performance of the collision detection algorithm. Two algorithm contrast experiments are designed. The performance of the SSVs hybrid bounding tree algorithm is proved to be superior to that of the traditional algorithm by analyzing the experimental results compared with the traditional algorithm.
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6
【参考文献】
相关期刊论文 前8条
1 陈明晶;方源敏;陈杰;;初始凸包对改进快速凸包算法效率的影响[J];测绘科学;2016年07期
2 谢倩茹;耿国华;;虚拟手术环境中软组织的快速碰撞检测[J];计算机应用研究;2015年08期
3 岳玉洁;赵建国;;基于Inventor三维吊装仿真系统的研究与应用[J];机械设计与制造;2012年04期
4 赵伟;谭睿璞;杨秋娜;丁文保;李文辉;;基于着色算法的并行碰撞检测算法[J];计算机应用研究;2009年05期
5 朱元峰;孟军;谢光华;马文娟;;基于复合层次包围盒的实时碰撞检测研究[J];系统仿真学报;2008年02期
6 刘晓平;曹力;;基于MPI的并行八叉树碰撞检测[J];计算机辅助设计与图形学学报;2007年02期
7 王建宇;吴慧中;;基于图像的虚拟战场环境[J];火力与指挥控制;2006年08期
8 魏小亮,魏尚荣;凸包算法的变形及应用[J];中央民族大学学报(自然科学版);2000年01期
相关硕士学位论文 前5条
1 郑晓辉;基于混合包围盒的混凝土泵车防碰撞算法研究[D];湘潭大学;2016年
2 王炫殊;高维Voronoi图的生成与应用研究[D];华南理工大学;2016年
3 唐磊;凸包围多面体生成算法及应用[D];清华大学;2015年
4 许熠;基于混合包围盒的碰撞检测算法的优化研究[D];南京理工大学;2013年
5 成军;碰撞检测在虚拟拆装仿真系统中的研究与应用[D];湖南大学;2010年
，本文编号：2133066
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2133066.html
