From 953c41b0ec054997cdbc77bf6953187a22d9bd12 Mon Sep 17 00:00:00 2001
From: Matthew Kosarek <mattkae@protonmail.com>
Date: Thu, 24 Jun 2021 09:18:36 -0400
Subject: Updating roadmap, and getting started on SAT collisions
---
2d/_collisions/polygon_polygon.html | 47 ++++++++++++++++++++++++-----
2d/_collisions/polygon_polygon.html.content | 45 +++++++++++++++++++++++----
2d/_collisions/rectangle_line.html | 2 +-
2d/_collisions/rectangle_rectangle.html | 2 +-
4 files changed, 81 insertions(+), 15 deletions(-)
(limited to '2d/_collisions')
diff --git a/2d/_collisions/polygon_polygon.html b/2d/_collisions/polygon_polygon.html
index 23658ce..ce26f62 100644
--- a/2d/_collisions/polygon_polygon.html
+++ b/2d/_collisions/polygon_polygon.html
@@ -26,7 +26,7 @@
<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">Polygon-Polygon</a></li>
+ <li><a title="/2d/_collisions/polygon_polygon.html" href="/2d/_collisions/polygon_polygon.html">Separating Axis Theorem</a></li>
</ul>
</li>
<li>
@@ -67,8 +67,40 @@
</script>
<article>
- <h1>Polygon Intersections</h1>
+ <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>
+ </section>
+ <section>
+ <h2>Explanation of Separating Axis Theorem</h2>
+ <p>
+ SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. The way to think about it is this:
+
+ <br/>
+ <br/>
+
+ Given two shapes <b>A</b> and <b>B</b>.
+
+ Imagine we could isolate a single edge of A and shine a light on it.
+
+
+ </p>
+ </section>
+ <section>
+ <h2>Algorithm for Finding the Intersection</h2>
+ <p>
+ Given two polygons <b>A</b> and <b>B</b>:
+ <ol>
+ <li>For each edge on A, 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.</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>
+ </p>
+
</section>
<section>
<h2>
@@ -83,12 +115,13 @@
Stop
</button>
</div>
- <footer id="references">
- <h2>References</h2>
- <ul>
- </ul>
- </footer>
</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>
diff --git a/2d/_collisions/polygon_polygon.html.content b/2d/_collisions/polygon_polygon.html.content
index 820fcbc..2d6f6b7 100644
--- a/2d/_collisions/polygon_polygon.html.content
+++ b/2d/_collisions/polygon_polygon.html.content
@@ -15,8 +15,40 @@
</script>
<article>
- <h1>Polygon Intersections</h1>
+ <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>
+ </section>
+ <section>
+ <h2>Explanation of Separating Axis Theorem</h2>
+ <p>
+ SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. The way to think about it is this:
+
+ <br/>
+ <br/>
+
+ Given two shapes <b>A</b> and <b>B</b>.
+
+ Imagine we could isolate a single edge of A and shine a light on it.
+
+
+ </p>
+ </section>
+ <section>
+ <h2>Algorithm for Finding the Intersection</h2>
+ <p>
+ Given two polygons <b>A</b> and <b>B</b>:
+ <ol>
+ <li>For each edge on A, 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.</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>
+ </p>
+
</section>
<section>
<h2>
@@ -31,10 +63,11 @@
Stop
</button>
</div>
- <footer id="references">
- <h2>References</h2>
- <ul>
- </ul>
- </footer>
</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>
diff --git a/2d/_collisions/rectangle_line.html b/2d/_collisions/rectangle_line.html
index e36df62..dbaac7c 100644
--- a/2d/_collisions/rectangle_line.html
+++ b/2d/_collisions/rectangle_line.html
@@ -26,7 +26,7 @@
<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">Polygon-Polygon</a></li>
+ <li><a title="/2d/_collisions/polygon_polygon.html" href="/2d/_collisions/polygon_polygon.html">Separating Axis Theorem</a></li>
</ul>
</li>
<li>
diff --git a/2d/_collisions/rectangle_rectangle.html b/2d/_collisions/rectangle_rectangle.html
index 89310ef..fb741fc 100644
--- a/2d/_collisions/rectangle_rectangle.html
+++ b/2d/_collisions/rectangle_rectangle.html
@@ -26,7 +26,7 @@
<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">Polygon-Polygon</a></li>
+ <li><a title="/2d/_collisions/polygon_polygon.html" href="/2d/_collisions/polygon_polygon.html">Separating Axis Theorem</a></li>
</ul>
</li>
<li>
--
cgit v1.2.1