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

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,et al . 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]	黄涛, 张智, 丁玉杰, 陈艳波, 王晶, 张文倩. 考虑动态频率安全与N-k故障的鲁棒应急调度方法[J]. 系统仿真学报, 2025, 37(12): 2981-2993.
[2]	张润昭, 陈艳波, 黄涛, 田昊欣, 强涂奔, 张智. 基于异构负荷特征解析预测的虚拟电厂调度方法[J]. 系统仿真学报, 2025, 37(12): 2994-3006.
[3]	于祥星, 赵艳东, 张宝琳. 基于电涡流NES的海上风机塔架振动控制[J]. 系统仿真学报, 2025, 37(12): 3007-3017.
[4]	李斌, 王于绰. 基于多策略融合的光伏系统故障诊断方法[J]. 系统仿真学报, 2025, 37(12): 3018-3032.
[5]	李孝斌, 胡冰, 尹超, 李波, 马军. 基于时空图卷积的汽车配件供应链需求预测与仿真分析[J]. 系统仿真学报, 2025, 37(12): 3060-3074.
[6]	彭艺, 雷云揆, 杨青青, 李辉, 王健明. 改进PID搜索算法的山地环境无人机路径规划[J]. 系统仿真学报, 2025, 37(12): 3075-3086.
[7]	陈逸, 邱思航, 朱正秋, 季雅泰, 赵勇, 鞠儒生. 基于启发式的人-大模型协作寻源方法[J]. 系统仿真学报, 2025, 37(12): 3112-3127.
[8]	索婧怡, 卢柏宏, 屈澈. 影视LED光源光强分布测定及其在游戏引擎中的仿真研究[J]. 系统仿真学报, 2025, 37(12): 3140-3151.
[9]	龚建兴, 胡海, 任海慧, 吴瑞祥. 面向虚实结合的军事训练系统互操作模型与运用[J]. 系统仿真学报, 2025, 37(12): 3161-3175.
[10]	徐智霞, 王蕊, 孙楠, 何兵, 沈晓卫, 朱晓菲. 基于改进遗传算法的协同干扰资源分配问题研究[J]. 系统仿真学报, 2025, 37(12): 3176-3189.
[11]	刘翔, 金乾坤. 基于PAC-Bayes的多目标强化学习A2C算法研究[J]. 系统仿真学报, 2025, 37(12): 3212-3223.
[12]	杨兰英, 李超, 邹海锋, 万江涛, 张仁强, 刘惠, 卢宏. 基于改进蚁群算法与A*算法相融合的机器人路径规划优化[J]. 系统仿真学报, 2025, 37(11): 2956-2965.
[13]	苏筱婷, 张小威, 田义, 李奇, 王帅豪. 星光导航动态仿真场景时序设计方法研究[J]. 系统仿真学报, 2025, 37(11): 2946-2955.
[14]	张志利, 刘瑾, 周召发, 梁哲, 张云昊. 基于ISCSO-BP神经网络模型的光纤陀螺温度补偿技术研究[J]. 系统仿真学报, 2025, 37(11): 2904-2917.
[15]	陈际同, 周佳加, 吴迪, 江海龙. 基于TD3-RRT的特殊环境下USV路径规划算法研究[J]. 系统仿真学报, 2025, 37(11): 2888-2903.