中文摘要：

本项目研究利用二次曲面壳（quadric shell）作为包围盒，对由三维散乱点即'点云'表示的复杂形状的物体进行碰撞检测。项目的主要研究内容有1）研究'点云'模型表面子区域二次曲面壳包围盒的构造方法；2）研究两二次曲面壳碰撞检测的精确快速算法；3）研究构造层次化的二次曲面壳进行'点云'模型的碰撞检测。多面体表示的三维物体间的碰撞检测已有较成熟的方法，但'点云'模型间的碰撞检测问题一直很少有人研究。自然界和生命科学中许多复杂形状，如人或动物表面、地表模型以及分子结构模型等大都利用三维'点云'表示，模型之间的碰撞检测可应用于手术仿真、机器人路径规划、计算机动画、触觉反馈（haptic feedback）及生命科学中的几何计算等方面。在计算机辅助设计、虚拟现实以及机器人自动化等领域有非常重要的研究意义。

结论摘要：

点云模型的碰撞检测是几何计算、虚拟现实领域的研究热点之一，本课题主要研究利用二次曲面壳作为包围盒，对无结构的点云模型进行精确、快速的碰撞检测。围绕课题计划，本课题主要研究提出了利用signature sequence 方法判定两二次曲面交线形态（包括拓扑和几何）的精确分类方法，设计了对已知路径上有理运动的两二次曲面壳进行精确碰撞检测的算法；利用变分优化的方法基于二次曲面逼近对点云模型表面进行分割，分割后的区域用二次曲面壳表示；基于平方最小距离(SDM)设计了 三维"点云"模型两点间测地线的计算算法；提出了两二次曲线段的表示方法，位置关系判定条件，实现了两运动平面曲线多边形精确碰撞检测算法，针对平面凸多边形，课题组提出了基于Voronoi区域划分的多边形相交判断的新方法，进而设计出了相应的两运动多边形的碰撞检测方法。课题组在简化模型的平滑轮廓计算方面做出了显著的成果。课题研究成果作可以应用在机器人路径规划、计算机辅助设计、虚拟现实、数字娱乐等方面。