碰撞检测是物理仿真、路径规划、虚拟装配及触觉渲染等诸多计算机科学领域内的一类基础问题,至今已有许多解决该问题的算法被提出,然而这些算法各有优劣。例如V-Clip算法、Lin-Canny算法、GJK算法都将多面体视为凸体对象,因此对于凹多面体,需要通过构造凸包来转化为凸体对象。而且当具体到实际应用中时,还会遇到一些其他挑战:例如触觉渲染要求极高的刷新率;精密零件的虚拟装配不但需要算法能够快速得到结果,而且对结果的准确性要求也很高,因此根据实际应用环境对已有的凸包构造算法和碰撞检测算法进行优化改进是一个值得研究的领域,具有理论意义与实际工程价值。本论文以刚性的基于三角形图元的机械表精密零件模型作为研究对象,论述了凸包构造和碰撞检测两个阶段的相关问题。本文主要进行的工作及成果如下:1.研究了凸包的性质,并在此基础上对三维空间的卷包裹(Gift-Wrapping)算法和快速凸包(QuickHull)算法的基本思想和计算复杂度进行了论述,重点讨论了快包法的优缺点,并由此提出了一种改进的三维点集凸包构造算法,该算法通过优先考虑与凸包顶点共面的其他顶点,避免中间面的产生,减少最终构成凸包的图元数量。本文使用该算法构造零件模型的凸包,利用凸包加快包围体的构造,并实现机械表零件与夹具及环境的快速碰撞检测和仿真。2.研究了碰撞检测全局阶段的N-体剔除方法:包围体树、空间剖分以及拓扑法,并讨论了各自的适用场景。在拓扑法中,我们重点分析了最著名的扫掠剪除(SaP)算法以及其各类变种的优缺点和执行效率,并提出一种基于样本估计的SaP优化算法,该算法通过样本估计动态选择离散排序轴,降低了大型场景中模型积聚和模型规模变化对实时性的负面影响。实验结果表明新算法的性能优于其他同类算法,且能够适应各种场景环境,其适用性更广。3.研究了碰撞检测局部阶段的精确相交测试方法,针对现有包围体树算法的实时性不足、对机械表装配场景的适用性不佳的问题,本文提出一种改进的混合包围体树算法,该算法在创建树节点时使用了多个相关包围体,并对树的构造方式进行修改,从而对零件模型间的相交状态可以更加精确高效的检测。我们还对如何优化内存占用进行了讨论。4.利用Unity3D引擎实现了机械表虚拟装配系统,并以系统的场景为模板构造实验环境,以碰撞检测算法的运行时间、准确性以及综合性能几个方面为考察目标,设计了两个算法对比实验。通过分析与传统算法的对比实验结果,验证了本文提出的SSVs混合包围体树算法在性能上优于传统算法。