Thread: Equation rearranging?

Posted this else where in the forum and haven't got a reply, I have edited the original post so this is the only thread about it. Here goes:

I am trying to find the simplest way of calculating the exact instant that two spheres collide.

Each sphere has an initial position, initial velocity, acceleration and radius. I am working in 2D.

This will be used in a computer program, so I apologize if some of my math looks more like code. I am also trying to avoid using functions such as square root as they are computationally expensive.

I can get an equation that will tell me the distance between the two spheres at a given time, but I cannot re-arrange to get the time at a given distance.

After doing research on the internet I have come up with the following.


It is easier to assume that one sphere is stationary at the origin so we end up with one set of relative vectors.

relative position (rP) = sphere 2 position - sphere 1 position
relative velocity (rV) = sphere 2 velocity - sphere 1 velocity
relative acceleration (rA) = sphere 2 acceleration - sphere 1 acceleration

We can also add the two radii so we are then trying to work out when the point is sumRadii from the origin.

The distance between the two points is calculated using Pythagoras's theory.

d^2 = x^2 + y^2

From the equations of motion we know:

s = ut + 0.5at^2

therefore:

finalPosistion = initalPosition + initalvelocity*t + 0.5*acceleration*t^2


For my scenario it would be:

d^2 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2

Assuming the spheres are not touching to start with, when d^2 = sumRadii^2 we know the spheres have collided. This means we can rearrange the equation slightly to give:

0 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2 - sumRadii^2

As the collision time.

I have tried using both my head and derive (a maths program that has been working for 18 hours solid) to give me a function for t but I cannot figure it out.

I would be very grateful if you could help me solve the last stages of this problem.

Thanks in advance,

Rob

If I understand correctly:

You are simulating the motion of two spheres and want to know if and when they collide. Rearranging the equations of motion you have established will give you the exact time of collision (if it is possible to do algebraically). However is this actually what you are writing a program to do? It looks like your program is meant to be a simulation of the motion, and solving for t will not aid you in this simulation.

For computations involving time you will need to treat t as a "time step" of some small duration (say .01 seconds). You can approximate the motion of the spheres to a very high degree, depending on the size of your timestep. You can keep a running total of time elapsed and halt when the spheres collide. This will give you an approximate solution of arbitrary accuracy (within computational limits) for the time they collide.

While collision = false
- t=0 the program initializes, each ball has initial position, velocity and acceleration.
- timestep elapses: t=t+.01, calculate position, velocity, acceleration.
- Check for collision
Loop

What do you think?

That's exactly what I need to do, however it will be used for scientific visualization so it needs to be as accurate as possible.

I am stepping time by 20ms (to give 50 fps) and calculating the new positions which is easy, however I need to know if during that 20ms the two sphere will have collided and when. This way I can simulate the collision and ensure that the spheres are in the correct place. Of course this will be come more challenging when more then 2 spheres are involved but I already have a plan to implement it.

If I neglected acceleration things would be far easier.

0 = (rPx + (rVx * t))^2 + (rPy + (rVy * t))^2 - sumRadii^2

rearranged gives:

0 = (t^2) * (rVx^2 + rVy^2 ) + (t) * 2(rPx·rVx + rPy·rVy) + (rPx^2 + rPy^2 - sumRadii^2)

Which is a quadratic and will give two solutions, which-ever is lowest will be the collision. If this were the case I would already have a simulation.

However as my simulation will model accelerations, this means the resulting equation has t^4, t^3, t^2 and t. I think it needs treating as a polynomial but I don't know much about them.

I need to get the equation in my first post so that I can calculate the roots, quickly and easily by supplying the rest of the data. If there is a quick check I can use to decide if a collision will happen in the time step it would help make my simulation quicker, as I would only calculate the roots if I knew they collided.

Perhaps using the derivative of the equation would work?

d^2 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2

As I believe that would give me the minimum distance within the time step? So if it is less then sumRadii^2 I know they collide within the step.

