一种任意多面体剖分成四面体的改进算法

Improved algorithm for dividing arbitrary polyhedron into tetrahedrons

针对原相关算法中存在的不足,提出了凸顶点的凸空间从原多面体中完整剖分出去的充要条件。引入平面切角和空间切角的概念,使剖分思想更加直观、简化。对空间多边形进行Delaunay三角剖分时,充分考虑了凸空间的结构特点,采用了透视投影的思想,使投影后的平面多面形保持了原空间多边形的拓扑结构和顶点的凹凸性,保证了三角剖分的合理性、正确性。基于空间相关性的思想,对凸顶点的邻接点生成有向空间包围盒,快速排除与凸空间不相交的面,加快了多面体剖分的速度;最后给出了改进后的剖分算法,对相关应用有着极大的实用价值。

Facing the shortage of related original algorithm, necessary and sufficient conditions for detaching the convex space from its polyhedron completely are presented. The concepts of plane corner-cutting and space corner-cutting are introduced, which can make the algorithm simple and intuitive. When doing Delaunay triangula- tion for a space polygon, a perspective projection method is used, which can keep the topological structure and concavity-convexity of original space polygon and can ensure the rationality and correctness of Delaunay triangula- tion. Based on space correlation, an Oriented Bounding Box（OBB） for the adjacent points of a convex vertex is generated, which can exclude facets intersecting with the convex space and speed up polyhedron dividing. Finally an improved dividing algorithm is proposed and is of great value to related applications.