Vector intersection

I can't quite figure out how to calculate the intersection of two vectors mathematically. (The closest I could find was this, but it uses the brute-force method, which I'd prefer not to do. It has a good description of the problem, however, so you should read it in addition to my description, which is probably hard to understand.)

Here's a description of the problem. An object (let's call it T, for target) is moving some distance away from you. You have another object which moves at a fixed speed (Y, for you). You have to aim this object so that it will collide with T (the point of intersection, I). (Basically you need to figue out the angle at which to fire Y.) You know only: the distance between Y and T (YT); the velocity (speed (delta TI) and direction) of T; and the speed at which Y will travel (delta YI).

Code:

^ I <--------\-- . T \ | \ | \. Y

I managed to solve it for the restricted case where T is travelling perpendicular to Y:

Code:

TI = sqrt(TY/((delta YI/delta TI)^2-1))

However, the above formula relys on Pythagoras' Theorem, which isn't true for non-right angle triangles.

The other two cases I have been able to solve are when T is travelling directly away from Y and when T is travelling directly towards Y. This leaves two cases which aren't handled: T is travelling at an acute angle towards Y (which has the potential for two intersections), and T is travelling at an obtuse angle away from Y. And of course, it is possible that Y cannot intersect with T at all, if it can't go fast enough.

Can anyone come up with the general formula for this?

Do you know the cosine rule.

Yes, I'm almost certain that the solution involves the law of cosines and the quadratic formula, but I can't figure it out.

A vector is only a direction and a magnitude, if you want to find an intersection point, you need to know the points at which the vectors originate.

Two parametric rays:

r1*t1=p1+(t1*d1)
r2*t2=p2+(t2*d2)

Solve for t1 and t2 to find the point of intersection.

r1(t1)=r2(t2)
p1+t1(d1)=p2+t2(d2)

t1=((p2-p1) cross d1) dot (d1 cross d2)/(magnitude(d1 cross d2)*magnitude(d1 cross d2))

If parallel: cross of d1 and d2 is the zero vector
If skew (crossing but not on same plane): p1(t1) and p2(t2) are the points that are closest. Examine the distance between p1(t1) and p2(t2) to determine if they actually intersect in your world. This means you must use a fudge factor due to floating point imprecision.

I highly recommend 3D Math Primer for Graphics and Development and this is where the above information comes from.

A site that may help:
http://geometryalgorithms.com/Archiv...rithm_0102.htm

Okay, I didn't quite get that, but I'll look into that book.

If radius = 0 then they are two lines.

PHP Code:

double TimeOfSphereIntersection(Vector3 &PStart,Vector3 &PEnd, Vector3 &QStart, Vector3 &QEnd, float PRadius, float QRadius, float Epsilon) { Vector3 A = PStart - QStart; Vector3 B = (PEnd - PStart) - (QEnd - QStart); //relative velocity double ASq = A.BasicLength(); double AdotB = DotProduct(&A,&B); double AdotB_sq = AdotB * AdotB; double BSq = B.BasicLength(); double iBSq(0);// = BSq > .0000001f ? (1/BSq) : 1.0f; //Inverse of |B| squared if(BSq > .000001f) { iBSq = 1/ BSq; } else //if b_squared is zero, then they cannot collide (both stationary or moving in same direction) { SWEPTSPHEREDEBUG( trace << "BSquared is zero, setting to 1.0f" << "\n"; ) return -3.0f; // iBSq = 1.0f; } double sep_dist = PRadius + QRadius + Epsilon; double sep_dist_sq = sep_dist * sep_dist; double closest_sep_dist_sq = ASq - (AdotB_sq * iBSq); if(closest_sep_dist_sq > sep_dist_sq) { SWEPTSPHEREDEBUG( trace << "closest_sep_dist_sq > sep_dist_sq, returning -1" << "\n"; ) return -1.0f; } double under_root = AdotB_sq - (BSq * (ASq - sep_dist_sq)); if(under_root < 0) { SWEPTSPHEREDEBUG( trace << "negative under radical, no sphere intersection, returning -2" << "\n"; ) return -2.0f; } double root = sqrt(under_root); double time = (-AdotB - root) * iBSq; if(time >= 1.0f) { SWEPTSPHEREDEBUG( trace << "Fishy value of time, greater or equal to 1.0f: " << time << "\n"; ) SWEPTSPHEREDEBUG( trace << "Root: " << root << "under_root: " << under_root << "AdotB: " << AdotB << "\n\n"; ) } else { SWEPTSPHEREDEBUG( trace << "Value of time not fish, good" << "\n"; ) } return time; }

Bob's example is what you would use in an engine. Instead of finding the point of intersection you would find the time interval.

Thanks, I can figure out how to calculate where two vectors will intercept if I know the direction and magnitude of each; however, with my problem above, one of the vectors (Y) has a fixed speed, but not a fixed direction. I'd like to be able to calculate its direction. It's like having a windup car hit another windup car; the speed of the car you release is fixed, the best you can do is aim it in the right direction. (Although that analogy is a little different, because with it you could wait before releasing Y; in my situation, Y must be released.)

[edit] Finding the time interval is like having two vectors and figuring out where they will intercept, which is not what I'm looking for. (I'm looking for the angle to fire Y at to have it hit T.) It's the method used in the thread linked to in my original post. [/edit]

