From cdf770d6950befd25779a18ea3972deeb9f143bb Mon Sep 17 00:00:00 2001 From: Matthew Kosarek Date: Sun, 25 Apr 2021 15:33:53 -0400 Subject: Rectangle intersection with a line complete --- frontend/2d/_collisions/pill_line.html | 82 +++++++-------- frontend/2d/_collisions/pill_line.html.content | 82 +++++++-------- frontend/2d/_collisions/pill_pill.html | 80 +++++++-------- frontend/2d/_collisions/pill_pill.html.content | 80 +++++++-------- frontend/2d/_collisions/rectangle_line.html | 114 ++++++++++++++------- .../2d/_collisions/rectangle_line.html.content | 114 ++++++++++++++------- .../2d/_collisions/rectangle_line/dist/output.wasm | Bin 43326 -> 50544 bytes frontend/2d/_collisions/rectangle_line/main.cpp | 112 +++++++++++++++++++- 8 files changed, 425 insertions(+), 239 deletions(-) (limited to 'frontend/2d/_collisions') diff --git a/frontend/2d/_collisions/pill_line.html b/frontend/2d/_collisions/pill_line.html index bd5522e..1ba424d 100644 --- a/frontend/2d/_collisions/pill_line.html +++ b/frontend/2d/_collisions/pill_line.html @@ -47,47 +47,47 @@ - - -
-

Pill-Line

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
- -
-
+ + +
+

Pill-Line

+
+

+ Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. +

+
+ + + +
+ +
+
diff --git a/frontend/2d/_collisions/pill_line.html.content b/frontend/2d/_collisions/pill_line.html.content index c534d93..ce779d5 100644 --- a/frontend/2d/_collisions/pill_line.html.content +++ b/frontend/2d/_collisions/pill_line.html.content @@ -1,41 +1,41 @@ - - -
-

Pill-Line

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
- -
-
+ + +
+

Pill-Line

+
+

+ Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. +

+
+ + + +
+ +
+
diff --git a/frontend/2d/_collisions/pill_pill.html b/frontend/2d/_collisions/pill_pill.html index 812c10a..0883bc7 100644 --- a/frontend/2d/_collisions/pill_pill.html +++ b/frontend/2d/_collisions/pill_pill.html @@ -47,46 +47,46 @@ - - -
-

Pill-Pill

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
- -
-
+ + +
+

Pill-Pill

+
+

+ Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. +

+
+ + + +
+ +
+ diff --git a/frontend/2d/_collisions/pill_pill.html.content b/frontend/2d/_collisions/pill_pill.html.content index bd214b2..385ae3c 100644 --- a/frontend/2d/_collisions/pill_pill.html.content +++ b/frontend/2d/_collisions/pill_pill.html.content @@ -1,40 +1,40 @@ - - -
-

Pill-Pill

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
- -
-
+ + +
+

Pill-Pill

+
+

+ Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. +

+
+ + + +
+ +
+ diff --git a/frontend/2d/_collisions/rectangle_line.html b/frontend/2d/_collisions/rectangle_line.html index 17d95da..e0cd67e 100644 --- a/frontend/2d/_collisions/rectangle_line.html +++ b/frontend/2d/_collisions/rectangle_line.html @@ -47,44 +47,82 @@ - - -
-

Rectangle-Line

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
-
-

References

-
    -
-
-
-
+ + +
+

Rectangle intersection with a Line Segment

+
+

Algorithm

+

+ For each line segment that your rectangle could be intersecting with, + do the following: +

    +
  1. + For each corner of your rectangle, check if the distance from that point to the line is less than some epsilon, where epsilon is a reasonable small number (usually a 1 or 2 units, depending on the size of your lines). +
    2. +
  2. + To check each point, use the "distance from point to line segment" formula, which can be found here (I will not derive it just yet) +
    3. +
  3. + If a collision is found, we have all of the information required to solve the collision: +
      +
    • + Collision Normal: This is the perpendicular to the line segment, which can be found by: + + 
      +Vector2 getNormalToLineSegment(LineSegment* segment) {
+    Vector2 direction = segment->end - segment->start;
+    return *Vector2 { -direction.y, direction.x }).normalize();
+}
+
      +       +
      • +
    • + First Point of Application: Get the vector from the center of the rectangle (most like your position) to the corner which intersected. +
      • +
    • + Second Point of Application: Get vector from center of line to the corner which intersected. +
      • +
    +
    4. +
