基于三角形分解的三角网切割

doi:10.16182/j.issn1004731x.joss.201711009

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (11): 2656-2662.doi: 10.16182/j.issn1004731x.joss.201711009

基于三角形分解的三角网切割

陈国军¹, 黄莹莹¹, 李华², 李金玲¹, 刘婧怡¹

1.中国石油大学(华东) 计算机与通信工程学院,青岛 266580;
2.中国石油天然气股份有限公司勘探开发研究院,北京 100083

收稿日期:2016-06-13 发布日期:2020-06-05
作者简介:陈国军(1968-),男,江苏如东,博士,副教授,研究方向为图形图像处理,虚拟现实。
基金资助:
国家863计划 (2015AA016403),虚拟现实技术与系统国家重点实验室(北京航空航天大学)开放基金(BUAA-VR-15KF-13),山东省教育厅高校科技计划(J15LN66)

Triangular Mesh Clipping Using Triangular Decomposition

Chen Guojun¹, Huang Yingying¹, Li Hua², Li Jinling¹, Liu Jingyi¹

1. College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China;
2. Exploration and Development Research Institute of PetroChina Co Ltd, Beijing 100083, China

Received:2016-06-13 Published:2020-06-05

摘要/Abstract

摘要： 三角网的切割广泛应用于网格重构、网格变形、地形融合与分析等领域,在地理信息系统应用中,三角网切割是实现地形表面模型与建筑物模型融合的关键算法。现有的多边形裁剪算法没有考虑相邻三角形的空间关系,直接用于切割三角网往往会出现T交叉点,形成不稳定三角网。为了解决这一问题,提出了一种基于三角形分解的三角网切割算法,根据三角形与裁剪线的位置关系,对三角形进行分解裁剪,分解时不引入非裁剪多边形边上的交点。实验结果表明分解裁剪算法能避免裁剪结果中出现T交叉点,有效生成稳定三角网。

关键词: 三角网切割, T交叉点, 分解裁剪, 多边形裁剪

Abstract: Triangular mesh clipping is widely used in grid reconstruction, grid deformation, terrain fusion and analysis, and many other fields. In the application of geographic information system (GIS), triangular mesh clipping is the key to the fusion of terrain surface model and building model. However, existing polygon clipping algorithms do not take the space relationship of adjacent triangles into account.If they were directly used in triangular mesh clipping, T-intersections would appear in the cutting results, leading tounstable triangular mesh. In order to solve this problem, a triangular mesh clipping algorithm based on triangular decomposition is proposed. Triangular decomposition is implemented according to the location relationship between the triangle and the cutting line, whichdoes not introduce other intersections that are not on the polygon line. Results of the experiments show that the decomposition algorithm can avoid T-intersections and effectively generate stable triangular mesh.

Key words: triangular mesh clipping, T-intersections, triangular decomposition, polygon clipping

中图分类号:

TP391.9

陈国军, 黄莹莹, 李华, 李金玲, 刘婧怡. 基于三角形分解的三角网切割[J]. 系统仿真学报, 2017, 29(11): 2656-2662.

Chen Guojun, Huang Yingying, Li Hua, Li Jinling, Liu Jingyi. Triangular Mesh Clipping Using Triangular Decomposition[J]. Journal of System Simulation, 2017, 29(11): 2656-2662.

参考文献

