【作者】 邹益胜；

【导师】 许明恒； 丁国富；

【作者基本信息】 西南交通大学 ， 机械制造及其自动化， 2009， 博士

【摘要】 碰撞检测是以计算机仿真为基础的运动规划、虚拟制造和虚拟样机等领域的基础问题之一。在基于三维CAD的虚拟样机环境中,研究多体系统之间的碰撞检测问题对解决产品设计中的相关问题有着重要的现实意义。本论文以碰撞检测理论为基础,以机车车辆虚拟样机为应用背景,通过对相关算法的深入研究和开发,为基于虚拟样机的产品设计提供更全面可靠的依据,也为相关领域的研究提供参考。其主要研究内容包括:(1)综述了碰撞检测算法的研究现状,分析了当前研究中的特点和不足,提出了论文研究的内容和思路;(2)研究了基于有向包围盒(Oriented Bounding Box,OBB)层次树的碰撞检测算法的原理,实现了基于OBB层次树的碰撞检测算法并做了三点改进:1)设计了一种快速的空间三角形相交检测算法,利用三角形边向量间的线性相关性、矩阵运算中的线性特性及图形的投影特性,加速了问题的解决,理论分析和实验验证结果表明,在三角形相交率较高的场合,其检测效率优于同类算法,在三角形相交率低的场合,其检测效率与同类算法相当。而在基于包围盒的碰撞算法中,通过包围盒测试排除了大量不相交的情况,剩下的需要进行进一步测试的三角形相交率高,有效发挥了新算法的优势;2)为OBB层次树顶层构造混合包围盒,以快速排除明显不相交的物体,在大规模稀疏场景中明显提高了碰撞检测的效率,而且混合包围盒的构造及测试代价都很小;3)根据运动的连贯性,通过提取上一帧的碰撞检测信息,用于当前帧的碰撞检测,提高了检测的效率。测试结果表明,上述改进提高了算法的性能。(3)设计并实现了一种GPGPU的碰撞检测算法。该算法充分利用图形硬件计算并行性且运算速度快的特点,将整个碰撞检测算法完全映射到GPU中进行。算法首先将模型的包围盒信息及图形几何信息映射成纹理并下载到GPU,再利用渲染原理进行计算,然后利用离屏渲染技术将碰撞检测的结果输出到纹理,最后回读到CPU。该算法的碰撞检测部分全部在GPU中完成,只需要一次数据上传和一次数据回读,避免了数据在GPU和CPU间传输的瓶颈问题。测试结果表明,该算法保持了同类基于CPU的算法的精度,在简单场景中其性能不如基于CPU的同类算法,但在复杂场景中,该算法具有明显的优越性。(4)设计并实现了一种基于图像空间的碰撞检测算法,利用光线和封闭物体的相交特性,通过比较光线与物体正、背面相交的次数,结合模板缓存和深度缓存,判断两物体的碰撞情况。由于基于图像空间的碰撞检测算法需要进行物体的多次重绘,采用了VBO技术,大大提高了图形绘制的速度,从而也大幅提高了碰撞检测的速度,获得良好的实时性。另外采用包围盒确定相交区域,减少了绘图量,进一步保证了算法的效率,特别是对于复杂场景,具有明显的效果。测试结果表明,该算法可以有效地处理封闭的任意物体,但其检测精度和检测速度受到图形硬件的影响。(5)研究了基于图形空间和基于图像空间碰撞检测算法的优缺点以及CPU与GPU的负载平衡问题,设计并实现了一种基于图形空间和图像空间混合的碰撞检测算法,根据场景中参与碰撞的物体的数量,选择利用CPU还是GPU进行物体间的包围盒碰撞检测,生成粗略碰撞集(Rough Colliding Sets,RCS),再利用基于图像空间的面面间的碰撞检测算法,生成精确的碰撞集(AccurateColliding Sets,ACS),最后将ACS中的三角形进行精确地相交测试并返回结果。在三角形的相交测试中,分析基于CPU的算法与基于GPGPU的算法在不同规模下的检测效率,根据待检测的三角形规模,自动选择算法类型。测试结果表明,该算法继承了基于图像空间的算法快速、平稳等优点和基于图形空间判断准确、易于获取碰撞点等优点,实现速度和精度的折衷。(6)以基于OBB的碰撞检测改进算法FRCD为例,将研究结果应用于基于CAD设计模型机车车辆虚拟样机动力学分析和仿真子系统中,在进行动力学分析计算的同时,可以实时检测复杂的车辆部件CAD设计模型在运行中的干涉情况,从数值分析和三维可视化仿真的角度综合检验机车车辆的设计结果,为机车车辆的结构和动力学参数设计提供更全面的参考。通过以上研究和开发,改进了传统算法,并提出了一些新的算法,为机车车辆虚拟样机可视化平台的开发和完善提供技术基础,也为相关领域的碰撞检测研究提供参考思路。更多还原

