Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm working on the physics for my GTA2-like game so I can learn more about game physics.

The collision detection and resolution are working great.

I'm now just unsure how to compute the point of contact when I hit a wall.

Here is my OBB class:

public class OBB2D
{
   private Vector2D projVec = new Vector2D();
   private static Vector2D projAVec = new Vector2D();
   private static Vector2D projBVec = new Vector2D();
   private static Vector2D tempNormal = new Vector2D();
   private Vector2D deltaVec = new Vector2D();


// Corners of the box, where 0 is the lower left.
   private  Vector2D corner[] = new Vector2D[4];

   private Vector2D center = new Vector2D();
   private Vector2D extents = new Vector2D();

   private RectF boundingRect = new RectF();
   private float angle;

    //Two edges of the box extended away from corner[0]. 
   private  Vector2D axis[] = new Vector2D[2];

   private double origin[] = new double[2];

   public OBB2D(float centerx, float centery, float w, float h, float angle)
    {
       for(int i = 0; i < corner.length; ++i)
       {
           corner[i] = new Vector2D();
       }
       for(int i = 0; i < axis.length; ++i)
       {
           axis[i] = new Vector2D();
       }
       set(centerx,centery,w,h,angle);
    }

   public OBB2D(float left, float top, float width, float height)
  {
       for(int i = 0; i < corner.length; ++i)
       {
           corner[i] = new Vector2D();
       }
       for(int i = 0; i < axis.length; ++i)
       {
           axis[i] = new Vector2D();
       }
       set(left + (width / 2), top + (height / 2),width,height,0.0f);
   }

   public void set(float centerx,float centery,float w, float h,float angle)
   {
       float vxx = (float)Math.cos(angle);
       float vxy = (float)Math.sin(angle);
       float vyx = (float)-Math.sin(angle);
       float vyy = (float)Math.cos(angle);

           vxx *= w / 2;
           vxy *= (w / 2);
           vyx *= (h / 2);
           vyy *= (h / 2);

           corner[0].x = centerx - vxx - vyx;
           corner[0].y = centery - vxy - vyy;
           corner[1].x = centerx + vxx - vyx;
           corner[1].y = centery + vxy - vyy;
           corner[2].x = centerx + vxx + vyx;
           corner[2].y = centery + vxy + vyy;
           corner[3].x = centerx - vxx + vyx;
           corner[3].y = centery - vxy + vyy;

           this.center.x = centerx;
           this.center.y = centery;
           this.angle = angle;
           computeAxes();
           extents.x = w / 2;
           extents.y = h / 2;

           computeBoundingRect();
   }


   //Updates the axes after the corners move.  Assumes the
   //corners actually form a rectangle.
   private void computeAxes()
   {
       axis[0].x = corner[1].x - corner[0].x;
       axis[0].y = corner[1].y - corner[0].y;
       axis[1].x = corner[3].x - corner[0].x;
       axis[1].y = corner[3].y - corner[0].y;


       // Make the length of each axis 1/edge length so we know any
       // dot product must be less than 1 to fall within the edge.

       for (int a = 0; a < axis.length; ++a) 
       {
        float l = axis[a].length();
        float ll = l * l;
        axis[a].x = axis[a].x / ll;
        axis[a].y = axis[a].y / ll;
           origin[a] = corner[0].dot(axis[a]);
       }
   }



   public void computeBoundingRect()
   {
       boundingRect.left = JMath.min(JMath.min(corner[0].x, corner[3].x), JMath.min(corner[1].x, corner[2].x));
       boundingRect.top = JMath.min(JMath.min(corner[0].y, corner[1].y),JMath.min(corner[2].y, corner[3].y));
       boundingRect.right = JMath.max(JMath.max(corner[1].x, corner[2].x), JMath.max(corner[0].x, corner[3].x));
       boundingRect.bottom = JMath.max(JMath.max(corner[2].y, corner[3].y),JMath.max(corner[0].y, corner[1].y)); 
   }

   public void set(RectF rect)
   {
       set(rect.centerX(),rect.centerY(),rect.width(),rect.height(),0.0f);
   }

