How can I solve niche collision cases between circles and insides/outsides of AABBs or arcs?

Question

I am trying to create a game with some interesting geometry. Literally all the geometry that is involved are the circles that move large distances per frame, and the edge of an iPhone X display, which I am going to approximate using the following shapes:

• It is worth noting that instead of the inside quarter eclipse one could do another "outside of AABB" and another "inside of quarter-circle"

Here's the problem: These collision detections are very niche and I can't find anyone doing them anywhere. In fact I can't even find the algorithm to collide these fast moving circles with the outside of an AABB let alone the inside of one. And no formulas for circle collisions allow for a quarter circle collision to be calculated. Everything needs to be hyper efficient so I think using Bézier curves/complex shapes is really not an option.

How do I develop or find the algorithms to do these types of collisions?

Have I perhaps overthought everything? Would Bézier or some other spline curve be easier here? I suppose I made a bit of an assumption that that would be expensive to calculate. But maybe is that the answer?

Keep in mind whatever I do needs to work for over 1 thousand entities to collide with this shape in real time.

Answer 1

I'd argue you don't need anything niche here at all.

A disc colliding against any shape is equivalent to a point colliding with that same shape "inflated" by the radius of the disc.

Since your collision boundary is a closed path, this maps your input sequence of line segments and circular arcs to just another sequence of lines and circular arcs. You don't need any more exotic shapes or additional end caps.

To handle high speeds, we can use continuous collision detection, by sliding the point along a ray.

So, your situation reduces to:

• ray vs line segment
• ray vs circle

Two of the most bread and butter checks. So, I won't rehash the details of how to perform these raycasts here — you can find excellent answers & articles about high-performance implementations of these checks elsewhere.

Instead I'll focus on a few details:

• For concave circles: the quadratic formula used in your ray-circle intersection routine can find two roots. Conventionally, it will return the closer of the two (smaller time-to-impact t). To collide against a concave circle, take the farther root instead (larger t)

• For quarter-circle arcs: since your quarters are axis-aligned (and remain so after inflation), you don't need any angles or trig. Just check the signs of the x & y components of rayIntersection - circleCenter, discarding collisions in the other quadrants.

• Computing the original collision info: once you have your intersection between the ray and the inflated shape (what's called the Minkowsi sum of the original shapes), here's how that maps back to a collision between the original disc & original boundary...

Collision UnMinkowski(Collision minkowski, float discRadius) {
    // We can have up to two collision normals
    // if our ray struck a sharp corner exactly.
    Collision actual = new Collision(pointCount = minkowski.pointCoint);

    actual.timeOfImpact = minkowski.timeOfImpact;
    actual.discPositionAtImpact = minkowski.contactPoints[0];

    for(int i = 0; i < actual.pointCount; i++) {
        actual.normals[i] = minkowski.normals[i];
        actual.contactPoints[i] = minkowski.contactPoints[i] 
                       - discRadius * minkowski.normals[i];
    }

    return actual;
}

Answer 2

You need to represent the iphone as a rectangle where the 4 corners are the centers of the 4 circles. We know a point is inside the iphone's shape when the distance from this rectangle is less than the radius of the circles. The formula for the distance based on the center of the rectangle c, the position of the point p, the side lengths of the rectangle s and the radius of the circles r:

$$\vec d(|p_x-c_x|, |p_y-c_y|)-\frac{s}{2}$$ $$dist = \sqrt {max(d_x, 0)^2+max(d_y, 0)^2} - r$$

Now the only thing you need to do is get the distance from the center of the circle to the iphone, if it's less than the radius of that circle, then they are colliding.