空间三角形快速相交检测算法 被引量：14

1

作者 邹益胜 丁国富 +1 位作者 何邕 许明恒 《计算机应用研究》 CSCD 北大核心 2008年第10期2906-2910,共5页

综述了典型的快速稳定的三角形相交检测算法的原理及实现方法,并根据算法原理将其分为标量判别型和矢量判别型算法。从计算量角度对各种算法的适用场合和性能进行了分析比较及验证,结果显示矢量判别型算法中的Olivier Devillers & P... 综述了典型的快速稳定的三角形相交检测算法的原理及实现方法,并根据算法原理将其分为标量判别型和矢量判别型算法。从计算量角度对各种算法的适用场合和性能进行了分析比较及验证,结果显示矢量判别型算法中的Olivier Devillers & Philippe Guigue算法整体性能最优,而标量判别型算法中的Oren Tropp算法最适合于三角形相交率较高的场合。 展开更多

关键词 空间三角形 相交检测 标量判别 矢量判别

下载PDF 职称材料

快速空间三角形对相交检测算法 被引量：6

2

作者 邹益胜 丁国富 何邕 《西南交通大学学报》 EI CSCD 北大核心 2011年第6期984-988,共5页

为提高干涉检测的效率,提出了一种快速的三角形对相交检测算法.该算法基于三角形对的各边进行精确相交计算的原理,利用三角形边向量之间的线性相关性、线段的投影特性以及计算的中间结果,提高了三角形对相交检测的效率.采用多种样本对Gu... 为提高干涉检测的效率,提出了一种快速的三角形对相交检测算法.该算法基于三角形对的各边进行精确相交计算的原理,利用三角形边向量之间的线性相关性、线段的投影特性以及计算的中间结果,提高了三角形对相交检测的效率.采用多种样本对Guigue、Shen、Mller、Tropp等典型算法及本文算法的精度和效率进行测试.结果表明:本文算法与典型算法的检测精度相同,在三角形对样本相交率大于0.2的场合下,本文算法比典型算法的检测速度快3.5%以上,并且检测速度优势随相交率和检测规模的增加而增加. 展开更多

关键词 三角形 相交检测 线性相关 碰撞检测 投影特性

下载PDF 职称材料

基于夹边边对的凸多边形间快速相交检测算法 被引量：4

3

作者 申静波 唐国维 李井辉 《计算机工程与科学》 CSCD 2007年第12期93-94,133,共3页

本文在对现有的相交检测算法进行研究的基础上,提出了基于夹边边对的空间平面凸多边形快速相交检测算法,为平面凸多边形间判交问题提供了一致的计算方法,并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步:第一步,确定所... 本文在对现有的相交检测算法进行研究的基础上,提出了基于夹边边对的空间平面凸多边形快速相交检测算法,为平面凸多边形间判交问题提供了一致的计算方法,并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步:第一步,确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对,如果至少一个凸多边形中不存在相对于另一凸多边形所在平面的夹边边对,那么立即返回两个多边形不相交;第二步,根据前面计算得到的两个凸多边形中的夹边边对,计算两组边对间对应夹边的符号距离判断两个多边形是否相交。 展开更多

关键词 凸多边形 相交检测 夹边 碰撞检测

下载PDF 职称材料

凸多边形间的相交快速检测算法 被引量：2

4

作者 申静波 李井辉 +1 位作者 孔铁臣 李德宝 《大庆石油学院学报》 CAS 北大核心 2008年第1期80-82,123,共3页

以基于带符号距离的三角形快速求交算法为基础,提出一种基于夹边边对的空间平面凸多边形相交快速检测算法,为平面凸多边形间判交问题提供了有效的计算方法,并扩展了算法的应用对象.实验结果表明,该算法在凸多边形相交检测方面,具有理想... 以基于带符号距离的三角形快速求交算法为基础,提出一种基于夹边边对的空间平面凸多边形相交快速检测算法,为平面凸多边形间判交问题提供了有效的计算方法,并扩展了算法的应用对象.实验结果表明,该算法在凸多边形相交检测方面,具有理想的鲁棒性和高效性. 展开更多

关键词 凸多边形 相交检测 夹边边对 碰撞检测

下载PDF 职称材料

基于扫描线法的数字线划图中多边形相交检测算法 被引量：2

5

作者 孙春生 《城市勘测》 2020年第2期126-128,共3页