Since you don't express a force of attraction in your equations, the balls will only collide if your constants have specific values. I wrote this in Matlab and couldn't get the balls to collide except when:

rpx=rpy
rvx=rvy
rax=ray

Substituting this into your equation means you are choosing your coordinate axis so that the x coord is along the distance between the balls. Then your equation is solvable.


After experimenting further I have found other values that lead to solutions, but not just any value of the constants will give solutions. It seems to me something is wrong with your assumptions, because if there is no force acting to attract the balls, they need not always collide.

Are they moving so fast/the spheres are so small that it is possible they passed through each other within 1 timestep?

I used your equation and entered values of t from 0 to 50 , then plot to see about where it crosses the axis. Only for certain combinations of values will the function cross the axis.

For example:

>> r1 = 1; r2 = 2; rPx = 40; rPy = 41; rVx = 3; rVy = 4; rAx = 5; rAy = 5;
>> f=@(t)(rPx+(rVx*t)+(rAx*0.5*t.^2)).^2+(rPy+(rVy*t) +(rAy*0.5*t.^2)).^2-(r1+r2)^2;
>> plot([-50:.001:50],f([-50:.001:50]))

Originally Posted by iknowone

Are they moving so fast/the spheres are so small that it is possible they passed through each other within 1 timestep?

Yes, it is possible the spheres would be able to completely pass through each other in a single step.

Originally Posted by spammanon

Since you don't express a force of attraction in your equations, the balls will only collide if your constants have specific values. I wrote this in Matlab and couldn't get the balls to collide except when:

rpx=rpy
rvx=rvy
rax=ray

Substituting this into your equation means you are choosing your coordinate axis so that the x coord is along the distance between the balls. Then your equation is solvable.

After experimenting further I have found other values that lead to solutions, but not just any value of the constants will give solutions. It seems to me something is wrong with your assumptions, because if there is no force acting to attract the balls, they need not always collide.

I used your equation and entered values of t from 0 to 50 , then plot to see about where it crosses the axis. Only for certain combinations of values will the function cross the axis.

For example:

>> r1 = 1; r2 = 2; rPx = 40; rPy = 41; rVx = 3; rVy = 4; rAx = 5; rAy = 5;
>> f=@(t)(rPx+(rVx*t)+(rAx*0.5*t.^2)).^2+(rPy+(rVy*t) +(rAy*0.5*t.^2)).^2-(r1+r2)^2;
>> plot([-50:.001:50],f([-50:.001:50]))

You are right in saying that they will only collide given certain variables. Also you are also correct in assuming they may never collide.

Am I right in thinking but using differentiation we are able to get the maximum and minimum values for a function given a range of inputs?

For instance, given that:

x = rPx + (rVx * t) + (rAx * 0.5 * t * t)
y = rPy + (rVy * t) + (rAy * 0.5 * t * t)

distance from the origin squared = x pos squared + y pos squared

d^2 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2

We could (given a set of values for rPx, rPy, rVx, rVy, rAx, rAy) accurately calulate the maximum and minimum values of d^2 in a range of t values (0 to 0.02).

From this we can say the sphere have collided if the sign changes from min to max or the min or max are less then sumRadii^2 away from zero.

So theoretically we could use that to determine if the spheres will collide?


Once we know if the sphere collide or not we can use the roots of the other equation to figure out when.

0 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2 - sumRadii^2

Expanding this by t will give a polynomial or sorts I believe which can then by used to figure out the time that the collision will occur.

The polynomial is (separated to make it more readable):

0 =
t^4 * (rAx^2 + rAy^2) +
t^3 * 4 * (rAx * rVx + rAy * rVy) +
t^2 * 4 * (rAx * rPx + rAy * rPy + rVx^2 + rVy^2) +
t * 8 * (rPx*rVx + rPy*rVy) +
4 * rPx^2 + 4 * rPy^2 - 4 * sumRadii^2

So given that I know all the variables and we know the range of t, I should be able to find the roots and therefore collision times?