+

+
+
+

+ Live Example +

+
+ + + +
+ +
+
diff --git a/frontend/2d/_collisions/rectangle_line.html.content b/frontend/2d/_collisions/rectangle_line.html.content index 9f008a4..310c45a 100644 --- a/frontend/2d/_collisions/rectangle_line.html.content +++ b/frontend/2d/_collisions/rectangle_line.html.content @@ -1,38 +1,76 @@ - - -
-

Rectangle-Line

-
-

- Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. -

-
- - - -
-
-

References

-
    -
-
-
-
+ + +
+

Rectangle intersection with a Line Segment

+
+

Algorithm

+

+ For each line segment that your rectangle could be intersecting with, + do the following: +

    +
  1. + For each corner of your rectangle, check if the distance from that point to the line is less than some epsilon, where epsilon is a reasonable small number (usually a 1 or 2 units, depending on the size of your lines). +
    2. +
  2. + To check each point, use the "distance from point to line segment" formula, which can be found here (I will not derive it just yet) +
    3. +
  3. + If a collision is found, we have all of the information required to solve the collision: +
      +
    • + Collision Normal: This is the perpendicular to the line segment, which can be found by: + + 
      +Vector2 getNormalToLineSegment(LineSegment* segment) {
+    Vector2 direction = segment->end - segment->start;
+    return *Vector2 { -direction.y, direction.x }).normalize();
+}
+
      +       +
      • +
    • + First Point of Application: Get the vector from the center of the rectangle (most like your position) to the corner which intersected. +
      • +
    • + Second Point of Application: Get vector from center of line to the corner which intersected. +
      • +
    +
    4. +
+

+
+
+

+ Live Example +