针对数字线划图中多边形相交检测问题,提出了一种基于扫描线法的检测算法。该算法将多边形按节点拆分成多个线段,根据多边形节点绘制扫描线,获得扫描线与线段的交点,通过分析交点顺序及从属多边形,检测出相交多边形。算法效率高、数据... 针对数字线划图中多边形相交检测问题,提出了一种基于扫描线法的检测算法。该算法将多边形按节点拆分成多个线段,根据多边形节点绘制扫描线,获得扫描线与线段的交点,通过分析交点顺序及从属多边形,检测出相交多边形。算法效率高、数据处理能力强、利于编程实现,算法复杂度跟多边形节点数量正相关,适合处理数字线划图中大批量简单多边形的相交检测。 展开更多

关键词 扫描线法 数字线划图 多边形 相交检测

下载PDF 职称材料

基于分治思想的空间三角面对快速相交检测算法 被引量：2

6

作者 万瑶欣 黄婷婷 李大军 《江西科学》 2021年第1期35-40,共6页

空间三角面对相交是计算机图形中的基础问题,相关检测算法已广泛研究。现有算法中着重异面时的相交检测,对共面情况研究相对较少,而在空间三角面对相交问题中共面、异面各种情况均较常见,共面相交检测会影响整个相交检测问题的效率和准... 空间三角面对相交是计算机图形中的基础问题,相关检测算法已广泛研究。现有算法中着重异面时的相交检测,对共面情况研究相对较少,而在空间三角面对相交问题中共面、异面各种情况均较常见,共面相交检测会影响整个相交检测问题的效率和准确性,此外如何高效应用不同情况的检测算法的研究也较少。基于分治思想,考虑空间三角面对检测的各类情况及算法的实用性,将问题分为不相交快速排斥、共面相交检测和异面相交检测3类情况,通过优化算法流程来提高算法效率。实验结果表明,在共面和异面2种情况下,本文算法的计算效率均优于参考算法。 展开更多

关键词 空间三角面对 相交检测 分治法 快速排斥

下载PDF 职称材料

基于空间扫描策略的3维相交检测算法 被引量：2

7

作者 王永志 盛业华 +3 位作者 周良辰 郭飞 王永君 张平飞 《中国图象图形学报》 CSCD 北大核心 2011年第7期1262-1268,共7页

针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法———Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想... 针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法———Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想的空间扫描面;在扫描面移动的过程中,将空间对象的状态分为死亡态、激活态和休眠态,通过只对当前处于激活态的空间对象进行相交测试,有效地减少了空间对象间不必要的相交计算。该算法提高了虚拟场景中3维空间对象间相交检测的效率,为3D GIS中实时空间分析提供了有力的技术支持。最后,通过对比测试验证了本文算法的实用性。 展开更多

关键词 相交检测 空间扫描策略 红蓝思想 虚拟地理环境 3D GIS

原文传递

基于Ogre的漫游场景中精确碰撞检测方法 被引量：1

8

作者 吴静 李琳 《电脑应用技术》 2011年第1期12-16,共5页

三维场景中为了方便用户交互与观察,往往提供漫游的功能,使其可以到达身临其境的感觉,而碰撞检测技术是漫游系统中一个不可或缺的重要部分。广泛采用的都是基于包围盒的碰撞检测,其精度不高。为了提高漫游系统的真实感,本文研究了精确... 三维场景中为了方便用户交互与观察,往往提供漫游的功能,使其可以到达身临其境的感觉,而碰撞检测技术是漫游系统中一个不可或缺的重要部分。广泛采用的都是基于包围盒的碰撞检测,其精度不高。为了提高漫游系统的真实感,本文研究了精确到三角面片级别的碰撞检测,利用基于AABB的射线查询得到碰撞实体,再提取出实体mesh的顶点信息和索引信息,根据顶点索引对射线与mesh的三角面片进行相交检测,返回距离射线发射点最近的交点。 展开更多

关键词 碰撞检测 包围盒 射线查询 顶点索引 相交检测

原文传递

STL模型相交性检测及交线追踪算法

9

作者 杨凯祥 陈鸿 谢明师 《科学技术与工程》 北大核心 2017年第1期255-259,共5页

在对传统STL模型相交性检测算法进行研究的基础上,进行优化改进,提出一种投影降维法,将空间问题转化为平面甚至线性问题,降低了算法的空间复杂度。针对一般算法求取的交线段离散,且需要后再连接的问题,根据模型相邻面片间的拓扑关系,提... 在对传统STL模型相交性检测算法进行研究的基础上,进行优化改进,提出一种投影降维法,将空间问题转化为平面甚至线性问题,降低了算法的空间复杂度。针对一般算法求取的交线段离散,且需要后再连接的问题,根据模型相邻面片间的拓扑关系,提出一种基于拓扑查找的交线追踪算法,将交线段求取与连接融合在一起,使交线环的确定更加简洁直接。经试验证明,算法高效且可靠性高。 展开更多

