Collision between line and ball problem

[reDo]

I have to learn basics at first and then I will give you know.  

[Disch]

I thought those were the basics  =x   lol

I assumed you already knew what sin/cos/etc are since you used SOHCAHTOA in your approach to the problem.

oh well.  ^^

[reDo]

yes I know sin, cos, tan, cotan but I dont know dot product and so on  

[Disch]

That's why I explained them in that post.  ;P


lol nevermind.

[reDo]

yes but I wanna learn from zero that I will understand everything, unit vector ...

[reDo]

Hi again, I learned vectors and now I am wondering how to use it to chcek collision between line and line    :roll:

[Disch]

You caught me at work!

I'll reply when I get home (maybe ~6 hrs from now)

But yeah, line-line collision is easy and fast using these same concepts.

[Disch]

OK!

Say you have two lines AB (with endpoints A and B) and CD (with points C and D)

Any point on line AB can be represented in the following form:
P = (B - A) * k + A

Where 'P' is the point, and 'k' is a value between [0..1].  Basically k acts as a "scale" to find the point according to it's distance from A.  So if P is exactly halfway between A and B, k would be 0.5

The same can be said of line CD.  Any point can be represented in the following form:
Q = (D - C) * m + C

To shorten/simplify future equations, I'm going to use some shorthand and say vBA = (B-A) and vDC = (D-C)


Now, assuming AB and CD extend to infinity, that means P=Q at the intersection point.

Which further means that:

Code: [Select]

P = vBA * k + A
Q = vDC * m + C

          P = Q
vBA * k + A = vDC * m + C

Now if we solve this equation for k and m, we have found the intersection point.  Assuming you know standard algebra, you should be able to solve it yourself so I'll skip the steps.  Basically you're left with this:

Code: [Select]

k = (vDC * m + vCA) / vBA
m = (vBA * k - vCA) / vDC

Now keep in mind that each of these equations are actually 2 equations in one, because the vectors all consist of both an x component and a y component.  So, actually, we have 2 ways to find k:

Code: [Select]

k = (vDC.x * m + vCA.x) / vBA.x
and
k = (vDC.y * m + vCA.y) / vBA.y

Likewise, we have 2 ways to find m.

Using this, we can substitute 'm' in one of the 'k' equations to eliminate it as a variable:

Code: [Select]

k = (vDC.x * m + vCA.x) / vBA.x
m = (vBA.y * k - vCA.y) / vDC.y

so

k = (vDC.x * (             m             ) + vCA.x) / vBA.x
k = (vDC.x * ((vBA.y * k - vCA.y) / vDC.y) + vCA.x) / vBA.x


Now we can solve for 'k' and have the result using only the given points A,B,C, and D.  We can also do the same thing to get 'm'.

So after all that solving you finally get this:

Code: [Select]

k = (vDC.y*vCA.x - vDC.x*vCA.y) / (vDC.y*vBA.x - vDC.x*vBA.y)
m = (vBA.y*vCA.x - vBA.x*vCA.y) / (vDC.y*vBA.x - vDC.x*vBA.y)

But wait a moment.... don't those expressions look a little familiar?

Code: [Select]

inline double PerpDot(const Point& a,const Point& b)                    { return (a.y*b.x) - (a.x*b.y); }

That's right!  It's good old PerpDot!  That magical linear algebra function!

This means we can further simplify:

Code: [Select]


k = PerpDot(vDC,vCA) / PerpDot(vDC,vBA)
m = PerpDot(vBA,vCA) / PerpDot(vDC,vBA)


Note the bottom part for each is the same.

Knowing that we're working with finite lines -- this means k and m must both be within the range [0..1] or else there is no intersection.

Also note the divide by 0 situation.  If PerpDot(vDC,vBA) is zero, there is no intersection.  Remember that PerpDot gives you sin(theta) and if sin(theta) is zero, it means the lines are parallel, so they cannot intersect.  Hence why the above equation wouldn't work in that case.



So all that roundabout math aside, we're left with a very, very simple function:

Code: [Select]


