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 +- 2d/rigidbody/rigidbody_1.html | 2 +- 2d/rigidbody/rigidbody_2.html | 2 +- 2d/rigidbody/rigidbody_3.html | 2 +- 3d/rigidbody.html | 2 +- index.html | 2 +- roadmap.html | 17 ++++++++--- roadmap.html.content | 15 ++++++--- transpiler/pages.txt | 2 +- 12 files changed, 110 insertions(+), 30 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 @@
  • 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
  • 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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • 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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • 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 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • diff --git a/3d/rigidbody.html b/3d/rigidbody.html index 7921b24..38dc4c7 100644 --- a/3d/rigidbody.html +++ b/3d/rigidbody.html @@ -26,7 +26,7 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • diff --git a/index.html b/index.html index 616c2f9..21cc8d3 100644 --- a/index.html +++ b/index.html @@ -26,7 +26,7 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • diff --git a/roadmap.html b/roadmap.html index 931d893..8d7f3e3 100644 --- a/roadmap.html +++ b/roadmap.html @@ -26,7 +26,7 @@
  • Rectangle-Line
  • Rectangle-Rectangle
    • -
  • Polygon-Polygon
    • +
  • Separating Axis Theorem
  • @@ -87,6 +87,10 @@ color: red; } + .abandoned { + color: grey; + } + section ul li.done:before { content: '✓' } @@ -104,12 +108,11 @@

    May/June 2021: More Collisions

    Obviously, the month of April did not go as planned. I got caught up with a number of tasks that I couldn't handle, @@ -130,6 +133,10 @@ simulation up and running with simple objects (spheres, cubes, etc.). From there, I want to begin exploring more complex physics simulation topics like oct-trees, multiple collision resolution, etc. We will see what happens, but I am optimistic, so long as I stay the course. +

    + Edit: I am going to focus on SAT collision and AABB collision detection going forward for this month. In addition, + I am going to finish the descriptions/demos for regular rigidbody collision. Afterwards, if I have time, I will move onto + 3D collisions.

    diff --git a/roadmap.html.content b/roadmap.html.content index c20a0ef..ee60886 100644 --- a/roadmap.html.content +++ b/roadmap.html.content @@ -35,6 +35,10 @@ color: red; } + .abandoned { + color: grey; + } + section ul li.done:before { content: '✓' } @@ -52,12 +56,11 @@

    May/June 2021: More Collisions

    Obviously, the month of April did not go as planned. I got caught up with a number of tasks that I couldn't handle, @@ -78,6 +81,10 @@ simulation up and running with simple objects (spheres, cubes, etc.). From there, I want to begin exploring more complex physics simulation topics like oct-trees, multiple collision resolution, etc. We will see what happens, but I am optimistic, so long as I stay the course. +

    + Edit: I am going to focus on SAT collision and AABB collision detection going forward for this month. In addition, + I am going to finish the descriptions/demos for regular rigidbody collision. Afterwards, if I have time, I will move onto + 3D collisions.

    diff --git a/transpiler/pages.txt b/transpiler/pages.txt index 369ad07..cea23dd 100644 --- a/transpiler/pages.txt +++ b/transpiler/pages.txt @@ -6,7 +6,7 @@ >"Collisions" >>/2d/_collisions/rectangle_line.html "Rectangle-Line" >>/2d/_collisions/rectangle_rectangle.html "Rectangle-Rectangle" ->>/2d/_collisions/polygon_polygon.html "Polygon-Polygon" +>>/2d/_collisions/polygon_polygon.html "Separating Axis Theorem" 🌠 "3D" >"Rigidbody" >>/3d/rigidbody.html "Rigidbody in 3D" -- cgit v1.2.1