From 6fa7b10d244b226c7651747d88ffdfaa5c5814e2 Mon Sep 17 00:00:00 2001 From: Matthew Kosarek Date: Thu, 24 Jun 2021 15:54:37 -0400 Subject: (mkosarek) A description of the separating axis theorem with images --- 2d/_collisions/polygon_polygon.html | 62 +++++++++++++++++++++++++-- 2d/_collisions/polygon_polygon.html.content | 62 +++++++++++++++++++++++++-- 2d/_collisions/polygon_polygon/images/1.png | Bin 0 -> 8299 bytes 2d/_collisions/polygon_polygon/images/2.png | Bin 0 -> 7962 bytes 2d/_collisions/polygon_polygon/images/2a.png | Bin 0 -> 8434 bytes 2d/_collisions/polygon_polygon/images/2b.png | Bin 0 -> 8006 bytes 2d/_collisions/polygon_polygon/images/2c.png | Bin 0 -> 8022 bytes 2d/_collisions/polygon_polygon/images/2d.png | Bin 0 -> 10826 bytes 2d/_collisions/polygon_polygon/images/2e.png | Bin 0 -> 11330 bytes 2d/_collisions/polygon_polygon/images/2f.png | Bin 0 -> 9354 bytes 2d/_collisions/polygon_polygon/images/3.png | Bin 0 -> 8105 bytes 11 files changed, 116 insertions(+), 8 deletions(-) create mode 100644 2d/_collisions/polygon_polygon/images/1.png create mode 100644 2d/_collisions/polygon_polygon/images/2.png create mode 100644 2d/_collisions/polygon_polygon/images/2a.png create mode 100644 2d/_collisions/polygon_polygon/images/2b.png create mode 100644 2d/_collisions/polygon_polygon/images/2c.png create mode 100644 2d/_collisions/polygon_polygon/images/2d.png create mode 100644 2d/_collisions/polygon_polygon/images/2e.png create mode 100644 2d/_collisions/polygon_polygon/images/2f.png create mode 100644 2d/_collisions/polygon_polygon/images/3.png (limited to '2d/_collisions') diff --git a/2d/_collisions/polygon_polygon.html b/2d/_collisions/polygon_polygon.html index e8fe7ea..c1c3a2e 100644 --- a/2d/_collisions/polygon_polygon.html +++ b/2d/_collisions/polygon_polygon.html @@ -76,25 +76,79 @@

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: + 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 not intersect.

- Given two shapes A and B. + Images two shapes A and B as shown below (they are triangles here, but they can be anything really). +
+ +

+ +
+ +
+ 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: +
+ +
+ +
- Imagine we could isolate a single edge of A and shine a light on it. +
+ That line could be any of the infinite number of lines between the objects, so we can't really select that exact line. So the problem becomes: how do we infer 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. + +
+
+ To do separating axis theorem, we iterate all of the edges of both 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). +
+ +
+ +
+ +
+ + 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). + +
+ +
+ +
+ + At this point, you will see that I named the three vertices on each of the triangles. Triangle A is made of vertices a1, a2, a3 and triangle B is made of vertices b1, b2, b3. 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 maximizes the dot product and which one minimizes the dot product. The projection of the shape is then the range defined by this min and max value. + +
+ +
+ +
+ +
+ + Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do not 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. + +
+ +
+ +
+ +

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. Project each vertex v of A onto n. Return the minimum and maximum projection of all vertices as the projection of the shape.
  4. Repeat Step 2 for polygon B.
  5. If the min and max projections found in Steps 2 and 3 do NOT overlap, the polygons are not intersecting. Return false.
  6. If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.
    7. diff --git a/2d/_collisions/polygon_polygon.html.content b/2d/_collisions/polygon_polygon.html.content index ffa9b15..a0da872 100644 --- a/2d/_collisions/polygon_polygon.html.content +++ b/2d/_collisions/polygon_polygon.html.content @@ -24,25 +24,79 @@

    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: + 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 not intersect.

    - Given two shapes A and B. + Images two shapes A and B as shown below (they are triangles here, but they can be anything really). +
    + +

    + +
    + +
    + 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: +
    + +
    + +
    - Imagine we could isolate a single edge of A and shine a light on it. +
    + That line could be any of the infinite number of lines between the objects, so we can't really select that exact line. So the problem becomes: how do we infer 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. + +
    +
    + To do separating axis theorem, we iterate all of the edges of both 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). +
    + +
    + +
    + +
    + + 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). + +
    + +
    + +
    + + At this point, you will see that I named the three vertices on each of the triangles. Triangle A is made of vertices a1, a2, a3 and triangle B is made of vertices b1, b2, b3. 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 maximizes the dot product and which one minimizes the dot product. The projection of the shape is then the range defined by this min and max value. + +
    + +
    + +
    + +
    + + Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do not 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. + +
    + +
    + +
    + +

    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. Project each vertex v of A onto n. Return the minimum and maximum projection of all vertices as the projection of the shape.
    4. Repeat Step 2 for polygon B.
    5. If the min and max projections found in Steps 2 and 3 do NOT overlap, the polygons are not intersecting. Return false.
    6. If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.
      7. diff --git a/2d/_collisions/polygon_polygon/images/1.png b/2d/_collisions/polygon_polygon/images/1.png new file mode 100644 index 0000000..0e4268a Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/1.png differ diff --git a/2d/_collisions/polygon_polygon/images/2.png b/2d/_collisions/polygon_polygon/images/2.png new file mode 100644 index 0000000..3dd2020 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2.png differ diff --git a/2d/_collisions/polygon_polygon/images/2a.png b/2d/_collisions/polygon_polygon/images/2a.png new file mode 100644 index 0000000..02bfa02 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2a.png differ diff --git a/2d/_collisions/polygon_polygon/images/2b.png b/2d/_collisions/polygon_polygon/images/2b.png new file mode 100644 index 0000000..1cfc780 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2b.png differ diff --git a/2d/_collisions/polygon_polygon/images/2c.png b/2d/_collisions/polygon_polygon/images/2c.png new file mode 100644 index 0000000..d9ca28b Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2c.png differ diff --git a/2d/_collisions/polygon_polygon/images/2d.png b/2d/_collisions/polygon_polygon/images/2d.png new file mode 100644 index 0000000..8e6f6cc Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2d.png differ diff --git a/2d/_collisions/polygon_polygon/images/2e.png b/2d/_collisions/polygon_polygon/images/2e.png new file mode 100644 index 0000000..fdaeae3 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2e.png differ diff --git a/2d/_collisions/polygon_polygon/images/2f.png b/2d/_collisions/polygon_polygon/images/2f.png new file mode 100644 index 0000000..9a862b5 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/2f.png differ diff --git a/2d/_collisions/polygon_polygon/images/3.png b/2d/_collisions/polygon_polygon/images/3.png new file mode 100644 index 0000000..0e6d218 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/3.png differ -- cgit v1.2.1