    // Returns true if other overlaps one dimension of this.
    private boolean overlaps1Way(OBB2D other)
    {
        for (int a = 0; a < axis.length; ++a) {

            double t = other.corner[0].dot(axis[a]);

            // Find the extent of box 2 on axis a
            double tMin = t;
            double tMax = t;

            for (int c = 1; c < corner.length; ++c) {
                t = other.corner[c].dot(axis[a]);

                if (t < tMin) {
                    tMin = t;
                } else if (t > tMax) {
                    tMax = t;
                }
            }

            // We have to subtract off the origin

            // See if [tMin, tMax] intersects [0, 1]
            if ((tMin > 1 + origin[a]) || (tMax < origin[a])) {
                // There was no intersection along this dimension;
                // the boxes cannot possibly overlap.
                return false;
            }
        }

        // There was no dimension along which there is no intersection.
        // Therefore the boxes overlap.
        return true;
    }



    public void moveTo(float centerx, float centery) 
    {
        float cx,cy;

        cx = center.x;
        cy = center.y;

        deltaVec.x = centerx - cx;
        deltaVec.y  = centery - cy;


        for (int c = 0; c < 4; ++c)
        {
            corner[c].x += deltaVec.x;
            corner[c].y += deltaVec.y;
        }

        boundingRect.left += deltaVec.x;
        boundingRect.top += deltaVec.y;
        boundingRect.right += deltaVec.x;
        boundingRect.bottom += deltaVec.y;


        this.center.x = centerx;
        this.center.y = centery;
        computeAxes();
    }

    // Returns true if the intersection of the boxes is non-empty.
    public boolean overlaps(OBB2D other)
    {
        if(right() < other.left())
        {
            return false;
        }

        if(bottom() < other.top())
        {
            return false;
        }

        if(left() > other.right())
        {
            return false;
        }

        if(top() > other.bottom())
        {
            return false;
        }


        if(other.getAngle() == 0.0f && getAngle() == 0.0f)
        {
            return true;
        }

        return overlaps1Way(other) && other.overlaps1Way(this);
    }

    public Vector2D getCenter()
    {
        return center;
    }

    public float getWidth()
    {
        return extents.x * 2;
    }

    public float getHeight() 
    {
        return extents.y * 2;
    }

    public void setAngle(float angle)
    {
        set(center.x,center.y,getWidth(),getHeight(),angle);
    }

    public float getAngle()
    {
        return angle;
    }

    public void setSize(float w,float h)
    {
        set(center.x,center.y,w,h,angle);
    }

    public float left()
    {
        return boundingRect.left;
    }

    public float right()
    {
        return boundingRect.right;
    }

    public float bottom()
    {
        return boundingRect.bottom;
    }

    public float top()
    {
        return boundingRect.top;
    }

    public RectF getBoundingRect()
    {
        return boundingRect;
    }

    public boolean overlaps(float left, float top, float right, float bottom)
    {
        if(right() < left)
        {
            return false;
        }

        if(bottom() < top)
        {
            return false;
        }

        if(left() > right)
        {
            return false;
        }

        if(top() > bottom)
        {
            return false;
        }

        return true;
    }

    public static float distance(float ax, float ay,float bx, float by)
    {
      if (ax < bx)
        return bx - ay;
      else
        return ax - by;
    }


    public Vector2D project(float ax, float ay)
    {
        projVec.x = Float.MAX_VALUE;
        projVec.y = Float.MIN_VALUE;

      for (int i = 0; i < corner.length; ++i)
      {
        float dot = Vector2D.dot(corner[i].x,corner[i].y,ax,ay);

        projVec.x = JMath.min(dot, projVec.x);
        projVec.y = JMath.max(dot, projVec.y);
      }

      return projVec;
    }

    public Vector2D getCorner(int c)
    {
        return corner[c];
    }

    public int getNumCorners()
    {
        return corner.length;
    }

