文件名称:
Linear Algebra & Trigonometry
开发工具:
文件大小: 51mb
下载次数: 0
上传时间: 2019-03-04
详细说明：Linear Algebra & TrigonometryContents
25 Collision Detection
25.1 Broad phase collision Detection
25.2 Mid phase coll
25. 3 Narrow Phase Collision Detection
17
25.4 Collision Detection with rays
25.5 Dynamic Cd Using bsP Trees
25.6 Time-Critical Collision Detection
25.7 Deformable models
25.8 Continuous collision detection
31
25.9 Collision Response
25.10 Particle
25.11 Dynamic Intersection Testing
Referenc
43
Bibliography
45
d
51
Chapter 25
Collision detection
To knock a thing down, especially if it is cocked at an arrogant
angle, is a deep delight to the blood
eorge santayana
Collision detection( Cd)is a fundamental and important ingredient in many computer
graphics applications. Areas where CD plays a vital role include virtual manufactur-
ing, CAD/CAM, computer animation, physically based modeling, games. Hight and
vehicle simulators, robotics, path and motion planning(tolerance verification),assem
bly, and almost all virtual reality simulations. Due to its huge number of uses, CD
has been and still is a subject of extensive research
Collision dctection is part of what is often referred to as collision handling, which
can be divided into three major parts: collision detection, collision determination
and collision. respon se. The result, of collision detection is a. boolean saying whet, her
two or more objects collide, while collision determination finds the actual intersections
between objects; finally, collision response determines what actions should be taken
in response to the collision of two objects
Consider an old-style clock consisting of springs and cog-wheels. Say this clock
is represented as a detailed three-dimensional model in the computer. Now imagine
that the clock's movements are to be simulated using collision detection. The spring is
wound and the clock's motion is simulated as collisions are detected and responses are
generated. Such a system would require collision detection between possibly thousands
of pairs of objects. Another challenge would be to simulate all the ants and all the
pine needles in an anthill. a brute-force search of all possible collision pairs would be
incredibly inefficient and so is impractical under these circumstances. An example of
complex collision detection is shown in Figure 25.1
To cope with large scenes, it is common to divide a collision detection system
into three phases. Broad phase CD works on a per object level and finds pairs of
objects whose BVs overlap(Section 25. 1). Mid phase CD(Section 25. 2)continues the
work and detects parts of two objects that Inlay overlap, and finally, larrow phase CD
(Section 25.3 )works on leaves of primitives or on convex parts of objects. These three
hases can be used together in a large CD system
25. Collision Detection
Figure 25.l. Rigid-body collision detection using tens of thousands of small geometrical objects
mostly boxes, torii, and an occasional ragdoll. (Images generated using the PhysX Kapla demo
courtesy of NVIDIA Corporation
In Section 25. 4 we discuss simple and extremely fast collision detection techniques
that are useful in some scenarios. The main idea is to approximate a complex ob
ject using a set of line segments. These line segments are then tested for intersection
with the primitives of the environment. This technique is sometimes used in games
Another approximative method is described in Section 25.5, where a bsP tree rep
resentation of the environment is used, and a cylinder may be used to describe a
charactcr. Howevcr, all objects cannot always bc approximated with linc scgmcnts or
cylinders, and soine applications Inlay require Inore accurate tests
Time-critical collision detection is a technique for doing approximate collision de-
tection in constant time. and is treated in Section 25.6. Then follows sections on
deformable models, continuous CD, collision response, and finally, how to handle par-
ticles. in Section 25.10
It must be pointed out that performance evaluations are difficult in the case of cD
since the algorithms are sensitive to the collision scenarios, and there is no algorithm
that per forIns best in all cases 33. Also, Iote that CD is often perforMed on the CPU
side, but due to the generality of GPUs, all algorithms can be executed on the GPU
s well. In gcncral, algorithms nccd to bc adapted to the particular architccturc's
memory system and feature set in order to maximize performance
To conclude, we present some dynamic intersection tests. Determining whether
two moving objects collide during a given duration adds literally another dimension
to the problem: time. This final section provides common tests for various primitive
combinations and tools for deriving more complex interactions
25.1. Broad Phase Collision Detection
Object transformations
Broad phasc Overlapping objects
collision
Mid phase
Simulation
(object
st
Colliding
arrow
Collision
pl
response
convex parts)
Figure 25.2. A collision dctection systcm that is fcd ob jcct transformations using somc kind of
simulation. All objects in a scene are then processed by broad phase CD in order to quickly find
objects pairs whose bounding volumes overlap. Next, the mid phase cd continues to work on pairs of
objects to find leaves of primitives or convex parts that overlap. Finally, the CD system performs the
lowest level operations in the Ilarrow phase, where onle can compute priImlitive-priInitive intersections
or use distance queries and then feed the result to collision response
25.1 Broad Phase Collision Detection
In this section, we describe several broad phase Cd algorithms. Ilowever, first we
illustrate the broad, mid, and narrow phase of Cd in Figure 25.2, which is a two-
level CD system [16 where the last phase has been split up into a mid and a narrow
hase The target is large-scale environments with multiple objects in motion. The
broad phase of this system reports potential collisions among all the objects in the
environment. Next, the mid phase works on pairs of objects and attempts to
leaves of primitives that potentially overlap or convex parts that overlap, for example
The marrow phase computes prilnlitive-priInlitive intersections or uses distance queries
to make sure that objects do not penetrate each ot her. Finally, collision response
(Section 25. 9) is computed, whose result is fed into a simulation subsystem that can
compute final transforms for each object
Since a scene may contain thousands of moving objects, a good CD system must
handle such situations well. If the scene contains n moving and m static objects, then
a naive method would perform
25
object tests for each frame. The first term corresponds to testing the number of
static objects against the dynamic(moving)objects, and the last term corresponds to
testing the dynamic objects against each other. The naive approach quickly becomes
expensive as /I and T, rise. This situation calls for SIllarter Inethods, which are th
subject this section
25. Collision Detection
The goal of each phase is to minimize the amount of work passed to the subsequent
phase, i. e, we want to minimize pairs of objects, primitives, convex parts, etc, that
are fed to the next phase. At the first phase. testing is done On the object level anld
it is therefore often called broad phase CD
Most algorithms for this phasc start by enclosing cach object in a BV, and then
apply some technique to find all BV/BV pairs that overlap. A simple approach is to
use an a.xis-a. ligned bounding box(AaBB) for each object. To avoid recomputing this
AABB for an object undergoing rigid-body motion, the AABB is adjusted to be a
ficed cube large enough to contain the object in any arbitrary orientation. The fixed
cubes are used to rapidly determine which pairs of objects' bounding volumes are
disjoint. Sometimes it may be better to use dynamically resized AABBs, which are
fast to recompute for oricnted boxes, spheres, and capsules, for cxamplc
Spheres call be used instead of fixed cubes. This is reasonable, since the sphere
is the perfect Bv with which to enclose an object at any orientation. It is also
possible to use the apex map 53(Section 22 13.4). In the following, we describe
three algorithms for broad phase cd, namely, sweep-and-prune, using grids, and using
BVHs. An entirely different method is to use the loose octree structure presented in
ection 19.1.3
25.1.1 Sweep-and-Prune
We assume that each object has an enclosing AABB. In the sweep-and-prune tech
nique 3, 62, 93, temporal coherence, which often is present in typical applications, is
exploited. Temporal coherence mcans that objects undergo rclativcly small (if an
changes in their position and orientation froin fraile to fraile (and so it is also called
frame-to-frame coherence).
Lin 62 points out that the overlapping bounding box problem in three dimensions
can be solved in O(nlog n+k) time(where k is the number of pairwise overlaps), but
it can be improved upon by exploiting coherence and so can be reduced to O(n+k)
However, this assumes that the animation has a fair amount of temporal coherence
If two AABBs overlap, all three one-dimensional intervals(formed by the start and
enld points of AABBs) ill each main axis direction Illust also overlap. Here, we will
describe how all overlaps of a number of one-dimensional intervals can be detected
cfficicntly when the framc-to-framc coherency is high. Givcn that solution, the thrcc
dimensional problem for AABBs is solved by using the one-dimensional algorithm for
each of the three main axes
Assume that n intervals(along a particular axis) are represented by si and ei
where si x ei and 0
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
