Jump to content

  • Log In with Google      Sign In   
  • Create Account

Colliding position


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 ryt   Members   -  Reputation: 294

Like
0Likes
Like

Posted 19 January 2014 - 02:23 PM

I have two objects and I want to find when will they collide. Lets say first target has position p0, velocity v0 and the time it will arrive at desired position is t0. Similar for the second target it has position p1, velocity v1 and the time t1.

The general formula for speed with constant velocity is:

 

p = v*t + p0

 

So if we try to find their colliding position p0 and p1 should be equal at desired time so p0 = p1.

 

v1 * t1 + p1 = v2 * t2 + p2

 

t2 = v1 * t1 + p1 - p2 / v2

 

t2 is the time that will second object arrive at colliding position.

I wonder how we can calculate this ? On the right hand side of last equation we have vector division. So since t2 is a scalar on the right hand side there also must be a scalar. So I think we should take the magnitude of vectors on right side and divide them.

What to do in these situations when we have a division of two vectors ? Is this approach correct one ?


Edited by ryt, 20 January 2014 - 01:42 PM.


Sponsor:

#2 richardwagner   Members   -  Reputation: 104

Like
0Likes
Like

Posted 19 January 2014 - 03:23 PM

Generally, you can not divide vectors. In your particular case, you should take t1 = t2 (because object collision is equivalent to that objects are at same place in same time). So 
v1 * t1 + p1 = v2 * t1 + p2
t1 * (v1 - v2) = p2 - p1
Hence you only need to check if vectors a = (v1 - v2) and b = (p2 - p1) are collinear. This can be done in two-dimensional space by computing dot product : a*B, where B is normal vector to b. More simply, if a = (a1, a2) and b = (b1, b2) you should check if a1 * b2 - a2 * b1 = 0 with necessary accurancy, or just if a1 / a2 = b1 / b2. 


Edited by richardwagner, 19 January 2014 - 03:24 PM.


#3 jjd   Crossbones+   -  Reputation: 2075

Like
0Likes
Like

Posted 20 January 2014 - 09:29 AM

I have two objects and I want to find when will they collide. Lets say first target has position p0, velocity v0 and the time it will arrive at desired position is t0. Similar for the second target it has position p1, velocity v1 and the time t1.

The general formula for speed with constant velocity is:

 

p = v*t + p0

 

So if we try to find their colliding position p0 and p1 should be equal at desired time so p0 = p1.

 

v1 * t1 + p1 = v2 * t2 + p2

 

t2 = v1 * t1 + p1 - p2 / v2

 

t2 is the time that will second object arrive at colliding position.

I wonder how we can calculate this ? On the right hand side of last equation we have vector division. So since t2 is a scalar on the right hand side there also must be a scalar. So I think we should take the magnitude of vectors on right side and divide them.

What to do in these situations when we have a division of two vectors ? Is this approach correct one ?

 

I'm not sure what you are trying to solve for here. There are two ways that this problem can have no solution: 1) the lines that the objects are moving along do not intersect and 2) that they arrive at the target location at different times.

 

The way that you have phrased the problem suggests that both of the objects are moving towards a common location. So they should intersect. However, the velocities in your equations are arbitrary so mathematically, this intersection is not guaranteed. To ensure that the objects do intersect you should construct the velocities of the objects so that they are oriented towards to target location. You can do this using the starting position of the object and the target position,

 

v1 = s1 * (p1(0) - p0) / |p1(0) - p0|

 

where 's' is the speed of the first object. The equation of motion for the first object becomes,

 

p1(t) = t * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0)

 

The time it takes for object 1 to get to the target is independent of object 2 so we can for 't' directly from this equation,

 

p1(t') = p0 = t' * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0)

 

0 = t' * s1 * (p1(0) - p0) / |p1(0) - p0| + p1(0) - p0

