层次包围盒

摘要： 针对吊装仿真碰撞检测过程中AABB或OBB包围盒树的实时更新,本文提出一种基于二维投影的碰撞检测包围盒中心坐标动态计算方法。基于二维投影的碰撞检测包围盒中心坐标动态计算方法是一种针对层次包围盒动态碰撞检测过程中,吊装物、吊索具和上车臂架包围盒中心点坐标的实时更新策略。依据该方法,在吊装仿真过程中动态计算包围盒中心坐标,进而实时更新重构物体包围盒树,达到实时碰撞检测目的。

摘要： 针对航天员水下训练超大作业空间中的人机安全问题,提出了一种快速、精准的机械臂碰撞检测方法。首先,基于最小包络和二分法寻找模型最小包络球体及胶囊体,实现模型的最优球体及胶囊体包围盒的自动生成;然后,基于二叉树的思想,采用轴对齐包围盒(AABB)和球体及胶囊体包围盒2层结构,按照自顶向下的顺序对机械臂及舱体模型建立混合层次包围盒树,遵循同层优先的原则对层次包围盒树节点进行遍历,利用上层AABB层实现碰撞部位的快速定位,利用下层球体及胶囊体包围盒层保证碰撞检测的精度;最后,将该方法集成于自主研发的水下训练机械臂操控系统,进行了试验验证。结果表明:该方法减少了包围盒的多余体积,提高了碰撞检测的精度,计算效率提升了45%以上,满足超大作业空间碰撞检测准确性及实时性要求。

摘要： 光线追踪是常用的绘制技术之一,由于能够方便的模拟生成复杂光照效果,生成高质量图像,在很多领域都有着广泛的应用。光线追踪渲染的主要运算操作耗费在光线与场景相交的判断上,可以在两个方面提升效率,一是通过建立某种空间组织结构来加速相交计算过程;另一种方式是通过并行计算模式,结合硬件来实现同时计算。首先介绍了并行计算在光线追踪计算中的作用;接着介绍了并行计算及GPU计算的一些重要概念;然后介绍了常用的加速结构及实现原理,以及基于表面积的启发式算法;再接下来进行了基于加速结构和CUDA的射线追踪算法的并行化实现及效率测试,最后进行相关分析和总结。

摘要： [目的]针对现有虚拟装配与维修中可移动空间计算的算法精度、效率较低,甚至缺少算法的问题,结合舰船虚拟装配、维修的实际需求,提出一种能够快速、准确计算零部件在移动空间中碰撞验证的算法.[方法]首先,以层次包围盒与三角面片相交检测算法为基础,改进层次包围盒与三角面片在移动空间中进行变换的方法;然后,根据二分法与递增法求得干涉距离,提出一种空间碰撞验证与空间距离验证的算法;最后,利用CATIA二次开发技术设计并开发空间快速验证模块,验证算法的合理性与准确性.[结果]实例结果表明,在复杂程度不同的2000多个零件模型中,计算空间碰撞的时间在100 ms以内,计算空间距离的时间约为0.5 s.[结论]该算法在舰船设计人员考虑装配与维修空间时可起到较大的辅助作用,能够有效缩短舰船设计周期、生产周期与维护周期.

摘要： 对于碰撞检测算法,使用传统的AABB包围盒来构建包围盒层次树时,其包围盒层次树的层数、叶子结点的个数和各结点的存储字节数是影响碰撞检测效率的主要因素.为了减少结点存储容量对碰撞检测效率的影响,提高碰撞检测的效率,文中采取B+树的存储结构来存储包围盒等信息.在包围盒相交测试之前,使得各结点存储索引有序,不需要再对各结点进行额外的排序,减少了内存开销,并且避免了不必要的包围盒测试.此外B+树的非叶子结点不存储具体的数据信息,从而减少了整棵树的存储空间.实验表明,在检测环境和检测对象相同的条件下,使用B+树存储的AABB包围盒碰撞检测算法的检测时间明显比传统的AABB算法短.

