基于空间索引与碰撞检测的TIN求交算法

doi:10.3969/j.issn.1000-3428.2014.12.056

计算机工程 ›› 2014, Vol. 40 ›› Issue (12): 296-301. doi: 10.3969/j.issn.1000-3428.2014.12.056

基于空间索引与碰撞检测的TIN求交算法

赵景昌^a,白润才^a,刘光伟^a,刘威^b

辽宁工程技术大学 a.矿业学院; b.理学院,辽宁阜新 123000

收稿日期:2013-11-13 修回日期:2014-01-13 出版日期:2014-12-15 发布日期:2015-01-16
作者简介:赵景昌(1974－),男,讲师、博士研究生,主研方向:三维地学模拟技术;白润才,教授、博士;刘光伟,讲师、博士;刘威,副教授、博士研究生。
基金资助:
国家自然科学基金资助项目(51304104);中国煤炭工业协会指导性计划基金资助项目(MTKJ 2012-306);辽宁省教育厅科学研究基金资助一般项目(L2011051)。

TIN Intersection Algorithm Based on Spatial Index and Collision Detection

ZHAO Jingchang^a,BAI Runcai^a,LIU Guangwei^a,LIU Wei^b

a.School of Mining; b.College of Science,Liaoning Technical University,Fuxin 123000,China

Received:2013-11-13 Revised:2014-01-13 Online:2014-12-15 Published:2015-01-16

摘要/Abstract

摘要： 针对三维矿床地质模型构建及后续应用分析中的需求,提出一种基于空间索引与碰撞检测的不规则三角网(TIN)快速求交算法。通过建立TIN模型的空间格网索引,将相交测试与计算限定在映射于同一个空间格网单元内的三角形对之间,在求交计算过程中,应用包围盒碰撞检测方法快速剔除不相交三角形对,并分别采用边-面及改进的边-边求交算法计算异面与共面三角形交线,并根据交线段之间的空间邻接关系完成交线的快速分离。实验及应用结果表明,该算法效率高、运行稳定、计算结果可靠,能够满足大规模TIN快速求交计算的需要。

关键词: 三维矿床地质模型, 不规则三角网求交, 空间索引, 包围盒, 碰撞检测, 交线分离

Abstract: According to the needs of three-dimensional geological deposit model construction and subsequent analysis,a fast Triangulated Irregular Network(TIN) intersection algorithm based on spatial index and collision detection techniques is proposed.A spatial grid index of TIN model is established,then the intersection test and calculation are limited to those pairs of triangles which map to a same grid unit.During the calculation of intersection,the bounding box collision detection technology is applied to remove the non-intersect triangles quickly,and the intersection lines are calculated by applying line-plane and improves line-line algorithm to the non-coplanar and coplanar triangles respectively.They are separated efficiently according to their spatial adjacent information.Experimental results and practical application show that the algorithm is fast,robust and reliable,and it can meet the need for rapid intersection calculation of large-scale TIN.

Key words: three-dimensional geological deposit model, Triangulated Irregular Network(TIN) intersection, spatial index, bounding box, collision detection, intersection lines separation

中图分类号:

TP301.6

赵景昌,白润才,刘光伟,刘威. 基于空间索引与碰撞检测的TIN求交算法[J]. 计算机工程, 2014, 40(12): 296-301.

ZHAO Jingchang,BAI Runcai,LIU Guangwei,LIU Wei. TIN Intersection Algorithm Based on Spatial Index and Collision Detection[J]. Computer Engineering, 2014, 40(12): 296-301.

http://www.ecice06.com/CN/Y2014/V40/I12/296

参考文献

[1] 尹长林,喻定权.一种基于拓扑搜索的三角网求交算法[J].计算机工程与应用,2006,42(36):209-211.
[2] 蒋钱平,唐杰,袁春风.基于平均单元格的三角网格曲面快速求交算法[J].计算机工程,2008,34(21):172-174.
[3] 张少丽,王毅刚,陈小雕.基于空间分解的三角网格模型求交方法[J].计算机应用,2009,29(10):2671-2673.
[4] 陈学工,马金金,邱华,等.三维网格模型的稳定布尔运算算法[J].计算机应用,2011,31(5):1198-1201.
[5] 吴立新,史文中.地理信息系统原理与算法[M].北京:科学出版社,2003.
[6] 邬伦,刘瑜,张晶,等.地理信息系统:原理、方法和应用[M].北京:科学出版社,2001.

