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

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

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

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

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.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

摘要/Abstract

摘要： 针对原相关算法中存在的不足，提出了凸顶点的凸空间从原多面体中完整剖分出去的充要条件。引入平面切角和空间切角的概念，使剖分思想更加直观、简化。对空间多边形进行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

李昌领1，张虹1，朱良峰2. 一种任意多面体剖分成四面体的改进算法[J]. 计算机工程与应用, 2012, 48(25): 20-23.

LI Changling1, ZHANG Hong1, ZHU Liangfeng2. Improved algorithm for dividing arbitrary polyhedron into tetrahedrons[J]. Computer Engineering and Applications, 2012, 48(25): 20-23.

[1]	廉西猛1，2，单联瑜1，隋志强1，赵翠霞1. 基于四面体剖分的并行地质块体建模方法[J]. 计算机工程与应用, 2018, 54(21): 246-250.
[2]	孙钊，许增朴，王永强，周聪玲. 机器视觉测量中透视投影误差分析控制与补偿[J]. 计算机工程与应用, 2018, 54(2): 266-270.
[3]	公维理. 基于嵌入式CPU-GPU的高清鱼眼视频实时校正系统[J]. 计算机工程与应用, 2016, 52(14): 172-179.
[4]	王俊，郑永安，史忠科. 基于柱幕投影的飞机大迎角仿真系统实现[J]. 计算机工程与应用, 2014, 50(1): 260-266.
[5]	郭星1，2，刘政怡1，2，李炜1，2，吴建国2，3. 一种大屏幕人机交互系统的实现方法[J]. 计算机工程与应用, 2012, 48(1): 176-179.
[6]	黄连杰1，李纳2. 用鞍点保证拓扑正确的快速等值面提取技术[J]. 计算机工程与应用, 2011, 47(26): 196-199.
[7]	蒋健勋1，方志刚1，2，徐洁2，王晓池2. 基于Sphere-OBB的改进碰撞检测算法及其应用[J]. 计算机工程与应用, 2011, 47(17): 172-174.
[8]	关文革，陆琰，武若. 四面体网格散列可视化测试方法研究[J]. 计算机工程与应用, 2010, 46(11): 161-163.
[9]	李鸿. 粒计算的四面体模型[J]. 计算机工程与应用, 2009, 45(28): 43-47.
[10]	朱奭¹,顾耀林². 基于体元投影的一种非规则数据场体绘制方法[J]. 计算机工程与应用, 2008, 44(15): 68-70.
[11]	曹秋萍，高满屯，史仪凯. 基于点线关系从透视画隐线图重构三维平面立体[J]. 计算机工程与应用, 2007, 43(20): 90-92.