diff options
Diffstat (limited to '2d')
| -rw-r--r-- | 2d/_collisions/polygon_polygon.html | 47 | ||||
| -rw-r--r-- | 2d/_collisions/polygon_polygon.html.content | 45 | ||||
| -rw-r--r-- | 2d/_collisions/rectangle_line.html | 2 | ||||
| -rw-r--r-- | 2d/_collisions/rectangle_rectangle.html | 2 | ||||
| -rw-r--r-- | 2d/rigidbody/rigidbody_1.html | 2 | ||||
| -rw-r--r-- | 2d/rigidbody/rigidbody_2.html | 2 | ||||
| -rw-r--r-- | 2d/rigidbody/rigidbody_3.html | 2 |
7 files changed, 84 insertions, 18 deletions
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> diff --git a/2d/rigidbody/rigidbody_1.html b/2d/rigidbody/rigidbody_1.html index b02d2ef..00ea74a 100644 --- a/2d/rigidbody/rigidbody_1.html +++ b/2d/rigidbody/rigidbody_1.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/rigidbody/rigidbody_2.html b/2d/rigidbody/rigidbody_2.html index e716374..4d85e50 100644 --- a/2d/rigidbody/rigidbody_2.html +++ b/2d/rigidbody/rigidbody_2.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/rigidbody/rigidbody_3.html b/2d/rigidbody/rigidbody_3.html index c2c78ff..9cb1041 100644 --- a/2d/rigidbody/rigidbody_3.html +++ b/2d/rigidbody/rigidbody_3.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> |