[7] Lo S H,Wang W X.A Fast Robust Algorithm for the Intersection of Triangulated Surfaces[J].Engineering with Computers,2004,20(1):11-21.
[8] 马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006,18(4):1058-1061.
[9] Gino van den Bergen.Efficient Collision Detection of Complex Deformable Models Using AABB Trees[J].Journal of Graphics Tools,1997,2(4):1-13.
[10] Hubbard P M.Collision Detection for Interactive Graphics Applications[J].IEEE Transactions on Visualization and Computer Graphics,1995,1(3):218-230.
[11] Gottschalk S,Lin M C,Manocha D.OBBTree:A Hierarchical Structure for Rapid Interference De-tection[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques.New York,USA:ACM Press,1996:171-180.
[12] Zachmann G.Rapid Collision Detection by Dynamically Aligned DOP-trees[C]//Proceedings of Virtual Reality Annual International Symposium.Washington D.C.,USA:IEEE Press,1998:90-97.
[13] Klosowski J T,Held M,Mitchell J S B,et al.Efficient Collision Detection Using Bounding Volume Hierarchies of K-dops[J].IEEE Transactions on Visualization and Computer Graphics,1998,4(1):21-36.
[14] Christer E.Real-time Collision Detection[M].San Fran-cisco,USA:Elsevier/Morgan Kaufmann Publishers,2005.
[15] 初剑,魏志强,孟祥宾,等.基于Delaunay三角剖分的曲面求交技术[J].系统仿真学报,2009,21(z1):155-158.
[16] Tomas M.A Fast Triangle-triangle Intersection Test[J].Journal of Graphics Tools,1997,2(2):25-30.
[17] Philip J S,David H.计算机图形学几何工具算法详解[M].周长发,译.北京:电子工业出版社,2005.

选择文件类型/文献管理软件名称

选择包含的内容

基于空间索引与碰撞检测的TIN求交算法

TIN Intersection Algorithm Based on Spatial Index and Collision Detection

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	费蓉, 马梦阳, 张晓, 黑新宏, 徐庆征, 邱原. 基于轨迹预测与冲突检测的自动驾驶碰撞检测模型[J]. 计算机工程, 2023, 49(7): 10-20.
[2]	靳雁霞, 史志儒, 杨晶, 刘亚变, 乔星宇, 张翎. 布料与精细建模物体间的碰撞检测算法研究[J]. 计算机工程, 2023, 49(7): 269-277.
[3]	彭振,吴百锋. 基于数据并行的碰撞检测[J]. 计算机工程, 2017, 43(9): 1-6.
[4]	童立靖,郑俊朝. 散乱点云曲面边界的二次提取算法[J]. 计算机工程, 2017, 43(2): 252-256.
[5]	刘艳,张静,吕敏. 基于视频的虚拟人群运动仿真方法[J]. 计算机工程, 2015, 41(4): 222-227,231.
[6]	易显天,徐展,郭承军,刘丹,张可. 基于Patricia树的空间索引结构[J]. 计算机工程, 2015, 41(12): 69-74.
[7]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[8]	吴勇，罗腾元，王美珍. 可定位图像采集与检索方法研究[J]. 计算机工程, 2014, 40(7): 207-211,220.
[9]	赵龙，闵世平，代强玲. 基于八叉树的三维地质剖面生成算法[J]. 计算机工程, 2014, 40(2): 250-255.
[10]	张龙涛,赵海峰,罗斌,郭庆. 基于网格拓扑优化的连续碰撞检测算法[J]. 计算机工程, 2014, 40(12): 292-295,301.
[11]	姜晓路, 刘渊. 基于混合包围盒的碰撞检测算法优化[J]. 计算机工程, 2012, 38(9): 285-287.
[12]	张立印, 陈根方, 杜旋, 胡海鸥, 赵琼迪. 中文简谱的图像分割与歌词提取研究[J]. 计算机工程, 2012, 38(9): 217-219,236.
[13]	王雪光, 付新良. 基于视线的智能碰撞检测方法[J]. 计算机工程, 2012, 38(18): 178-181.
[14]	郑延斌, 郭凌云, 刘晶晶. 混合包围盒碰撞检测算法研究[J]. 计算机工程, 2012, 38(13): 257-259.
[15]	沈学利, 吴琼. 基于包围盒和空间分割的混合碰撞检测算法[J]. 计算机工程, 2012, 38(06): 256-258.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于空间索引与碰撞检测的TIN求交算法

TIN Intersection Algorithm Based on Spatial Index and Collision Detection

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价