Hi everyone,

I'm developing realistic billiard game. For now I've finished for predicting collision time of Circle-Circle (Thank you for Leckie,W. and Greenspan, M. POOL PHYSICS SIMULATION BY EVENT PREDICTION II:).

The position as a function of time r(t)

ball radius = R, so When circle-circle collide,

|d(t)| = 2R ---> d(t)^2 = 4(R^2) and finally the equation will be A(X^4) + B(X^3) + C(X^2) + DX + E = 0

the quartic polynomial can be solved to get exact collision time.

But now I cannot find time of Circle and Line segment collision.

Could you help me create equation for predicting collision time of moving circle and static line segment? Thank you

Circle-Line Segment picture

Hi,

Do the balls only move in a linear way?

Just asking because there is a curve between the circle and the line.

If you know the circle's parametric path through space, you can do a curve-line intersection test and find the parameter value of intersections.

Add some details to cadjunkie's answer:

Assume the path of center is C(t) = (x(t), y(t)), line equation is L: ax+by=0, and the current time is t0.

"Translate" the line to find the intersection at t0, say it's P1(x1,y1).

Then at any time t, position of P1 would be P1(t) = C(t) + (x1-x(t0), y1-y(t0)) = (x1(t), y1(t))

Now solve the equation for t1:

a * x1(t1) + b * y1(t1) = 0

And t1 - t0 is the answer

Note we need special handling if line equation is y=0

Hi,

Do the balls only move in a linear way?

Just asking because there is a curve between the circle and the line.

Hi 3pic_F4il_FTW,

The balls are moving in non-linear. the path of the ball is,

r(t) = r0 + v0t + a0(t^2)

r(x,y) = current position of the ball at any time t

r0(x,y) = initial position of the ball

v0(x,y) = Initial velocity of ball

u0(x,y) = Initial relative velocity of the ball

Add some details to cadjunkie's answer:

Assume the path of center is C(t) = (x(t), y(t)), line equation is L: ax+by=0, and the current time is t0.

"Translate" the line to find the intersection at t0, say it's P1(x1,y1).

Then at any time t, position of P1 would be P1(t) = C(t) + (x1-x(t0), y1-y(t0)) = (x1(t), y1(t))

Now solve the equation for t1:

a * x1(t1) + b * y1(t1) = 0

And t1 - t0 is the answer

Note we need special handling if line equation is y=0

Hi HypnotiC and cadjunkie,

Thank you for your help.

I don't have a good knowledge for math and physics, but I'm trying.

My static line segment will not parallel to X-Axis or Y-Axis.

the trajectory of my circle (billiard ball) is,

r(t) = r0 + v0t + a0(t^2)

r(x,y) = current position of the ball at any time t

r0(x,y) = initial position of the ball

v0(x,y) = Initial velocity of ball

u0(x,y) = Initial relative velocity of the ball

I have questions about you help,

1. What you give me is the time of center of circle intersect line segment (not the radius intersect line)?

2. Could you explain me more about your equation P1(t) = C(t) + (x1-x(t0), y1-y(t0)) = (x1(t), y1(t)), what is x1 and y1?

Thank you.

1. What you give me is the time of center of circle intersect line segment (not the radius intersect line)?

You find the implicit line of the line segment \( ax+by+c=0 \), and since the circle's path is \( x(t) = a_xt^2+b_xt+c_x \) and \( y(t) = a_yt^2+b_yt+c_y \), you can substitute those into the line equation: \( a(a_xt^2+b_xt+c_x) + b(a_yt^2+b_yt+c_y) + c = 0 \). This can be easily factored into a quadratic equation with \(t\) as the independent variable. Solving the quadratic for \(t\), you can get the intersections of the circle's path and the static line segment. Since this is quadratic, you can get the possibility of two real roots (two intersections), one real root (curve is tangent to the line), or two complex roots (no intersections) depending on if the discriminant \(B^2 - 4AC\) is greater than zero, zero, or less than zero, respectively. The \(t\) values will be in terms of the circle's parametric path, so plugging \(t\) back in will yield the \((x,y)\) point of the intersection.

You find the implicit line of the line segment \( ax+by+c=0 \), and since the circle's path is \( x(t) = a_xt^2+b_xt+c_x \) and \( y(t) = a_yt^2+b_yt+c_y \), you can substitute those into the line equation: \( a(a_xt^2+b_xt+c_x) + b(a_yt^2+b_yt+c_y) + c = 0 \). This can be easily factored into a quadratic equation with \(t\) as the independent variable. Solving the quadratic for \(t\), you can get the intersections of the circle's path and the static line segment. Since this is quadratic, you can get the possibility of two real roots (two intersections), one real root (curve is tangent to the line), or two complex roots (no intersections) depending on if the discriminant \(B^2 - 4AC\) is greater than zero, zero, or less than zero, respectively. The \(t\) values will be in terms of the circle's parametric path, so plugging \(t\) back in will yield the \((x,y)\) point of the intersection.

Hi cadjunkie,

Thank you for your reply.

I think, your equation is analytical solution for finding collision time between point (center of circle) and infinite line?

How to make the equation (analytical) that can find collision time between circle (including radius) and line segment?

@Blackperl: I don't know if there's a single simple approach as with point-vs-infinite-line, but I've implemented "moving point vs moving capsule" by performing 4 sweep tests:

2x circle-vs-circle (for the query point vs the moving capsule's endpoints)

2x circle-vs-infinite-line* (for the query point vs the two sides/faces of the segment)

(*: you need a slight modification for these queries: when you find t (just like cadjunkie showed), check if the collision point at that time is on the segment at that time; if not, it doesn't count as a collision.)

Each of these 4 tests reports their earliest t, and the min() of those 4 t values is the time of intersection for point-vs-capsule.

If there's a simple "analytical"/direct way to solve this, I'd love to know

I have a feeling I don't need to do 2x point-vs-line, and instead I could solve for the times when the distance is r (instead of solving for when it's 0).. but I haven't thought enough about it yet.