From 0ebc47873fc58645ad6b4dbef68a3571f6e67bbb Mon Sep 17 00:00:00 2001 From: Matthew Kosarek Date: Wed, 30 Jun 2021 19:13:11 -0400 Subject: Honestly, a much better simulation going on here --- 2d/_collisions/polygon_polygon.html | 39 ++++++-- 2d/_collisions/polygon_polygon.html.content | 43 +++++++-- 2d/_collisions/polygon_polygon/dist/output.wasm | Bin 57700 -> 57631 bytes 2d/_collisions/polygon_polygon/images/1.png | Bin 8299 -> 8299 bytes 2d/_collisions/polygon_polygon/images/2.png | Bin 7962 -> 7962 bytes 2d/_collisions/polygon_polygon/images/2a.png | Bin 8434 -> 8434 bytes 2d/_collisions/polygon_polygon/images/2b.png | Bin 8006 -> 8006 bytes 2d/_collisions/polygon_polygon/images/2c.png | Bin 8022 -> 8022 bytes 2d/_collisions/polygon_polygon/images/2d.png | Bin 10826 -> 10826 bytes 2d/_collisions/polygon_polygon/images/2e.png | Bin 11330 -> 11330 bytes 2d/_collisions/polygon_polygon/images/2f.png | Bin 9354 -> 9354 bytes 2d/_collisions/polygon_polygon/images/3.png | Bin 8105 -> 8105 bytes 2d/_collisions/polygon_polygon/images/3a.png | Bin 0 -> 13397 bytes 2d/_collisions/polygon_polygon/images/3b.png | Bin 0 -> 12768 bytes 2d/_collisions/polygon_polygon/images/3c.png | Bin 0 -> 11957 bytes 2d/_collisions/polygon_polygon/main.cpp | 118 ++++++++++++------------ 16 files changed, 130 insertions(+), 70 deletions(-) create mode 100644 2d/_collisions/polygon_polygon/images/3a.png create mode 100644 2d/_collisions/polygon_polygon/images/3b.png create mode 100644 2d/_collisions/polygon_polygon/images/3c.png diff --git a/2d/_collisions/polygon_polygon.html b/2d/_collisions/polygon_polygon.html index 4c4698a..2e22f49 100644 --- a/2d/_collisions/polygon_polygon.html +++ b/2d/_collisions/polygon_polygon.html @@ -217,17 +217,44 @@

SAT Collision Resolution

- Now that we know our objects have intersected, we want to be able to send them tumbling away from each other to simulate a collision. To do this, we will need to find the following things: + Now that we know that our objects have intersected, we want to send them tumbling away from one another in order to simulate a collision. To do this, we will need to find the following things:

-

Collision Normal

-

- -

+ To find these values, we must first find both the shape and the edge that caused the intersection in the first place. To do this, we will think about what we know so far and try to arrive at some intutitive understanding of it. Keep in mind that I am not a proof-minded person, so you will not be finding that here. +
+ +

Finding the Intersecting Edge

+ We can already figure out that the following two triangles intersect one another: +
+
+ +
+ +
+ +

+ + We know that A can only intersect B if: (1) a vertex from A is inside of B, (2) an edge of A flatly intersects an edge of B, or (3) a vertex of A overlaps exactly a vertex of B. Honestly, for our purposes, scenarios 2 and 3 are quite unlikely, but we can explore them a bit just to see how we might resolve them. We will start with the first case, since it is more likely. We will start by drawing the axis defined by the leftmost edge of B with both polygons projected onto it: + +

+ +
+ +
+ +

+ This is a poorly drawn picture, but you should be able to see that the bit in green represents the intersection between the projections of the two polygons. If we were to repeat this same exercise for every edge here, we'll begin to see something very interesting. And, if we take new shapes and continue this stategy, we can begin to come to a very elegant conclusion: +
+
+ + The intersecting edge will be the one where the projection of triangle A overlaps with the projection of triangle B the least! + +

+ I'm sure someone more inclined to proving mathematical truities would love to describe this to you, but, for all intents and purposes, this intutitive understanding is good enough for us. We just want to make games, anyhow.

diff --git a/2d/_collisions/polygon_polygon.html.content b/2d/_collisions/polygon_polygon.html.content index 29c284d..4f99d71 100644 --- a/2d/_collisions/polygon_polygon.html.content +++ b/2d/_collisions/polygon_polygon.html.content @@ -115,17 +115,48 @@

SAT Collision Resolution

- Now that we know our objects have intersected, we want to be able to send them tumbling away from each other to simulate a collision. To do this, we will need to find the following things: + Now that we know that our objects have intersected, we want to send them tumbling away from one another in order to simulate a collision. To do this, we will need to find the following things:

    -
  • Collision Normal: in what direction, point towards object A, did the polygons intersect
  • Point of Application: at what point on each object did the objects first intersect
    • +
  • Collision Normal: in what direction, point towards object A, did the polygons intersect
  • Relative Velocity: easily found by taking the difference between the two velocities.