0 = (t' * s1 / |p1(0) - p0| + 1) * (p1(0) - p0))

 

Assuming that p1(0) != p0,

 

0 = t' * s1 / |p1(0) - p0| + 1

 

Or,

 

t' = -|p1(0) - p0| / s1

 

Now, that makes sense; it is negative because I defined the velocity direction away from the target and there is no solution if s1 == 0, which is the same as if the object had no speed.

 

If you want to know if the two objects arrive at the same time, then you would have to have,

 

|p1(0) - p0| / s1 = |p2(0) - p0| / s2

 

However, this means that speeds of the objects have to be chosen just right depending upon their starting position in order to collide. If the speeds of the objects are not variables that you are trying to solve for, and you still want to determine if the objects will collide with one another, they problem becomes a little harder because you actually have to find the distance between the objects as a function of 't' and they collide if that minimum distance is less than some threshold. Assuming that the objects are spheres, that problem can be written as,

 

let x(t) = p1(t) - p2(t)

 

To find the time of the collision between the objects you have to solve,

 

x(t)^2 - r^2 = 0

 

where 'r' is your threshold distance (the sum of the radii of the objects if they are spheres). Expanding this equation out gives a quadratic equation,

 

(v1 * t + p1(0) - v2 * t - p2(0)) . (v1 * t + p1(0) - v2 * t - p2(0)) - r^2 = 0

t^2 * (v1 . v1 + v2 . v2 - 2 * v1 . v2) + t * (v1 . (p1(0) - p2(0)) - v2 . (p1(0) - p2(0))) + (p1(0) . p1(0) + p2(0) . p2(0) - 2 * p1(0) . p2(0)) - r^2 = 0

 

Lots of terms there (definitely check my working). However, the only thing that is unknown is 't', so we just have to solve,

 

A * t^2 + B * t + C = 0

 

Like any quadratic equation, there can be 0, 1, or 2 solutions. 0 solutions implies that there is no collision at all, 1 solution implies that the objects touch at one point in time, and 2 solutions means that the objects collide for a finite period of time.

 

-Josh


--www.physicaluncertainty.com
--linkedin
--irc.freenode.net#gdnet


#4 ryt   Members   -  Reputation: 294

Like
0Likes
Like

Posted 20 January 2014 - 01:41 PM

Well my original question was about how to deal with the situation when we have vector division. In this case I took the magnitude of resulting vectors like:

 

t2 = |v1 * t1 + p1 - p2| / |v2|

 

So I wonder if this is the right way to use the magnitude and to get time t2 ?

 

In my example the two objects always collide since their final positions are same like p1 = p2 where p1 is final position of first object and p2 is final position of second object.

If first object has some speed at some time t1 will arrive at position p1. So if their final positions of two objects are the same p2 is also known and we can find v2 and t2. If we set v2 to some speed and direction all we need to find is t2. This is the time that is in last equation.

I made a mistake in the original post. I meant to say p1 = p2.


Edited by ryt, 20 January 2014 - 01:42 PM.


#5 DT....   Members   -  Reputation: 487

Like
0Likes
Like

Posted 20 January 2014 - 06:30 PM

I think you should be solving:

 

p0 = p0 + v0 ( T )

p1 = p1 + v1 ( T )

 

T = Dot ( n, p1 - p0 )  / 

      Dot ( n, v0 - v1 )

 

where   n = Normalize( p1 - p0 )

 
 

instead of 

 

p0 = p0 + v0 ( T0 )

p1 = p1 + v1 ( T1 )

 

Otherwise, you’re probably looking for a “ray to ray” intersection test.

 

Also, once you find T, p0 and p1 will be close, but never exact.  32-bits of precision can cause nightmares…



#6 ryt   Members   -  Reputation: 294

Like
0Likes
Like

Posted 21 January 2014 - 01:28 PM

I don't understand. Why we should take T0 = T1 that is compute it for some T. The two objects will have the same position and it will take different times to get there. That is if first object travels faster or is closer to the collision point than obviously T0 < T1.

 

Why did you took the Dot and normalized the vectors ?



#7 Buckeye   Crossbones+   -  Reputation: 4880

Like
1Likes
Like

Posted 23 January 2014 - 09:14 AM

Since you qualified your question to specify that collision is guaranteed, then yes, you can use the magnitude of the vectors. IF they both will arrive at final position p, then v0 and v1 must be coplanar, and it can be assumed that time = distance / speed.

p = p0 + v0 * t0; // p0 is the initial position of object 0
p - p0 = v0 * t0;
t0 = mag(p-p0) / mag( v0 );

t1 (similarly) = mag(p - p1) / mag( v1 ); p1 is the initial position of object 1

time to collision = greater( t0, t1 )

Caution: if the velocity of one or both objects is away from p, you'll get erroneous results. I.e., one or both objects will arrive in negative time.


Edited by Buckeye, 23 January 2014 - 10:08 PM.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#8 DT....   Members   -  Reputation: 487

Like
0Likes
Like

Posted 23 January 2014 - 06:00 PM


I don't understand. Why we should take T0 = T1 that is compute it for some T. The two objects will have the same position and it will take different times to get there. That is if first object travels faster or is closer to the collision point than obviously T0 < T1.

 

 

http://fivedots.coe.psu.ac.th/Software.coe/241-213/F.Dunn,%20I.Parberry%20-%203D%20Math%20Primer%20for%20Graphics%20and%20Game%20Development.pdf

 

Page 283






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS