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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<link rel="stylesheet" href="/index.css">
<title>Physics for Games</title>
<link rel="shortcut icon" href="/favicon/favicon.ico" type="image/x-icon">
<meta name="description" content="A place to learn all about real-time physics simulations through descriptions, code snippets, and example programs all written in C++ and OpenGL.">
<meta name="og:description" content="A place to learn all about real-time physics simulations through descriptions, code snippets, and example programs all written in C++ and OpenGL.">
</head>
<body>
<header>
<h1><a title="physicsforgames.com" href="/">Physics for Games</a></h1>
</header>
<main>
<nav>
<ul class="outer-tree">
<li><a href="/">Introduction</a></li>
<li>
<span>🏀<span>2D</span></span>
<ul class="inner-tree">
<li><label>Rigidbody</label></li>
<li><a title="/2d/rigidbody/rigidbody_1.html" href="/2d/rigidbody/rigidbody_1.html">Linear Forces</a></li>
<li><a title="/2d/rigidbody/rigidbody_2.html" href="/2d/rigidbody/rigidbody_2.html">Rotational Forces</a></li>
<li><a title="/2d/rigidbody/rigidbody_3.html" href="/2d/rigidbody/rigidbody_3.html">Collisions</a></li>
<li><label>Collisions</label></li>
<li><a title="/2d/_collisions/rectangle_line.html" href="/2d/_collisions/rectangle_line.html">Rectangle-Line</a></li>
<li><a title="/2d/_collisions/rectangle_rectangle.html" href="/2d/_collisions/rectangle_rectangle.html">Rectangle-Rectangle</a></li>
<li><a title="/2d/_collisions/polygon_polygon.html" href="/2d/_collisions/polygon_polygon.html">Separating Axis Theorem</a></li>
</ul>
</li>
<li>
<span>🌠<span>3D</span></span>
<ul class="inner-tree">
<li><label>Rigidbody</label></li>
<li><a title="/3d/rigidbody.html" href="/3d/rigidbody.html">Rigidbody in 3D</a></li>
</ul>
</li>
<li>
<span>🔧<span>WebAssembly</span></span>
<ul class="inner-tree">
<li><a title="/intro/intro.html" href="/intro/intro.html">Introduction</a></li>
</ul>
</li>
<li>
<span>🛈<span>About</span></span>
<ul class="inner-tree">
<li><a title="/roadmap.html" href="/roadmap.html">Roadmap</a></li>
</ul>
</li>
</ul>
</nav>
<script src="./polygon_polygon/dist/output.js"></script>
<script>
window.onload = function() {
var lPlayElement = document.getElementById('gl_canvas_play'),
lStopElement = document.getElementById('gl_canvas_stop');
lPlayElement.addEventListener('click', function() {
lPlayElement.style.display = 'none';
lStopElement.style.display = 'block';
});
lStopElement.addEventListener('click', function() {
lStopElement.style.display = 'none';
lPlayElement.style.display = 'block';
});
}
</script>
<article>
<h1>Separating Axis Theorem</h1>
<section>
<p>
The Separating Axis Theorem (SAT) provides a way to find the intersection between any <i>n</i>-sided <a href='https://ianqvist.blogspot.com/2009/09/convex-polygon-based-collision.html'>convex</a> polygon or circle. In this tutorial, I will explain how this theorem works, and how you can use it to both detect and resolve collisions in your simulation.
</p>
<ul>
<li><a href='#explanation_of_separating_axis_theorem'>Explanation of Separating Axis Theorem</a></li>
<li><a href='#algorithm_for_finding_intersection'>Algorithm for Finding the Intersection</a></li>
<li><a href='#collision_resolution'>SAT Collision Resolution</a></li>
<ul>
<li><a href='#intersecting_edge'>Finding the Intersecting Edge</a></li>
<li><a href='#intersecting_point'>Finding the Intersecting Point</a></li>
</ul>
<li><a href='#algorithm_for_collision_resolution'>Algorithm for Collision Resolution</a></li>
<li><a href='#live_example'>Live Example</a></li>
</ul>
</section>
<section>
<h2 id="#explanation_of_separating_axis_theorem">Explanation of Separating Axis Theorem</h2>
<p>
SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. I believe the best way to describe it is to show you the instance where two polygons do <b>not</b> intersect.
<br/>
<br/>
Images two shapes <b>A</b> and <b>B</b> as shown below (they are triangles here, but they can be anything really).
<br/>
<br />
<div class='image'>
<img src="polygon_polygon/images/1.png" />
</div>
<br/>
We know inutitively that if we were able to draw a line between the two objects, that means that they're not intersecting. In this case, that line is a vertical-ish line:
<br/>
<br />
<div class='image'>
<img src='polygon_polygon/images/2.png' />
</div>
<br/>
That line could be any of the infinite number of lines between the objects, so we can't really select that <i>exact</i> line. So the problem becomes: how do we <i>infer</i> that the vertical line shown in the previous diagram is a line that splits the objects? That is where the Separating Axis Theorem comes in.
<br />
<br/>
To do separating axis theorem, we iterate all of the edges of <b>both</b> shapes. For each edge, we get the normal at that edge (In two-dimensions, this amounts to getting the perpendicular of the line segment defined by the two points of the edge).
<br />
<br />
<div class='image'>
<img src='polygon_polygon/images/2a.png' />
</div>
<br />
We then, in our heads, extend this normal to create an axis across our scene (keep in mind that you won't have to do any "extending" of this axis in code; the normal will do just fine).
<div class='image'>
<img src='polygon_polygon/images/2d.png' />
</div>
<br />
At this point, you will see that I named the three vertices on each of the triangles. Triangle <b>A</b> is made of vertices <i>a1, a2, a3</i> and triangle <b>B</b> is made of vertices <i>b1, b2, b3</i>. At this point, we project the shape onto the axis. To do this, we project the vertices of each shape onto the axis to figure out which one <i>maximizes</i> the dot product and which one <i>minimizes</i> the dot product. The projection of the shape is then the range defined by this min and max value.
<br />
<br />
<div class='image'>
<img src='polygon_polygon/images/2e.png' />
</div>
<br />
Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do <b>not</b> intersect. If they do overlap, we repeat the process for all of the other edges. If all of these ranges overlap, then the shape overlaps, and there is no separating line between them.
<br />
<br />
<div class='image'>
<img src='polygon_polygon/images/2f.png' />
</div>
<br />
</p>
</section>
<section>
<h2 id='algorithm_for_finding_intersection'>Algorithm for Finding the Intersection</h2>
<p>
Given two polygons <b>A</b> and <b>B</b>:
<ol>
<li>For each edge on <b>A</b>, get the normal <i>n</i> of that edge.</li>
<li>Project each vertex <i>v</i> of <b>A</b> onto <i>n</i>. Return the minimum and maximum projection of all vertices as the projection of the shape.</li>
<li>Repeat Step 2 for polygon <b>B</b>.</li>
<li>If the min and max projections found in Steps 2 and 3 do <b>NOT</b> overlap, the polygons are not intersecting. Return false.</li>
<li>If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.</li>
</ol>
And that is all there is to <i>finding</i> the intersection between two convex polygons. Here is the code snippet that does this if you are interested:
<pre><code><span class="code_keyword">Vector2</span> getProjection(Vector2* vertices, <span class="code_keyword">int</span> numVertices, <span class="code_keyword">Vector2</span> axis) {
<span class="code_comment">// Find the min and max vertex projections</span>
<span class="code_keyword">float32</span> min = axis.dot(vertices[0]);
<span class="code_keyword">float32</span> max = min;
for (int v = 1; v < numVertices; v++) {
<span class="code_keyword">float32</span> d = axis.dot(vertices[v]);
if (d < min) {
min = d;
} else if (d > max) {
max = d;
}
}
<span class="code_keyword">return</span> <span class="code_keyword">Vector2</span> { min, max };
}
<span class="code_keyword">bool</span> projectionsOverlap(Vector2 first, <span class="code_keyword">Vector2</span> second) {
<span class="code_keyword">return</span> first.x <= second.y && second.x <= first.y;
}
<span class="code_keyword">bool</span> doIntersect(ConvexPolygon* first, ConvexPolygon* second) {
IntersectionResult ir;
<span class="code_comment">// Check agaisnt the edges of the first polygon</span>
for (int i = 0; i < first->numVertices; i++) {
<span class="code_keyword">Vector2</span> normal = first->edges[i].normal;
<span class="code_keyword">Vector2</span> firstProj = getProjection(first->transformedVertices, first->numVertices, normal);
<span class="code_keyword">Vector2</span> secondProj = getProjection(second->transformedVertices, second->numVertices, normal);
if (!projectionsOverlap(firstProj, secondProj)) {
<span class="code_keyword">return</span> false;
}
}
<span class="code_comment">// Check against the edges of the second polygon</span>
for (int i = 0; i < second->numVertices; i++) {
<span class="code_keyword">Vector2</span> normal = second->edges[i].normal;
<span class="code_keyword">Vector2</span> firstProj = getProjection(first->transformedVertices, first->numVertices, normal);
<span class="code_keyword">Vector2</span> secondProj = getProjection(second->transformedVertices, second->numVertices, normal);
if (!projectionsOverlap(firstProj, secondProj)) {
<span class="code_keyword">return</span> false;
}
}
<span class="code_keyword">return</span> true;
}
</code></pre> </p>
</section>
<section>
<h2 id='collision_resolution'>SAT Collision Resolution</h2>
<p>
Now that we know that our objects have intersected, we want to send them tumbling away from one another in order to simulate a collision. To do this, we will need to find the following things:
<ul>
<li><b>Point of Application</b>: at what point on each object did the objects first intersect</li>
<li><b>Collision Normal</b>: in what direction, point towards object <b>A</b>, did the polygons intersect</li>
<li><b>Relative Velocity</b>: easily found by taking the difference between the two velocities.
</ul>
<h3 id='intersecting_edge'>Finding the Intersecting Edge</h3>
We can already figure out that the following two triangles intersect one another:
<br />
<br />
<div class='image'>
<img src='polygon_polygon/images/3a.png' />
</div>
<br/><br/>
We know that <b>A</b> can only intersect <b>B</b> if: (1) a vertex from <b>A</b> is inside of <b>B</b>, (2) an edge of <b>A</b> flatly intersects an edge of <b>B</b>, or (3) a vertex of <b>A</b> overlaps exactly a vertex of <b>B</b>. For our purposes, scenario 3 is quite unlikely, so we can ignore it for now. We will start with the first case, since it is the most likely.
<br /> <br />
The following drawing shows both of our objects projected onto the axis defined by object <b>B</b>'s leftmost edge:
<br /> <br />
<div class='image'>
<img src='polygon_polygon/images/3c.png' />
</div>
<br/><br/>
If you were to repeat this exercise of projecting the shapes onto every axis of both shapes, you will begin to unconver an interesting truth: <i>The intersecting edge will be the one where the projection of triangle <b>A</b> overlaps with the projection of triangle <b>B</b> the <b>least</b></i>! This should be unsurprising if you consider it. If our simulation is running quickly enough, the point of object <b>A</b> that is penetrating the edge of object <b>B</b> will just <i>barely</i> be inside of <b>B</b>. At the same time, it <i>should</i> be the only point that is currently inside of B. Hence, the overlap of the projection on that axis will be from that edge of <b>B</b> to that point on <b>A</b>. Knowing that this edge caused the intersection, we now have the collision normal.
<br />
<h3 id='intersecting_point'>Finding which point causes the intersection</h3>
This part is made easy by the fact that we know which edge of object <b>B</b> caused the intersection in the first place. We know, then, that the intersecting point on object <b>A</b> must be the point that is currently inside of <b>B</b>. Simply put, this point will be the vertex of <b>A</b> that was projected onto that axis that is <i>closest</i> to the edge of <b>B</b>. This will be true so long as the simulation is properly fast and the object is not infinitesmley small (in which case, we're dealing with particle physics, and you shouldn't be using this tutorial).
</p>
</section>
<section>
<h2 id='algorithm_for_collision_resolution'>Algorithm for Collision Resolution</h2>
<p>
Given two polygons <b>A</b> and <b>B</b>:
<ol>
<li>Find the intersecton as before</li>
<li>While finding the intersection, keep track of the axis that the projection on object <b>A</b> overlapped with the corresponding projection on object <b>B</b> the least. Remember the edge that this that held this axis.</li>
<li>Using this axis, find out which point on the other object inside of the edge by comparing the distances from the two points on the edge to the two points projected onto the axis created by that edge.</li>
<li>Use the calcualted edge to find the normal and the overlap point to find the point of application.</li>
</ol>
And that is it! Here is the code for this algorithm:
<pre><code><span class="code_keyword">struct</span> IntersectionResult {
<span class="code_keyword">bool</span> intersect = false;
<span class="code_keyword">Vector2</span> collisionNormal;
<span class="code_keyword">Vector2</span> relativeVelocity;
<span class="code_keyword">Vector2</span> firstPointOfApplication;
<span class="code_keyword">Vector2</span> secondPointOfApplication;
};
<span class="code_keyword">struct</span> Edge {
<span class="code_keyword">Vector2</span> normal;
<span class="code_keyword">Vector2</span> start;
<span class="code_keyword">Vector2</span> end;
};
<span class="code_keyword">struct</span> SATResult {
Edge* minOverlapEdge = NULL; <span class="code_comment">// Edge that caused the intersection (on the 'first' shape)</span>
<span class="code_keyword">Vector2</span> overlapPoint; <span class="code_comment">// Point that caused the intersection (on the 'second' shape)</span>
<span class="code_keyword">float32</span> minOverlap = FLT_MAX; <span class="code_comment">// Smallest projection overlap</span>
};
<span class="code_keyword">struct</span> ProjectionResult {
<span class="code_keyword">Vector2</span> minVertex;
<span class="code_keyword">Vector2</span> maxVertex;
<span class="code_keyword">Vector2</span> projection;
};
<span class="code_comment">// Given the vertices in the shape, we find the min and max vertices that project</span>
<span class="code_comment">// onto the axis. We also save which vertices were which so that we can resolve</span>
<span class="code_comment">// the collision later.</span>
ProjectionResult getProjection(Vector2* vertices, <span class="code_keyword">int</span> numVertices, <span class="code_keyword">Vector2</span> axis) {
ProjectionResult pr;
<span class="code_keyword">float32</span> min = axis.dot(vertices[0]);
<span class="code_keyword">float32</span> max = min;
for (int v = 1; v < numVertices; v++) {
<span class="code_keyword">float32</span> d = axis.dot(vertices[v]);
if (d < min) {
pr.minVertex = vertices[v];
min = d;
} else if (d > max) {
pr.maxVertex = vertices[v];
max = d;
}
}
pr.projection = <span class="code_keyword">Vector2</span> { min, max };
<span class="code_keyword">return</span> pr;
}
<span class="code_keyword">bool</span> projectionsOverlap(Vector2 first, <span class="code_keyword">Vector2</span> second) {
<span class="code_keyword">return</span> first.x <= second.y && second.x <= first.y;
}
<span class="code_keyword">float32</span> getProjectionOverlap(Vector2 first, <span class="code_keyword">Vector2</span> second) {
<span class="code_keyword">float32</span> e = MIN(first.y, second.y);
<span class="code_keyword">float32</span> f = MAX(first.x, second.x);
<span class="code_keyword">return</span> e - f;
}
<span class="code_keyword">bool</span> runSatForShapesEdges(SATResult* result, ConvexPolygon* first, ConvexPolygon* second) {
for (int i = 0; i < first->numVertices; i++) {
<span class="code_keyword">Vector2</span> normal = first->edges[i].normal;
ProjectionResult firstProj = getProjection(first->transformedVertices, first->numVertices, normal);
ProjectionResult secondProj = getProjection(second->transformedVertices, second->numVertices, normal);
if (!projectionsOverlap(firstProj.projection, secondProj.projection)) {
<span class="code_keyword">return</span> false;
}
<span class="code_keyword">float32</span> overlap = getProjectionOverlap(firstProj.projection, secondProj.projection);
if (overlap < result->minOverlap) {
result->minOverlap = overlap;
result->minOverlapEdge = &first->edges[i];
<span class="code_comment">// The overlapPoint will be the point on the other shape that penetrated the edge.</span>
<span class="code_comment">// If we caught the intersection reasonably early, it should be the point on 'second'</span>
<span class="code_comment">// that is nearest to the points on 'first'.</span>
<span class="code_keyword">float32</span> min1min2 = (firstProj.minVertex - secondProj.minVertex).length();
<span class="code_keyword">float32</span> min1max2 = (firstProj.minVertex - secondProj.maxVertex).length();
<span class="code_keyword">float32</span> max1max2 = (firstProj.maxVertex - secondProj.maxVertex).length();
<span class="code_keyword">float32</span> max1min2 = (firstProj.maxVertex - secondProj.minVertex).length();
<span class="code_keyword">float32</span> closest = MIN(min1min2, MIN(min1max2, MIN(max1max2, max1min2)));
if (closest == min1min2 || closest == max1min2) {
result->overlapPoint = secondProj.minVertex;
} else {
result->overlapPoint = secondProj.maxVertex;
}
}
}
<span class="code_keyword">return</span> true;
}
<span class="code_keyword">const</span> <span class="code_keyword">float32</span> EPSILON = 1.f;
IntersectionResult getIntersection(ConvexPolygon* first, ConvexPolygon* second) {
IntersectionResult ir;
SATResult sat;
if (!runSatForShapesEdges(&sat, first, second)) {
<span class="code_keyword">return</span> ir;
}
if (!runSatForShapesEdges(&sat, second, first)) {
<span class="code_keyword">return</span> ir;
}
ir.intersect = true;
ir.relativeVelocity = first->body.velocity - second->body.velocity;
ir.collisionNormal = sat.minOverlapEdge->normal;
ir.firstPointOfApplication = sat.overlapPoint - first->body.position;
ir.secondPointOfApplication = sat.overlapPoint - second->body.position;;
<span class="code_keyword">return</span> ir;
}
</code></pre> </p>
</section>
<section>
<h2 id='live_example'>
Live Example of Intersection Detection
</h2>
<div class="opengl_canvas_container">
<canvas id="gl_canvas" width="800" height="600"></canvas>
<button id="gl_canvas_play" class="play_button">
Play
</button>
<button id="gl_canvas_stop" class="stop_button">
Stop
</button>
</div>
</section>
<footer id="references">
<h2>References</h2>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Vector_projection">Vector Projection Wikapedia</a></li>
</ul>
</footer>
</article>
</main>
</body>
</html>
|
