基于构型分析的曲面碰撞检测理论及应用

碰撞检测是虚拟现实、物理模拟、机器人学、数控技术等诸多前沿领域的关键问题，高效准确的碰撞检测算法是其共同诉求。本项目将以构型分析为理论核心，以二次曲面为基本包围体，研究三维曲面碰撞检测的系列问题。..项目的主要创新是：传统碰撞检测中的“分离、相交、内含”或“交线的几何形态”仅检测了两几何体的相对位置关系，而构型分析可使两几何体地位的不对等性得以表达。在数控机床、机器人等对安全敏感的环境中，两几何体的互换会导致相应环境质的变化，提供几何体在相交时各自具体的几何或拓扑行为更加重要。..项目的预期贡献为：1.通过代数手段完成两二次曲面构型的穷举及分类；2.给出判定两二次曲面构型的符号计算方法；3.建立所有构型的连通图以建立碰撞预判机制；4.设计高效准确的检测两曲面构型变化过程的符号计算算法；5.设计开源软件包并在数控机床或机器人等工业环境中实践。

Collision detection is a key step of many advanced areas such as virtual reality, physical simulation, robotics and CNC machining, where efficient and exact collision detection algorithms are required. The project aims at investigating the collision detection of 3D surfaces bounded by quadrics through configuration analysis. ..The main innovation of the project is the use of configuration analysis that reveals the asymmetry of two target objects neglected by traditional collision detection techniques based on determination of the relative relationship such as ‘separation, overlapping, containment’ or morphology of the intersection curves. In many safe-sensitive environments such as CNC machining and robotics, interchanging the two objects can lead to qualitative change of the environment, hence providing the concrete geometric or topological behavior of each object is more important. ..The contributions of the project include: 1) establish enumeration and classifications of two quadric surfaces through algebraic approaches; 2) provide a symbolic algorithm of deciding the configuration of two static bounding volumes; 3) construct a stratification graph for all enumerated configurations to establish collision prediction system; 4) provide symbolic algorithms of detecting the configuration variations of two moving objects; 5) develop open source software package and apply to practical industry environments such as CNC machining and robotics.