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

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.

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

碰撞检测是虚拟现实、物理模拟、机器人学、数控技术等诸多前沿领域的关键问题。高效、准确的碰撞检测算法是这些应用环境的共同诉求。本项目以构型分析为理论核心，研究三维曲面的碰撞检测相关的系列问题，包括排列穷举与判定、曲面求交、曲面奇点计算等。项目解决两个国际公开问题：一、椭球排列的完全分类、判定及连通图构建。这是在曲面求交领域从面求交向体求交提升的重要公开问题，也是组合几何学的重要问题；二、有理曲面的奇点快速稳定计算，这是计算代数与几何建模领域在CAGM2016三位大会主席Ron Goldman, Laurent Buse, Hal Schenck共同提出的公开问题。项目完成高水平论文20篇，包括ACM Transactions on Graphics 、IEEE Transactions on Image Processing、Pattern Recognition、ICM、Computer Aided Design、Computer Aided Geometric Design 等，获得多个专利与软件著作权。项目完成国家优青、科技部重点研发计划项目首席、中科院优博、CSIAM青年奖等人才培养及奖项。