【作者】 张辉；

【导师】 孙维超；

【作者基本信息】 哈尔滨工业大学 ， 控制科学与工程， 2023， 硕士

【摘要】 碰撞检测问题作为近年来自动驾驶领域和计算机动画游戏等领域的研究热点,随着问题场景逐渐多变化,物体模型更为复杂化和精细化,物体模型之间的运动的突然性和不确定性增加,传统的包围盒算法在复杂物体(如凹多面体)之间的碰撞检测表现不佳,所以针对复杂物体模型的高实时性的碰撞检测算法研究具有重大的意义。本课题的研究内容主要针对两个问题:一是解决凹多面体之间的碰撞检测问题,二是在物体模型复杂度提升后或者物体数量增多后,提升碰撞检测算法实时性。为此,本文主要的研究内容有三部分:第一部分构建物体模型的AABB和OBB包围盒,给出传统包围盒碰撞检测算法设计,通过主成分分析(PCA)来构建寻找包围盒主轴进而确定物体包围盒,应用分离轴理论(SAT)来检测包围盒之间的碰撞。虽然该算法较为高效,但是在处理凹多面体之间的碰撞检测问题时,包围盒只能为凸体,导致碰撞结果不准确。第二部分创新地提出基于点云数据的改进GJK算法,对点云数据进行栅格化处理,使用法向量聚类降采样并使用优先队列和大根堆等数据结构对算法进行遍历优化,该部分的研究工作可以完美的解决凹多面体之间的碰撞检测问题,但是在处理点云数据时,时间复杂度过高进而影响算法的实时性。第三部分,针对提升碰撞检测的实时性,通过近似凸分解手段(ACD)将凹多面体进行分割成凸多面体集合进而进行碰撞检测,又通过点云数据构建三角面片,使用空间三角形的相交测试代替计算点云欧式距离来进行碰撞检测,有效的解决了针对复杂形状物体之间的碰撞检测难题,同时在一定程度上提升了碰撞检测算法的实时性。本课题以码头装船机在自动装船的过程中,货船与装船机之间的碰撞检测为实际应用场景,通过激光雷达扫描得到的点云数据作为研究模型,在货船与装船机相对运动时检测算法的准确性和实时性,来验证本课题算法的实际应用意义。更多还原

【Abstract】 Collision detection has become a research hotspot in the field of automatic driving and computer animation games in recent years.With the gradual change of problem scenes,object models become more complex and refined,and the sudden and uncertainty of motion between object models increase,the traditional bounding box algorithm performs poorly in collision detection between complex objects(such as concave polyhedron),Therefore,the research on collision detection algorithms with high real-time performance for complex object models is of great significance.The research content of this topic mainly aims at two problems: one is to solve the collision detection problem between concave polyhedron,and the other is to improve the real-time performance of collision detection algorithm after the complexity of object model is increased or the number of objects is increased.Therefore,the main research content of this article consists of three parts:Part 1: Constructing AABB and OBB bounding boxes for object models,designing traditional bounding box collision detection algorithms,using principal component analysis(PCA)to construct and find the bounding box spindle to determine the object bounding box,and applying the separation axis theory(SAT)to detect collisions between bounding boxes.Although this algorithm is more efficient,when dealing with the collision detection problem between concave polyhedron,the bounding box can only be convex,resulting in inaccurate collision results.The second part innovatively proposes an improved GJK algorithm based on point cloud data,which rasterizes the point cloud data,uses normal vector clustering Downsampling,and uses data structures such as priority queue and large root stack to traverse and optimize the algorithm.The research work in this part can perfectly solve the collision detection problem between concave polyhedron,but the time complexity of processing point cloud data is too high,which affects the real-time performance of the algorithm.In the third part,in order to improve the real-time performance of collision detection,concave polyhedron is divided into convex polyhedron sets by means of approximate convex decomposition(ACD)for collision detection,and triangular patches are constructed from point cloud data.Instead of calculating the European distance of point cloud,intersection testing of spatial triangles is used for collision detection,which effectively solves the problem of collision detection between objects with complex shapes,At the same time,it improves the real-time performance of collision detection algorithms to a certain extent.This project takes collision detection between cargo ships and loaders during the automatic loading process of dock loaders as the practical application scenario.Using point cloud data scanned by Li DAR as the research model,the accuracy and real-time requirements of the detection algorithm during the relative movement of cargo ships and loaders are verified to verify the practical application significance of the algorithm in this project.更多还原