实时渲染第四版-深入探讨碰撞检测

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

"《Real-time Rendering》第四版的在线章节：碰撞检测，涵盖了从广义阶段到细粒度阶段的碰撞检测技术，包括动态CD、变形模型、连续碰撞检测和碰撞响应等内容。" 《Real-time Rendering》是3D渲染领域的权威著作，其第四版深入探讨了实时渲染的各个方面。其中，碰撞检测这一章节详细阐述了在实时图形应用中如何高效准确地处理物体间的碰撞问题。碰撞检测在虚拟制造、CAD/CAM、计算机动画以及物理基础的模拟等领域有着至关重要的作用。 1. 广义阶段碰撞检测（Broad-Phase Collision Detection）：这是碰撞检测的第一步，目的是快速筛选出可能有碰撞的物体对，减少后续计算的复杂度。常见的方法有空间划分结构，如AABB（轴对齐边界盒）树、OBB（oriented bounding box）树、 octrees 和细胞自动机等。 2. 中间阶段碰撞检测（Mid-Phase Collision Detection）：在广义阶段筛选出的物体对之间进行更精确的测试，以确定它们是否真的发生碰撞。通常涉及到几何体的近似表示，如多边形网格、凸包、简化模型等，并使用分离轴定理或距离场等技术进行检测。 3. 细粒度阶段碰撞检测（Narrow-Phase Collision Detection）：对于已经确认可能相交的物体对，这一阶段会执行最精确的检测，以找出接触点或接触面。这通常包括使用支持向量、 penetration depth 计算和接触点生成等算法。 4. 射线与碰撞检测（Collision Detection with Rays）：在游戏和可视化中，射线碰撞检测非常常见，例如视线检测、光照计算等。这个过程涉及发射射线并检测它们与场景中的物体的交点。 5. 动态CD使用BSP树（Dynamic CD Using BSP Trees）： BSP树是一种用于加速碰撞检测的数据结构，特别适合动态场景中物体的碰撞处理。通过不断分割空间，可以快速定位移动物体的碰撞可能性。 6. 时间关键的碰撞检测（Time-Critical Collision Detection）：在实时环境中，必须在严格的时间限制内完成碰撞检测。这可能需要优化算法，如预测物体未来的位置，或者采用增量更新策略。 7. 变形模型的碰撞检测（Deformable Models）：处理可变形物体的碰撞更为复杂，因为形状会随时间变化。这可能需要连续的碰撞检测方法，如基于弹簧的模型或刚柔耦合的模拟。 8. 连续碰撞检测（Continuous Collision Detection）：与离散碰撞检测不同，连续碰撞检测考虑物体在整个运动期间的碰撞，而不是只检查特定时刻。这对于避免穿透现象和确保物理真实感至关重要。 9. 碰撞响应（Collision Response）：检测到碰撞后，需要计算适当的响应，如反弹力、摩擦力等，以保持物理系统的稳定。这包括动量守恒、能量损失和接触力的计算。 10. 粒子系统碰撞（Particles）：在粒子系统中，大量小粒子的碰撞处理需要高效的算法，如格栅法或基于代理的碰撞检测。 11. 动态交集测试（Dynamic Intersection Testing）：针对运动物体之间的交集测试，可能需要实时更新的交集数据结构，如kd-trees 或者使用启发式方法提高效率。《Real-time Rendering》第四版的碰撞检测章节详细解析了实时环境下处理碰撞的各种技术和策略，为开发者提供了宝贵的理论和实践指导。

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页未读，继续阅读

LovePurple

粉丝: 12
资源: 43

实时渲染第四版-深入探讨碰撞检测

Real Time Rending 4th 最新第四版（高清）Part1

Real-Time Rendering, Fourth Edition PDF

Real-Time Rendering 4th Edition高清全彩版

Real-time Rendering 第四版-线性代数部分

Real-Time Rendering（英文版）

Real-Time Rendering --- Word版

Real-Time Rendering

real-time rendering

Real-time rendering, 英文第4版

Real-time Rendering 实时渲染清晰版

最新资源