关键词 STL 相交检测 拓扑重建 交线追踪

下载PDF 职称材料

面向牙科三维网格数据的非流形结构检测及快速修复

10

作者 魏广顺 马龙 +1 位作者 杨润泽 周元峰 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2024年第4期516-522,共7页

针对现有口腔扫描设备获取的网格数据存在自相交、孔洞等一系列问题,提出一种快速、有效的自相交检测算法.为了降低全局网格自相交检测的时间复杂度,引入一种特殊的八叉树算法,利用细分的思想把三角面片放置在不同的立方体内以实现快速... 针对现有口腔扫描设备获取的网格数据存在自相交、孔洞等一系列问题,提出一种快速、有效的自相交检测算法.为了降低全局网格自相交检测的时间复杂度,引入一种特殊的八叉树算法,利用细分的思想把三角面片放置在不同的立方体内以实现快速自相交检测,并通过删除操作消除错误连接;为了修复上一步骤中形成的大量网络孔洞,设计一种特殊的双边数据结构,能够快速有效地检测单连通封闭孔洞,并正确处理多个孔洞共用同一顶点的问题;孔洞修复完成后,利用拉普拉斯平滑策略对孔洞区域进行处理,获得过渡自然平滑的补洞效果.在80套口腔内扫描数据上的实验结果表明,所提算法不仅能够快速检测网格数据的自相交区域,而且能够高效完成补洞操作;与现有算法相比,在网格数量大于100万的数据上,处理速度提高大约10倍. 展开更多

关键词 网格修复 自相交检测 孔洞修复

下载PDF 职称材料

基于MATLAB的导弹毁伤效能数值计算效率优化方法

11

作者 肖师云 陈文 《火箭军工程大学学报》 2024年第3期1-8,共8页

为解决蒙特卡洛仿真法评估导弹毁伤效能计算时间长、效率低的问题,研究了一种基于MATLAB的导弹毁伤效能仿真计算效率优化方法。在建立一体化目标易损性模型和战斗部威力场模型的基础上,应用包围球相交检测法实现破片射击线与目标部件相... 为解决蒙特卡洛仿真法评估导弹毁伤效能计算时间长、效率低的问题,研究了一种基于MATLAB的导弹毁伤效能仿真计算效率优化方法。在建立一体化目标易损性模型和战斗部威力场模型的基础上,应用包围球相交检测法实现破片射击线与目标部件相交的快速检测,并建立了交点求解优化算法;基于MATLAB编制了导弹毁伤效能快速数值计算程序。实例结果表明:与常规线面相交求解算法相比,优化方法的计算效率提高了约16倍。 展开更多

关键词 杀伤概率 目标易损性 战斗部威力场 蒙特卡洛仿真 包围球相交检测

下载PDF 职称材料

基于三角面-三角形相交检测的五轴数控加工碰撞干涉检测算法研究 被引量：5

12

作者 刘雄伟 张平 +1 位作者 刘飞鹏 徐志洋 《机床与液压》 北大核心 2011年第9期23-26,共4页

碰撞干涉检测速度是五轴数控加工的关键难题之一。为了提高碰撞干涉检测速度,提出一种新的基于三角面片的碰撞干涉检查算法。使用分层OBB和八叉树相结合的算法快速检测出被检测面上可能存在干涉的碰撞叶子节点,将碰撞叶子节点用三角面... 碰撞干涉检测速度是五轴数控加工的关键难题之一。为了提高碰撞干涉检测速度,提出一种新的基于三角面片的碰撞干涉检查算法。使用分层OBB和八叉树相结合的算法快速检测出被检测面上可能存在干涉的碰撞叶子节点,将碰撞叶子节点用三角面片表示出来;在包含碰撞干涉叶子节点的三角面片和OBB的三角面片之间,通过三角面片的矢量判别法实现工件表面和加工轴之间的碰撞干涉检测。该算法克服了传统算法速度慢、效率低等问题,提高了碰撞干涉检测的准确性和精度。 展开更多

关键词 碰撞干涉检测 五轴数控加工 方向包围盒 八叉树 三角面-三角形相交检测

下载PDF 职称材料

雅可比旋量的装配体并联结构公差分析方法研究 被引量：4

13

作者 戴宏玮 陈琨 +3 位作者 于慧 杜欣霏 高建民 高智勇 《西安交通大学学报》 EI CAS CSCD 北大核心 2022年第5期156-165,222,共11页

