An idea for an implementation of continuous collision detection of circles [closed]

Question

So I'm making a 2D pool game in OpenGL (you might've guessed as soon as I've mentioned collision of circles). I'm having a little trouble with collision detection. What I mean by that is that I have an algorithm that currently works but I'm thinking of improving it.

So far I've used discrete collision detection, disregarding the possibilities that it might not work at high velocities. However, I've noticed that I in fact sometimes do need the circles (pool balls) to travel at velocities at which the discrete collision detection might fail. The reason for that is that some of those velocities are quite realistic in a real-life game of pool (I've calculated that an average professional break shot in pool can make the ball travel as fast as six times the ball's diameter per 33 milliseconds which is the time interval that one frame lasts on 30FPS machines). Therefore in every such shot my discrete collision detection is very likely to fail.

This is the idea I've had:

The dashed circles represent the positions of the balls in the previous frame. The lines from them represent the velocity vectors and, obviously, the circles that they're connected to are their positions in the current frame.

One thing I would do immediately is check whether the velocity vectors are collinear in which case there's no need to check for any kind of collision. If they're not collinear, I'd find the intersection point of the line segments represented by the points of previous position and the next position (if they don't intersect I just disregard everything) . After that I'd manually translate the balls "before" the point of intersection (I was too lazy to actually compute where the balls would touch so I just put them somewhere near that point for the purposes of illustration, but it doesn't really matter). After I've done all that I would just let the discrete collision detection algorithm, which I already have, do the work.

Couple of things I'm worried about here:

(1) Since I have more than 2 balls on the table (16 to be precise) can the manual translation step somehow impact eventual collision of one of the balls that have been translated and some other, third ball? It seems to me like it shouldn't, but I'm not sure.

(2) On one hand I'm thinking that this might cause some glitching since I'm translating the balls "back" after I've already drawn them at their positions. On the other hand since this will only be happening at high velocities it might not matter that much. This also causes me to wonder whether I should do draw - collide or collide - draw. That is, should I use the principle I've described here (first draw the balls, then check whether they've been drawn too far) or maybe I should "look ahead", as in check whether the next position could cause problems instead of whether the previous position has caused them?

Not looking for any code, just ideas and thoughts.

Thanks in advance.

Answer 1

I think you should determine the "next collision point" in your whole 16-ball-and-table-border system and adjust your simulation 'Delta t" depending on it. Rendering should be de-coupled from this anyway, or it will show irregular ball movements... .

Some further thoughts:

1. Collinear velocity vectors do not mean there is no collision - if v1 != v2 ...
2. In good pool games you can define the 'hit point', where the queue hits the ball. Then "curvy" ball trajectories are generated, etc. etc.
3. Your system should also consider friction, therefore: v->0 over time. This should also affect your collision calculations.

Answer 2

I don't know if you just didn't write it or really intended not to do it, but in general it's now enough to check the velocity vectors for inersection. First off, the vectors might intersect but the balls pass the intersection point on different times, resulting in no collision. Second, you do not take the radius of each ball into consideration.

From my (limited) experience, contiuous collision detection is either done with a technique called conservative advancement, signed distance field or (which would apply for your case) solving for a mathmatical equation dependent on time $t\in[0,1]$. Even with bent trajectories you are able to do this.

Once you have solved for $t$ and computed all pair-wise collisions (all 16 balls with each other and possibly the edges in some way), you can sort them by their collision time $t_i$ (earliest collisions should be handled first) and solve the collision restrains with some phyiscal response. Because of the nature of continuous collision detection, you will not have an actual intersection where you would get the contact normal and penetration depth from. Usually you will have some distance of two balls that qualify (numerically) as a collision, like $d(B_1, B_2) < \varepsilon$. But there are mutliple easy ways to fix this, particularly for you scenario.

After you have solved all the collisions and updated all velocities, you have to repeat the whole process because there might now be different collisions between different balls. In theory, you would have to repeat this until all collisions have been properly solved. However, there might be cases where there are somewhat cyclic collisions (think Newton's cradle) and these will be tough to properly handle. Again, this is up to implementation but a good start (at least to avoid infite collisions) would be to use a limited number of iterations per frame for this.

Then, after finishing all collisions for one frame, you finally can render you scene.

Good luck with your project! I know how tough it can be to implement a proper collision detection, let alone a continuous collision detection.