From 0ebc47873fc58645ad6b4dbef68a3571f6e67bbb Mon Sep 17 00:00:00 2001
From: Matthew Kosarek <mattkae@protonmail.com>
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