虚拟环境中碰撞检测问题概述

　　1碰撞检测的基本步骤.

　　在虚拟环境中，碰撞检测算法在处理包含大量物体的复杂场景时，首先将多数明显不相交的物体对进行快速排除，然后再对可能相交的物体对进行进一步检测，把这个过程统称为碰撞检测算法的初步检测阶段。而对于初步检测阶段的后继阶段，称之为碰撞检测算法的详细检测阶段。
 

　　1.1初步检测阶段

　　当动态场景中物体的个数超过两个，碰撞检测遇到的*明显的问题就是需要对所有N个物体进行两两求交检测，其时间复杂度达到O(N2)。这个问题也被称为“完全物体对检测问题”。很明显，这是任何碰撞检测算法在处理多物体的场景时都会遇到的严重影响算法效率的问题。因此，当场景中物体个数较多时，非常有必要利用一些优化策略或方法来快速排除明显不发生碰撞的物体，找出潜在的相交区域或潜在的相交物体对。空间剖分法是初步检测阶段所采用的技术之一，其基本思想是将场景均匀剖分成一个个小方块区间，检查这些小方块内是否有物体存在，否则将不包括物体的区间剔除，从而快速判断出潜在的相交区域。
 

　　1.2详细检测阶段

　　碰撞检测算法经过初步检测阶段确定了潜在的相交区域或潜在的相交物体对集合之后，转入详细检测阶段。详细检测阶段根据已经确定的潜在的相交区域或潜在的相交物体对集合做进一步的相交检测。这个过程分为两个层次：一个是逐步求精层;另一个是*求交层。逐步求精层通常采用两种典型的加速技术：空间层次剖分技术和层次包围盒树技术。空间层次剖分技术与初步检测阶段的空间剖分技术相类似，但要把潜在的相交区域子空间继续割分下去，直到找到相交物体的多边形面片，而层次包围盒树技术是指算法利用预先建构好的物体层次包围盒树，通过遍历物体对的层次包围盒树，递归检测它们的层次包围盒树上各层节点包围盒之间的相交情况，直到各一个层次树的叶子节点，*终获取物体对的相交检测结果的技术。在*求交层中，碰撞检测算法主要处理多边形面片减基本体素之间的*相交检测。基于多边形表示的碰撞检测算法在*求交层中需要进行多边形与多边形之间的相交检测。由于多边形均可转化为三角形，并且三角形之间的相交检测更简单，因而有很多研究工作集中于三角形之间的快速相交检测。
 

　　2碰撞检测算法分类

　　碰撞检测算法种类繁多，本文从两个角度对碰撞检测算法进行分类：一是从时间域的角度来分;二是从空间域的角度来分。
 

　　2.1基于时间域的碰撞检测算法

　　从时间域的角度来分，碰撞检测算法可分为静态碰撞检测算法、离散碰撞检测算法和连续碰撞检测算法三种。
 

　　静态碰撞检测算法是指当场景中物体在整个时间轴上都不发生变化时，用来检测在这个静止状态中各物体之间是否发生碰撞的算法。静态碰撞检测问题在计算几何中有着广泛的研究，一般对这类算法没有实时性的要求，但是对算法精度要求较高;离散碰撞检测算法则是指在时间轴的每个离散点t(mo)，t(m1)t(mn)……上不断地检测场景中所有物体之间是否发生碰撞的算法。离散碰撞检测算法在每一时间离散点上可以通过类似于静态碰撞检测算法的方祛来实现，它更注重算法的效率;连续碰撞检测算法是指在一个连续的时间间隔(t(mo)，t(mn)内，判断运动物体是否与其他物体相交的算法。该算法的研究一般涉及到四维时空问题或结构空间*的建模问题，这类算法通常计算速度比较慢，尤其是在大规模场景中无法实现实时的碰撞检测。
 

　　2.2基于空间域的碰撞检测算法

　　从空间域的角度来分，碰撞检测算法大体可分为两大类：一类是基于物体空间的碰撞检测算法;另一类是基于图象空间的碰撞检测算法。这两类算法的主要区别在于是利用物体三维几何特性进行求交计算还是利用物体二维投影的图象加上深度信息来进行相交分析。
 

　　2.2.1基于物体空间的碰撞检测算法

　　基于物体空间的碰撞检测算法一直是人们研究的重点，它可采用不同的空间结构来提高效率，根据所用空间结构的不同可将它们分为两类：空间剖分法和层次包围盒法。这两类方怯都是通过尽可能减少进行*求交的物体对或基本几何元素的个数来提高算法效率的。不同的是，空间剖分法采用对整个场景的层次剖分技术来实现，场景的层次剖分方法主要有均匀剖分、BSP树、k-d树和八叉树等。层次包围盒珐则是对场景中每个物体建构合理的层次包围盒树来实现。物体的层次包围盒可以根据其所采用包围盒类型的不同来加以区分，主要包括包围球、AABB包围盒、OBB包围盒以及k-DOPs包围盒等。
 

　　2.2.2基于图象空间的碰撞检测算法

　　基于图象空间的碰撞检测算法一般利用图形硬件对物体的二维图象采样和相应的深度信息来判别两物体之间的相交情况。这类算法优势在于能有效利用图形硬件加速技术来减轻CPU的计算负担，从而达到提高算法效率的目的。但是基于图象空间的碰撞检测算法由于其检测结果的不*性和依赖硬件支持而一直发展较慢。近些年，随着图形硬件计算性能的迅速增长，基于图象空间的碰撞检测算法进入了一个新的快速发展阶段。Rossignac和Shinya等人在1991年前后开创性地提出了图形硬件辅助碰撞检测的方法。
 

　　3结语

　　在虚拟场景中，主要是如何解决碰撞检测的实时性和*性的矛盾，不同的应用场合，对实时性和*性的要求不尽相同，因此大部分碰撞检测算法都是针对具体的应用场合设计的，没有一种算法适用于所有的情形。目前的碰撞检测算法主要集中于在静态环境下两个物体之间碰撞检测效率的研究，而对于动态环境下、复杂虚拟场景中虚拟对象之间的碰撞检测问题，高效率的检测算法还不多，因此快速有效的碰撞检测算法对提高虚拟环境的真实性起着至关重要的作用。
 

　　百检检测机构致力于为企业及个人提供便捷的检测服务。简化检测流程，提升检测服务效率，利用互联网+检测电商，为客户提供多样化选择,从根本上降低检测成本提升时间效率，打破行业局限和行业瓶颈，打造出行业创新新平台。公司主要业务范围包括食品、农产品、环境土壤、环保以及行业标准培训、零售商服务等，为您提供优质、便捷、专业的检测服务。

检测流程