一种用于光线与三角形网格求交运算的有效剔除算法(英文)

提出一种用于光线与三角形网格求交运算中的有效剔除算法.算法中,一根光线被定义为两个非平行平面的交线.针对由稠密三角形网格组成的复杂场景,算法通过三角形和测试平面的相交判断剔除与投射光线不相交的绝大多数三角面片.利用该算法,光线跟踪中主光线在图像空间的相关性可以方便、直观地被利用.为了利用物体在景物空间的相关性,算法可以结合层次包围盒、八叉树等常见的场景划分方法.而且,该算法可以方便地扩展应用于一般多边形网格.

3维不规则空间对象的求交和距离运算及其在矿山透水性分析中的应用

讨论了 3维不规则空间对象和栅格集合的求交运算和距离运算的概念及其数学描述方法 ,设计了相应的算法 。

参数曲面点元离散求交法

提出了一种基于点元的参数曲面求交交互式新算法。该算法在参数曲面上进行自适应的离散点元采样,将点元组织为空间八叉树结构进行求交运算,最后进行交点排序并得到最终的求交结果。与以往的参数曲面求交方法相比,本算法更简单高效。实验结果表明,本算法稳定可靠,误差可控,而且可以达到交互速度。

以节点操作实现多边形求交的算法

根据多边形之间的交点状态确定与交点相关的节点信息,以节点操作为核心求解两多边形之间的交集。在此基础上,考虑重叠边、边边相交于边节点等情形,通过遍历交点来完成交集多边形边界的构建,从而提出一种多边形求交运算的改进算法。该算法结构简单,具有较快的计算速度和较高的效率,适合于地理信息系统中的空间叠置分析、缓冲区分析应用,对于地图制图中区域要素的截取操作也具有重要的参考价值。

离散求交算法中的点元采样

从要进行求交的曲面方程中提取出曲面的高斯曲率、平均曲率、边界点等几何信息,根据这些信息将曲面离散成点元的形式,然后进行求交运算。实验表明,通过对曲面特征分析,缩小了点元动态重采样范围,能够有效地避免一些特征点丢失导致交点遗漏的情况,使离散求交算法更加稳定可靠。

数值流形法中确定不规则单元的多边形求交法

由数学覆盖和物理网格形成的流形单元的积分区域可以有任意形状,其形状为物理网格和数学网格的相交部分,所以流形单元积分区域的形成为两个多边形(数学网格和物理网格)的求交运算。文章提出了以节点操作求解两多边形交集的方法和算法,对于实心任意多边形的任意相交方式,该方法是准确和通用的,且易于计算机程序的实现。

基于双向链表操作的多边形求交与并的算法改进

对两个多边形的各边依次求交,根据交点所在边起始点与另一多边形的包含关系确定交点的入出状态,并按交点所在边的序号及距边起始点的距离排序,再插入到双向链表中,利用链表中各交点的入出状态搜索其交集、并集。论文算法中对点重合、边重合等特殊情况,仅需对在求取交点时做简单的特殊处理,其后续操作均使用统一处理方式,相比其它传统的算法,论文提出的算法简单高效。

基于剪枝优化与索引求交的改进Eclat算法

针对现有Eclat算法中普遍存在的候选集规模大、求交效率低的问题,提出了基于剪枝优化和索引求交的改进Eclat算法。首先根据频繁集的性质采用预剪枝和后剪枝相结合的候选集优化策略,即利用预剪枝技术裁剪待连接的项集数量以减少项集连接操作,同时利用先验性质对连接后的项集进行后剪枝处理;接着提出了一种基于事务索引的布尔数组求交方法,即通过将事务标识作为索引来设置并检索布尔数组,以获得项集支持度计数;最后通过设计对比实验,在经典数据集上测试该方法的有效性。实验表明,通过该方法能够有效压缩候选集规模,改善求交计算效率,特别是在支持度阈值小、事务数规模大的情况下,算法的运行效率得到了明显的提升。

三维复杂地质体的布尔运算算法研究与实现

提出一种稳定快速的三维复杂地质体的布尔运算算法。该算法不需要跟踪交线,利用带拓扑信息的交边对实体区域进行分类,避免面在体内的判断,提高运算速度。算法在进行布尔运算前解决了数值计算误差引起的相关分类间的冲突,保证运算的稳定性。将该方法应用于蓝光矿山数字化平台系统,实践结果证明其适合数据分散、数据密集及带孔洞的实体,特别是大规模、奇异的三维复杂地质体。

以节点操作确定两任意实心多边形交集的方法

两多边形求交问题在计算几何学、计算机图形学、地理信息系统、地质灾害预测评估及土木工程领域都有涉及。根据多边形节点所处的几何位置为其设置节点状态,基于多边形节点状态提出了以节点操作为核心的求解两多边形交集的方法和算法。该方法概念简单,易于计算机程序实现,避开了多边形求交运算中较难处理的布尔运算的奇异问题,能很好的解决重叠边、边与边相交于多边形顶点等多边形求交的难点问题。对于实心任意多边形的任意相交方式,该方法是准确和通用的。