摘要： 三维激光雷达被广泛应用在无人驾驶系统中对道路环境的检测和防碰撞检测.为增加激光雷达对扫描点云进行分割的准确性,提出一种基于深度投影的点云目标实时分割方法.首先采用体素化滤波去除噪声点,然后使用渐进式形态学滤波方法去除地面点,最后将点云进行深度投影,建立三维点云与深度投影图像的映射关系,利用深度投影图像的自适应角度阈值对点云进行目标分割,并将分割后的点云目标构造混合层次包围盒进行碰撞检测.实验结果表明该方法相对于传统聚类算法在时间效率上有明显提升,并且能有效降低过分割问题,实验数据目标分割准确率达到了78.82％,结合混合层次包围盒算法对分割后的点云目标进行碰撞检测,可有效地识别并判断物体空间位置关系,提升碰撞识别的准确性.

摘要： 针对复杂虚拟场景中碰撞检测效率低、精度差等问题,基于层次八叉包围盒的构建,提出多线程并行碰撞检测算法.构建三维网格模型的层次八叉包围盒,采用多线程并行的算法实现多层次包围盒的并行碰撞检测,基于动态任务分配策略,在保证负载均衡度的前提下提高检测速度和检测精度.相关实验结果表明了该算法的有效性.

摘要： 针对配电线的地理接线图自动转换为单线图时,线和设备的重叠交叉问题,该文提出了一种基于层次包围盒技术的自动成图排布算法;针对层次包围盒不紧密性造成的空间浪费,提出了一种对排布方向可能相交的临近路径的包围盒进行相交检测,及时利用空闲空间排布线路的方法.算法支持架空、地缆及混合型的区域电气接线图,真正解决了实际应用问题.

摘要： 定义了虚拟角色层次包围盒层级的概念,用有向无环图(DAG)描述和表达了虚拟角色层次包围盒层级,将虚拟角色层次包围盒层级、虚拟角色几何模型作为子系统与虚拟角色的骨骼系统进行正向层次联结,用基于虚拟角色关节驱动层次包围盒层级变形的方法研究了虚拟角色与虚拟环境对象之间基于层次包围盒的碰撞检测算法,从顶点、线段、三角形面三个几何层级得出了虚拟环境中的对象与包围盒发生碰撞的判定规则,研究了虚拟角色层次包围盒层级的纵向优先遍历算法,实验结果表明了算法及判定规则的有效性。

摘要： 定义了虚拟角色层次包围盒层级的概念,用基于虚拟角色关节驱动层次包围盒层级变形的方法研究了虚拟角色与虚拟环境对象之间基于层次包围盒的碰撞检测算法,从顶点、线段、三角形面3个几何层级得出了虚拟环境对象与虚拟角色层次包围盒发生碰撞的判定规则,研究了虚拟角色层次包围盒层级的遍历算法,对实验结果进行了分析和比较,表明了算法的高效率及判定规则的有效性.

摘要： 在层次包围盒的基础上,提出一种基于多智能体粒子群的快速碰撞检测方法.算法首先利用层次包围盒方法快速减小物体间可能发生的碰撞检测区域,并基于随机碰撞检测核心思想将问题转变为物体特征对间距离机制的非线性优化问题,在建立的层次拓扑结构基础上,结合多智能体系统技术和粒子群算法的进化策略,设计了一种多智能体粒子群算法来求解碰撞检测问题.通过仿真测试表明,该算法具有很高的搜索效率和寻优性能,能够满足碰撞检测的实时性要求.

摘要： 传统的基于CPU的光线投射算法绘制速度较慢,限制了它的应用.在保证绘制质量的同时,为了提高光线投射体绘制的速度以达到实时可交互,本文利用离屏渲染技术,提出了一种基于CUDA的层次包围盒空间跳跃加速的光线投射体绘制算法,利用八叉树结构组织体数据,并统计体数据在各个层次包围盒内的最小最大值等信息,在绘制时依据当前传递函数的不透明度跳过对重建图像无贡献的空体素,以加速光线投射.实验结果表明,该算法能很好地利用GPU的高性能并行计算能力,并提高包含大量空体素的体数据的绘制速度.