Unfortunately once its bigger than a quadratic, I haven't a clue so any help on this part of the problem would be useful too.

You could use a numeric approximation technique to find the roots of the polynomial such as Newton's method or the bisection method.

Managed to find a quartic equation solver that explains the method it uses. Prototyping in excel and will port it over to c++ when I am happy with it.

Solving Quartic Equations

So if someone can give me a hand with the differentiation, I should be all set. Is there anyone in particular who it may be worth talking to?

That seems like a huge mess. You only care about real solutions so why not just use Newton's method to approximate the solution. It converges very quickly and to within arbitrary accuracy.

What about differentiation do you need to know? The quartic solver doesn't require differentiation.

To differentiate the polynomial multiply each coefficient by the corresponding exponent on t and subtract one from the exponent.

at^4 ---derivative---> 4at^3

Thanks for the info, I will have a look for site that explains Newton's method clearly and see which is quicker to execute. No harm in having more than one option to use.

I was going to use differentiation to figure out if a collision occurred and if it was worth solving the quartic. It may also be worth adding some other get out early checks in as well. If you can think of any it would be appreciated.

Originally Posted by langers2k

Am I right in thinking but using differentiation we are able to get the maximum and minimum values for a function given a range of inputs?

For instance, given that:

x = rPx + (rVx * t) + (rAx * 0.5 * t * t)
y = rPy + (rVy * t) + (rAy * 0.5 * t * t)

distance from the origin squared = x pos squared + y pos squared

d^2 = (rPx + (rVx * t) + (rAx * 0.5 * t * t))^2 + (rPy + (rVy * t) + (rAy * 0.5 * t * t))^2

We could (given a set of values for rPx, rPy, rVx, rVy, rAx, rAy) accurately calulate the maximum and minimum values of d^2 in a range of t values (0 to 0.02).

From this we can say the sphere have collided if the sign changes from min to max or the min or max are less then sumRadii^2 away from zero.

So theoretically we could use that to determine if the spheres will collide?

Newton's method approximtes a function by its tangent line at a point and uses the root of that tangent line to guess what the actual root is. You then find the tangent line of the function at the this approximate root and repeat. This method is not guaranteed to converge is the function is changing directions wildly over short intervals and if your initial guess is "reasonably close" to the actual root, but is more efficient than bisection method.

So calculate the derivative of the function at your first guess . This is the slope of the tangent line to the function .

Then calculate your next guess:

Iterate until the change in your guesses is smaller than your accuracy threshold. The above recursive definition of is easy to derive from the definition of a lines slope.

Bisection:
You can also use a bisection method. Guess a value where and a value where . Find the value of the function at the midpoint: Redefine your end points appropriately so that the root is still contained within the interval and repeat.

Differentiation:
A polynomial will have a local max or min where its derivative vanishes, the second derivative at that point will indicate whether it is a max or a min. Positive second derivative means the function "opens up" (min), negative second derivative means the function "opens down" (max).

Right, I now have a function that will give me the closest root to 0 using the Newton–Raphson method (I think).

Is there any way to get the closest positive root? Or would I need to change the initial guess value to give me something positive? At the moment the initial guess is 0 (hence it returns the closest root to 0 right?), as I know t lies between 0 and 0.02 would I be better starting at 0.01?

Getting a sense of the shape of the polynomial will help you make the best initial guess. If the polynomial has multiple roots or changes direction wildly it is possible that Newton's method may enter an orbit around the root, never converging or it may converge on a root other than the first one.

You could take "small steps" recording in what interval the function changes sign to get a good initial guess:

x0=0
step = 1/n
x1 = x0+step
DO
IF (f(x0) > 0 and f(x1) < 0) or (f(x0) < 0 and f(x1) > 0) THEN
DEFINE initialGuess = x_0, BREAK
ELSE x0 = x1, x1 = x1+step
LOOP

Again this may step over the interval in which the function is negative (if 1/n is too large).