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.

In my 2D physics engine, I can detect AABB vs AABB collisions, and resolve them by finding the shortest penetration vector and adding it to the AABB's position.

Doing this "pushes" the first AABB outside of the second AABB, but doesn't deal with velocity/acceleration changes at all.

If I add gravity acceleration to my simulation, the velocity of the first dynamic AABB keeps growing even when it is resting on top of the second static AABB. Eventually, the velocity will become too big and the collision won't be detected (the dynamic AABB will fall through the static one).

I tried setting the velocity to zero after resolution, but it obviously didn't work well, and created unrealistic simulations.

I read online that resolving collisions by manually working on the position or the velocity is not correct. I tried implementing forces (mass is an "hardcoded" 1 for now):

void Body::applyForce(sf::Vector2f mForce) { acceleration += mForce; }

void Body::integrate(float mFrameTime)
{
    velocity += acceleration * mFrameTime;
    position += velocity * mFrameTime;

    acceleration = {0, 0};
}

If I apply the shortest penetration vector as a force during collision resolution, the dynamic AABB will get "pushed out" from the static one, but its velocity will never decrease in a simulation without gravity and it will keep moving forever.

Is there a way to apply a "temporary" force? A force that deals with pushing the first AABB out of the second AABB, then stops when the AABB doesn't collide anymore?

Entire source code available here: https://github.com/SuperV1234/SSVSCollision

share|improve this question
1  
I'm interested in this. Have you come up with a solution yet? –  TravisG Feb 3 '13 at 12:57
    
@TravisG: not yet, unfortunately. I'll add a bounty tomorrow if I don't get any reply. –  Vittorio Romeo Feb 3 '13 at 13:38
    
Force does not equal acceleration, first of all. You need mass to calculate acceleration. If you're modifying positions to stop the two bodies from penetrating, you should use mass as well and move both bodies based on it. Applying a force equal to the penetration vector has no merit. Box2D is impulse based, it works on velocities directly, it may not be "correct", but it's good enough. Dealing with velocity changes in an impulse based engine is very simple, so could you specify if you definitively want a force based solution, or is the much simpler impulse based solution good enough. –  dreta Feb 3 '13 at 15:06
    
Personally, i'd suggest picking up a book on physics engines, at least read the first few chapters on Newtonian physics. Your assumptions are incorrect and trying to reply to this question would mean having to teach you basics of physics while trying to explain high level algorithms for solving collisions. –  dreta Feb 3 '13 at 15:11
    
@dreta his assumptions are fine. He pointed out that his mass for all objects is simply "1" for now, which makes his code sections valid. By the way, even though Box2D may deal with velocities directly, it somehow must deal with the same problem. If instead of applying a force, Box2D applies an impulse, it somehow must still deal with the fact that the impulse doesn't just go away once the objects are separated. Although, it's possible that it does in fact not deal with this at all and just lets the objects keep their energy (it would be like this in the real world after all) –  TravisG Feb 3 '13 at 15:14
show 5 more comments

3 Answers

up vote 5 down vote accepted
+100

First, I recommend using a free, open-source physics library like Box2D and just focusing on the aspects of your game that make it unique! If you insist on re-inventing the wheel, read on... note all physics engines are approximations, and while the method I outline below will be more accurate than your current model, Box2D's results will be far more realistic.


For a quick way to model more accurate collision resolution of two objects A and B:

  1. Find the positions right before the collision. You are already approximating this by: "finding the shortest penetration vector and adding it to the AABB's position."
  2. Find the velocities right after the collision using Newtonian physics:
    • For the case where mass is hard-coded as 1, simply swap the velocities (this does not apply to static objects which must have infinite mass):
      • A.v = B.u
      • B.v = A.u
    • If objects A and B have different masses:
      • A.v = (A.u * (A.m - B.m) + (2 * B.m * B.u)) / (A.m + B.m)
      • B.v = (B.u * (B.m - A.m) + (2 * A.m * A.u)) / (A.m + B.m)
    • where:
      • v: velocity after collision
      • u: velocity before collision
      • m: mass (use the largest number possible for the mass of a fixed, static object)
  3. Set acceleration to 0: The acceleration from the collision was accounted for above by the velocity calculations in step number 2.

Please take a look at my sample asteroids program which demonstrates these concepts.


Next, account for stacked objects:

As you have noted, using velocity to simulate stacked/resting objects does not work well: velocity is the speed an object is moving, so if it is resting on a static object, velocity should be near 0. It does not make sense to increase the velocity of an object to make it appear at rest:

If I add gravity acceleration to my simulation, the velocity of the first dynamic AABB keeps growing even when it is resting on top of the second static AABB. Eventually, the velocity will become too big and the collision won't be detected (the dynamic AABB will fall through the static one).

