From 953c41b0ec054997cdbc77bf6953187a22d9bd12 Mon Sep 17 00:00:00 2001 From: Matthew Kosarek 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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • @@ -67,8 +67,40 @@
    -

    Polygon Intersections

    +

    Separating Axis Theorem

    +

    + The Separating Axis Theorem (SAT) provides a way to find the intersection between any n-sided convex 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. +

    +
    +
    +

    Explanation of Separating Axis Theorem

    +

    + 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: + +
    +
    + + Given two shapes A and B. + + Imagine we could isolate a single edge of A and shine a light on it. + + +

    +
    +
    +

    Algorithm for Finding the Intersection

    +

    + Given two polygons A and B: +

      +
    1. For each edge on A, get the normal n of that edge.
      2. +
    2. Project each vertex v of A onto n. Return the minimum and maximum projection of all vertices.
      3. +
    3. Repeat Step 2 for polygon B.
      4. +
    4. If the min and max projections found in Steps 2 and 3 do NOT overlap, the polygons are not intersecting. Return false.
      5. +
    5. If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.
      6. +
    +

    +

    @@ -83,12 +115,13 @@ Stop -
    -

    References

    -
      -
    -

    +
    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 @@
    -

    Polygon Intersections

    +

    Separating Axis Theorem

    +

    + The Separating Axis Theorem (SAT) provides a way to find the intersection between any n-sided convex 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. +

    +
    +
    +

    Explanation of Separating Axis Theorem

    +

    + 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: + +
    +
    + + Given two shapes A and B. + + Imagine we could isolate a single edge of A and shine a light on it. + + +

    +
    +
    +

    Algorithm for Finding the Intersection

    +

    + Given two polygons A and B: +

      +
    1. For each edge on A, get the normal n of that edge.
      2. +
    2. Project each vertex v of A onto n. Return the minimum and maximum projection of all vertices.
      3. +
    3. Repeat Step 2 for polygon B.
      4. +
    4. If the min and max projections found in Steps 2 and 3 do NOT overlap, the polygons are not intersecting. Return false.
      5. +
    5. If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.
      6. +
    +

    +

    @@ -31,10 +63,11 @@ Stop -
    -

    References

    -
      -
    -

    +
    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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • 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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • -- cgit v1.2.1