摘要： 在基于层次包围盒碰撞检测算法中，参与相交测试的包围盒的数目直接会影响到碰撞检测的速度。针对这一特点，本文利用虚拟环境中对象运动的时空相关性对k-DOPs包围盒树进行优化，通过跟踪上一时间点对包围盒树的遍历过程，确定当前时间点的遍历路径，从而有效地减少遍历过程中包围盒相交的次数，大大地提高了碰撞检测的速度。

摘要： 虚拟漫游系统中的视点大部分时间是在一个平面内运动的,本文结合这一特点提出了一种快速检测视点与场景中物体灰撞的层次包围盒策略.其核心思想是:在视平面上为物体建立二维包围盒,即包围凸多边形,判断包围多边形与视点的碰撞关系.通过这种方式来降低碰撞检测的维度,将三维空间中的碰撞检测问题转化到二维平面上.

摘要： 本发明提供了用于对光线执行光线跟踪的技术。该技术包括：基于包围盒层次的第一次遍历，识别被分类为驻留的第一存储页面；获得该包围盒层次的与该第一存储页面相关联的第一部分；根据光线相交测试遍历该包围盒层次的该第一部分；基于该包围盒层次的第二次遍历，识别被分类为有效且非驻留的第二存储页面；以及响应于该第二存储页面被分类为有效且非驻留，确定该包围盒层次在该第二存储页面内的每个节点发生未命中。

摘要： 本发明涉及一种层次包围盒构建方法，属于计算机图形处理技术领域，具体是涉及一种基于动态任务调度的层次包围盒构建方法。发明遍历BVH时将一个线程对应叶子结点，在聚类幼树重构时一个Warp对应2个内部结点，使得BVH构建算法在单个主机上的并行度进一步的提高，相比当前通用的方法BVH构建速度提升了大约25％。

摘要： 本发明涉及一种基于AOAAE层次包围盒及非接触角度分析碰撞检测方法。方法包括计算模型AABB、OBB包围盒；机械臂与工件AABB间相交测试；机械臂与工件的OBB间相交测试；AABB包围盒重叠区域的筛选；几何元素AABB包围盒筛选；基本几何元素相交测试。本发明的优点是避开了传统构建繁杂的层次包围盒方法，通过改进OBB直接相交测试算法，分别构建碰撞模型和基本几何元素的AABB包围盒筛选掉不相交面片，从而提出AOAAE碰撞检测算法，较之传统测试方法，加快了碰撞检测的速度。

摘要： 本发明提供一种基于层次包围盒碰撞检测的三维管线优化方法，包括以下步骤：S1：构建AABB包围盒模拟真实管线建筑场景；S2：设计基于层次包围盒的碰撞检测算法，通过遍历各个层次包围盒完成初步检测和逐步求精，得出管线碰撞检测报告；S3：根据管线碰撞检测报告确定需要进行调整的管线，基于二次开发平台BIM优化管线设计方案，得到最佳的空间分配和管线的布置；S4:对优化后的三维管线方案进行验证评价。其效果是：本发明可以运用于新建、改建和重建的中大型建筑之中，提高建筑工程管线施工的效率，减少管线资源成本，该方法结合软件二次开发平台，建立虚拟三维施工建筑模型，实现通过碰撞检测知识优化空间分配和综合管线布置。

摘要： 本发明公开了一种没有着色器干预下对交点进行连续层次包围盒遍历的方法。基于硬件的遍历协处理器提供树遍历操作的加速，该树遍历操作搜索树形数据结构中表示的图元与光线之间的交点。图元可以包括用于生成虚拟场景的不透明三角形和α三角形。基于硬件的遍历协处理器被配置为确定与光线相交的图元，并将交点信息返回到流式多处理器用于进一步处理。基于硬件的遍历协处理器被配置为省略被确定为与光线相交的一个或更多个图元的报告。省略的图元包括可证明能够被省略而不会对可视化虚拟场景产生功能性影响的图元。

