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/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 ++++++++++++------------ 14 files changed, 60 insertions(+), 58 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 (limited to '2d/_collisions/polygon_polygon') 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