Solving obtuse interior corner collisions

Question

I'm having some trouble solving collisions in obtuse interior corners.

In the above image, the black circle is the initial position, the red is the projected movement (straight into the corner), the green is the position after solving the first plane (by moving the circle along the plane normal by the amount of penetration), and the blue the after solving the second. On the left, the right plane is solved first. On the right, the bottom plane is solved first.

The problem is apparent in both images: resolving the collisions results in a gap between the circle and one of the planes when it should ideally rest against both of them.

Square corners will result in a correct solution in a single iteration and acute corners will eventually reach a solution after several iterations, but obtuse angles present this problem. Is there some other method, something I'm missing, or is this just one of this acceptable inaccuracies?

Answer 1

There is an alternate way to think about solving this. You can do a transform by offseting the lines by radius of your circle then the solution is same as intersection of 2 lines.

Image 1: You can convert the problem to line intersection testing of lines A and B.

This also makes general intersection testing easy as you do line to pillshape testing. You can even cache the offsets if you wish. This makes it also obvious for collision testing that the ball would probably not hit the corner on a straight move but instead slightly off corner as was pointed pointed out in the comment section. But that may be besides the point.

Image 2: the intersection wont be the corner though. But yes it may then slide if its sticky etc.

Anyway weather this is easier, faster or convenient on you or not is another thing. If you make a billiard ball game then it might. Its just that one of offset, line intersection or pill collision is often already written in whatever your using and it comes sometimes handy in constrained environments (like say Adobe Illustrator and Inkscape).

PS: offseting lines is just a vector move rotated 90 degrees from lines direction. (you can also use magnitude of a corss product etc.)

Answer 2

I assume that you want a solution for collisions in general, which also works well for interior corners.

When resolving a collision against one plane, do not move the circle perpendicular to the plane. Instead, move it back along its path until it does not collide with the plane. The distance along the path will be

$$d = r \sec \theta = \frac{r}{\cos \theta},$$

where \$r\$ is the radius of the circle and \$\theta\$ is the angle between the plane normal and the circle.

Then, find the component (projection) of the circle's velocity which is perpendicular to (towards) the plane, subtract that from the total velocity (or a bit more if you want a bounce), and continue simulating the remaining amount of the motion in the current timestep (a sliding along the plane).

This is a simple form of “continuous collision detection” — we can see this process as finding the time at which the collision happens. (In fact, you'll need to do that too to figure out how much remaining time there is for the second step. You can compute it from the distance moved back and the velocity.)

When you hit the second plane, you can just do this again, but there's a catch: you'll end up simulating the trajectory as if the ball hit them in succession, and the ball will slide out of the corner slightly (as if it had hit a curve and slid around it) in some direction. This is almost the same as your original gap, except it is in velocity rather than position, so it might be more acceptable. If you want it to be perfectly stopped, you'll need to include some time or distance threshold for "these two successive collisions were actually at the same moment" and decide that sliding into the second plane just stops the ball instead of letting it slide further.

(Also, in case of acute corner angles, don't iterate this more than two steps, or 3 steps in 3D; it won't make further progress and you don't want to get stuck in an infinite loop.)

In any case, this procedure will ensure that the circle never enters a plane except slightly, due to floating-point rounding error. You'll still need resolution for in case the circle does end up in such intersecting cases, though.

Answer 3

To find the position where the circle is resting against both planes, you could use following approach:

We define the line k which is the bisector of the angle between g and h. Every point on line k has equal distance to g and h, so we know that the sought after point must lie on the line k. To calculate the distance from the corner point to the sought after point, we can use trigonometry. We first construct the right-angled triangle a, b, c:

Since α is a right angle and we already know that β is half the angle between g and h, we can use the trigonometric function

$$sin(\theta) = \frac{opposite}{hypotenuse}$$ $$hypotenuse = \frac{opposite}{sin(\theta)}$$

to determine the hypotenuse. If we fill in our values we get the formula

$$a= \frac{b}{sin(\beta)}$$

By moving from point B along the line k by the amount a we get the sought after position C. This approach works for obtuse angles as well as for acute angles.

Answer 4

I am guessing what you want to simulate is "the ball is moving in a particular direction. If it runs into a barrier, it will slide along the barrier. It will never move against the direction it is moving".

To solve this problem, what I would do is first pretend my two lines I am colliding with are infinitely long. Each line is described as some point \$p\$, a unit vector \$u\$, and a range of multiples of that unit vector along the line \$\lambda\$: \$p + \lambda u\$.

The ball's movement would be described as a parameter of \$t\$. Lacking any obstruction, the center of the ball would be at position \$x_0 + t v\$ after \$t\$ time.

Then I solve for "for what \$(t, \lambda)\$-values would my ball cross those infinite lines".

Solving for "I'm (almost) parallel to the line" is one sub-problem. For non-parallel trajectories we can find when the center crosses the line, and then work out by "backtracking" when the circle did.

We can project our ball's velocity along the line with a simple dot product: \$v . u\$, and its normal velocity via the cross product \$v x u\$. Divide the magnitude of the cross product by the ball's radius to say how long ago (in \$t\$ units) that the ball first touched the line. To find the difference between the center collision and the first time the ball crossed it in \$\lambda\$, multiply the delta-\$t\$ calculated by \$v . u\$.

You now have an interval along the infinite line where your ball is within its radius of the line, as well as a time interval when this happens. You actually want a ball-line segment intersection, but this is a good start.

If you aren't worried about hitting the ends of the line segments (and if you "know" you are going into a corner like that, this holds), you can skip the line segment problem.

If you are worried, you have to do ball-ball intersections on the end of the line segments, and prune your \$t\$ and \$lambda\$ values based on that.

Usually you only care about when you first hit the line, as the universe changes when you do. So take the minimum positive t in that interval. (if it is 0, it means either you are touching the line or are overlapping with it).

Starting at that time point \$t\$ you will now be restricted to sliding along the line you are touching. Be careful! If you want to model "being shoved along a certain path", simply recursively solving with this new direction will lead to strange bounces. You may, on the other hand, want this -- maybe you want running into a "circular turn-around" could cause your ball to spin around and fly in the other direction.

Assuming you don't want this, you need to treat this as a constraint on your velocity, not a new velocity. This constrained vector (by the line) follows the line (until it longer collides with it). And you compare against all other lines in the universe.

Use the same algorithm to find out what other lines you run into, but when working out your end velocity apply each line as a constraint, not a full redirection; don't take initial velocity, deflect by first constraint, then deflect the result by the 2nd (and 3rd etc) unless you are playing billiards.

Instead you have a velocity vector and a bunch of "you can't go in this direction" constraints.

Given the angle of the balls movement, each constraint will either be on the left or the right (ie, it is hitting the ball on its left side, or its right side, as it moves along). If you have a constraint on both sides your ball stops. If you don't, you only care about the greatest constraint active, and you apply it.

This lets you hit a line on your right, then a line that pushes you even further on the right. Only when your left side hits a line do you stop.

To deterimine left vs right, look at the time of collision; the center of the ball and the point on the line the ball's radius touches. Those will form a line of length ball radius that is perpendicular to the vector of travel of the ball, and avoids a numerical rounding error problem (your ball is touching 2 lines almost completely parallel on one side. A floating point error could put them on opposite sides if you aren't careful.)