一种改进的AABB包围盒树更新算法

包围盒树的更新效率是基于AABB包围盒树碰撞检测算法的瓶颈之一。利用时间相关性原理,在底层包围盒更新之后进行预处理,判断是否继续更新,从而减少更新的包围盒的数目,节省包围盒树更新所消耗的时间。实验证明在基元数目为4万个时,采用改进方法更新包围盒树比常用的SOLID算法库节省了20%的时间,提高了算法效率。

基于动态包围盒树的碰撞检测算法研究

改进了以AABB包围盒为基础的碰撞检测算法.在多物体筛选阶段,利用AABB的构造特性和物体的运动特性,结合一维投影和二维投影来快速排除不可能相交的物体对,为了加快相交测试的速度,在投影测试之前划分坐标轴;在对可能相交的物体对进行进一步检测时,分割物体包围盒寻找可能碰撞的图元,在分割过程中建立动态包围盒树,减少了算法存储空间,有利于物体的更新操作.实现表明,改进后的算法效率有所提高.

地下空间轴向包围盒树三维碰撞检测算法研究

在综合比较多种三维碰撞检测包围盒的特点并分析以地下建(构)筑物为代表的地下空间对象基本形态的基础上,提出了基于轴向包围盒树的地下空间三维碰撞检测算法,并研究了算法的实现途径。通过上海地下空间信息基础平台大范围、多对象三维场景中碰撞检测的验证,该算法可以有效降低地下空间三维碰撞检测运算的复杂度,从而显著提高其运算速度。同时,该算法设计简单,利于计算机编程实现,对地下空间三维信息化系统的建设具有一定的借鉴意义。

一种基于莫顿码及镜像编码的平衡八叉树模型

在接触分析和动画模拟等网格规模庞大、需要实时更新的应用场景下,普遍采用莫顿码实现包围盒层次树结构的快速重构。但现有的层次树由于结构平衡性差,普遍存在搜索效率不稳定的问题,为此本文在莫顿码法的基础上提出了一种兼顾构建与搜索效率的平衡八叉树模型BOT树(Balanced Octree)。设计了镜像编码来保证树的上层节点均有8个分支,且同层树节点所含三角面数之差不超过1。实际算例表明,BOT树与现有模型OIOT树在CUDA并行框架下对比,构建加速比最高可达1.29×,且网格规模越大,BOT树构建效率的优势越明显。同时,与OIOT树相比BOT树的筛除率更高,在凸体接触和边缘接触算例中加速比分别达到1.13×和1.06×。

基于AABB包围盒的碰撞检测算法的研究

利用虚拟空间中对象运动的特性和AABB包围盒的构造特性,改进了基于AABB层次包围盒的碰撞检测算法。传统的该类算法分为两个检测过程,在初步检测过程中,基于运动对象碰撞行为的局部性,改进了原来的排序方法,采用希尔排序。为了提高检测效率,在相交测试之前将检测对象细分,划分测试区域,避免了不必要的相交测试;在对可能相交的对象进行精确检测过程中,基于AABB包围盒的构造特性,对可能碰撞对象的层次包围盒树进行压缩存储,通过减少算法的存储空间来提高算法的检测速度。对算法的两个检测过程同时进行改进,实验表明在检测对象较多的情况下减少了算法所需的执行时间。

基于混合包围盒的碰撞检测算法优化

为提高复杂场景中碰撞检测的效率,提出一种传统混合包围盒碰撞检测算法的优化算法。从数据结构上对混合包围盒树进行改进,引入时空相关性概念,将包围盒树分为上下2层结构,上层采用包围球,下层采用轴向包围盒,构造混合层次包围盒树,实现物体的快速碰撞检测,利用碰撞检测的时空相关性,简化树的搜索过程。实验结果表明,与传统的混合包围盒碰撞检测算法相比,该算法具有较好的碰撞检测性能。

混合包围盒碰撞检测算法的优化研究

首先分析球包围盒（Sphere）、轴向包围盒（AABB）、方向包围盒（OBB）、离散方向包围盒（K—DOPs）在包围盒构造和更新速度以及包围紧密性的优劣，兼顾碰撞检测对精确度和实时性的要求，采用AABB包围盒与OBB包围盒混合的碰撞检测算法，优化树的遍历过程，有效提高了碰撞检测的效率，具有很好的实用性。

基于包围盒细分的碰撞干涉检查算法研究

提出了一种基于轻量化三维模型的碰撞干涉检查算法.本算法只需要获得某时刻三维模型信息中的三角片顶点位置信息,就可以采用包围盒和判断空间三角形相交结合的方法完成轻量化三维模型的碰撞干涉检查.检查过程根据轻模型的三角片顶点信息构造包围盒,并对包围盒做分割处理,组织成八叉树结构,再进行这些分割后的包围盒的碰撞干涉检查,对发生干涉的叶节点包围盒则再对其中包含的三角面进行相交判断,若相交则说明发生了碰撞干涉.算法已得到初步应用,极大缩短了由大量三角面片构成的轻模型的碰撞干涉检查时间,而且提高了检查的效率和精度.

起重机吊装系统包围盒坐标动态递归计算方法

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

基于OBB树的无网格几何数据处理

