计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (25): 20-23.

• 博士论坛 • 上一篇    下一篇

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

李昌领1,张  虹1,朱良峰2   

  1. 1.中国矿业大学 环境与测绘学院,江苏 徐州 221008
    2.华东师范大学 地理信息科学教育部重点实验室,上海 200062
  • 出版日期:2012-09-01 发布日期:2012-08-30

Improved algorithm for dividing arbitrary polyhedron into tetrahedrons

LI Changling1, ZHANG Hong1, ZHU Liangfeng2   

  1. 1.School of Environmental Science and Spatial Informatics, China University of Mining and Technology, Xuzhou, Jiangsu 221008, China
    2.Key Laboratory of GISciences for the Ministry of Education, East China Normal University, Shanghai 200062, China
  • Online:2012-09-01 Published:2012-08-30

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

关键词: 多面体剖分, 四面体, 有向包围盒, 透视投影, 平面切角, 空间切角

Abstract: 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 triangulation 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 triangulation. 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.

Key words: polyhedron dividing, tetrahedron, Oriented Bounding Box(OBB), perspective projection, plane corner-cutting, space corner-cutting