多面体的剖分算法及应用

An Algorithm for Dividing a Polyhedron into Tetrahedrons and Its Application

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

This paper proposes an algorithm dividing an arbitrary polyhedron into tetrahedrons. Its basic idea is to find a plane and a vertex to construct a simple polyhedron. After removing the simple polyhedron from the original polyhedron, we can obtain a new polyhedron and such simple polyhedron can be divided into tetrahedrons. Above steps are repeated until we finish all of divisions. We give the algorithms theoretic base, data type and its implementation, and then discuss its application on collision detection of the robot.