There are a couple more uber simple ways of doing this, albeit with some restrictions.

One way is to simply choose the time you want the cars to hit at, e.g. you fire the target in a direction T (or whatever you called it), and you want to hit it in one second. You calculate where it will be in one second, then aim for it. This means that you have to choose the speed of the firing vector.

If you want to fire a projectile at an object from a 3D point called Source to a 3D point called target you need to expand what you would do in 2D to accomplish this to 3D.

This does not tell you, however, how to turn to face the vector. That must be calculated using 3 dot products if I remember correctly.

Code:

void Compute2DVectorTo(point2D Source,point2D Target,point2D &Result) { float diffx=Target.x-Source.x; float diffy=Target.y-Source.y; float length=sqrt( (diffx*diffx)+ (diffy*diffy)); Result.x=diffx/length; Result.y=diffy/length; } void Compute3DVectorTo(vector3 Source,vector3 Target,vector3 &Result) { float diffx=Target.x-Source.x; float diffy=Target.y-Source.y; float diffz=Target.z-Source.z; float length=( (diffx*diffx*) + (diffy*diffy) + (diffz*diffz) ); Result.x=diffx/length; Result.y=diffy/length; Result.z=diffz/length; }

You would then use Result as the normalized velocity vector.

Code:

void CGameObject::Update(float fTimeDelta) { //New position is function of velocity vector component times speed times framedelta to account for //framerate m_vPos.x+=m_vVel.x*m_fSpeed*fTimeDelta; m_vPos.y+=m_vVel.y*m_fSpeed*fTimeDelta; m_vPos.z+=m_vVel.z*m_fSpeed*fTimeDelta; //Perform any scaling if needed D3DXMATRIX matScale; ... ... //Perform local rotations D3DMATRIX matLocalRot; ... ... //Translate to world position D3DXMATRIX matTrans; D3DXMatrixTranslation(m_vPos.x,m_vPos.y,m_vPos.z,&matTrans); //Perform post translation rotations if needed D3DXMATRIX matRot; ... ... m_matWorldMatrix=matScale*matLocalRot*matTrans*matRot; }

To find out if you need to rotate from your current vector to another you can perform the dot product between the right, look and up vectors to determine where you need to go to get to the new vector. It is very important to move away from actual Euler angle values and sin, cos, tan because they are truly not needed most of the time with vectors and are expensive when they are needed. When you move to quaternions this will be even more true and the above code would need to be modified slightly. After all sin, cos and tan all break down into ratios and if we can obtain the same ratios using diff methods then we should employ them. Very rarely in any system will you need actual angle values. It took me a long time to realize this but when I did, everything began to fall into place.

I had a game way back when called Star Trek: The Kobayashi Alternative. It was a text adventure put out by Simon and Schuster at the time. During the game you could tell your helmsman, a new ensign filling in for Sulu, to plot a course to this planet or that. But you could also plot a course to any 3d point in the universe. You then set the warp value and the ship flies towards that point and all numbers arrive there at exactly the same point in time regardless of speed. So I wondered for ages how they did this and figured it out by doing some math. Little did I know at the time I was using the same exact method I just posted here, but I didn't know the exact academic name for it.

So to make a long story short which I rarely do (:)), get rid of angle values for now. Now apply Bob's suggestion and estimate or calcuate where the object will be and fire at that point. The problem comes down to a simple calcuate how long (T) it will take to go from A to B at Speed S. Once you have that value you can use it along with the target object's speed and velocity vector to arrive at the final point. Next you aim your weapon at that target point using the methods I presented. You are basically extending the vector of the target object out to the point it will be at, given it does not turn, in the amount of time it takes for the weapon to travel from Source to Target.

So if the weapon takes 3 seconds to travel to the target you want to fire at a point 3 seconds into the future along the Target's velocity vector. Now if the target turns and if acceleration of the Source, Target, and weapon are not constant you will certainly miss the target. You can use calculus to account for these variables, however, the imprecision inherent in the approximation might actually be better. We've all played games where the bad guys aim was just a little too precise.