虚拟手术中的快速碰撞检测算法

为了解决当前虚拟手术仿真中使用单一包围盒进行碰撞检测实时性不能满足要求的问题,提出了一种针对虚拟手术的基于层次包围体的快速碰撞检测方法。该方法主要应用了层次包围盒(BVH)的思想,同时根据不同对象的拓扑结构特征,采用不同的包围盒技术来表示。首先,用层次包围盒来表示手术工具,用层次包围球表示手术对象;然后,利用包围球和方向包围盒的相交测试快速排除不相交部分;最后,对于可能发生碰撞的部分再使用更为精确的三角面片相交测试来确定碰撞信息。实验结果表明,在相同的虚拟手术场景下,提出的这种方法较使用单一的层次包围盒具有更快的速度。     

虚拟场景中碰撞检测技术研究

碰撞检测技术对于虚拟场景的逼真度起着致关重要的作用。论文分析了碰撞检测的基本原理，分别对空间分解法和包围盒检测法进行了阐述，提出了先用包围盒检测法排除不可能相撞的对象。再利用射线与三角面相交法确定碰撞的确切位置。这种方法有效地提高了碰撞检测的效率和场景的真实性。     

基于空间剖分的碰撞检测算法研究

针对虚拟环境中物体碰撞检测效率不高的问题,提出了一种基于空间剖分的碰撞检测算法。利用物体空间分布特性以及运动物体碰撞行为的局部性,先用空域分割中定性-定量结合的方法快速确定可能碰撞的物体对,再用混合层次包围盒进行精确测试,明显地提高了碰撞检测速度。实验分析表明,该算法不仅可实现复杂场景下多个物体同时发生碰撞的检测,也能保证算法在物体高速运动时的有效性。     

基于运动对象局部场景截取的碰撞检测算法

为了解决虚拟心脏介入手术系统中的碰撞检测问题,提出了一种基于运动对象局部场景截取的碰撞检测算法.通过实时构建运动对象的局部场景截取体,可以获取该对象周围的局部场景数据,有效地降低了碰撞检测复杂性.并且它对虚拟场景中埘象的形变属性没有特殊要求,可适用于虚拟环境中包含可形变对象的情形.通过虚拟心脏介入手术中的碰撞检测实验表明,碰撞检测频率达到500Hz以上,并能精确给出碰撞点和发生碰撞的基本几何元素等碰撞信息,可以满足虚拟心脏介入手术对碰撞检测的实时性与精确性要求.     

虚拟手术环境中软组织的快速碰撞检测

针对虚拟手术中软组织碰撞检测的实时性问题,提出了一种基于延迟更新策略的快速检测方法。该方法应用层次包围盒（BVH）的思想并根据拓扑结构特征来表示手术环境中的对象,同时使用延迟更新的策略来降低更新的计算量。首先用不同的层次包围盒来表示手术工具和手术对象;然后利用包围盒的相交测试快速排除不相交部分;再对可能发生碰撞的部分使用更为精确的三角面片相交测试来确定碰撞信息,最后使用延迟更新的策略来完成软组织变形时层次包围盒的更新。实验表明,该方法相较于现有算法在保持检测精度的同时能够有效提高碰撞检测的速度。     

复杂场景中基于拓扑空间网格的碰撞检测算法

为了提高复杂场景的碰撞检测效率,提出一种基于拓扑空间网格的碰撞检测算法. 由于场景中存在众多形状复杂、尺寸不一且运动状态不同的物体,首先采取场景预处理对空间进行均匀八叉树网格划分,建立物体方向包围盒层次树与空间网格拓扑结构,利用静态大尺寸物体分割策略提升定位精确性,然后在实时检测中利用拓扑空间网格及投影相交测试排除大量不相交物体对,利用层次包围盒算法对潜在碰撞对进行精确检测并计算出碰撞点. 实验结果表明,本算法有效地提高了实时检测的效率,适用于复杂虚拟场景中的碰撞检测.     

碰撞检测在虚拟心脏介入手术中的应用

虚拟手术系统是虚拟现实技术在现代医学的重要应用。碰撞检测是虚拟手术系统的基础问题。基于心脏介入手术中碰撞的特点,提出了结合空间分解和包围盒层次的混合碰撞检测算法。它能够满足虚拟心脏介入手术系统中对碰撞检测的实时性要求。该算法对被检测对象形变引起的更新不敏感,具有天然的解决可变形对象间碰撞检测的能力。     

