论文摘要
针对目前碰撞检测算法普遍存在的准确性和实时性的矛盾,本文提出一种基于特征点的碰撞检测算法,以三维实体的特征点作为碰撞检测的计算依据,应用轴向包围盒AABB作为碰撞检测的辅助工具,在保证碰撞检测准确性的同时,降低算法的计算复杂度,加快碰撞检测的速度,提高算法的效率。在Julien Tierny提出的应用于骨架抽取的特征点提取算法的基础上,以局部极值作为判断依据,提出基于局部极值的特征点提取算法(Feature Point Extraction Based on Local Extremum, F-LE),增加有意义的特征点的提取数量。针对F-LE算法计算复杂度过高,提出两种基于夹角的特征点提取算法:基于邻接面夹角的特征点提取算法(Feature Point Extraction Based on Neighbor Faces Angle, F-NFA)和基于邻接点法矢夹角的特征点提取算法(Feature Point Extraction Based on Neighbor Point Vectors Angle, F-NPVA)。F-NFA算法和F-NPVA算法都是针对三角网格模型提出的。F-NFA算法以模型每条边的两个邻接面的夹角作为判断依据,F-NPVA算法以模型每条边的两个邻接顶点法向矢量的夹角作为判断依据。两种方法都能够快速有效地提取模型的特征点,并且提取的特征点的数量和准确度可以满足碰撞检测的需求。针对F-NFA算法和F-NPVA算法对不同模型进行特征点提取的阈值设定问题,提出三维模型特征点提取自适应阈值公式(Feature Points Extraction Self-Accommodated Value, F-SAV),根据模型自身的特点,可以方便地设定适合特征点提取的阈值。F-NPVA算法涉及顶点法向矢量计算,为解决狭长三角面对公共顶点法向失量的贡献问题,提出基于圆面积加权的点法矢计算方法(Point Vector Based on Circle Area, PV-CA),将狭长三角形各部分对公共顶点法向矢量的贡献进行合理地划分。实验结果表明,基于特征点的碰撞检测算法在保证碰撞检测准确性的同时,具有较低的计算复杂度,可以有效地提高碰撞检测的速度,适应实时碰撞检测的要求。