提出一种新的基于有向包围盒树(OrientedBoundingBox,OBB树)的处理无网格几何数据方案.与最常用的八叉树比较,它具有三方面优点:首先,OBB树反映了统计意义上的几何模型空间分布,它不仅提供了辅助的层次结构,其本身还可以用于生成原始几何模型的形状逼近;其次,OBB树的节点数目和所需内存比八叉树少,且更贴近几何模型;其三,遍历OBB树的代价略高于八叉树,收敛速度却更快.针对点云模型,作者将OBB树结构应用于点云模型的自适应绘制.实验结果验证了OBB树的上述优点.

多目标复合可视性约束下的机械臂无模型标定位姿研究

与基于模型的机械臂标定方法相比,无模型标定方法具有算法简洁和线性化误差小的优点,但这种方法需要在多个机械臂姿态下同时采集各连杆表面的靶标位姿,因此其可视性同时受视场角狭窄、靶面方向异常以及臂体遮挡的影响,增加测量位姿的构造难度。为此,提出一种基于多目标视觉的复合可视性约束下的机械臂无模型标定位姿遴选方法。依据机械臂连杆参数及轮廓尺寸,生成贴合其等效模型的有向包围盒树,并依据臂体外形特征设定各连杆靶标固连位姿。在此基础上,分别建立靶标角点被包含判据、靶面法向夹角判据以及各包围盒与靶面视锥干涉判据,将其融合为多目标复合可视性约束条件,该算法可在既定工作轨迹下遴选出全体靶标均为可视的机械臂位姿。最后,通过搭建实验台验证所提方法的有效性。实验结果表明:该方法对臂体与靶面的遮挡关系判断精准,靶标在所选位姿处可视性良好,满足机械臂实时无模型标定方法对于多靶标位姿同时采集的需求。

碰撞检测技术综述

综述了当前出现的各种碰撞检测算法。总体上讲大部分的算法都采用先采样然后进行静态碰撞检测的方法。不同算法采样的方式不同决定了算法的种类,距离预测法或者是时间预测法。减少采样次数,提高静态检测的速度是降低算法复杂度最重要的因素。目前研究的重点有层次数据表示法、动态距离跟踪算法、静态检测算法等。

一种快速的基于并行的碰撞检测算法

提出了一种基于并行的碰撞检测算法,主要采用分治策略建立平衡包围盒树,通过遍历包围盒树组成任务树,采用流水线技术遍历任务树来加速碰撞检测。该算法同时应用了多线程技术,能运行于单处理机和多处理机。

多分辨率层次点模型分片

基于点模型的有向包围盒树,首先建立点模型带拓扑信息的简化模型,基于这种几何表示,将网格模型的层次分片算法推广到点模型中·为解决大规模点模型的分片速度和分片效果之间的矛盾,将有向包围盒树与层次分片技术相结合,实现了多分辨率层次点模型分片·实验结果表明,文中算法能直接处理大规模点模型,且具有速度快、对噪声数据不敏感的优点·

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。

基于并行的快速碰撞检测算法的研究

为了提高检测速度,提出了一种基于并行的快速碰撞检测算法,该算法首先将任意多面体的剖分为多个四面体,然后对四面体进行并行碰撞检测,并通过建立包围盒树进一步提高算法的效率,并行算法采用基于MPI库方式来实现。结果表明,该算法显著提高检测速度并具备较高精度。

一种基于分治和流水线技术的并行碰撞检测算法

提出了一种基于并行的碰撞检测算法,主要采用并行算法中的分治策略,建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树,形成对一任务树的遍历,并将所有任务树的遍历平均分配到每个处理器,然后采用并行算法中的流水线技术,通过划分进程来遍历任务树,从而加速碰撞检测算法,同时在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。

铁路门吊司机仿真培训系统实现的关键技术

三维建模与实时碰撞检测是实现仿真培训系统的两个关键技术。利用3dmax建立几何模型,从3ds文件中导入图形元素,利用OpenGL的几何图元构造三维模型。通过建立包围盒树,采用基于包络树的碰撞检测算法实现碰撞检测。实验结果表明,提出的方法提高了虚拟环境的真实性与内存的利用率,并且能够快速实现碰撞检测,达到实时性要求。

基于拓扑层次图的碰撞检测算法

为了提高虚拟环境中碰撞检测的实时性和精确性,提出了一种基于拓扑层次图的碰撞检测方法。利用拓扑结构的连接关系将模型分割成凸集;然后利用凸集较强的适应性和OBB紧密性好的优点构造包围盒的拓扑层次图,提高了剔除不相交包围盒的效率,减少了检测时间;利用智能搜索算法———改进的A*算法搜索潜在碰撞集(PCS),进一步提高相交检测的速度和准确性。实验表明,该算法具有较高的速度和精度,能够满足复杂虚拟环境碰撞检测实时性和精确性的要求。

面向复杂产品交互虚拟装配操作的并行碰撞检测算法

运动对象间碰撞检测是交互式虚拟装配的一个基本问题,提出一种虚拟环境中运动对象间的并行化碰撞检测方法.该方法使用一种并行的、基于区域分割和快速相交校验排序的分解算法来包围盒层次模型,检测计算时依据用户的操作动态决定碰撞检测对以减少检测计算量,同时基于微机和局域网的并行方法来计算模型间碰撞,两个模型间碰撞检测时使用包围盒层次树动态更新方法.随后,以某型汽车底盘虚拟装配时的实时碰撞检测来验证算法性能.结果表明,该方法可以快速建立包围盒层次树模型,并可在交互操作中完成给定精度的实时碰撞检测.