碰撞检测 最早被广泛用于生产中的自动操作和处理，即虚拟组装和拆卸。近年来，

碰撞检测和响应的研究在虚拟现实中扮演了越来越重要的角色，特别是用碰撞检测和响

应来模拟现实生活中的接触、抓、移动和打击等情况。下面我们将对于碰撞检测的研究

状况进行简单介绍。

对于碰撞检测和响应的研究主要集中在对实体01精确碰撞检测算法和碰撞响应的处

理。目前己经形成了一些比较成熟的算法。虚拟现实中检测两个实体之间是否发生了碰

撞，实际上就是检测这两个实体所占的几何空间是否相交，常用的方法有离散方法和连

续方法。离散方法〔Discrete Methods)也称为静态方法(Static Methods)，是指当检测

时间CTs ,Te)内是否发生碰撞，则仅在Ts<Ts+t1<Ts+t2< <I、斗tk<Te一系列离散的时

间点上进行碰撞检测。Moore,M.和Wilhelms,J.提出了两种基于实体模型点、边和面几何

关系的碰撞检测方法。一种方法直接计算两个实体顶点、边和面之间的关系，另一种方

法是使用点积来判断一个点是否进入另一个实体内部.M.K.Ponamgi,D.Manocha,Ming

C.Lin等人提出了一种基于Varonoi区域的碰撞检测方法。这种方法利用虚拟环境中实体

运动的一致性，即实体运动状态的变化在dt时间内是有限的，大大减少了检测两个凸多

面体是否碰撞的时间，取得了实时碰撞检测的突破性进展。连续方法(Continuum

Methods)也称为动态方法(Dynamic Methods)，是指检侧当前实体从当前状态运动到下

一状态所滑过的四维空间与其它实体同时滑过的四维空间是否发生重叠。T.Duf的区间

分析(IntervalA nalysis)方法就是一种连续碰撞检测方法。由于连续方法比较复杂，计

算量比较大，所以绝大多数虚拟现实系统采用离散的碰撞检测方法。

当检 测到虚拟环境中发生碰撞时，需要根据碰撞情况修改发生碰撞实体的运动表示，

即修改实体的运动方程，确定实体的损坏和形变，实现碰撞对实体的影响，这就是碰撞

响应。在虚拟现实研究初期，对碰撞响应的要求比较简单。例如，在虚拟漫游系统碰撞

检测只是当检测到碰撞时禁止该方向的运动。现在对碰撞响应的研究越来越多。目前对

碰撞响应的研究主要有两个方向，一类是研究针对虚拟实体物理特性的碰撞响应，即碰

撞对实体的运动行为和本身特性的影响。例如美国联邦铁路部(FRA)对防撞性评估系

统的研究，主要分为三步:第一步是对单节机动有轨车辆碰撞物理特性的定义;第二步

是机动有轨车辆碰撞动力学模型的建立;第三步是计算碰撞结果，评估两铁路系统的防

撞性。另一类着重于研究碰撞响应的图形效果，即碰撞后实体损伤的图形表示和一些烟

火等特殊效果。在5TOW97的联合演练中，已经完成了炮弹爆炸后所产生的弹坑，道

路、桥梁及建筑物不同程度的损坏，车辙和一些明显痕迹的图形效果。

关于 平 面 碰撞检测问题的研究主要有3个方面，包括可碰撞、可移动区域和最初碰

撞部位的检测。近10几年来，许多专家学者对平面碰撞问题进行了深入的研究，并取

得一些很好的结果，提出了许多算法。Tetsuya, Toshiaki和Mario等人提出了一种称为

空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检侧它们的碰撞

