diff options
Diffstat (limited to '2d/_collisions/polygon_polygon')
14 files changed, 60 insertions, 58 deletions
diff --git a/2d/_collisions/polygon_polygon/dist/output.wasm b/2d/_collisions/polygon_polygon/dist/output.wasm Binary files differindex 8e0443b..5b2ba39 100755 --- a/2d/_collisions/polygon_polygon/dist/output.wasm +++ b/2d/_collisions/polygon_polygon/dist/output.wasm diff --git a/2d/_collisions/polygon_polygon/images/1.png b/2d/_collisions/polygon_polygon/images/1.png Binary files differindex 0e4268a..d554c2a 100644 --- a/2d/_collisions/polygon_polygon/images/1.png +++ b/2d/_collisions/polygon_polygon/images/1.png diff --git a/2d/_collisions/polygon_polygon/images/2.png b/2d/_collisions/polygon_polygon/images/2.png Binary files differindex 3dd2020..67f379c 100644 --- a/2d/_collisions/polygon_polygon/images/2.png +++ b/2d/_collisions/polygon_polygon/images/2.png diff --git a/2d/_collisions/polygon_polygon/images/2a.png b/2d/_collisions/polygon_polygon/images/2a.png Binary files differindex 02bfa02..6e2d4b2 100644 --- a/2d/_collisions/polygon_polygon/images/2a.png +++ b/2d/_collisions/polygon_polygon/images/2a.png diff --git a/2d/_collisions/polygon_polygon/images/2b.png b/2d/_collisions/polygon_polygon/images/2b.png Binary files differindex 1cfc780..f1fbcc4 100644 --- a/2d/_collisions/polygon_polygon/images/2b.png +++ b/2d/_collisions/polygon_polygon/images/2b.png diff --git a/2d/_collisions/polygon_polygon/images/2c.png b/2d/_collisions/polygon_polygon/images/2c.png Binary files differindex d9ca28b..bdecfb2 100644 --- a/2d/_collisions/polygon_polygon/images/2c.png +++ b/2d/_collisions/polygon_polygon/images/2c.png diff --git a/2d/_collisions/polygon_polygon/images/2d.png b/2d/_collisions/polygon_polygon/images/2d.png Binary files differindex 8e6f6cc..932a7c3 100644 --- a/2d/_collisions/polygon_polygon/images/2d.png +++ b/2d/_collisions/polygon_polygon/images/2d.png diff --git a/2d/_collisions/polygon_polygon/images/2e.png b/2d/_collisions/polygon_polygon/images/2e.png Binary files differindex fdaeae3..3a47d46 100644 --- a/2d/_collisions/polygon_polygon/images/2e.png +++ b/2d/_collisions/polygon_polygon/images/2e.png diff --git a/2d/_collisions/polygon_polygon/images/2f.png b/2d/_collisions/polygon_polygon/images/2f.png Binary files differindex 9a862b5..774830f 100644 --- a/2d/_collisions/polygon_polygon/images/2f.png +++ b/2d/_collisions/polygon_polygon/images/2f.png diff --git a/2d/_collisions/polygon_polygon/images/3.png b/2d/_collisions/polygon_polygon/images/3.png Binary files differindex 0e6d218..22eddde 100644 --- a/2d/_collisions/polygon_polygon/images/3.png +++ b/2d/_collisions/polygon_polygon/images/3.png diff --git a/2d/_collisions/polygon_polygon/images/3a.png b/2d/_collisions/polygon_polygon/images/3a.png Binary files differnew file mode 100644 index 0000000..cb8626b --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/3a.png diff --git a/2d/_collisions/polygon_polygon/images/3b.png b/2d/_collisions/polygon_polygon/images/3b.png Binary files differnew file mode 100644 index 0000000..f03fda1 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/3b.png diff --git a/2d/_collisions/polygon_polygon/images/3c.png b/2d/_collisions/polygon_polygon/images/3c.png Binary files differnew file mode 100644 index 0000000..4f50821 --- /dev/null +++ b/2d/_collisions/polygon_polygon/images/3c.png 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; } |