[1] 张英慧, 陈琦, 唐勇. 一个可靠实用的多边形裁剪算法[J]. 燕山大学学报, 1999(1):79-81.
Zhang Yinghui, Chen Qi, Tang Yong.A reliable and useful polygon clipping algorithm[J]. Journal of Yanshan University, 1999 (1): 79-81.
[2] 鲍虎军, 彭群生. 一个有效的多边形裁剪算法[J]. 自动化学报, 1996(6):741-744.
BaoHujun, PengQunsheng. An efficient algorithm for polygon clipping[J]. ActaAutomaticaSinica, 1996 (6): 741-744.
[3] 李志涛, 李霖, 吴贤良,等. 任意多边形裁剪算法的研究及其实现[J]. 测绘信息与工程, 2004, 29(5):8-10.
Li Zhitao, Li Lin, Wu Xianliang, et al.Research and implementation of polygon clipping algorithm[J]. JournalofGeomatics, 2004, 29(5): 8-10.
[4] Vatti B R.A generic solution to polygon clipping[J]. Communications of the Acm(S0001-0782), 1992, 35(7): 56-63.
[5] Greiner G, Hormann K.Efficient clipping of arbitrary polygons[J]. Acm Transactions on Graphics (S0730-0301), 1998, 17(17):71-83.
[6] 刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4):845-856.
Liu Yongkui, Gao Yun, Huang Youqun.An efficient algorithm for polygon clipping[J].Journal of Software, 2003, 14(4): 845-856.
[7] 付迎春, 袁修孝. 一种有效的任意多边形裁剪算法[J]. 计算机工程, 2006, 32(7):278-280.
Fu Yingchun, Yuan Yan.An efficient algorithm for polygon clipping[J]. Computer Engineering, 2006, 32(7): 278-280.
[8] Martínez F, Rueda A J, Feito F R.A new algorithm for computing Boolean operations on polygons[J]. Computers & Geosciences (S0098-3004), 2009, 35(35):1177-1185.
[9] 王结臣, 沈定涛, 陈焱明, 等. 一种有效的复杂多边形裁剪算法[J]. 武汉大学学报:信息科学版, 2010(3): 369-372.
Wang Jiechen, ShenDingtao, Chen Yanming, et al. An efficient algorithm for complex polygon clipping[J]. Journal of Wuhan University: Information Science Edition, 2010 (3): 369-372.
[10] 何陈棋, 陆国栋, 谭建荣. 基于编码与分类技术的任意多边形裁剪新算法[J]. 计算机工程与应用, 2003, 39(21): 56-58.
He Chen chess, Lu Guodong, Tan Jianrong. A high efficient polygon clipping algorithm against rectangular window based on encoding and classification technique[J]. Computer Engineering and Applications, 2003, 39(21): 56-58.
[11] 彭欢, 陆国栋, 谭建荣. 基于端点与交点编码的矩形窗口多边形裁剪新算法[J]. 图学学报, 2006, 27(4): 72-76.
PengHuan, Lu Guodong, Tan Jianrong. A new algorithm of polygon clipping against rectangular window based on the endpoint and intersection-point encoding[J]. Journal of Graphics, 2006, 27(4): 72-76.
[12] 范俊甫, 孔维华, 马廷,等. RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报, 2015(3): 338-345.
Fan Junfu, Kong Weihua, Ma Ting, et al.RaPC:ARasterization-based Polygon Clipping Algorithm and Its Error Analysis[J]. Acta Geodaeticaet Cartographica Sinica, 2015 (3): 338-345.
[13] Karinthi R, Srinivas K, Almasi G.A Parallel Algorithm for Computing Polygon Set Operations[J]. Journal of Parallel & Distributed Computing(S0743-7315), 1994, 26(26):115-119.
[14] Puri S, Prasad S K.Output-sensitive parallel algorithm for polygon clipping[C]//Parallel Processing (ICPP), 2014 43rd International Conference on. IEEE, 2014: 241-250.
[15] 李金玲. 三角网的并行切割算法及应用[D].青岛: 中国石油大学(华东), 2015.
Li Jinling.A parallel cutting algorithm of triangular mesh and its application [D]. Qingdao: China University of Petroleum (Hua Dong), 2015.

基于三角形分解的三角网切割

Triangular Mesh Clipping Using Triangular Decomposition

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184.
[2]	陈斌, 刘悦, 杨亚磊. 基于STN的机场航班过站保障时间协同规划建模[J]. 系统仿真学报, 2022, 34(6): 1196-1207.
[3]	杨凯, 陈纯毅, 胡小娟, 于海洋. 蒙卡渲染画面多特征非局部均值滤波降噪算法[J]. 系统仿真学报, 2022, 34(6): 1259-1266.
[4]	陈麒, 崔昊杨. 基于改进鸽群层级的无人机集群视觉巡检模型[J]. 系统仿真学报, 2022, 34(6): 1275-1285.
[5]	王沐晴, 张磊, 范秀敏, 骆晓萌, 朱文敏. VR外设驱动的虚拟人姿态优化仿真方法[J]. 系统仿真学报, 2022, 34(6): 1296-1303.
[6]	陆承, 靳学胜. 基于Steam VR的交互仿真水枪灭火训练系统设计[J]. 系统仿真学报, 2022, 34(6): 1312-1319.
[7]	高宏鼐, 付丽疆, 夏倩, 郭亚. 可观测度在光合作用模型性能评估中的应用[J]. 系统仿真学报, 2022, 34(6): 1330-1342.
[8]	倪凌佳, 黄晓霞, 李红旮, 张子博. 基于协作式深度强化学习的火灾应急疏散仿真研究[J]. 系统仿真学报, 2022, 34(6): 1353-1366.
[9]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[10]	郭宇飞, 赵康, 海永清. 面向有限元分析的三角网格布尔运算方法[J]. 系统仿真学报, 2022, 34(5): 1003-1014.
[11]	吴桐, 王清辉, 徐志佳. 三周期极小曲面多孔材料渗透率尺度特性研究[J]. 系统仿真学报, 2022, 34(5): 1015-1024.
[12]	蒋阳升, 王思琛, 高宽, 刘梦, 姚志洪. 混入智能网联车队的混合交通流元胞自动机模型[J]. 系统仿真学报, 2022, 34(5): 1025-1032.
[13]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[14]	张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063.
[15]	邢根上, 鲁芳, 李书山, 罗定提. 基于产品体验性的供应链交货模型与仿真研究[J]. 系统仿真学报, 2022, 34(5): 1064-1075.