bool LineCollision( const Point& A, const Point& B,  // line AB
                    const Point& C, const Point& D,  // line CD
                    Point* out                       )  // filled with intersection point
{

    Point vBA(B - A);
    Point vDC(D - C);

    double f = PerpDot(vDC,vBA);
    if(!f)      // lines are parallel
        return false;
   
    Point vCA(C - A);

    double k = PerpDot(vDC,vCA) / f;
    if(k < 0)           return false;
    if(k > 1)           return false;

    double m = PerpDot(vBA,vCA) / f;
    if(m < 0)           return false;
    if(m > 1)           return false;

    if(out)
        *out = (vDC * m) + C;  // or (vBA * k) + A if you prefer -- same thing

    return true;
}


[reDo]

Thanks I will learn it  :wink:

[reDo]

I tried to make collision detection rotated rectangle vs rotated rectangle(I know that one is not rotated but this is just a test =) ) using separating axis theorem by this article http://www.gamedev.net/page/resources/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604 , but it doesnt work sometimes. Can someone help me find that bug please, because I am beginner in vectors so I am glad it works most of the time ? Thanks a million for any help :roll:

Here is bug picture

Code: [Select]

#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <SFML/Window.hpp>
#include <iostream>
#include <cmath>

using namespace std;

typedef sf::Vector2f VECTOR;

float RetDotProduct(const VECTOR & v1, const VECTOR & v2)
{
    return (v1.x*v2.x + v1.y*v2.y);
}

void DrawRect(sf::RenderWindow & App, const VECTOR rect[], int r, int g, int b)
{
    for(int i=0;i<4;i++)
        App.Draw(sf::Shape::Line(rect[i].x,rect[i].y,
                                 rect[i+(i==3? -3 : 1)].x,rect[i+(i==3? -3 : 1)].y,1,sf::Color(r,g,b)));
}

float FindMax(float projects[])
{
    float max = projects[0];
    for(int i=0;i<4;i++)
        if(max < projects[i])
            max = projects[i];
    return max;
}

float FindMin(float projects[])
{
    float min = projects[0];
    for(int i=0;i<4;i++)
        if(min > projects[i])
            min = projects[i];
    return min;
}

bool IsColOnAxis(const VECTOR axisA, const VECTOR axisB, const VECTOR rectA[], const VECTOR rectB[])
{
    VECTOR axisAB = axisA - axisB;
    float Aprojections[4];
    float Bprojections[4];
    //rect A
    for(int i=0;i<4;i++)
    {
        Aprojections[i] = RetDotProduct(axisAB,rectA[i]-axisA) / RetDotProduct(axisAB,axisAB);
    }
    //rect B
    for(int i=0;i<4;i++)
    {
        Bprojections[i] = RetDotProduct(axisAB,rectB[i]-axisA) / RetDotProduct(axisAB,axisAB);
    }

    float Amax = FindMax(Aprojections);
    float Amin = FindMin(Aprojections);
    float Bmax = FindMax(Bprojections);
    float Bmin = FindMin(Bprojections);

    if((Bmin > Amin && Bmin < Amax) || (Bmax > Amin && Bmax < Amax))
        return true;

    return false;
}
bool RectVsRect(const VECTOR rectA[], const VECTOR rectB[])
{
    if(IsColOnAxis(rectA[0],rectA[1],rectA,rectB) &&
       IsColOnAxis(rectA[1],rectA[2],rectA,rectB) &&
       IsColOnAxis(rectB[0],rectB[1],rectA,rectB) &&
       IsColOnAxis(rectB[1],rectB[2],rectA,rectB))
    return true;

    return false;
}

