1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
---
title: 3D 碰撞检测
slug: Games/Techniques/3D_collision_detection
translation_of: Games/Techniques/3D_collision_detection
---
<div>{{GamesSidebar}}</div><p class="summary">本文介绍了用于在3D环境中实现不同边界体积碰撞检测的技术。 后续文章将讨论特定3D库中的实现。</p>
<h2 id="Axis-aligned_bounding_boxes（AABB包围盒）">Axis-aligned bounding boxes（<strong>AABB包围盒</strong>）</h2>
<p> </p>
<p>在游戏中，为了简化物体之间的碰撞检测运算，通常会对物体创建一个规则的几何外形将其包围。其中，AABB（axis-aligned bounding box）包围盒被称为轴对齐包围盒。</p>
<p>与2D碰撞检测一样，轴对齐包围盒是判断两个物体是否重叠的最快算法，物体被包裹在一个非旋转的（因此轴对齐的）盒中，并检查这些盒在三维坐标空间中的位置，以确定它们是否重叠。</p>
<p><img alt="" src="https://mdn.mozillademos.org/files/11797/Screen%20Shot%202015-10-16%20at%2015.11.21.png" style="display: block; height: 275px; margin: 0px auto; width: 432px;"></p>
<p>由于性能原因，轴对齐是有一些约束的。两个非旋转的盒子之间是否重叠可以通过逻辑比较进行检查，而旋转的盒子则需要三角运算，这会导致性能下降。如果你有旋转的物体，可以通过修改边框的尺寸，这样盒子仍可以包裹物体，或者选择使用另一种边界几何类型，比如球体(球体旋转，形状不会变)。下图是一个AABB物体旋转，动态调节盒大小适应物体的例子。</p>
<p><img alt="" src="https://mdn.mozillademos.org/files/11799/rotating_knot.gif" style="display: block; height: 192px; margin: 0px auto; width: 207px;"></p>
<div class="note">
<p><strong>Note:</strong> 参考<a href="https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection/Bounding_volume_collision_detection_with_THREE.js">这里</a>，<font><font>使用</font></font><font><font>Three</font></font><font><font>.js进行</font><font>边界体积碰撞检测。</font></font></p>
</div>
<h3 id="点与_AABB">点与 AABB</h3>
<p>如果检测到一个点是否在AABB内部就非常简单了 — 我们只需要检查这个点的坐标是否在AABB内; 分别考虑到每种坐标轴. 如果假设 <em>P<sub>x</sub></em>, <em>P<sub>y</sub> 和</em> <em>P<sub>z</sub></em> 是点的坐标, <em>B<sub>minX</sub></em>–<em>B<sub>maxX</sub></em>, <em>B<sub>minY</sub></em>–<em>B<sub>maxY</sub></em>, 和 <em>B<sub>minZ</sub></em>–<em>B<sub>maxZ</sub></em> 是AABB的每一个坐标轴的范围, 我们可以使用以下公式计算两者之间的碰撞是否发生:</p>
<p><math><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>P</mi><mo>,</mo><mi>B</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><msub><mi>P</mi><mi>x</mi></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>X</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>x</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>X</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>P</mi><mi>y</mi></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Y</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>y</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Y</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>P</mi><mi>z</mi></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Z</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>z</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Z</mi></mrow></msub><mo stretchy="false">)</mo></mrow><annotation encoding="TeX">f(P,B)= (P_x >= B_{minX} \wedge P_x <= B_{maxX}) \wedge (P_y >= B_{minY} \wedge P_y <= B_{maxY}) \wedge (P_z >= B_{minZ} \wedge P_z <= B_{maxZ})</annotation></semantics></math></p>
<p>或者用JavaScript:</p>
<pre class="brush: js">function isPointInsideAABB(point, box) {
return (point.x >= box.minX && point.x <= box.maxX) &&
(point.y >= box.minY && point.y <= box.maxY) &&
(point.z >= box.minY && point.z <= box.maxZ);
}</pre>
<h3 id="AABB_与_AABB">AABB 与 AABB</h3>
<p>检查一个AABB是否和另一个AABB相交类似于检测两个点一样. 我们只需要基于每一条坐标轴并利用盒子的边缘去检测. 下图显示了我们基于 X 轴的检测 — 当然, <em>A<sub>minX</sub></em>–<em>A<sub>maxX</sub></em> 和 <em>B<sub>minX</sub></em>–<em>B<sub>maxX</sub></em> 会不会重叠?</p>
<p><img alt="updated version" src="https://mdn.mozillademos.org/files/11813/aabb_test.png" style="display: block; height: 346px; margin: 0px auto; width: 461px;"></p>
<p>在数学上的表示就像这样:</p>
<p><math><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>A</mi><mo>,</mo><mi>B</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>X</mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>X</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>X</mi></mrow></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>X</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Y</mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Y</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Y</mi></mrow></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Y</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Z</mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Z</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>Z</mi></mrow></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mi>Z</mi></mrow></msub><mo stretchy="false">)</mo></mrow><annotation encoding="TeX">f(A,B) =</annotation></semantics></math></p>
<p>在JavaScript我们可以这样:</p>
<pre class="brush: js">function intersect(a, b) {
return (a.minX <= b.maxX && a.maxX >= b.minX) &&
(a.minY <= b.maxY && a.maxY >= b.minY) &&
(a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}
</pre>
<h2 id="球体碰撞">球体碰撞</h2>
<p>球体碰撞边缘检测比AABB盒子稍微复杂一点,但他的检测仍相当容易的。球体的主要优势是他们不变的旋转，如果包装实体旋转，边界领域仍将是相同的。他们的主要缺点是,除非他们包装的实体实际上是球形,包装的实体通常不是一个完美的球形(比如用这样的球形包装一个人将导致一些错误,而AABB盒子将更合适)。</p>
<h3 id="点与球">点与球</h3>
<p>检查是否一个球体包含一个点，我们需要计算点和球体的中心之间的距离。如果这个距离小于或等于球的半径,这个点就在里面。</p>
<p><img alt="" src="https://mdn.mozillademos.org/files/11803/point_vs_sphere.png" style="display: block; height: 262px; margin: 0px auto; width: 385px;"></p>
<p>两个点A和B之间的欧氏距离是<br>
<math><semantics><msqrt><mrow><mo stretchy="false">(</mo><msub><mi>A</mi><mi>x</mi></msub><mo>-</mo><msub><mi>B</mi><mi>x</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo stretchy="false">)</mo><mo>+</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mi>y</mi></msub><mo>-</mo><msub><mi>B</mi><mi>y</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mi>z</mi></msub><mo>-</mo><msub><mi>B</mi><mi>z</mi></msub><mo stretchy="false">)</mo></mrow></msqrt><annotation encoding="TeX">\sqrt{(A_x - B_x) ^ 2) + (A_y - B_y)^2 + (A_z - B_z)}</annotation></semantics></math> ,我们的公式指出，球体碰撞检测是:</p>
<p><math><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>P</mi><mo>,</mo><mi>S</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mi>S</mi><mrow><mi>r</mi><mi>a</mi><mi>d</mi><mi>i</mi><mi>u</mi><mi>s</mi></mrow></msub><mo>>=</mo><msqrt><mrow><mo stretchy="false">(</mo><msub><mi>P</mi><mi>x</mi></msub><mo>-</mo><msub><mi>S</mi><mi>x</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>P</mi><mi>y</mi></msub><mo>-</mo><msub><mi>S</mi><mi>y</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>P</mi><mi>z</mi></msub><mo>-</mo><msub><mi>S</mi><mi>z</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow></msqrt></mrow><annotation encoding="TeX">f(P,S) = S_{radius} >= \sqrt{(P_x - S_x)^2 + (P_y - S_y)^2 + (P_z - S_z)^2}</annotation></semantics></math></p>
<p>或者用JavaScript:</p>
<pre class="brush: js">function isPointInsideSphere(point, sphere) {
// we are using multiplications because is faster than calling Math.pow
var distance = Math.sqrt((point.x - sphere.x) * (point.x - sphere.x) +
(point.y - sphere.y) * (point.y - sphere.y) +
(point.z - sphere.z) * (point.z - sphere.z));
return distance < sphere.radius;
}
</pre>
<div class="note">
<p>上面的代码有一个平方根,是一个开销昂贵的计算。一个简单的优化,以避免它由半径平方,所以优化方程不涉及<code>distance < sphere.radius * sphere.radius</code>.</p>
</div>
<h3 id="球体与球体">球体与球体</h3>
<p>球体与球体的距离类似于点和球体。我们需要测试是球体的中心之间的距离小于或等于半径的总和。</p>
<p><img alt="" src="https://mdn.mozillademos.org/files/11805/sphere_vs_sphere.png" style="display: block; height: 262px; margin: 0px auto; width: 414px;"></p>
<p>在数学上,像这样:</p>
<p><math><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>A</mi><mo>,</mo><mi>B</mi><mo stretchy="false">)</mo><mo>=</mo><msqrt><mrow><mo stretchy="false">(</mo><msub><mi>A</mi><mi>x</mi></msub><mo>-</mo><msub><mi>B</mi><mi>x</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mi>y</mi></msub><mo>-</mo><msub><mi>B</mi><mi>y</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mi>z</mi></msub><mo>-</mo><msub><mi>B</mi><mi>z</mi></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow></msqrt><mo><=</mo><msub><mi>A</mi><mrow><mi>r</mi><mi>a</mi><mi>d</mi><mi>i</mi><mi>u</mi><mi>s</mi></mrow></msub><mo>+</mo><msub><mi>B</mi><mrow><mi>r</mi><mi>a</mi><mi>d</mi><mi>i</mi><mi>u</mi><mi>s</mi></mrow></msub></mrow><annotation encoding="TeX">f(A,B) = \sqrt{(A_x - B_x)^2 + (A_y - B_y)^2 + (A_z - B_z)^2} <= A_{radius} + B_{radius}</annotation></semantics></math></p>
<p>或者JavaScript:</p>
<pre class="brush: js">function intersect(sphere, other) {
// we are using multiplications because it's faster than calling Math.pow
var distance = Math.sqrt((sphere.x - other.x) * (sphere.x - other.x) +
(sphere.y - other.y) * (sphere.y - other.y) +
(sphere.z - other.z) * (sphere.z - other.z));
return distance < (sphere.radius + other.radius); }
}</pre>
<h3 id="球体与AABB">球体与AABB</h3>
<p>测试一个球和一个AABB的碰撞是稍微复杂,但过程仍然简单和快速。一个合乎逻辑的方法是，检查AABB每个顶点,计算每一个点与球的距离。然而这是大材小用了,测试所有的顶点都是不必要的,因为我们可以侥幸计算AABB最近的点(不一定是一个顶点)和球体的中心之间的距离,看看它是小于或等于球体的半径。我们可以通过逼近球体的中心和AABB的距离得到这个值。</p>
<p><img alt="" src="https://mdn.mozillademos.org/files/11837/sphere_vs_aabb.png" style="display: block; height: 282px; margin: 0px auto; width: 377px;"></p>
<p>在 JavaScript, 我们可以像这样子做:</p>
<pre class="brush: js">function intersect(sphere, box) {
// get box closest point to sphere center by clamping
var x = Math.max(box.minX, Math.min(sphere.x, box.maxX));
var y = Math.max(box.minY, Math.min(sphere.y, box.maxY));
var z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ));
// this is the same as isPointInsideSphere
var distance = Math.sqrt((x - sphere.x) * (x - sphere.x) +
(y - sphere.y) * (y - sphere.y) +
(z - sphere.z) * (z - sphere.z));
return distance < sphere.radius;
}
</pre>
<h2 id="使用一个物理引擎">使用一个物理引擎</h2>
<p><strong>3D physics engines</strong> provide collision detection algorithms, most of them based on bounding volumes as well. The way a physics engine works is by creating a <strong>physical body</strong>, usually attached to a visual representation of it. This body has properties such as velocity, position, rotation, torque, etc., and also a <strong>physical shape</strong>. This shape is the one that is considered in the collision detection calculations.</p>
<p>We have prepared a <a href="http://mozdevs.github.io/gamedev-js-3d-aabb/physics.html">live collision detection demo</a> (with <a href="https://github.com/mozdevs/gamedev-js-3d-aabb">source code</a>) that you can take a look at to see such techniques in action — this uses the open-source 3D physics engine <a href="https://github.com/schteppe/cannon.js">cannon.js</a>.</p>
<h2 id="See_also">See also</h2>
<p>Related articles on MDN:</p>
<ul>
<li><a href="https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection/Bounding_volume_collision_detection_with_THREE.js">Bounding volumes collision detection with Three.js</a></li>
<li><a href="/en-US/docs/Games/Techniques/2D_collision_detection">2D collision detection</a></li>
</ul>
<p>External resources:</p>
<ul>
<li><a href="http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php">Simple intersection tests for games</a> on Gamasutra</li>
<li><a href="https://en.wikipedia.org/wiki/Bounding_volume">Bounding volume</a> on Wikipedia</li>
</ul>
|
