Vector intersection

This is a discussion on Vector intersection within the A Brief History of Cprogramming.com forums, part of the Community Boards category; I can't quite figure out how to calculate the intersection of two vectors mathematically. (The closest I could find was ...

  1. #1
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046

    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?
    Last edited by dwks; 09-27-2006 at 12:07 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  2. #2
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Do you know the cosine rule.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Yes, I'm almost certain that the solution involves the law of cosines and the quadratic formula, but I can't figure it out.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    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
    Last edited by VirtualAce; 09-27-2006 at 01:16 PM.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Okay, I didn't quite get that, but I'll look into that book.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7

    Join Date
    May 2005
    Posts
    1,041
    If radius = 0 then they are two lines.

    PHP Code:

    double    TimeOfSphereIntersection
    (Vector3 &PStart,Vector3 &PEnd
                                     
    Vector3 &QStartVector3 &QEnd
                                     
    float PRadiusfloat QRadiusfloat 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 1BSq;
        }
        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;

    I'm not immature, I'm refined in the opposite direction.

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    Bob's example is what you would use in an engine. Instead of finding the point of intersection you would find the time interval.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10

    Join Date
    May 2005
    Posts
    1,041
    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.
    I'm not immature, I'm refined in the opposite direction.

  11. #11
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    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.
    Last edited by VirtualAce; 09-28-2006 at 12:25 AM.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21