What should really happen is an acceleration force that is going in the opposite direction as gravity should cancel gravity out. (This is called the normal contact force). A shortcut is to simply not apply gravity to bodies that are not in the air:

  • One method of doing this by is keeping a "grounded" state:
    • Do not apply gravity to objects in a grounded state.
    • If an object collides with an object from below and its velocity is very small it enters the grounded state.
    • An object exits the grounded state when its vertical velocity exceeds a certain positive value.

Update:

  • In layman's terms, Newtonian physics says the total energy before and after a collision must match. When two objects crash into each other, their energy is redistributed. Energy is a combination of speed and weight: heavier, faster things have more energy. That's intuitive. However, what's not intuitive is the exact way weights affect the energy redistribution.
  • Swapping velocities is a shortcut only for two dynamic, unfixed bodies that have the same mass (static, fixed objects have very large, infinite masses).
  • The shortcut when one static body is fixed is: the other dynamic, unfixed body keeps the same speed; only angle is changed (imagine a pool table when a ball hits the rail. The rail essentially has a very large, infinite mass).
  • For other cases, like three or more objects, the full Newtonian motion equations must be solved (conservation of momentum and conservation of kinetic energy).
  • I'm not sure if the Newtonian equations for motion can be solved for more than two bodies. Fortunately, however, three objects almost never collide at the exact same time. It is sufficient to handle the first two bodies that collide, then handle any following collisions using the new velocities from the previous collision resolutions. This is a good reason to keep your physics time steps as small as possible and handle collisions before any penetrations occur.
  • You'll notice in my asteroids demo many bodies are created as bigger rocks are split into smaller ones. However, I always handle collisions between pairs of bodies; never explicitly handling a collision with more than two bodies.
share|improve this answer
    
Thanks for the detailed reply. There is something I don't understand though: swapping velocities work well in a collision with 2 bodies - however, I don't see how it can work when multiple bodies (and also static bodies) all collide at the same time. Even without gravity, having a dynamic body collide at the same time with a static body and another dynamic body causes problems. Since the velocity is swapped, it all depends on the order of collision. If the static body is collided last, the body will stop moving. If the dynamic one is, the body will move again. How is this fixed? –  Vittorio Romeo Feb 6 '13 at 14:48
    
@Vee: Good questions! Three+ bodies and static bodies are two separate issues. I addressed both in an update. Summary: handle collisions two objects at a time; static bodies have very large, infinite mass. –  Leftium Feb 6 '13 at 18:25
    
Your model for resting contacts is odd. Resting contacts aren't just for gravity, they should work for any force. The easiest way that works is to just remove the velocity gained due to acceleration in the previous frame upon contact. Also for small velocities you can remove restitution completely, though your calculations don't account for restitution. This approach works for all forces, it's easy to implement and looks good enough. –  dreta Feb 21 '13 at 18:32
add comment

enter image description here

In the real world, there is no force that "pushes" one body outside of another body because objects don't ever penetrate each other. The closest thing is the normal force: created at the moment of contact in real-world collisions, it prevents penetration in the first place.

The angle of this normal force is perpendicular to the contact surface of the two colliding objects. The magnitude depends on how much force is needed to prevent penetration. (Note only the y component of the normal force should be used unless other forces like the friction force are also modeled).

While is is possible to explicitly model the normal force, it is simpler to model only its effects:

  1. Prevent object intersection by either:
    • Adjusting velocities by resolving collisions at the moment of impact. (best)
    • Manually adjusting the positions of the bodies so they do not intersect. (easier) You're already doing this "by finding the shortest penetration vector and adding it to the AABB's position."
  2. Do not apply gravity where there would be a normal force canceling out the gravity force.
    • An object in contact with another object below it is subject to the normal force. Thus it is a matter of keeping track of those objects. (Actually any objects that are in contact should have a normal force applied, but not all of these will have a net effect with respect to gravity.)
    • If you want to add objects that can slide down other objects that are at an angle, you will have to add the friction force and x component of the normal force.

I described this slightly differently in my other answer which is more about collisions in general.

share|improve this answer
add comment

Solving this problem requires adjusting position and possibly velocity. Rigid body physics engines have a solver that march objects forward in time using Newton's laws of motion while also solving non-penetration constraints and friction. These engines can compute the right combination of linear and angular motion to create plausible trajectories.

If you only want to resolve overlap, you can use pseudo velocities that generate separating trajectories without adding to momentum. This is done in Box2D's position solver.

I recommend getting my GDC presentations from 2006 and 2007 here:

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

Also, you can look at Box2D Lite for a simplified implementation.

share|improve this answer
    
+1 for the remark of being necessary to adjust the position as well. Few people indulge this, but to add to the simulation stability, most engines cheat by adjusting the positions directly. All in all, if it's plausible, it works for games. –  teodron Feb 6 '13 at 9:58
    
Thanks for the answer. I wanted to know something which I probably missed in the presentation: are static bodies handled in a special way in Box2D? I mean - what happens when a dynamic body hits a static body? –  Vittorio Romeo Feb 6 '13 at 15:03
add comment

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.