+
+ + + +
+ +
+
diff --git a/frontend/2d/_collisions/rectangle_line/dist/output.wasm b/frontend/2d/_collisions/rectangle_line/dist/output.wasm index 11fa4c5..41e549e 100755 Binary files a/frontend/2d/_collisions/rectangle_line/dist/output.wasm and b/frontend/2d/_collisions/rectangle_line/dist/output.wasm differ diff --git a/frontend/2d/_collisions/rectangle_line/main.cpp b/frontend/2d/_collisions/rectangle_line/main.cpp index 321e8b5..39cb079 100644 --- a/frontend/2d/_collisions/rectangle_line/main.cpp +++ b/frontend/2d/_collisions/rectangle_line/main.cpp @@ -51,6 +51,14 @@ struct Rigidbody { } }; +struct IntersectionResult { + bool intersect = false; + Vector2 collisionNormal; + Vector2 relativeVelocity; + Vector2 firstPointOfApplication; + Vector2 secondPointOfApplication; +}; + struct Rectangle { OrthographicShape shape; Rigidbody body; @@ -79,6 +87,8 @@ struct Rectangle { } shape.load(vertices, 6, renderer); + body.reset(); + body.momentOfInertia = (1.f / 12.f) * body.mass * (width + height * height * height); } void update(float32 dtSeconds) { @@ -172,15 +182,115 @@ void load() { segmentList[3].load(&renderer, Vector4().fromColor(205, 178, 214, 255.f), Vector2 { 50.f, 150.f }, Vector2 { context.width - 50.f, 50.f }); rectangle.load(&renderer, Vector4 { 230.f, 182.f, 35.f, 255.f }, 64.f, 32.f); - rectangle.body.position = Vector2 { context.width / 2.f, context.height / 2.f }; + rectangle.body.position = Vector2 { context.width / 3.f, context.height / 2.f }; mainLoop.run(update); } +float32 getDistancePointToLine(Vector2 point, LineSegment* segment) { + float32 xLength = segment->end.x - segment->start.x; + float32 yLength = segment->end.y - segment->start.y; + return fabs(xLength * (segment->start.y - point.y) - (segment->start.x - point.x) * yLength) + / sqrtf((xLength * xLength) + (yLength * yLength)); +} + +const float32 EPSILON = 1.f; +IntersectionResult getIntersection(Rectangle* rectangle, LineSegment* segment) { + IntersectionResult ir; + + float32 halfWidth = rectangle->width / 2.f; + float32 halfHeight = rectangle->height / 2.f; + + Vector2 bottomLeft = rectangle->shape.model * Vector2 { -halfWidth, -halfHeight }; + Vector2 topLeft = rectangle->shape.model * Vector2 { -halfWidth, halfHeight }; + Vector2 bottomRight = rectangle->shape.model * Vector2 { halfWidth, -halfHeight }; + Vector2 topRight = rectangle->shape.model * Vector2 { halfWidth, halfHeight }; + + Vector2 collisionPoint; + + if (getDistancePointToLine(bottomLeft, segment) <= EPSILON) { + ir.intersect = true; + collisionPoint = bottomLeft; + } else if (getDistancePointToLine(topLeft, segment) <= EPSILON) { + ir.intersect = true; + collisionPoint = topLeft; + } else if (getDistancePointToLine(bottomRight, segment) <= EPSILON) { + ir.intersect = true; + collisionPoint = bottomRight; + } else if (getDistancePointToLine(topRight, segment) <= EPSILON) { + ir.intersect = true; + collisionPoint = topRight; + } else { + ir.intersect = false; + return ir; + } + + ir.collisionNormal = segment->getNormal(); + ir.relativeVelocity = rectangle->body.velocity - segment->body.velocity; + ir.firstPointOfApplication = (collisionPoint - rectangle->body.position); + ir.secondPointOfApplication = collisionPoint - segment->getPointOnLine(0.5f); + + return ir; +} + +void resolveCollision(Rigidbody* first, Rigidbody* second, IntersectionResult* ir) { + Vector2 relativeVelocity = ir->relativeVelocity; + Vector2 collisionNormal = ir->collisionNormal; + Vector2 firstPerp = ir->firstPointOfApplication.getPerp(); + Vector2 secondPerp = ir->secondPointOfApplication.getPerp(); + float32 firstPerpNorm = firstPerp.dot(collisionNormal); + float32 sndPerpNorm = secondPerp.dot(collisionNormal); + + float32 cofOfRestition = (first->cofOfRestition + second->cofOfRestition) / 2.f; + float32 numerator = (relativeVelocity * (-1 * (1.f + cofOfRestition))).dot(collisionNormal); + float32 linearDenomPart = collisionNormal.dot(collisionNormal * (1.f / first->mass + 1.f / second->mass)); + float32 rotationalDenomPart = (firstPerpNorm * firstPerpNorm) / first->momentOfInertia + (sndPerpNorm * sndPerpNorm) / second->momentOfInertia; + + float32 impulseMagnitude = numerator / (linearDenomPart);// + rotationalDenomPart); + first->velocity = first->velocity + (collisionNormal * (impulseMagnitude / first->mass)); + second->velocity = second->velocity - (collisionNormal * (impulseMagnitude / second->mass)); + first->rotationalVelocity = first->rotationalVelocity + firstPerp.dot(collisionNormal * impulseMagnitude) / first->momentOfInertia; + second->rotationalVelocity = second->rotationalVelocity - secondPerp.dot(collisionNormal * impulseMagnitude) / second->momentOfInertia; +} void update(float32 deltaTimeSeconds, void* userData) { // Update + Rectangle rectCopy = rectangle; rectangle.update(deltaTimeSeconds); + + for (int32 segmentIndex = 0; segmentIndex < 4; segmentIndex++) { + IntersectionResult ir = getIntersection(&rectangle, &segmentList[segmentIndex]); + if (!ir.intersect) { + continue; + } + + // Handle collison here + IntersectionResult irCopy = ir; + float32 copyDt = deltaTimeSeconds; + + do { + ir = irCopy; + rectangle = rectCopy; + copyDt = copyDt /= 2.f; + + rectangle.update(copyDt); + irCopy = getIntersection(&rectangle, &segmentList[segmentIndex]); + + if (copyDt <= 0.f) { + printf("Error: Should not be happening.\n"); + break; + } + + } while (irCopy.intersect); + + printf("Found intersection at timestamp: %f\n", copyDt); + + resolveCollision(&rectangle.body, &segmentList[segmentIndex].body, &ir); + float32 frameTimeRemaining = deltaTimeSeconds - copyDt; + + update(frameTimeRemaining, userData); + return; + } // Renderer renderer.render(); -- cgit v1.2.1