针对使用雅可比旋量模型进行公差分析时,装配体局部并联结构累积公差难以计算的问题,提出了一种考虑配合表面接触状态的分步计算方法。该方法构建了局部并联结构的功能要求形成连接图,对装配结果的形成过程进行了描述,进一步建立了零部... 针对使用雅可比旋量模型进行公差分析时,装配体局部并联结构累积公差难以计算的问题,提出了一种考虑配合表面接触状态的分步计算方法。该方法构建了局部并联结构的功能要求形成连接图,对装配结果的形成过程进行了描述,进一步建立了零部件的雅可比旋量模型,计算了配合表面在零部件坐标系下的变动旋量。设计了配合平面空间位置关系检测算法,保证了配合平面间正确的物理接触;使用差分进化算法,以正确装配后被装配零部件重心最低为优化目标,计算了局部并联结构的公差累积结果。在充分利用设计信息的基础上,完成了含局部并联链的装配连接关系图向单一串联链的转化。以汽轮机通流间隙的建模和计算为例,验证所提方法的可行性。结果表明:所提方法对相关公差和配合信息进行了合理的平衡,能够显著提高模型的精确性和可靠性。 展开更多

关键词 雅可比旋量模型 装配体局部并联结构 空间面片相交检测算法 差分进化算法 汽轮机通流间隙

下载PDF 职称材料

多形态布料仿真中与刚体的实时碰撞检测 被引量：3

14

作者 唐勇 严凯丽 +1 位作者 刘宇涵 吕梦雅 《小型微型计算机系统》 CSCD 北大核心 2016年第10期2347-2350,共4页

现实环境中布料存在多种形态并不可避免的与其他物体发生碰撞.为了丰富布料动画模拟的场景,采用不同硬度、不同分辨率、不同风速条件下的布料与物体发生碰撞,实时模拟多种条件下的布料动态场景,进一步提高布料动画模拟的实用性.首先,使... 现实环境中布料存在多种形态并不可避免的与其他物体发生碰撞.为了丰富布料动画模拟的场景,采用不同硬度、不同分辨率、不同风速条件下的布料与物体发生碰撞,实时模拟多种条件下的布料动态场景,进一步提高布料动画模拟的实用性.首先,使用改进后的质点弹簧模型对布料进行建模,有效减少了虚拟弹簧的种类数,提高了计算速度和算法的稳定性.其次,提出一种简单风场模型描述真实风场,将布料受力均匀离散到各个质点上,简化了计算的复杂性;再次,使用改进的基元相交检测算法检测布料质点与碰撞物体三角面是否相交,有效避免了误判的产生;最后,根据布料与物体碰撞后会发生能量的耗散原理,修正碰撞后质点的位置和速度,有效解决了布料与物体的碰撞响应问题,大大增强了布料动画模拟的真实感. 展开更多

关键词 布料模拟 风场 质点弹簧模型 基元相交检测 能量耗散

下载PDF 职称材料

基于OBB与八叉树的数控加工碰撞干涉算法的研究 被引量：3

15

作者 周艳飞 王子牛 《贵州大学学报（自然科学版）》 2012年第5期68-71,共4页

为了提高碰撞干涉的检测速度,在构造层次包围盒时融合OBB与包围球的优点,能首先将多数明显不相交物体对快速排除。干涉检测分为快速检测和详细检测两阶段,先采用分层OBB结合八叉树的算法,快速检测出可能存在干涉碰撞的叶子节点;再在包... 为了提高碰撞干涉的检测速度,在构造层次包围盒时融合OBB与包围球的优点,能首先将多数明显不相交物体对快速排除。干涉检测分为快速检测和详细检测两阶段,先采用分层OBB结合八叉树的算法,快速检测出可能存在干涉碰撞的叶子节点;再在包含干涉叶子节点的三角面片和OBB的三角面片之间采用基于三角面—三角形相交检测算法,实现详细干涉检测。由于刀具路径离散点具有连续性,可以设置缓冲区来减少需要处理的节点数。这些改进有效简化算法,从而提高了碰撞干涉检测的效率。 展开更多

关键词 碰撞干涉检测 OBB 包围球 八叉树 三角面一三角形相交检测

下载PDF 职称材料

多视立体密集匹配点云的三维TIN构建算法 被引量：2

16

作者 韦江霞 李英成 《遥感信息》 CSCD 北大核心 2016年第5期139-144,共6页