-

Collision Normal

-

- -

+ To find these values, we must first find both the shape and the edge that caused the intersection in the first place. To do this, we will think about what we know so far and try to arrive at some intutitive understanding of it. Keep in mind that I am not a proof-minded person, so you will not be finding that here. +
+ +

Finding the Intersecting Edge

+ We can already figure out that the following two triangles intersect one another: +
+
+ +
+ +
+ +

+ + We know that A can only intersect B if: (1) a vertex from A is inside of B, (2) an edge of A flatly intersects an edge of B, or (3) a vertex of A overlaps exactly a vertex of B. Honestly, for our purposes, scenarios 2 and 3 are quite unlikely, but we can explore them a bit just to see how we might resolve them. We will start with the first case, since it is more likely. We will start by drawing the axis defined by the leftmost edge of B with both polygons projected onto it: + +

+ +
+ +
+ +

+ This is a poorly drawn picture, but you should be able to see that the bit in green represents the intersection between the projections of the two polygons. If we were to repeat this same exercise for every edge here, we'll begin to see something very interesting. And, if we take new shapes and continue this stategy, we can begin to come to a very elegant conclusion: +
+
+ + The intersecting edge will be the one where the projection of triangle A overlaps with the projection of triangle B the least! + +

+ I'm sure someone more inclined to proving mathematical truities would love to describe this to you, but, for all intents and purposes, this intutitive understanding is good enough for us. We just want to make games, anyhow. +
+ +

Finding which point causes the intersection

+