    public static float collisionResponse(OBB2D a, OBB2D b,  Vector2D outNormal) 
    {

        float depth = Float.MAX_VALUE;


        for (int i = 0; i < a.getNumCorners() + b.getNumCorners(); ++i)
        {
            Vector2D edgeA;
            Vector2D edgeB;
            if(i >= a.getNumCorners())
            {
                edgeA = b.getCorner((i + b.getNumCorners() - 1) % b.getNumCorners());
                edgeB = b.getCorner(i % b.getNumCorners());
            }
            else
            {
                edgeA = a.getCorner((i + a.getNumCorners() - 1) % a.getNumCorners());
                edgeB = a.getCorner(i % a.getNumCorners());
            }

             tempNormal.x = edgeB.x -edgeA.x;
             tempNormal.y = edgeB.y - edgeA.y; 


          tempNormal.normalize();


          projAVec.equals(a.project(tempNormal.x,tempNormal.y));
          projBVec.equals(b.project(tempNormal.x,tempNormal.y));

          float distance = OBB2D.distance(projAVec.x, projAVec.y,projBVec.x,projBVec.y);

          if (distance > 0.0f)
          {
            return 0.0f;
          }
          else
          {
            float d = Math.abs(distance);

            if (d < depth)
            {
              depth = d;
              outNormal.equals(tempNormal);
            }
          }
        }

        float dx,dy;
        dx = b.getCenter().x - a.getCenter().x;
        dy = b.getCenter().y - a.getCenter().y;
        float dot = Vector2D.dot(dx,dy,outNormal.x,outNormal.y);
        if(dot > 0)
        {
            outNormal.x = -outNormal.x;
            outNormal.y = -outNormal.y;
        }

        return depth;
    }

    public Vector2D getMoveDeltaVec()
    {
    return deltaVec;
}
};

Thanks!

Append

Can someone please tell me what I need to provide to get an answer for this? How do 2D games calculate the force of an impact without an impact point??

I know how to find the normals of collision but that is not enough. And it is NOT simply a corner.

I really do not want to award the bounty to the current -4 downvoted answer.

enter image description here

share|improve this question
1  
Isn't this basically the same as your other question? –  Nathan Reed Nov 12 '12 at 23:26
    
Nope, that was getting the car out of it, for that you find the normal and push out the car by the penetration amount. This is to find the point where it collides. –  Milo Nov 12 '12 at 23:33
    
The technique is identical to your other question if the objects are static. If you're talking about moving OBBs that's a whole different question. –  wildbunny Nov 18 '12 at 17:12
    
One is moving, the car and one is static, the building. –  Milo Nov 18 '12 at 17:53
    
Not sure why the point of contact is not just a corner. Maybe a diagram would help. –  Ken Nov 19 '12 at 23:39

4 Answers 4

I'm quite sure (100% sure, because I've implemented this myself) that your point of contact is either the corner of your car, or the corner of the building. Whether you use the corner before or after the car's position is adjusted to handle it's penetration with the static object, is up to you (I recommend after).

It seems your concern is that you don't think the corner of the car is the correct location to apply a force on the vehicle when it hits a wall. However, it actually is! Here's why:

The corner of the car is exactly the point that originally contacts the wall, so conceptually it is the point you are looking for. Also, it only matters for the angular force you're going to apply to the car. The point on the car at which you apply a linear force is not important, because angular and linear momentum are entirely decoupled.

This phenomenon simplifies things greatly; we can apply the force equal-and-opposite to the car's velocity into the wall directly to the center of mass of the car, and viola, the calculation for the change of the car's linear momentum is complete!

As for calculating the angular force exerted on the car by the wall... it's a little more complicated, because the point of contact will matter. I will again put a plug in for Chris Hecker's articles on rigid body dynamics. Almost everything you need will be explained there. Hecker explains it clearly enough that I'd struggle to give a better explanation here, but I'll provide a synopsis.

There is a formula for calculating the angular momentum of a point around another point. Assuming that you know the center of mass of your car, you can calculate the angular momentum of the corner with something like the following:

angularMomentum = dot(perp(A-B), momentumOfB);