复杂场景中快速碰撞检测算法及GPU加速

为了保证在大规模复杂场景中,碰撞检测的实时性和精确性,提出了一种基于图形空间与改进的图像空间相结合,并利用GPU加速的快速碰撞检测方法.利用AABB包围盒的检测策略,快速剔除不相交物体,确定潜在碰撞对象.改进传统的基于图像空间的碰撞检测算法,设计了基于向指定平面投影、模板测试和深度测试的碰撞检测算法.在此基础上,利用GPU的并行计算能力加速整个检测过程,有效地减少了碰撞检测时间.通过在虚拟驾驶系统当中的应用,验证了该方法在大规模复杂场景中碰撞检测的实时性和精确性.     

虚拟装配中快速碰撞检测算法的研究与实现

针对虚拟装配中碰撞检测的特殊要求，提出了一种基于包围盒与空间剖分法的两级碰撞检测算法HSDHBB。该算法首先用空间剖分法找出潜在的相交区域，然后用包围盒求得碰撞的三角面片对和精确的碰撞点。给出了层次包围盒树的构造方法和空间网格的剖分方法，在空间剖分中采用哈希表的数据结构加快检索速度。最后，在CATIA环境中实现了该算法，结果表明该算法能够满足虚拟装配系统的实时性和精确性的要求。     

一种基于半透明颜色叠加与深度值的碰撞检测算法

为了快速验证虚拟装配仿真过程中零部件的可装配性,改进了一种基于图像空间的快速碰撞检测算法。该算法首先通过半透明颜色叠加实现对无碰撞装配体的快速滤除,并确定出潜在的碰撞区域;然后利用像素深度值求出遮挡对象与待装配物体在其运动方向的最小分离距离,弥补了基于图像空间的碰撞检测算法只能判断物体间是否发生碰撞而不能求距的缺点;最后针对求距环节提出了一种像素区域划分策略,以提高算法的检测精度。测试结果表明,所提算法在整体上能够满足虚拟装配系统实时性和精确性的要求。     

An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies

Collision detection tests between objects dominate run time simulation of rigid body animation. Traditionally, hierarchical bounding box tests are used to minimize collision detection time. But the bounding boxes do not take shapes of the objects into account which results in a large number of collision detection tests. We propose an adaptive spatial subdivision of the object space based on octree structure to rectify this problem. We also present a technique for efficiently updating this structure periodically during the simulation.     

改进的基于AABB包围盒的碰撞检测算法

介绍了一种改进的基于AABB包围盒的碰撞检测算法,通过对对象不断的分割逐步构造出贴近对象的层次包围盒,在碰撞检测阶段对其逐层遍历以实现精确而快速的碰撞检测.实验结果表明,与层次包围球算法相比,该方法在构造二叉树和进行精确的碰撞检测时,性能都有较为明显的提高.     

刚体在软体对象环境中的碰撞检测的研究

刚体在软体对象环境中的碰撞检测在虚拟现实的研究领域具有很大的普遍性 ,但以往的研究较少 .文中给出了一种基于固定方向凸包 (FDH)包围盒树的碰撞检测方法 ,并着重论述了利用线性规划的思想以解决刚体自由运动后包围盒树的更新以及通过一种自底向上的方法解决软体对象变形后包围盒树的更新 .实验表明 ,该方法不仅能较好地解决刚体间的碰撞检测 ,而且能有效地解决刚体与软体间的碰撞检测     

A geospatial technique for detecting distance and Reflection Angle between real and virtual objects

This paper presents a geospatial collision detection technique consisting of two methods: Find Object Distance (FOD) and Find Reflection Angle (FRA). We show how the geospatial collision detection technique using a computer vision system detects a computer generated virtual object and a real object manipulated by a human user and how the virtual object can be reflected on a real floor after being detected by a real object. In the geospatial collision detection technique, the FOD method detects the real and virtual objects, and the FRA method predicts the next moving directions of virtual objects. We demonstrate the two methods by implementing a floor based Augmented Reality (AR) game, Ting Ting, which is played by bouncing fire-shaped virtual objects projected on a floor using bamboo-shaped real objects. The results reveal that the FOD and the FRA methods of the geospatial collision detection technique enable the smooth interaction between a real object manipulated by a human user and a virtual object controlled by a computer. The proposed technique is expected to be used in various AR applications as a low cost interactive collision detection engine such as in educational materials, interactive contents including games, and entertainment equipments. Keywords: Augmented reality, collision detection, computer vision, game, human computer interaction, image processing, interfaces.     

