Collision not working at higher speeds

This is a discussion on Collision not working at higher speeds within the Game Programming forums, part of the General Programming Boards category; Hey everyone, I've heard before there is a way to prevent objects from going right through each other when using ...

  1. #1
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964

    Collision not working at higher speeds

    Hey everyone, I've heard before there is a way to prevent objects from going right through each other when using AABB collision, I'm just not sure what term to look for as far as the right terms or techniques would be called. I want to do it myself.

    Could anyone point me in the right direction of an article or site to explain the proper fix for this kind of thing?

    Hah I suppose it might help if you saw my code!

    Code:
    void Physics::Update(std::vector<Renderable_Object*> & Game_Objects)
    {		
    	for (unsigned int i = 0; i < Game_Objects.size(); i++)
    	{
    		if (!Game_Objects[i]->isPhysical) continue;
    	
    		for (unsigned int j = i+1; j < Game_Objects.size(); j++)
    		{
    			if (!Game_Objects[j]->isPhysical) continue;
    			
    			if(	Game_Objects[i]->AABB && 
    				Game_Objects[j]->AABB && 
    				collision2d(	Game_Objects[i]->getMin(), Game_Objects[i]->getMax(), 
    								Game_Objects[j]->getMin(), Game_Objects[j]->getMax()))
    			{
    				collisionResponse(Game_Objects[i], Game_Objects[j]);
    			}
    
    			else if(Game_Objects[i]->Plane && 
    					Game_Objects[j]->AABB && 
    					planeIntersection2d(Game_Objects[i], Game_Objects[j]->getLocation()))
    			{
    				collisionResponse(Game_Objects[i], Game_Objects[j]);
    			}
    			else if(Game_Objects[j]->Plane && 
    					Game_Objects[i]->AABB && 
    					planeIntersection2d(Game_Objects[j], Game_Objects[i]->getLocation()))
    			{
    				collisionResponse(Game_Objects[j], Game_Objects[i]);
    			}
    		}
    	}
    }
    
    void Physics::collisionResponse(Renderable_Object * collidedObjectA , Renderable_Object * collidedObjectB)
    {
    	if (collidedObjectA->defaultCollisionResponse == 1 && collidedObjectB->defaultCollisionResponse == 1)
    	{
    		if (collidedObjectA->Plane)
    		{
    			collidedObjectB->getLocation().x = collidedObjectA->getLocation().x;
    		}
    		if (collidedObjectB->Plane)
    		{
    			collidedObjectA->getLocation().x = collidedObjectB->getLocation().x;
    		}
    	}
    	if (collidedObjectA->defaultCollisionResponse == 0)
    	{
    		if (collidedObjectA->getVelocity().x != 0)
    		{
    			reverse_x_velocity(collidedObjectA->getVelocity());
    		}
    		if (collidedObjectA->getVelocity().y != 0)
    		{
    			reverse_y_velocity(collidedObjectA->getVelocity());
    		}
    	}
    	else if (collidedObjectB->defaultCollisionResponse == 0)
    	{
    		if (collidedObjectB->getVelocity().x != 0)
    		{
    			reverse_x_velocity(collidedObjectB->getVelocity());
    		}
    		if (collidedObjectB->getVelocity().y != 0)
    		{
    			reverse_y_velocity(collidedObjectB->getVelocity());
    		}
    	}
    }
    bool Physics::collision2d(Vector2 & a_min, Vector2 & a_max, Vector2 & b_min, Vector2 & b_max) 
    {
    	return (a_min.x <= b_max.x) && (a_min.y <= b_max.y) && (a_max.x >= b_min.x) && (a_max.y >= b_min.y);
    }
    
    bool Physics::planeIntersection2d(Renderable_Object * boundingPlane, Vector2 & objectPosition)
    {
    	Ray line_between_objects(objectPosition,boundingPlane->getLocation());
    	double DotProduct=line_between_objects.direction.dot(boundingPlane->getLocation().normal());
    	double l2;
    
    	//determine if ray parallel to plane
    	if ((DotProduct<0)&&(DotProduct>-0)) 
    		return false;
    
    	l2=(boundingPlane->getLocation().normal().dot(boundingPlane->getLocation()-objectPosition))/DotProduct;
    
    	if (l2<-0) 
    		return false;
    
    	return true;
    }
    
    void Physics::reverse_y_velocity(Vector2 & velocity)
    {
    	velocity.y *= -1;
    }
    void Physics::reverse_x_velocity(Vector2 & velocity)
    {
    	velocity.x *= -1;
    }
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  2. #2

    Join Date
    May 2005
    Posts
    1,041
    The term you are looking for might be tunneling, but that ought not apply for swept volume methods.
    I'm not immature, I'm refined in the opposite direction.

  3. #3
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    For objects where the sum of the absolute velocities exceeds the initial distance between them, you want to use the point of closest approach algorithm. It includes the source code below.

    Assuming you have a bounding box precalculated for each object, you can then check if at that point they collide.

    Code:
    // Copyright 2001, softSurfer (www.softsurfer.com)
    // This code may be freely used and modified for any purpose
    // providing that this copyright notice is included with it.
    // SoftSurfer makes no warranty for this code, and cannot be held
    // liable for any real or imagined damage resulting from its use.
    // Users of this code must verify correctness for their application.
    
    // Assume that classes are already given for the objects:
    //    Point and Vector with
    //        coordinates {float x, y, z;}
    //        operators for:
    //            Point  = Point  Vector
    //            Vector = Point - Point
    //            Vector = Vector  Vector
    //            Vector = Scalar * Vector
    //    Line and Segment with defining points {Point P0, P1;}
    //    Track with initial position and velocity vector
    //            {Point P0; Vector v;}
    //===================================================================
    
    #define SMALL_NUM  0.00000001 // anything that avoids division overflow
    // dot product (3D) which allows vector operations in arguments
    #define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
    #define norm(v)    sqrt(dot(v,v))  // norm = length of vector
    #define d(u,v)     norm(u-v)       // distance = norm of difference
    #define abs(x)     ((x) >= 0 ? (x) : -(x))   // absolute value
    
    // dist3D_Line_to_Line():
    //    Input:  two 3D lines L1 and L2
    //    Return: the shortest distance between L1 and L2
    float
    dist3D_Line_to_Line( Line L1, Line L2)
    {
        Vector   u = L1.P1 - L1.P0;
        Vector   v = L2.P1 - L2.P0;
        Vector   w = L1.P0 - L2.P0;
        float    a = dot(u,u);        // always >= 0
        float    b = dot(u,v);
        float    c = dot(v,v);        // always >= 0
        float    d = dot(u,w);
        float    e = dot(v,w);
        float    D = a*c - b*b;       // always >= 0
        float    sc, tc;
    
        // compute the line parameters of the two closest points
        if (D < SMALL_NUM) {         // the lines are almost parallel
            sc = 0.0;
            tc = (b>c ? d/b : e/c);   // use the largest denominator
        }
        else {
            sc = (b*e - c*d) / D;
            tc = (a*e - b*d) / D;
        }
    
        // get the difference of the two closest points
        Vector   dP = w + (sc * u) - (tc * v);  // = L1(sc) - L2(tc)
    
        return norm(dP);   // return the closest distance
    }
    //===================================================================
    
    // dist3D_Segment_to_Segment():
    //    Input:  two 3D line segments S1 and S2
    //    Return: the shortest distance between S1 and S2
    float
    dist3D_Segment_to_Segment( Segment S1, Segment S2)
    {
        Vector   u = S1.P1 - S1.P0;
        Vector   v = S2.P1 - S2.P0;
        Vector   w = S1.P0 - S2.P0;
        float    a = dot(u,u);        // always >= 0
        float    b = dot(u,v);
        float    c = dot(v,v);        // always >= 0
        float    d = dot(u,w);
        float    e = dot(v,w);
        float    D = a*c - b*b;       // always >= 0
        float    sc, sN, sD = D;      // sc = sN / sD, default sD = D >= 0
        float    tc, tN, tD = D;      // tc = tN / tD, default tD = D >= 0
    
        // compute the line parameters of the two closest points
        if (D < SMALL_NUM) { // the lines are almost parallel
            sN = 0.0;        // force using point P0 on segment S1
            sD = 1.0;        // to prevent possible division by 0.0 later
            tN = e;
            tD = c;
        }
        else {                // get the closest points on the infinite lines
            sN = (b*e - c*d);
            tN = (a*e - b*d);
            if (sN < 0.0) {       // sc < 0 => the s=0 edge is visible
                sN = 0.0;
                tN = e;
                tD = c;
            }
            else if (sN > sD) {  // sc > 1 => the s=1 edge is visible
                sN = sD;
                tN = e + b;
                tD = c;
            }
        }
    
        if (tN < 0.0) {           // tc < 0 => the t=0 edge is visible
            tN = 0.0;
            // recompute sc for this edge
            if (-d < 0.0)
                sN = 0.0;
            else if (-d > a)
                sN = sD;
            else {
                sN = -d;
                sD = a;
            }
        }
        else if (tN > tD) {      // tc > 1 => the t=1 edge is visible
            tN = tD;
            // recompute sc for this edge
            if ((-d + b) < 0.0)
                sN = 0;
            else if ((-d + b) > a)
                sN = sD;
            else {
                sN = (-d + b);
                sD = a;
            }
        }
        // finally do the division to get sc and tc
        sc = (abs(sN) < SMALL_NUM ? 0.0 : sN / sD);
        tc = (abs(tN) < SMALL_NUM ? 0.0 : tN / tD);
    
        // get the difference of the two closest points
        Vector   dP = w + (sc * u) - (tc * v);  // = S1(sc) - S2(tc)
    
        return norm(dP);   // return the closest distance
    }
    //===================================================================
    
    // cpa_time(): compute the time of CPA for two tracks
    //    Input:  two tracks Tr1 and Tr2
    //    Return: the time at which the two tracks are closest
    float
    cpa_time( Track Tr1, Track Tr2 )
    {
        Vector   dv = Tr1.v - Tr2.v;
    
        float    dv2 = dot(dv,dv);
        if (dv2 < SMALL_NUM)      // the tracks are almost parallel
            return 0.0;            // any time is ok.  Use time 0.
    
        Vector   w0 = Tr1.P0 - Tr2.P0;
        float    cpatime = -dot(w0,dv) / dv2;
    
        return cpatime;            // time of CPA
    }
    //===================================================================
    
    // cpa_distance(): compute the distance at CPA for two tracks
    //    Input:  two tracks Tr1 and Tr2
    //    Return: the distance for which the two tracks are closest
    float
    cpa_distance( Track Tr1, Track Tr2 )
    {
        float    ctime = cpa_time( Tr1, Tr2);
        Point    P1 = Tr1.P0 + (ctime * Tr1.v);
        Point    P2 = Tr2.P0 + (ctime * Tr2.v);
    
        return d(P1,P2);           // distance at CPA
    }
    //===================================================================
    Last edited by abachler; 12-15-2009 at 12:43 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help explaining test questions
    By Sentral in forum General Discussions
    Replies: 26
    Last Post: 11-09-2009, 11:10 PM
  2. Collision detection using gltranslatef?
    By Jake.c in forum Game Programming
    Replies: 8
    Last Post: 10-18-2009, 02:30 PM
  3. Replies: 8
    Last Post: 05-07-2009, 12:31 PM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 02:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 10:40 PM

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