[211。这种算法基于这样一条原理:没有任何物体和其他物体占有同一个球体，也不需要

特殊的计算来检测碰撞。并且，在它们的方法中，每个物体连同它们所占有的球体在3D

空间中都被赋予一个名字，因而其他物体知道它们和哪个物体发生碰撞。Chin及Wang

研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的

单调性，提出了判别凸n-边形和一个简单非凸m一边形的相交问题的最优算法[2z1，并且

研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题，其时间复

杂度都为0(m+n)e David Baraf研究了平面内多个凸多边形的碰撞问题，并采用将凹多

边形分解为凸多边形的方法来求解碰撞问题，其实质还是凸多边形的碰撞问题

关于 三 维 空间碰撞问题的研究一般有可碰撞和碰撞规避两方面。所谓可碰撞问题就

是物体A和B在空间沿给定轨迹移动时是否发生碰撞。可移动区域就是物体A沿给定

的规律运动，而不与物体B发生碰撞的所有可能运动的区域。最初碰撞点的检测就是当

物体A以给定的运动规律运动，并将与物体B发生碰撞时，检测它们在最初发生碰撞

时的接触部位。碰撞规避就是两个或多个物体的无碰撞运动。从对平面碰撞检测问题的

研究中，可得到有力和巧妙的技巧。而对于空间(?3D)的情形，则潜藏着难以克服的

困难，这也许是平面碰撞问题己得到很深入的研究，并提出了很多种最优算法，而对于

空间问题尚少有高效算法的一个原因吧。

很多 学 科 都对研究和模拟三维物体的干涉问题感兴趣。物体的千涉是两个或多个物

体的体积占有相同的空间。通常，物体的干涉有两大类，即静态干涉和动态碰撞检测。

动态碰撞检测就是沿特定轨迹移动的物体的干涉检测。动态碰撞检测算法又可分为两大

类:①判断移动的物体之间是否发生碰撞亦即可碰撞问题:②检测到碰撞的存在并采取

措施进行规避，也就是碰撞规避问题。静态干涉检测算法根据所用实体表示模型的不同，

现有实体千涉检验算法大致可分成两类。一类算法主要基于B-rep模型。在这方面，Gant

提出空间分割技术(24]。另一类算法是以层次模型为基础的，如八叉树千涉检验算法和层

次Sphere检验算法[(25(26 1[271。动态碰撞检测可应用两类技术，第1类技术是一种基于在

给定轨迹上反复利用静态干涉检测被称为“单步检测”的方法，第2类技术是基于产生称

之为“扫描实体’的物体。对于这两类技术的研究许多研究者都提出自己的算法aruyama

提出了一种递归空间分割算法和一种一般的面对面相交算法。然而，Boyse提出了第1

种可用的单步检测系统1281Ga nte:及Isarankura发展了单步检测方法，提出了一种空间分

割技术的方法。Hahn采用层次包围盒技术来加速多面体场景的碰撞检测。Moore与

Wilhelems根据Cyrus-Beck裁剪算法提出了一种凸多面体碰撞检测算法，即通过检测多

面体顶点是否相互包含来判定它们是否发生碰撞。对于具有n个凸多面体、每个多面体

有m个顶点的问题，此算法的时间复杂度为。(n2m2);对于凹多面体则分解为多个凸多

面体来处理。Ganter和Isara nkura提出了一种空间分割的方法，即将给定物体所占有的

空间划分成一系列子空间，将碰撞测试限定在两物体的重叠子空间中进行，并且在重叠

子空间里的元素都按最大、最小来排序，从而进一步减少了测试时间。最坏情况下的处

理时间为O(*N2/2), *N是重叠区域的单元面的总个数

From Wikipedia, the free encyclopedia

A bounding box for a three dimensional model

For building code compliance, see Bounding.

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.

A bounding volume for a set of objects is also a bounding volume for the single object consisting of their union, and the other way around. Therefore it is possible to confine the description to the case of a single object, which is assumed to be non-empty and bounded (finite).

[edit] Uses of bounding volumes

Bounding volumes are most often used to accelerate certain kinds of tests.

In ray tracing, bounding volumes are used in ray-intersection tests, and in many rendering algorithms, they are used for viewing frustum tests. If the ray or viewing frustum does not intersect the bounding volume, it cannot intersect the object contained in the volume. These intersection tests produce a list of objects that must be displayed. Here, displayed means rendered or rasterized.

In collision detection, when two bounding volumes do not intersect, then the contained objects cannot collide, either.

Testing against a bounding volume is typically much faster than testing against the object itself, because of the bounding volume’s simpler geometry. This is because an ‘object’ is typically composed of polygons or data structures that are reduced to polygonal approximations. In either case, it is computationally wasteful to test each polygon against the view volume if the object is not visible. (Onscreen objects must be ‘clipped’ to the screen, regardless of whether their surfaces are actually visible.)

To obtain bounding volumes of complex objects, a common way is to break the objects/scene down using a scene graph or more specifically bounding volume hierarchies like e.g. OBB trees. The basic idea behind this is to organize a scene in a tree-like structure where the root comprises the whole scene and each leaf contains a smaller subpart.

[edit] Common types of bounding volume

The choice of the type of bounding volume for a given application is determined by a variety of factors: the computational cost of computing a bounding volume for an object, the cost of updating it in applications in which the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intesection test. It is common to use several types in conjunction, such as a cheap one for a quick but rough test in conjunction with a more precise but also more expensive type.

The types treated here all give convex bounding volumes. If the object being bounded is known to be convex, this is not a restriction. If non-convex bounding volumes are required, an approach is to represent them as a union of a number of convex bounding volumes. Unfortunately, intersection tests become quickly more expensive as the bounding boxes become more sophisticated.

A bounding sphere is a sphere containing the object. In 2-D graphics, this is a circle. Bounding spheres are represented by centre and radius. They are very quick to test for collision with each other: two spheres intersect when the distance between their centres does not exceed the sum of their radii. This makes bounding spheres appropriate for objects that can move in any number of dimensions.

A bounding ellipsoid is an ellipsoid containing the object. Ellipsoids usually provide tighter fitting than a sphere. Intersections with ellipsoids are done by scaling the other object along the principal axes of the ellipsoid by an amount equal to the multiplicative inverse of the radii of the ellipsoid, thus reducing the problem to intersecting the scaled object with a unit sphere. Care should be taken to avoid problems if the applied scaling introduces skew. Skew can make the usage of ellipsoids impractical in certain cases, for example collision between two arbitrary ellipsoids.

A bounding cylinder is a cylinder containing the object. In most applications the axis of the cylinder is aligned with the vertical direction of the scene. Cylinders are appropriate for 3-D objects that can only rotate about a vertical axis but not about other axes, and are otherwise constrained to move by translation only. Two vertical-axis-aligned cylinders intersect when, simultaneously, their projections on the vertical axis intersect – which are two line segments – as well their projections on the horizontal plane – two circular disks. Both are easy to test. In video games, bounding cylinders are often used as bounding volumes for people standing upright.

A bounding capsule is a swept sphere (i.e. the volume that a sphere takes as it moves along a straight line segment) containing the object. Capsules can be represented by the radius of the swept sphere and the segment that the sphere is swept across). It has traits similar to a cylinder, but is easier to use, because the intersection test is simpler. A capsule and another object intersect if the distance between the capsule’s defining segment and some feature of the other object is smaller than the capsule’s radius. For example, two capsules intersect if the distance between the capsules’ segments is smaller than the sum of their radii. This holds for arbitrarily rotated capsules, which is why they’re more appealing than cylinders in practice.

A bounding box is a cuboid, or in 2-D a rectangle, containing the object. In dynamical simulation, bounding boxes are preferred to other shapes of bounding volume such as bounding spheres or cylinders for objects that are roughly cuboid in shape when the intersection test needs to be fairly accurate. The benefit is obvious, for example, for objects that rest upon other, such as a car resting on the ground: a bounding sphere would show the car as possibly intersecting with the ground, which then would need to be rejected by a more expensive test of the actual model of the car; a bounding box immediately shows the car as not intersecting with the ground, saving the more expensive test.

In many applications the bounding box is aligned with the axes of the co-ordinate system, and it is then known as an axis-aligned bounding box (AABB). To distinguish the general case from an AABB, an arbitrary bounding box is sometimes called an oriented bounding box (OBB). AABBs are much simpler to test for intersection than OBBs, but have the disadvantage that when the model is rotated they cannot be simply rotated with it, but need to be recomputed.

A minimum bounding rectangle or MBR – the least AABB in 2-D – is frequently used in the description of geographic (or “geospatial”) data items, serving as a simplified proxy for a dataset’s spatial extent (see geospatial metadata) for the purpose of data search (including spatial queries as applicable) and display. It is also a basic component of the R-tree method of spatial indexing.

A discrete oriented polytope (DOP) generalizes the AABB. A DOP is a convex polytope containing the object (in 2-D a polygon; in 3-D a polyhedron), constructed by taking a number of suitably oriented planes at infinity and moving them until they collide with the object. The DOP is then the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices for constructing DOPs in 3-D graphics include the axis-aligned bounding box, made from 6 axis-aligned planes, and the beveled bounding box, made from 10 (if beveled only on vertical edges, say) 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners). A DOP constructed from k planes is called a k-DOP; the actual number of faces can be less than k, since some can become degenerate, shrunk to an edge or a vertex.

A convex hull is the smallest convex volume containing the object. If the object is the union of a finite set of points, its convex hull is a polytope, and in fact the smallest possible containing polytope.

[edit] Basic intersection checks

For some types of bounding volume (OBB and convex polyhedra), an effective check is that of the separating axis theorem. The idea here is that, if there exists an axis by which the objects do not overlap, then the objects do not intersect. Usually the axes checked are those of the basic axes for the volumes (the unit axes in the case of an AABB, or the 3 base axes from each OBB in the case of OBBs). Often, this is followed by also checking the cross-products of the previous axes (one axis from each object).

In the case of an AABB, this tests becomes a simple set of overlap tests in terms of the unit axes. For an AABB defined by M,N against one defined by O,P they do not intersect if (M_x>P_x) or (O_x>N_x) or (M_y>P_y) or (O_y>N_y) or (M_z>P_z) or (O_z>N_z).

An AABB can also be projected along an axis, for example, if it has edges of length L and is centered at C, and is being projected along the axis N:
, and or , and where m and n are the minimum and maximum extents.

An OBB is similar in this respect, but is slightly more complicated. For an OBB with L and C as above, and with I, J, and K as the OBB’s base axes, then:

For the ranges m,n and o,p it can be said that they do not intersect if m>p or o>n. Thus, by projecting the ranges of 2 OBBs along the I, J, and K axes of each OBB, and checking for non-intersection, it is possible to detect non-intersection. By additionally checking along the cross products of these axes (I₀×I₁, I₀×J₁, …) one can be more certain that intersection is impossible.

This concept of determining non-intersection via use of axis projection also extends to convex polyhedra, however with the normals of each polyhedral face being used instead of the base axes, and with the extents being based on the minimum and maximum dot products of each vertex against the axes. Note that this description assumes the checks are being done in world space.

[edit] See also

• Minimum bounding rectangle
• Spatial index
• Minimum bounding box

[edit] External links

• Illustration of several DOPs for the same model, from epicgames.com