任意多面体的剖分算法及应用

An Algorithm for Dividing an Arbitrary Polyhedron into Tetrahedrons and Its Application

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

This paper proposes an algorithm to divide an arbitrary polyhedron to tetrahedrons and gives its theoretical basis, data type and implementation. The basic principle of the algorithm is to find a plane and a vertex to construct a simple polyhedron. After removing the simple polyhedron from the original polyhedron, we obtain a new one and the simple polyhedron can also be divided into tetrahedrons. Continue this procedure again and again until all polyhedrons are divided into simple polyhedrons.Every simple polyhedron is further divided into tetrahedrons.Finally the paper discusses the application of the algorithm in robot collision detection.