针对多视立体密集点云(航空影像多视匹配得到的点云)数据海量、分布散乱造成构建三维TIN(Triangulated Irregular Network)效率低、错误率高以及适应性低的问题,提出一种自适应多视立体密集匹配点云的三维TIN的构建算法。该算法对二维... 针对多视立体密集点云(航空影像多视匹配得到的点云)数据海量、分布散乱造成构建三维TIN(Triangulated Irregular Network)效率低、错误率高以及适应性低的问题,提出一种自适应多视立体密集匹配点云的三维TIN的构建算法。该算法对二维构网方法进行改进,使算法适应不同地形的三维TIN构建。算法首先对密集匹配得到的点云进行自适应的分块索引,快速构建第一个三角形,然后对使用次数为1的边进行排序,对优先级最高的边进行扩展,生成新的三角形。在构建新三角形的过程中,为了避免三维空间内三角形的空间相交或包含(一定角度范围内),引入快速空间三角形相交检测方法,同时引进封闭点、封闭边以及封闭块的概念,动态删除封闭的点和封闭边,减少搜索次数,加快三维三角形的构建过程。实验结果表明,该算法对于城市地区起伏较大的地区构建的三维TIN,具有很高的适应性和效率。 展开更多

关键词 三维 三角网 点云 三角网生长法 快速相交检测

下载PDF 职称材料

三维虚拟战场环境中雷达网防御范围建模计算及可视化方法 被引量：2

17

作者 王闯 徐垚 《现代计算机》 2014年第3期19-23,共5页

针对虚拟战场环境中雷达网防御范围的建模计算及三维可视化需求,参照STK的方法,在通用建模的基础上通过预先处理及三角形对的相交快速检测等算法求得雷达网防御范围。试验结果表明,该算法通用性较强,对战场环境三维可视化的建模与仿真... 针对虚拟战场环境中雷达网防御范围的建模计算及三维可视化需求,参照STK的方法,在通用建模的基础上通过预先处理及三角形对的相交快速检测等算法求得雷达网防御范围。试验结果表明,该算法通用性较强,对战场环境三维可视化的建模与仿真具有重要的借鉴意义。 展开更多

关键词 虚拟战场环境 雷达网 三维可视化 三角形对快速相交检测

下载PDF 职称材料

区域边界合并算法的设计与实现

18

作者 葛平 杨洋 彭博 《测绘科学与工程》 2014年第5期30-33,37,共5页

本文通过对图幅内多边形进行拓扑构建与预处理，克服了多边形数据量大、拓扑关系复杂带来的处理困难，采用改进的多边形合并算法，通过接边处理点与环链位置关系和环链问位置关系的判断，成功实现了对多个图幅中同属性多边形的合并，为... 本文通过对图幅内多边形进行拓扑构建与预处理，克服了多边形数据量大、拓扑关系复杂带来的处理困难，采用改进的多边形合并算法，通过接边处理点与环链位置关系和环链问位置关系的判断，成功实现了对多个图幅中同属性多边形的合并，为完整显示任意复杂面对象及其之间的相互融合提供了有效的算法支持。 展开更多

关键词 计算机图形学 多边形 多边形合并算法 自相交检测

下载PDF 职称材料

通航飞机避碰区域防撞模型的等效性研究 被引量：6

19

作者 彭良福 颜悦 +1 位作者 石佳奇 陈亦鲜 《中国安全科学学报》 CAS CSCD 北大核心 2016年第8期95-99,共5页

为克服现有TCASⅡ只能提供垂直方向防撞措施的局限性,有必要建立通航飞机的多维机动防撞模型。基于低空空域通航飞机飞行防撞的特点,采用以包围体形成最小安全保护区的方法,分别建立以球体和圆柱体为包围体的通航飞机防撞模型。通过将... 为克服现有TCASⅡ只能提供垂直方向防撞措施的局限性,有必要建立通航飞机的多维机动防撞模型。基于低空空域通航飞机飞行防撞的特点,采用以包围体形成最小安全保护区的方法,分别建立以球体和圆柱体为包围体的通航飞机防撞模型。通过将包围体模型投影到水平和垂直方向上,再把水平和垂直2个方向的结果进行逻辑"与"运算,使复杂的三维防撞问题简化为2个二维防撞问题。采用3D游戏与计算机图形学中关于相交性检测的方法,对通航飞机的分别以本机和侵入机为参考中心的2个防撞模型进行分析和比较。结果表明,分别以本机和侵入机为参考中心建立的2个基于避碰区域(CAZ)的通航飞机防撞模型是完全等效的。 展开更多

关键词 通航飞机 机载防撞系统(TCASⅡ) 包围体 避碰区域(CAZ) 相交性检测

下载PDF 职称材料