diff --git a/2d/_collisions/polygon_polygon/dist/output.wasm b/2d/_collisions/polygon_polygon/dist/output.wasm index 8e0443b..5b2ba39 100755 Binary files a/2d/_collisions/polygon_polygon/dist/output.wasm and b/2d/_collisions/polygon_polygon/dist/output.wasm differ diff --git a/2d/_collisions/polygon_polygon/images/1.png b/2d/_collisions/polygon_polygon/images/1.png index 0e4268a..d554c2a 100644 Binary files a/2d/_collisions/polygon_polygon/images/1.png 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 index 3dd2020..67f379c 100644 Binary files a/2d/_collisions/polygon_polygon/images/2.png 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 index 02bfa02..6e2d4b2 100644 Binary files a/2d/_collisions/polygon_polygon/images/2a.png 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 index 1cfc780..f1fbcc4 100644 Binary files a/2d/_collisions/polygon_polygon/images/2b.png 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 index d9ca28b..bdecfb2 100644 Binary files a/2d/_collisions/polygon_polygon/images/2c.png 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 index 8e6f6cc..932a7c3 100644 Binary files a/2d/_collisions/polygon_polygon/images/2d.png 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 index fdaeae3..3a47d46 100644 Binary files a/2d/_collisions/polygon_polygon/images/2e.png 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 index 9a862b5..774830f 100644 Binary files a/2d/_collisions/polygon_polygon/images/2f.png 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 index 0e6d218..22eddde 100644 Binary files a/2d/_collisions/polygon_polygon/images/3.png and b/2d/_collisions/polygon_polygon/images/3.png differ diff --git a/2d/_collisions/polygon_polygon/images/3a.png b/2d/_collisions/polygon_polygon/images/3a.png new file mode 100644 index 0000000..cb8626b Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/3a.png differ diff --git a/2d/_collisions/polygon_polygon/images/3b.png b/2d/_collisions/polygon_polygon/images/3b.png new file mode 100644 index 0000000..f03fda1 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/3b.png differ diff --git a/2d/_collisions/polygon_polygon/images/3c.png b/2d/_collisions/polygon_polygon/images/3c.png new file mode 100644 index 0000000..4f50821 Binary files /dev/null and b/2d/_collisions/polygon_polygon/images/3c.png differ diff --git a/2d/_collisions/polygon_polygon/main.cpp b/2d/_collisions/polygon_polygon/main.cpp index 348e8d2..8648e94 100644 --- a/2d/_collisions/polygon_polygon/main.cpp +++ b/2d/_collisions/polygon_polygon/main.cpp @@ -261,7 +261,20 @@ void load() { mainLoop.run(update); } -Vector2 getProjection(Vector2* vertices, int numVertices, Vector2 axis) { +struct SATResult { + Edge* minOverlapEdge = NULL; // Edge that caused the intersection + Vector2 overlapPoint; // Point that caused the intersection on the other shape (i.e. not minOverlapShape) + float32 minOverlap = FLT_MAX; // Smallest projection overlap +}; + +struct ProjectionResult { + Vector2 minVertex; + Vector2 maxVertex; + Vector2 projection; +}; + +ProjectionResult getProjection(Vector2* vertices, int numVertices, Vector2 axis) { + ProjectionResult pr; float32 min = axis.dot(vertices[0]); float32 max = min; @@ -269,13 +282,16 @@ Vector2 getProjection(Vector2* vertices, int numVertices, Vector2 axis) { float32 d = axis.dot(vertices[v]); if (d < min) { + pr.minVertex = vertices[v]; min = d; } else if (d > max) { + pr.maxVertex = vertices[v]; max = d; } } - - return Vector2 { min, max }; + + pr.projection = Vector2 { min, max }; + return pr; } bool projectionsOverlap(Vector2 first, Vector2 second) { @@ -288,74 +304,60 @@ float32 getProjectionOverlap(Vector2 first, Vector2 second) { return e - f; } -const float32 EPSILON = 1.f; -IntersectionResult getIntersection(ConvexPolygon* first, ConvexPolygon* second) { - IntersectionResult ir; - - // For two rectangles to overlap, it means that at least one of the corners of one is inside of the other - float32 minOverlap = FLT_MAX; - Edge* minOverlapEdge = NULL; - bool minOverlapWasFirst = false; - - for (int i = 0; i < first->numVertices; i++) { +bool runSatForShapesEdges(SATResult* result, ConvexPolygon* first, ConvexPolygon* second) { + for (int i = 0; i < first->numVertices; i++) { Vector2 normal = first->edges[i].normal; - Vector2 firstProj = getProjection(first->transformedVertices, first->numVertices, normal); - Vector2 secondProj = getProjection(second->transformedVertices, second->numVertices, normal); + ProjectionResult firstProj = getProjection(first->transformedVertices, first->numVertices, normal); + ProjectionResult secondProj = getProjection(second->transformedVertices, second->numVertices, normal); - if (!projectionsOverlap(firstProj, secondProj)) { - return ir; + if (!projectionsOverlap(firstProj.projection, secondProj.projection)) { + return false; } - float32 overlap = getProjectionOverlap(firstProj, secondProj); - if (overlap < minOverlap) { - minOverlap = overlap; - minOverlapEdge = &first->edges[i]; - minOverlapWasFirst = true; + float32 overlap = getProjectionOverlap(firstProj.projection, secondProj.projection); + if (overlap < result->minOverlap) { + result->minOverlap = overlap; + result->minOverlapEdge = &first->edges[i]; + + // The overlapPoint will be the point on the other shape that penetrated the edge. + // If we caught the intersection reasonably early, it should be the point on 'second' + // that is nearest to the points on 'first'. + float32 min1min2 = (firstProj.minVertex - secondProj.minVertex).length(); + float32 min1max2 = (firstProj.minVertex - secondProj.maxVertex).length(); + float32 max1max2 = (firstProj.maxVertex - secondProj.maxVertex).length(); + float32 max1min2 = (firstProj.maxVertex - secondProj.minVertex).length(); + + float32 closest = MIN(min1min2, MIN(min1max2, MIN(max1max2, max1min2))); + if (closest == min1min2 || closest == max1min2) { + result->overlapPoint = secondProj.minVertex; + } else { + result->overlapPoint = secondProj.maxVertex; + } } } - for (int i = 0; i < second->numVertices; i++) { - Vector2 normal = second->edges[i].normal; - - Vector2 firstProj = getProjection(first->transformedVertices, first->numVertices, normal); - Vector2 secondProj = getProjection(second->transformedVertices, second->numVertices, normal); + return true; +} - if (!projectionsOverlap(firstProj, secondProj)) { - return ir; - } +const float32 EPSILON = 1.f; +IntersectionResult getIntersection(ConvexPolygon* first, ConvexPolygon* second) { + IntersectionResult ir; + SATResult sat; + + if (!runSatForShapesEdges(&sat, first, second)) { + return ir; + } - float32 overlap = getProjectionOverlap(firstProj, secondProj); - if (overlap < minOverlap) { - minOverlap = overlap; - minOverlapEdge = &second->edges[i]; - minOverlapWasFirst = false; - } - } + if (!runSatForShapesEdges(&sat, second, first)) { + return ir; + } ir.intersect = true; ir.relativeVelocity = first->body.velocity - second->body.velocity; - ir.collisionNormal = minOverlapEdge->normal; - - // Time to find just where we intersected - Vector2 closestPoint; - float32 minDistance = FLT_MAX; - - for (int p = 0; p < (minOverlapWasFirst ? second->numVertices : first->numVertices); p++) { - Vector2 point = minOverlapWasFirst ? second->transformedVertices[p] : first->transformedVertices[p]; - - float32 distFromPointToStart = (minOverlapEdge->start - point).length(); - float32 distFromPointToEnd = (minOverlapEdge->end - point).length(); - float32 potentialMin = MIN(distFromPointToStart, distFromPointToEnd); - - if (potentialMin < minDistance) { - closestPoint = point; - minDistance = potentialMin; - } - } - - ir.firstPointOfApplication = closestPoint - first->body.position; - ir.secondPointOfApplication = closestPoint - second->body.position;; + ir.collisionNormal = sat.minOverlapEdge->normal; + ir.firstPointOfApplication = sat.overlapPoint - first->body.position; + ir.secondPointOfApplication = sat.overlapPoint - second->body.position;; return ir; } -- cgit v1.2.1