计算机图形学：碰撞检测技术详解

需积分: 9 96 浏览量更新于2024-07-17 收藏 51.67MB PDF 举报

本章节探讨的是线性代数与三角学在计算机图形学中的应用，特别是碰撞检测（Collision Detection）这一核心概念。《实时渲染第四版》在线章节25涵盖了碰撞检测的多个关键步骤和技术，这些技术对于虚拟制造、计算机辅助设计/制造（CAD/CAM）、计算机动画以及基于物理的真实感模拟等领域至关重要。首先，25.1节介绍了宽范围碰撞检测（BroadPhaseCollisionDetection），这是碰撞检测的第一阶段，主要用于快速排除大部分不相交的对象对，通过减少候选对的数量，提高整体算法效率。接下来，25.2节深入到中期阶段碰撞检测（MidPhaseCollisionDetection），它涉及到更精确但计算量较大的对象局部接触检查，确保在宽范围筛选后的候选对象之间进行细致的碰撞测试。窄范围碰撞检测（25.3）是关键环节，通过精确的几何形状比较和逼近方法来确定两个物体是否真正发生碰撞。这包括使用射线（25.4）进行碰撞检测，这是一种简化的方法，适用于动态场景中的点到面或点到线的测试。此外，第25.5节讨论了使用BSP树（Binary Space Partitioning Tree）实现动态碰撞检测的高效数据结构，这种数据结构有助于快速定位可能的碰撞区域。时间敏感的碰撞检测（25.6）对实时性能有极高的要求，当游戏或交互式系统需要频繁更新时，如何在保证准确性的前提下优化碰撞检测过程是研究重点。对于可变形模型（25.7），如角色动画或软体物体，处理它们的碰撞则需要考虑形状的变化和实时调整策略。连续碰撞检测（25.8）是一种针对连续运动物体的解决方案，它跟踪并预测物体的运动，以便提前判断未来可能的碰撞。粒子系统（25.10）在游戏和视觉效果中广泛应用，碰撞检测也是粒子行为控制不可或缺的一部分。最后，动态交点测试（25.11）不仅限于碰撞，还包括了碰撞后物体间的物理响应和交互。章节的尾部提供了参考文献（43-45页）和索引（51页），供读者进一步探索相关领域的深入研究。线性代数与三角学在这章中作为强大的工具，支持着计算机图形学中碰撞检测的理论基础和实际操作，其在复杂场景中的优化算法和技术对于现代图形应用的实时性和真实感至关重要。

6 25. Collision Detection

We can create a sorted list of intervals for all three main axes and use the preceding

algorithm to ﬁnd overlapping intervals for each axis. If all three intervals for a pair

overlap, their AABBs (which the intervals represent) also overlap; otherwise, they do

not. The expected time is linear, which results in an O(n + k)-expected-time sweep-

and-prune algorithm, where, again, k is the number of pairwise overlaps. If all an

object pair overlaps on all three axes (i.e., all three booleans are true), then that pair

could be added to a list of colliding pairs for fast access by later stages. This makes

for fast overlap detection of the AABBs. Note that this algorithm can deteriorate to

the worst expected performance for the sorting algorithm, which may be O(n

). This

can happen when clumping occurs. A common example is when a large number of

objects are lying on a ﬂoor. If the z-axis is pointing in the normal direction of the

ﬂoor, we get clumping on the z-axis. One solution would be to skip the z-axis entirely

and only perform the testing on the x- and y-axes [25]. In many cases, this works

well. Liu et al. [63] present a parallel version of SAP, where the sweep direction is

optimized as well. Their algorithm targets the GPU, and there is code online.

25.1.2 Grids

While grids and hierarchical grids are best known as data structures for ray tracing

acceleration, they can also be used for broad phase collision detection [88]. In its

simplest form, a grid is just an n-dimensional array of non-overlapping grid cells that

cover the entire space of the scene. Each cell is therefore a box, where all boxes have

the same size. From a high level, broad phase CD with a grid starts with insertion

of all the objects’ BVs in our scene into the grid. Then, if two objects are associated

with the same grid cell, we immediately know that the BVs of these two objects are

likely to overlap. Hence, we perform a simple BV/BV overlap test, and if they collide,

we can proceed to the second level of the CD system. To the left in Figure 25.4, a

two-dimensional grid with four objects is shown.

To obtain good performance, it is important to choose a reasonable grid cell size.

This problem is illustrated to the right in Figure 25.4. One idea is to ﬁnd the largest

object in the scene, and make the grid cell size large enough to ﬁt that object at all

possible orientations [25]. In this way, all objects will overlap at most eight cells in

the case of a three-dimensional grid.

Storing a large grid can be quite wasteful, especially if signiﬁcant portions of the

grid are left unused. Therefore, it has been suggested that spatial hashing could be

used instead [25, 86, 88]. In general, each grid cell is mapped to an index in a hash

table. All objects overlapping with a grid cell are inserted into the hash table, and

