摘要：本文提出了一种将任意多面体剖分为四面体的算法,给出了算法理论基础的证明、算法具体实现步骤及所用数据结构.该算法首先根据多面体类型,查找出符合剖分要求的多面体一个面与一个顶点,构成一个简单多面体,将原多面体剖分为该简单多面体和一个新的多面体,再对新的多面体重复剖分,直到多面体全部剖分为简单多面体.每个简单多面体进一步剖分为四面体.最后,文章讨论了该算法在机器人碰撞检测中的应用.

关键词：多面体 剖分算法 碰撞检测 算法描述 四面体 

单位：上海大学计算机工程与科学学院; 上海; 200072