Collision Detection for Animation using Sphere-Trees

The detection of collisions between moving polyhedral objects is one of the most computationally intensive tasks in the computer animation process. The use of object-oriented techniques to encapsulate data within the objects' structures compounds this problem through the requirement for inter-object message passing in order to obtain geometric information for collision detection. The REALISM system decreases the time for collision detection by using a three stage process. The first stage identifies objects in the same locality using a global bounding volume table. The second stage locates regions of possible collision using a sphere-tree data structure (a hierarchical tree of spheres based on octree-type spatial subdivision). The final stage finds intersections between polygonal faces of the objects that are contained within the intersecting pairs of leaf nodes. Hence the algorithm uses a spherical geometry approximation rapidly to locate regions of potential collisions and then uses a local intersection test with actual object geometry information. The system is therefore fast and accurate. Tests for various geometric objects support this and show performance improvements of jive times over traditional polyhedral intersection tests.     

基于层次包围盒的混合碰撞检测算法

针对碰撞检测算法实时性较差的缺点,本文提出基于AABB包围盒与OBB包围盒相结合的混合碰撞检测算法,首先由对象投影来判断是否相交,检测出不可能相交对象;然后对可能相交的对象投影反向构建AABB包围盒,快速地测试对象;再用OBB包围盒进行精确地检测,以实现虚拟环境对象间高效的碰撞检测。本文还针对传统的基元相交测试效率不高的缺点进行了一定的改进。实验结果表明,与另外两种算法对比,该方法在相同环境前提下能够有效的提高碰撞检测的效率。     

基于包围盒和空间分解的碰撞检测算法

文中提出一种基于包围盒和空间分解的碰撞检测算法,用以解决软体的碰撞检测。算法使用AABB包围盒做初步检测,确定可能发生碰撞的物体。再根据包围盒的重叠情况缩小可能发生碰撞的区域,利用哈希表作为数据储存结构进行空间分解,将物体包围盒重叠区域的基本几何元素的空间网格映射到哈希表中,将碰撞区域缩小到基本几何元素,最后用基元碰撞检测找出具体碰撞点。由于前期AABB包围盒的处理减少了空间分解阶段需要映射的基本几何元素数量,该算法具有较高的运算速度。     

多机器人体间动态碰撞检测方法仿真研究

当前多结合包围求碰撞检测法、Average-Case法、K-DOPs法等实现多机器人体间动态碰撞的检测,均存在寻优性能较差、检测效率较低的问题。为此提出一种基于动态粒子群的多机器人体间动态碰撞检测方法。采用OBB层次包围盒方法,缩小多机器人之间需要动态碰撞检测的区域,同时把动态碰撞检测问题转换为物体特征对间距离机制的非线性优化问题,进而构建层次拓扑框架进行局部碰撞检测,将机器人体引入到粒子群算法中建立混合进化算法,找到动态碰撞检测的最优解,实现多机器人体间动态碰撞检测。仿真结果证明,所提方法的检测效率高达96%,且具有较高的寻优性能。     

基于双层候选集的快速人体-服装冲突检测

冲突检测是人体-服装动画研究的核心技术之一,已有的层次冲突检测方法在处理服装变形时需要对层次节点进行大量更新,计算复杂度高,难以满足实时检测的要求,针对人体和服装的特殊位置关系和运动规律,提出一种基于双层候选集的实时冲突检测方法.首先为服装模型的每个顶点建立可能发生位置冲突的人体模型面片候选集,利用候选集的母子双层结构剔除绝大多数不可能发生冲突的图元.该候选集相对于已有的层次方法具有更快的更新速度且具有较好的独立性,便于并行处理;在确定可能冲突的图元后,采用GPU片段程序来加速大规模图元间的相交测试.实验结果表明,该方法检测迅速准确,对一般人体-服装模型(10000面以下)能达到30～75帧/s的实时处理.