testing can continue as usual. Without spatial hashing, we need to determine the size

of the AABB enclosing the entire scene before memory can be allocated for the grid.

We also must limit where objects can move, so they do not leave these bounds. These

problems are avoided altogether with spatial hashing, as objects can immediately be

inserted into the hash table, no matter where they are located.

25.1. Broad Phase Collision Detection 7

Figure 25.4. Left: a low-resolution two-dimensional grid with four objects. Note that since the ellipse

and the star overlap a shared grid cell, these objects have to be tested using a BV/BV test. In this

case, they do not collide. The triangle and the star also overlap a shared grid cell, and they do in fact

collide. Right: a higher-resolution grid. As can be seen, the star overlaps with many grid cells, which

can make this procedure expensive. Also note that there are many smaller objects where clumping

occurs, and this is another possible source of ineﬃciency.

As illustrated in Figure 25.4, it is not always optimal to use the same grid cell size

in the entire grid. Another option is to use hierarchical grids. In this scheme several

diﬀerent nested grids with diﬀerent cell sizes are used, and an object is inserted in only

the grid where the object’s BV is (just) smaller than the grid cell. If the diﬀerence

in grid cell size between adjacent levels in the hierarchical grid is exactly two, this

structure is quite similar to an octree. There are many details worth knowing about

when implementing grids and hierarchical grids for CD, and we refer to the excellent

treatment of this topic by Ericson [25] and the article by Pouchol et al. [76].

25.1.3 Bounding Volume Hierarchies

Bounding volume hierarchies (BVHs) were described in Section 19.1.1 as a means

to accelerate rendering using view frustum culling. How to build a BVH and how

to perform collision testing using these are described in detail in Section 25.2. The

broad phase can also be implemented using a BVH. Assume objects move every frame

and that an AABB exists for each object in a scene, i.e., each leaf node contains an

AABB and its underlying object. The BVH can be built rapidly using these AABBs.

The maximum number of children is usually adjusted to ﬁt the underlying target

architecture, e.g., using 8 children if the target SIMD width is 8.

After the BVH has been built, it is possible to detect which object pairs overlap,

i.e., which leaf nodes’ AABBs overlap. One method is to hierarchically test each

object’s AABB against the BVH. If the object’s AABB does not overlap a node’s BV

during traversing the BVH, then processing is terminated for that node’s subtree. If

instead there is an overlap, the recursion continues down. To ﬁnd out what D, in

Figure 25.5, overlaps, we start testing at the root, which it will always overlap. It

8 25. Collision Detection

Figure 25.5. In this BVH, consisting of axis-aligned bounding boxes, there are 7 nodes, denoted A

through G. A is the root and D-G are leaves, while B and C are internal nodes. See the text for two

diﬀerent methods to detect which leaf nodes overlap.

does not overlap C, so no further testing is needed in that subtree. Testing continues

in B, which D always overlap since it is a child in B’s subtree. Finally, D is tested

against E, which indicates that D does not overlap with any other object. Next, we

determine if E overlaps any other object. It overlaps A and B since E is in their

subtrees, but it also overlaps C. Traversing down in B, we discover that E does not

overlap anything there. In C, however, we will ﬁnd that E overlaps F but not G.

With this method, we test a leaf node X, and if recursion reaches a leaf node whose

AABB, Y , overlaps with X then the pair (X, Y ) is added to a list of overlapping pairs

of objects. Note that some care has to be taken so that, for example, we do not add

both (E, F ) and (F, E) to the list.

Alternatively, one can make a BVH versus BVH test, where the BVH is tested

against itself and recursion is terminated when two AABBs do not overlap. If a pair

of leaf nodes’ AABBs (corresponding to two diﬀerent objects) are found to overlap,

then this pair is added to a list which is then fed to the next phase. Note that care

has to be taken so that we do not report overlap between an AABB and itself. Using

Figure 25.5, testing starts at the root, and since a node will always overlap itself, we

descend into A and process B and C. B overlaps itself, and we descend into B only

to ﬁnd that D and E do not overlap. We also descend into C, and ﬁnd that F and

G overlap, so (F, G) is added to the list of overlapping pairs. Next, since B and C

overlap, we must test all B’s children against all of C’s children. Here, we ﬁnd that

E and F overlap, and add that pair to the list as well.

An important advantage of approaches using a BVH is that we build only a single

data structure over the objects’ AABBs, and this BVH can then be used for broad

phase CD, view frustum culling, occlusion culling, and ray tracing, for example.

剩余55页未读，继续阅读

qq_30449385

粉丝: 0
资源: 2

计算机图形学：碰撞检测技术详解

Trigonometry.ppt

Trigonometry

labview解方程Linear Algebra

Linear Algebra

numerical linear algebra trefethe pdf

彭国华linear algebra课后习题有答案吗

matrix analysis and applied linear algebra pdf

algebra and trigonometry答案

introduction to linear algebra线性代数pdf

introduction to linear algebra 5th习题解答

最新资源