摘要： 本发明公开了一种基于链表排序平衡二叉树的层次包围盒树构建方法，属于虚拟现实中软体碰撞检测技术领域。本发明将所要建立包围盒树的物体按照合理精度划分成基本几何图元，并生成对应的AABB层次包围盒，创建链表存储二叉树，对所建立二叉树进行遍历，在链表中每个二叉树对象增加一个属性值存储着该二叉树到参照地点的长度，根据链表中二叉树对象中该属性值对链表进行升序排列；遍历链表，将链表中的二叉树两两进行合并，合并结果存入该链表。本发明使用链表排序的平衡二叉树方法降低了树的高度，解决了二叉树合并过程中的重复排序问题，降低了遍历时的时间复杂度，节省了构造树的耗时，提升了碰撞检测过程的实时性及碰撞检测效率。

摘要： 本发明涉及一种基于AOAAE层次包围盒及非接触角度分析碰撞检测方法。方法包括计算模型AABB、OBB包围盒；机械臂与工件AABB间相交测试；机械臂与工件的OBB间相交测试；AABB包围盒重叠区域的筛选；几何元素AABB包围盒筛选；基本几何元素相交测试。本发明的优点是避开了传统构建繁杂的层次包围盒方法，通过改进OBB直接相交测试算法，分别构建碰撞模型和基本几何元素的AABB包围盒筛选掉不相交面片，从而提出AOAAE碰撞检测算法，较之传统测试方法，加快了碰撞检测的速度。

摘要： 本发明公开了一种虚拟环境中基于层次包围盒的碰撞检测方法，适用于虚拟装配以及三维地表建模领域。包括：(1)构建AABB‑OBB混合层次包围盒树；(2)对不同层次包围盒树中的节点中的包围盒进行相交测试；(3)检测不同层次包围盒树叶子节点中的三角形是否相交。本发明利用外层AABB包围内层OBB的特性，在外层AABB相交情况下，内层的OBB之间的相交测试只需检测特定的5条分离轴，可以大大减少包围盒相交测试的时间。最后在方法的基本图元相交测试阶段，利用OBB之间相交测试所计算的中间值代替三角形的坐标值，省去了不同模型中的三角形坐标变换这一步骤也提升了碰撞检测的效率。

摘要： 本发明涉及一种层次包围盒构建方法，属于计算机图形处理技术领域，具体是涉及一种基于动态任务调度的层次包围盒构建方法。发明遍历BVH时将一个线程对应叶子结点，在聚类幼树重构时一个Warp对应2个内部结点，使得BVH构建算法在单个主机上的并行度进一步的提高，相比当前通用的方法BVH构建速度提升了大约25％。

摘要： 一种三维复杂场景基于层次包围盒碰撞检测的路径规划优化方法，包括以下步骤：1)、定义两列表：待选列表L1和已选列表L2；2)、依次遍历L1表，取出当前结点c，放入L2表，表示对当前结点c找未碰撞领域拓展点；3)、以结点c为中心，进行粗试探，主要包括设置包围盒的尺寸与分割大小，沿一定方向进行预碰撞检测和精细碰撞检测；4)、判断粗试探是否成功，若成功则跳转L1表中的下一个结点，否则对当前结点C进行精搜索，沿设定方向进行预碰撞检测和精细碰撞检测，记录未碰撞区域拓展点N；5)、对未碰撞区域拓展点N进行A*代价评估，并进行降序排列插入到L1表；6)、循环遍历L1表找出代价评估最小值作为当前结点，重复上述步骤直至到达终点。本发明提供了一种有效提高路径规划效果和规划效率的三维复杂场景基于层次包围盒碰撞检测的路径规划优化方法。本发明解决其技术问题所采用的技术方案。