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
|
---
title: 3D Tifin umbberez
slug: Games/Techniques/3D_collision_detection
translation_of: Games/Techniques/3D_collision_detection
---
<div>{{GamesSidebar}}</div>
<p class="summary">Amagrad agi yettakked tazwart i yal itiknikiyen n wablaɣ n ujemmeq yettwasqedcen iw sedday n tifin umbberez deg tiwenaḍin 3D.imagraden n uḍfaṛ i tuddela usedday deg timkkarḍitin tulmisin 3D.</p>
<h2 id="Tankult_n_ujemmeq_usemsawi_ɣef_tinakatin">Tankult n ujemmeq usemsawi ɣef tinakatin</h2>
<p>Am tifin umbberez 2D,<strong>tinakatin ujemmeq asemsawi n ugellus</strong> (TJSG) d iwarzimen izerben i w-guccel n sin-agi ifendasen n wurar ma yella sembebbin naɣ uhu.ayagi i w-sburu ifendasen n wurar deg yiwet n tanaka ur nezzi.(akka tesemsawi s agellus) u ad tesselken ideggan n tixxamin deg tallunt n imsidag 3D akken ad nẓar ma yella temsembeddint.</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><strong>Tugdda yemsemsawin ɣef tanaka</strong> tella i wakken ad illint timellal.asembebbi gar snat n tinakatin ur nezzi nezmer ad ttwadaddent s isnemhal timeẓliwin daya,maca tinakatin yezzin yessefk-asent timehlin timastayin,ig ẓayen i usiḍen.ma ɣuṛwen ifendasen ara yezzin,tzemrem ad tbeddelem iseggiwen n taɣzut n talast i wakken ad yesegrer yal ass taɣawsa,neɣ ma ulac ad yili ufran nniḍen n tanzeggit n talast,am tabluleɣt (yellan ttimsaritin i tuzzya).yeskanay-d amedya n tuzzya n (TJSG) i yesmezgay afendas yettezzin,tanaka tettbeddil yal ass tisektiwin i wakken ad tesmezgay akken iwata ɣer tanaka yellan degs.</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>Tamawt:</strong> Walit amagrad <a href="https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection/Bounding_volume_collision_detection_with_THREE.js">Bounding Iblaɣen akked Three.js</a> iw akken ateẓṛem asnulfu yellan tallilt n tatiknikit agi.</p>
</div>
<h3 id="Ired_mgal_TJSG">Ired mgal TJSG</h3>
<p>Sefqed ired ma yella deg gensu n TJSG (AABB) ayagi d afrari - neḥwaǧ kan ad nefrari imsidgen n yired yellan deg gensu n TJSG (AABB);get yal agellus s ubrez.anɣil belli Px, Py ad Pz d imsigen n yired BminX-BmaxX,BminY-BmaxY ed BminZ-BmaxZ nutenti id tagrummiwin n yal exist n TJSG (AABB),nezmer ad nesḍen ma yeḍṛa-d umbberez gar sin-agi s useqdec n tsemselt-agi:</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>add</mi><mi></mi><mi></mi><mi>X</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>x</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>afel</mi><mi></mi><mi></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>add</mi><mi></mi><mi></mi><mi>Y</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>y</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>afel</mi><mi></mi><mi></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>add</mi><mi></mi><mi></mi><mi>Z</mi></mrow></msub><mo>∧</mo><msub><mi>P</mi><mi>z</mi></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>afel</mi><mi></mi><mi></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>Anda deg JavaScript:</p>
<pre class="brush: js">Tasɣent d ired deg gensu n TJSB AABB(ired, tanaka) {
Tuɣalin(ired.x >= tanaka.addayX && ired.x <= tanaka.afellayX) &&
(ired.y >= tanaka.addayY && ired.y <= tanaka.afellayY) &&
(ired.z >= tanaka.addayY && ired.z <= tanaka.afellayZ);
}</pre>
<h3 id="AABB_mgal_AABB">AABB mgal AABB</h3>
<p>Sefqed ma yella AABB imyagger AABB nniḍen deg ukayad n yired.Neḥwaǧ kan ad neg akayad i yal agellas , s useqdec n ibuda n tinakatin.ameskan-agi sedaw-a yeskanay-d akayad i nessedday ɣef ugellus n X-adasil,tiseddaṛin <em>A<sub>ddayX</sub></em>–<em>A<sub>fellayX</sub></em> ed <em>B<sub>ddayX</sub></em>–<em>B<sub>fellayX</sub></em> semnenint?</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>S tusnakt atan dacu ara d-yefɣen:<math><semantics><mrow><mi></mi></mrow></semantics></math></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></mi><mrow><mi></mi><mi></mi><mi></mi><mi></mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>fellay</mi><mi>X</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>fellay</mi><mi>X</mi></mrow></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>dday</mi><mi>X</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mrow><mi>dday</mi><mi>Y</mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>fellay</mi><mi>Y</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>fellay</mi><mi>Y</mi></mrow></msub><mo>>=</mo><msub><mi>B</mi><mrow><mi>dday</mi><mi></mi><mi></mi><mi>Y</mi></mrow></msub><mo stretchy="false">)</mo><mo>∧</mo><mo stretchy="false">(</mo><msub><mi>A</mi><mrow><mi>dday</mi><mi>Z</mi></mrow></msub><mo><=</mo><msub><mi>B</mi><mrow><mi>fellay</mi><mi></mi><mi></mi><mi>Z</mi></mrow></msub><mo>∧</mo><msub><mi>A</mi><mrow><mi>fellay</mi><mi></mi><mi></mi><mi>Z</mi></mrow></msub><mo>><sup>=</sup></mo><msub><mi><sup>B</sup></mi><mrow><mi><sup>fellay</sup></mi><mi></mi><mi></mi><mi><sup>Z</sup></mi></mrow></msub><mo stretchy="false"><sup>)</sup></mo></mrow><annotation encoding="TeX"></annotation></semantics></math><sup>f(A,B) =</sup></p>
<p>u deg JavaScript ad neseqdec aya:</p>
<pre class="brush: js"> Tiseɣnatin myaggerent(a, b) {
tuɣalin (a.ddayX <= b.fellayX && a.fellayX >= b.ddayX) &&
(a.ddayY <= b.fellayY && a.fellayY >= b.ddayY) &&
(a.ddayZ <= b.fellayZ && a.fellayZ >= b.ddayZ); </pre>
<h2 id="Bounding_spheres">Bounding spheres</h2>
<p>Using bounding spheres to detect collisions is a bit more complex than AABB, but still fairly quick to test. The main advantage of spheres is that they are invariant to rotation, so if the wrapped entity rotates, the bounding sphere would still be the same. Their main disadvantage is that unless the entity they are wrapping is actually spherical, the wrapping is usually not a good fit (i.e. wrapping a person with a bounding sphere will cause a lot of false positives, whereas a AABB would be a better match).</p>
<h3 id="Point_versus_sphere">Point versus sphere</h3>
<p>To check whether an sphere contains a point we need to calculate the distance between the point and the sphere's center. If this distance is smaller than or equal to the radius of the sphere, the point is inside it.</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>Taking into account that the euclidean distance between two points <em>A</em> and <em>B</em> is <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> , our formula for point versus sphere collision detection would work out like so:</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>Or in 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>The code above features a square root, which can be expensive to calculate. An easy optimization to avoid it consists of squaring the radius, so the optimized equation would instead involve <code>distance < sphere.radius * sphere.radius</code>.</p>
</div>
<h3 id="Sphere_versus_sphere">Sphere versus sphere</h3>
<p>The sphere vs sphere test is similar to the point vs sphere test. What we need to test here is that the distance between the sphere's centers is less than or equal to the sum of their radii.</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>Mathematically, this looks like so:</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>Or in 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="Sphere_versus_AABB">Sphere versus AABB</h3>
<p>Testing whether a sphere and an AABB are colliding is slightly more complicated, but still simple and fast. A logical approach would be to check every vertex of the AABB, doing a point vs sphere test for each one. This is overkill however — testing all the vertices is unnecessary, as we can get away with just calculating the distance between the AABB's <em>closest</em><em> point</em> (not necessarily a vertex) and the sphere's center, seeing if it is less than or equal to the sphere's radius. We can get this value by clamping the sphere's center to the AABB's limits.</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>In JavaScript, we'd do this test like so:</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="Using_a_physics_engine">Using a physics engine</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>
|