【Abstract】 Collision detection is one of the basic problems of computer simulation based motion planning, virtual manufacturing, virtual prototype, et al. In 3d CAD based virtual prototype environment, it has important practical significance for solving the related problems of product design to research collision detection among multi-body system. In the paper, collision detection theory is the basis, and virtual prototype of locomotive and railway vehicle is application background. The further study and development on collision detection will provide reliable basis for product design based on virtual prototype. It will also as a reference for research on related field. The main research contents include the following.(1) The research status of collision detection is summarized and the characteristics and shortages of recent research are analyzed, and research contents and methods of the paper are proposed.(2) The collision detection algorithm based on Oriented Bounding Box (OBB) are researched and implemented, and three improvements have been made. The first, a fast intersection algorithm between spatial triangles is proposed, in which the linear dependence of edge vector of triangle, linear characteristics of matrix calculation and projection characteristics of graphics are fully used to improve the performance. Theoretical analysis and experimental verification show that the algorithm proposed is better than other’s in the occasions with high triangle-triangle intersection ration, and is chime with other algorithm in the occasions with low intersection ration. In the collision detection algorithm based on bounding box, the intersection ration of triangles is high, therefore it is helpful to improve the performance of the collision detection algorithm. The second, a hybrid bounding box is constructed on top level of OBB hierarchical tree to eliminate the obviously disjoint object quickly, which improve the performance of algorithm, especially in large sparse scene. The costs of construction and test are all least. The last, according to motion coherence, the collision message of previous frame is buffered to detect the collision of current frame, which also improve the performance of algorithm. Testing results show that these improvements are efficient and successful, and which have improved the performance of algorithm.(3) A General-Purpose computation on GPUs (GPGPU) based collision detection algorithm is designed and implemented. The parallel and fast computation of graphics hardware is fully used, and all computation of algorithm is performed on GPU. Firstly, bounding boxes message and geometric message of models are mapped into textures and download to GPU. Then, the principle of render is used for computation. Therefore, the collision detection results are output to texture using off-screen rending technology. Lastly, the data on texture are read to CPU for next operation. All computation of algorithm is performed on GPU, so only two data exchanges between CPU and GPU are executed, one for downloading to GPU, and the other for reading to CPU. This method avoids the bottleneck of data transmission. Testing results show this algorithm keep the collision detection precision of the same kind algorithm performed on CPU. In simple case, the performance of this algorithm is worse than the same kind algorithm performed on CPU. But in complex case, this algorithm has obvious advantage than the later.(4) An image based collision detection algorithm is proposed and implemented. Using the intersection characteristic between ray and closed object, the times of the ray intersecting with front and back of the object are recorded to detect the collision of target objects with the aid of stencil buffer and depth buffer. Vertex Buffer Object (VBO) is used to raise drawing speed greatly and also the detection speed, for target objects need to be redrawn one more times in image based collision detection algorithm. Another way to improve performance is using bounding box to computer the intersection field, which can reduce the point number needed to be drawn. Testing results show that the algorithm can deal with the closed object effectively and powerfully, especially for complex models. The collision detection precision and speed however are affected by graphics hardware.(5) The advantages and disadvantages of graphics-based and image-based collision detection algorithm as wel as load balancing of CPU and GPU are analyzed. A graphics-based and image-based hybrid algorithm is proposed and implemented. According to the number of the target objects in the scene, a graphics-based (on CPU) or image-based (on GPU) collision detection between bounding box of object is chosen automatically, and then the Rough Collide Sets (RCS) is constructed. Next step, an image-based collision detection algorithm among surface is used to generate Accurate Collide Sets (ACS). At last, graphics-based triangles intersections in ACS are performed and the results are returned. In triangles intersections testing, the performance of GPGPU-based and CPU-based algorithm is analyzed in different scales, and according to the scales, a suitable algorithm can be choosed automatically by the software. Testing results show that the algorithm keeps the advantages of image-based algorithm, such as fastness and stationarity, and the advantages of graphics-based algorithm, such as accuracy and obtaining collision point easily. This algorithm strikes compromise between precision and speed.(6) The OBB-based collision detection improved algorithm named FRCD is applied to the visual dynamics simulation platform based on CAD model to detect the intersection among complex CAD models of railway vehicle main parts when them running. The dynamics analysis and visual 3D kinematics simulation are all based CAD model, and executed synchronistically. This method which includes digital analysis and visual 3D simulation will provide comprehensive reference for the dynamics parameters and structure design of railway vehicles.Based on these research and development, traditional algorithms are improved and some new algorithms are proposed. All these algorithms provide the technology basis for developing and perfecting visual platform of railway vehicle virtual prototype. It also provides reference for collision detection research in related field.更多还原