常见相交二次曲面体正轴测图的画法及消隐处理

本文论述一种用计算机绘制相交的圆柱、圆锥、球等常见二次曲面体正轴测图的方法。把立体作为凸多面体生成轮廓线,用素线交点法求作相贯线,对比较困难的消隐问题,提出分层次消隐的比较简易的方法。所编程序在AppleⅡe机与DMP-42绘图机联机绘图,效果较好。

改进射线跟踪法效率的新方法

提高射线跟踪法的运算效率一直是进行电波预测的一大难题,本文分析了影响射线跟踪法效率的诸多因素,提出了一种改进二维微小区室外环境射线跟踪法效率的有效方法。该方法对室外建筑物环境进行分组,同时对环境中的绕射点进行绕射分区,以减少射线同建筑物的求交运算次数,大幅提高射线跟踪法的计算效率。仿真结果表明这种方法是有效的。

基于层片分割算法弧齿锥齿轮及准双面齿轮五轴数控切削仿真

针对目前的弧齿锥齿轮及准双面齿轮切削仿真系统独立性差、仿真速度慢、精度低等问题,提出了层片分割算法,以该算法为核心开发出了五轴数控弧齿锥齿轮及准双面齿轮仿真系统。介绍了层片分割仿真核心算法实现的原理和弧齿锥齿轮及准双面齿轮仿真系统的整体结构、各个模块的作用以及实现的流程,给出了仿真实例。

基于层片分割算法的螺旋锥齿轮切削仿真

为解决螺旋锥齿轮切削过程几何仿真存在的问题,提出了层片切割算法.通过将被加工零件进行适当的层片分割,利用刀具与锥齿轮毛坯的分割特征求交,齿坯在每一切削瞬时的切削形状可由所有这些特征的集合表达,从而显示出每一瞬时的切削过程,并得到螺旋锥齿轮的最终形状.该算法求交速度快,求交结果精确.此外,该算法是建立在已有的编程语言基础上,可独立于现有的商业软件.给出了螺旋锥齿轮切削仿真实例,验证了该算法的可行性.

基于历史缓存技术的射线跟踪加速算法研究

通过分析影响射线跟踪效率的因素,提出一种基于历史缓存技术的射线跟踪加速算法,以提高射线跟踪的运算效率。通过建立一个缓存区存储历史信息,用来减少每条射线必须处理的建筑物面的数量和减少计算无效的交点。对提出的算法进行仿真计算,仿真结果证明了这种算法的正确性,有效降低了计算的复杂度。

基于射线跟踪和Voronoi图的室内定位算法

传统的射线跟踪方法在离线数据采集时需要大量的求交运算,计算效率低,而传统的在线定位需要遍历数据库才能确定目标位置,为此,提出一种提高室内定位运算效率的新方法。该方法利用Voronoi图势力范围特性和局域动态特性,大大减少了离线阶段中射线与物体的求交次数;同时利用Voronoi图一级邻接点的特点,减少了在线阶段的匹配计算量。仿真结果表明了该方法的有效性。

层片分割算法在切削仿真中的应用

为解决切削过程几何仿真中普遍存在的问题,提出了层片切割算法。通过将被加工零件进行适当的层片分割,进而将刀具与毛坯的分割特征求交,则毛坯在每一切削瞬时的切削形状可由求交结果的集合进行表达,该算法求交速度快,求交结果精确。此外,由于该算法是在Visual C++6.0平台上结合OpenGL图形库实现的,因此可独立于现有的商业软件。通过将该算法应用在渐开线圆柱齿轮以及螺旋锥齿轮加工仿真中,验证了其可行性。

改进的Cohen-Sutherland线段裁剪算法

针对目前Conhen-Sutherland线段裁剪算法不能有效地判断出线段是否完全在窗口外的问题,提出了一种改进算法,通过添加一个判断条件,使得所有完全位于窗口外的线段都能快速地过滤出来,从而减少了求交点的次数,提高了运算效率。

对Cohen-sutherland线段裁剪算法的分析及改进

研究分析了cohen-sutherland线段裁剪算法,针对cohen-sutherland线段裁剪算法不能有效地判断出所有完全位于窗口之外线段的情况,通过添加判断条件,能够判断出所有完全位于裁剪窗口之外的线段,从而减少了求交点的次数,提高了算法的运算效率.

点元表示的参数曲面相切判断与计算

提出了一种基于点元的参数曲面求切新算法,该算法先对曲面进行离散点元采样,通过层次包围盒测试,建立法向包围锥,对判断为可能相切的区域,根据精度自适应动态重采样点元,最后进行求切运算。实验表明,通过对曲面可能相切区域分析检测,能够针对曲面相切的情况在可控误差范围内有效求出切点,算法稳定可靠且易于交互。