int main()
{
    bool drag=false;

    sf::RenderWindow App(sf::VideoMode(800,600,32),"Vector");

    VECTOR rect1[4] = {VECTOR(200,200),VECTOR(300,100),VECTOR(500,300),VECTOR(400,400)};
    VECTOR rect2[4] = {VECTOR(350,200),VECTOR(450,200),VECTOR(450,400),VECTOR(350,400)};

    while(App.IsOpened())
    {
        sf::Event Event;
        App.PollEvent(Event);

        if(Event.Type == sf::Event::Closed)
            App.Close();
        if(Event.Key.Code == sf::Keyboard::Escape)
            App.Close();
        if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Up))
            rect2[0].y-=0.25;
        if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Down))
            rect2[0].y+=0.25;
        if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Right))
            rect2[0].x+=0.25;
        if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Left))
            rect2[0].x-=0.25;

        rect2[1] = VECTOR(rect2[0].x+200,rect2[0].y);
        rect2[2] = VECTOR(rect2[1].x,rect2[1].y+100);
        rect2[3] = VECTOR(rect2[0].x,rect2[0].y+100);

        App.Clear();
        if(RectVsRect(rect1,rect2))
            App.Draw(sf::Shape::Circle(100,100,10,sf::Color::Green));

        DrawRect(App,rect1,255,0,0);
        DrawRect(App,rect2,0,255,255);

        App.Display();

    }

    return 0;
}


[Disch]

Very good job.  You really seem to understand the concept pretty well.

The problem is how you're testing the overlap.  Here's the function with my comments and fix:

Code: [Select]



bool IsColOnAxis(const VECTOR axisA, const VECTOR axisB, const VECTOR rectA[], const VECTOR rectB[])
{
    VECTOR axisAB = axisA - axisB;  // should be perpendicular axis, not parallel, but doesn't matter for rectangles.

    // if you want to correct that, though, you would do this instead of axisA - axisB:
    axisAB.y = axisA.x - axisB.x;
    axisAB.x = axisB.y - axisA.y;  // now axisAB is perpendicular to AB, not parallel

    // but again this REALLY doesn't matter with rectangles because each of the 2 important
    // axis are perpendicular to each other anyway.  If you were doing some other
    // kind of shape, though, this would have screwed it up.

    float Aprojections[4];
    float Bprojections[4];
    //rect A
    for(int i=0;i<4;i++)
    {
        Aprojections[i] = RetDotProduct(axisAB,rectA[i]-axisA) / RetDotProduct(axisAB,axisAB);  // probably should be "rectA[i]-axisB" since axisB is your origin.
                    // but that really doesn't matter.  All that will do is negate all your projected lines, but they will all be negated the same
                    // way, so it won't really affect anything.  I only bring it up because it confused me a little when I first saw it.
    }
    //rect B
    for(int i=0;i<4;i++)
    {
        Bprojections[i] = RetDotProduct(axisAB,rectB[i]-axisA) / RetDotProduct(axisAB,axisAB);  // same notes as above
    }

    float Amax = FindMax(Aprojections);
    float Amin = FindMin(Aprojections);
    float Bmax = FindMax(Bprojections);
    float Bmin = FindMin(Bprojections);

    // you only check to see if the B points are "inside" the A line
    //  you do not check to see if the A points are inside the B line, which will cause a failure
    //  when the A line is fully enclosed in the B line.
    //
    //  IE:
    //    ==================================    <- B
    //            =============                 <- A
    //
    //  In this case, your test was returning false, but it should be returning true.  This is why the function was failing sometimes.

    /*
    if((Bmin > Amin && Bmin < Amax) || (Bmax > Amin && Bmax < Amax)
        || (Amin > Bmin && Amin < Bmax) || (Amax > Bmin && Amax < Bmax))  // <- to fix you can add this
        return true;
   
    return false;
    */

    // Although the massive if statements are fugly and confusing.  Instead I would get rid of the above junk and do this instead:
    if(Bmax < Amin)     return false;
    if(Amax < Bmin)     return false;
    if(Bmin > Amax)     return false;
    if(Amin > Bmax)     return false;
    return true;

    // much simpler.  Also note that this is fewer checks (4 conditionals instead of 8) so it'll likely be faster.


    // You could also optimize this for rectangles.  The thing with rectangles is 2 of their sides are parallel with the other 2 sides.
    //  so really you only need to project 2 corners and not 4 (specifically, the corners that are not adjacent to each other, like [0] and [2])
    //
    // You also only need to project them onto 2 axis, not 4.  Because the other 2 axis will be parallel.
}

[reDo]

Thanks a lot   now I feel really happy