where B is the center of mass, A is the corner of your car, or whatever point is contacting the wall, and perp is a function that returns the 'perpendicularized' vector from B to A. You can then do with this whatever you need to calculate the additional force that is applied to the car from the wall. Just to reiterate: though the force that the wall applies to the car is applied to the corner of the car, the car's linear momentum is unaffected by the locality of the force. Only the angular momentum depends on where the force is applied. Again, there is a formula for calculating the change in angular momentum given a force at a point, which involves the moment of inertia of the car. Hecker provides that formula in his articles as well.

The case you have to watch out for is when a face of the car is perfectly perpendicular to a face of the wall. Technically, you have an infinite number of contact points, making determining a contact point unsolvable. This is where things will get messy. I believe the best thing to do in this case is to, first, detect the situation by dotting together the normals of the relevant faces of the car and the building. If the result is -1, then you have this special case. From here, you can choose to cancel the angular momentum of the car, or leave it unmodified; to be honest, I'm not sure off the top what the "physically accurate" solution is, but it would be complicated. So the quick 'all-or-nothing' method is easier, and might give you results you're happy with. In sum, face-face contact is a non-trivial problem to solve.

Happy coding!

share|improve this answer
    
Thanks :) But what about the case I have illustrated here: i.stack.imgur.com/D8kE2.png The orange car is making contact yet none of its corners touch. –  Milo Nov 20 '12 at 2:27
    
What I want IS to fix angular momentum, thus I need the correct point(s), linear force works fine, angular does not. –  Milo Nov 20 '12 at 2:29
    
My RigidBody has this: ApplyForce(Vector worldForce, Vector worldOffset) –  Milo Nov 20 '12 at 2:32
    
Ah, I see. To decide which OOBB to take a corner from you can consider which axis the two OOBBs overlap on. You want the OOBB on whose axes there is no overlap, or there is the least overlap among all overlapping axes. For example, in the picture you linked, the overlap is on the axis of the car, so you want a corner of the building. I'm pretty sure that generalization will work in all cases. As for the angular forces, what exactly is going wrong? What behavior are you getting? –  ktodisco Nov 20 '12 at 2:39
    
The corner cases were misbahaving and spiraling the car out of control. I will however try to find the correct point. One thing I was wondering. If the car is perfectly perpendicular to the wall (facing it), wouldnt I need to apply to the 2 corners since they both equally touch the wall? –  Milo Nov 20 '12 at 2:46

You should look at Erin Catto's 2006 GDC presentation where he talks about how to do this.

http://code.google.com/p/box2d/downloads/list

According to him (He wrote Box2d) you should:

  • Find the axis of depest penetration (one of the OBB surface normals)
  • Find the incident face on the other OBB (It's dot product should have the largest negative magnitude)
  • Then clip the incident face against the face you got the surface normal from.

the resulting points are all of the collision points that you need to resolve from. Some solvers just use the most deeply embedded collision point and maintain a contact manifold (don't stop resolving against a point until you detect that it has moved out of collision) but clipping should be more stable.

share|improve this answer

EDIT ohh I got what you miss! When people say the point of contact is a corner, they don't mean it is necessarily a corner of the car, but a corner of either of the two colliding objects. In your picture, it is a corner of the wall. See my original response below.

Original response

Well, for 2D convex polygons, there can be up to 2 points of contact, but each point of contact IS definitely a corner. It can be a corner of the car, or a corner of the wall, but it is a corner nonetheless. This is because objects should not overlap in the first place; they can only touch, and when they do, the touching point is a corner (deleted irrelevant comment). These points are where you apply forces. The determination is commonly using Separating Axis Theorem. This method is useful to detect collision, determine the contact normal, contact point, as well as the amount of overlap. A good tutorial on the subject can be found here. For more detailed discussion, you can refer to the book "Real Time Collision Detection" by Christer Ericson.

share|improve this answer

Get the corner of your car, after you apply the wall normal.

share|improve this answer
2  
No, that won't work on a rotated bounding box, the angular force would be incorrectly calculated. –  Milo Nov 14 '12 at 0:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.