From 19b0a3cafe144e8e77974bb0c9c63141a812e30d Mon Sep 17 00:00:00 2001 From: Matthew Kosarek Date: Sun, 6 Jun 2021 20:24:55 -0400 Subject: Nearly working SAT collision here, but I think I am going to piviot to circles for sake of demonstration in this instance --- 2d/rigidbody/rigidbody_3/dist/output.wasm | Bin 53544 -> 52832 bytes 2d/rigidbody/rigidbody_3/main.cpp | 144 ++++++++++++++---------------- 2 files changed, 69 insertions(+), 75 deletions(-) (limited to '2d/rigidbody/rigidbody_3') diff --git a/2d/rigidbody/rigidbody_3/dist/output.wasm b/2d/rigidbody/rigidbody_3/dist/output.wasm index 5df757d..1a6e153 100755 Binary files a/2d/rigidbody/rigidbody_3/dist/output.wasm and b/2d/rigidbody/rigidbody_3/dist/output.wasm differ diff --git a/2d/rigidbody/rigidbody_3/main.cpp b/2d/rigidbody/rigidbody_3/main.cpp index 2063718..75379c4 100644 --- a/2d/rigidbody/rigidbody_3/main.cpp +++ b/2d/rigidbody/rigidbody_3/main.cpp @@ -170,6 +170,7 @@ void load() { r2.body.mass = 1.f; r2.body.position = Vector2 { context.width * (3.f / 4.f), context.height * (3.f / 4.f) }; r2.body.velocity = Vector2 { -300.f, -150.f }; + r2.body.rotationalVelocity = 0.9f; mainLoop.run(update); } @@ -193,6 +194,11 @@ void handleCollisionWithWall(Rectangle* r) { } } +/* + Do not worry about how w are exactly finding the intersection here, for now. + We are using the Separating Axis Theorem to do so here. In the 2D -> Collisions + section of the website, we describe this method at length. +*/ Vector2 getProjection(Vector2* vertices, Vector2 axis) { float32 min = axis.dot(vertices[0]); float32 max = min; @@ -210,108 +216,90 @@ Vector2 getProjection(Vector2* vertices, Vector2 axis) { return Vector2 { min, max }; } -bool projectionsOverlap(Vector2 first, Vector2 second) { +inline bool projectionsOverlap(Vector2 first, Vector2 second) { return first.x <= second.y && second.x <= first.y; } -float32 getProjectionOverlap(Vector2 first, Vector2 second) { - float32 firstOverlap = fabs(first.x - second.y); - float32 secondOverlap = fabs(second.x - first.y); +inline float32 getProjectionOverlap(Vector2 first, Vector2 second) { + float32 firstOverlap = (first.x - second.y); // TODO: Does this need to be absolute value? + float32 secondOverlap = (second.x - first.y); return firstOverlap > secondOverlap ? secondOverlap : firstOverlap; } -const float32 EPSILON = 1.f; -IntersectionResult getIntersection(Rectangle* first, Rectangle* second) { - IntersectionResult ir; - - // For two rectangles to overlap, it means that at least one of the corners of one is inside of the other - Edge* firstEdges = first->edges; - Vector2* firstPoints = first->transformedPoints; - - Edge* secondEdges = second->edges; - Vector2* secondPoints = second->transformedPoints; - +struct IntermediateIntersectionResult { float32 minOverlap = FLT_MAX; - Vector2 minOverlapAxis; - Edge* minOverlapEdge = NULL; - bool minOverlapWasFirstRect = false; - + Edge* minOverlapEdge; + bool isOverlapOnFirstEdge = true; +}; + +bool checkEdgeOverlap(Edge* edges, Rectangle* first, Rectangle* second, IntermediateIntersectionResult* iir, bool isFirstEdge) { + // Returns true if SAT passes for the provided set of edges. for (int i = 0; i < 4; i++) { - Vector2 normal = firstEdges[i].normal; + Vector2 normal = edges[i].normal; - Vector2 firstProj = getProjection(firstPoints, normal); - Vector2 secondProj = getProjection(secondPoints, normal); + Vector2 firstProj = getProjection(first->transformedPoints, normal); + Vector2 secondProj = getProjection(second->transformedPoints, normal); if (!projectionsOverlap(firstProj, secondProj)) { - return ir; + return false; } float32 overlap = getProjectionOverlap(firstProj, secondProj); - if (overlap < minOverlap) { - minOverlap = overlap; - minOverlapAxis = normal; - minOverlapEdge = &firstEdges[i]; - minOverlapWasFirstRect = true; + if (overlap < iir->minOverlap) { + iir->minOverlap = overlap; + iir->minOverlapEdge = &edges[i]; + iir->isOverlapOnFirstEdge = isFirstEdge; } } - for (int i = 0; i < 4; i++) { - Vector2 normal = secondEdges[i].normal; - - Vector2 firstProj = getProjection(firstPoints, normal); - Vector2 secondProj = getProjection(secondPoints, normal); + return true; +} - if (!projectionsOverlap(firstProj, secondProj)) { - return ir; - } +const float32 EPSILON = 1.f; +IntersectionResult getIntersection(Rectangle* first, Rectangle* second) { + IntersectionResult ir; - float32 overlap = getProjectionOverlap(firstProj, secondProj); - if (overlap < minOverlap) { - minOverlap = overlap; - minOverlapAxis = normal; - minOverlapEdge = &secondEdges[i]; - } + IntermediateIntersectionResult iir; + if (!checkEdgeOverlap(first->edges, first, second, &iir, true)) { + return ir; } + if (!checkEdgeOverlap(second->edges, first, second, &iir, false)) { + return ir; + } + ir.intersect = true; ir.relativeVelocity = first->body.velocity - second->body.velocity; - ir.collisionNormal = minOverlapAxis; - - // Find the point of collision, this is kind of tricky, and it is just an approximation for now. - // At this point, we know that we intersected along the minOverlapAxis, but we do not know where - // that exactly happened. To remedy this will, we create two parallel lines: one at the top of the - // normal area, and one at the bottom. For point on both of the Rectangles, we will check: - // (1) if it is between these two planes - // (2) if, for that rectangle, it is the closest point to the original normal vector - // (3) or if it is equally distant from normal vector as another point (then this is a "flat" collision) - // - // The collision point MUST be between these two planes. We can then say the corner/face of the non-monoverlapAxis - // Rectangle is the collision point. This enables us to then solve for their respective points of application fairly - // easily. If the collision "point" is an entire face, we make the collision point be the center point. - // - - Vector2 closestPoint; - float32 minDistance = FLT_MAX; - - for (int p = 0; p < 4; p++) { - Vector2 point = minOverlapWasFirstRect ? secondPoints[p] : firstPoints[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.collisionNormal = iir.minOverlapEdge->normal; + + float32 minDistanceFromEdge = FLT_MAX; + Vector2 pointOfContact; + Vector2* pointsToCheck = iir.isOverlapOnFirstEdge ? second->transformedPoints : first->transformedPoints; + for (int p = 0; p < 4; p++) { + Vector2 point = pointsToCheck[p]; + + float32 distanceFromEdge = MIN((iir.minOverlapEdge->start - point).length(), (iir.minOverlapEdge->end - point).length()); + + if (distanceFromEdge < minDistanceFromEdge) { + minDistanceFromEdge = distanceFromEdge; + pointOfContact = point; } - } + } + - ir.firstPointOfApplication = closestPoint - first->body.position; - ir.secondPointOfApplication = closestPoint - second->body.position;; + ir.firstPointOfApplication = pointOfContact - first->body.position; + ir.secondPointOfApplication = pointOfContact - second->body.position;; return ir; } +/** +In this method, we resolve the collision of two rigidbodies using the IntersectionResult +that we gathered from the collision information. Note that this particular tutorial +is not about how we find this collision, but rather how we use this collision. To see the +variety of ways of how this IntersectionResult can be calculated go to the 2D->Collision +section of the website. +***/ void resolveCollision(Rigidbody* first, Rigidbody* second, IntersectionResult* ir) { Vector2 relativeVelocity = ir->relativeVelocity; Vector2 collisionNormal = ir->collisionNormal; @@ -337,18 +325,21 @@ void update(float32 deltaTimeSeconds, void* userData) { r1.update(deltaTimeSeconds); r2.update(deltaTimeSeconds); - // Handle intersection between the two rectangles here + // Let's backtrack the simulation to find the precise point at which we collided. + // There exists many ways to find this precise point. This is by far the most + // expensive, but it gets the job done. IntersectionResult ir = getIntersection(&r1, &r2); if (ir.intersect) { IntersectionResult irCopy = ir; float32 copyDt = deltaTimeSeconds; + float32 subdivisionAmountSeconds = deltaTimeSeconds / 16.f; do { r1.restorePreviousBody(); r2.restorePreviousBody(); ir = irCopy; - copyDt = copyDt /= 2.f; + copyDt = copyDt - subdivisionAmountSeconds; r1.update(copyDt); r2.update(copyDt); @@ -364,6 +355,9 @@ void update(float32 deltaTimeSeconds, void* userData) { printf("Found intersection at timestamp: %f\n", copyDt); + // The following function is the main one that we're talking about in this tutorial. + // This function will take the collision data, and repel the objects away from one + // another using what we know from physics. resolveCollision(&r1.body, &r2.body, &ir); float32 frameTimeRemaining = deltaTimeSeconds - copyDt; -- cgit v1.2.1