碰撞检测(Collision Detection)是计算机辅助设计和制造、计算机图形学、虚拟现实、数控技术、机器人学、分子动力学模拟等诸多科技前沿与工业领域的重要问题。准确且高效的碰撞检测算法是上述应用环境的共同需求.
一般碰撞检测通常只计算“分离、相交、包含”三种简单位置关系,而忽略了两包围体彼此地位的不对等性。在许多具体的应用领域中,对两几何体交换会导致相应环境质的变化,提供两几何体在相交过程中各自具体的几何或拓扑行为更加重要,而构型关系的研究将使这些被传统研究忽略的信息得以表达。
椭球是碰撞检测中常用的几何包围体。贾晓红与其合作者首次完成了两椭球所有构型(在组合几何学中也称排列)的分类、穷举并给出了代数判定条件及快速判定算法。该分类从交体角度对碰撞检测分体进行了更深入细致的研究。该工作给出的是代数判定算法,不需进行几何计算,因此从效率和准确性上都很有优势。该工作同时也构建了所有20种构型的连通图,可用于机器人运动趋势的快速预判。其中给出的代数判定序列也被用于对达布圆文面的几何形态穷举,首次给出了达布圆纹面所有14种几何形态。
该论文被计算机图形学顶级期刊ACM Transaction on Graphics预接收。该期刊是计算机科学领域顶级期刊,在计算机科学的软件工程所有期刊中排名第一。
审稿意见认为:“opens a huge window of potential applications”“an excellent paper …presents a systematic study..”“gives a complete, thorough study over the problem..”“solid theory work and the thorough study over this topic.”
相关论文:
X. Jia, C. Tu, B. Mourrain and W. Wang. Complete Classification and Efficient Determination of Arrangements Formed By Two Ellipsoids. PROVISIONALLY ACCEPTED by ACM Transactions on Graphics. 2019.
附件下载: