I have written an algorithm which resolves collisions between axis aligned rectangles so that they are resting against one another after collision resolution.

The code is in Java using LibGDX

public class Rectangle
{
    public Vector2 position;
    public float halfW, halfH;
    private Vector2 restingDistance, currentDistance, overlap;

    public Rectangle(Vector2 position, float halfW, float halfH)
    {
        this.position = position;
        this.halfW = halfW;
        this.halfH = halfH;
        this.restingDistance = new Vector2();
        this.currentDistance = new Vector2();
        this.overlap = new Vector2();
    }

    public boolean intersects(Rectangle rectangle)
    {
        return (position.x - halfW < rectangle.position.x + rectangle.halfW &&
                position.x + halfW > rectangle.position.x - rectangle.halfW &&
                position.y - halfH < rectangle.position.y + rectangle.halfH &&
                position.y + halfH > rectangle.position.y - rectangle.halfH);
    }

    public void resolveCollision(Rectangle rectangle)
    {
        // Calculate the resting distance of the two rectangles
        restingDistance.set(halfW + rectangle.halfW, halfH + rectangle.halfH);

        // Calculate the current distance between the two rectangles
        currentDistance.set(position.x - rectangle.position.x, position.y - rectangle.position.y);

        // Calculate the overlap between the two rectangles
        overlap.set(restingDistance.x - Math.abs(currentDistance.x), restingDistance.y - Math.abs(currentDistance.y));

        // Remove the overlap of the axis with the greater overlap
        overlap.set(overlap.x < overlap.y ? overlap.x : 0, overlap.y < overlap.x ? overlap.y : 0);

        // Reverse the direction of the overlap depending on the positions of the rectangles
        overlap.set(position.x < rectangle.position.x ? -overlap.x : overlap.x, position.y < rectangle.position.y ? -overlap.y : overlap.y);
          
        // Add the overlap to the rectangles position
        position.add(overlap);
    }
}

The code is used like this

if(rectangle1.intersects(rectangle2))
{
    rectangle1.resolveCollision(rectangle2);
}

From my testing the code works. Colliding rectangles are moved out of collision so that they are resting against one another. Are there any problems with the way the code resolves collisions? Can the collision resolution code be improved and if so how? Thank you.

You resolve a collision yet you don't account for the velocities of the rects ( or the rects previous positions ). This is going to be necessary or at least I think so. The issue you will encounter is that a rect of arbitrary dimensions is moving along and it will either collide with the bottom/top or the left/right of the other rect, but which one depends on the dimensions of the two rects. The solution I took was to calculate both potential edges and determine which is correct. The greater overlap that you are using isn't necessarily the correct overlap given the velocity.

h8CplusplusGuru is right about velocities, but I think there are cases where continuous collision detection may not be necessary. For example, you might have an upper limit on per-update deltas sufficient to prevent unacceptable tunneling behavior.

Even then, what h8CplusplusGuru describes could occur, that is, the collision resolution could be applied in the 'wrong' direction. However, I can imagine scenarios where this slight inaccuracy would be benign and/or unnoticeable. In any case, it seems like a discrete test could be appropriate in some contexts.

Just as a general programming note, is there a reason the 'restingDistance', 'currentDistance', and 'overlap' variables are member fields? Are they used outside of the resolveCollision() function?

On 2/9/2019 at 3:20 PM, Zakwayda said:

Just as a general programming note, is there a reason the 'restingDistance', 'currentDistance', and 'overlap' variables are member fields?

Yes, these variables are member variables so that I do not instantiate new vectors each time the resolveCollision() function is called, which may be many times per frame. It is for performance reasons.

I do not understand what you mean about the need to take velocity into account. Would you please expand on that?

Yes that's right I do handle collisions discretely, they are resolved after the collisions have already occurred. In terms of potential object tunneling this is not a problem for me as if it does occur I will adjust the objects dimensions and speed so that it does not.

Is my approach to resolving collisions flawed or is it acceptable? I'm not sure if it is a problem but I have a feeling that taking the objects positions into account to determine the direction of displacement out of collision is wrong somehow or a bad way of doing it. It works of course but is it "proper"?

Here is the algo I used on a platformer recently. I am unsure if the following line is 100% correct as I haven't done as much testing as I'd like however it all seems to work just fine. Note that this only considers that the player has a velocity, not both objects. I haven't considered two velocities yet, though maybe this could be a starting point for you.

if (xD < yD && xDV.y() ){} //unsure if this is the correct way to determine outcome

The complete routine is as follows:

	void collisionCallback(btCollisionObject* obj1, btCollisionObject* obj2) {
		CollisionPhysics::CollisionObject* objA = static_cast<CollisionPhysics::CollisionObject*>(obj1->getUserPointer());
		CollisionPhysics::CollisionObject* objB = static_cast<CollisionPhysics::CollisionObject*>(obj2->getUserPointer());

	
		if (objB->getCollisionID() == COLLISION_IDS::ID_PLATFORM)
		std::swap(objA, objB);

		if (objA->getCollisionID() == COLLISION_IDS::ID_PLATFORM) {

			if (objB->getCollisionID() == COLLISION_IDS::ID_PLAYER) {

				//a collision between these two objects has occured

				//platform collides with player, uncollide player;
				GameObject* player = dynamic_cast<GameObject*>(objB);
				PlatformObject* platform = dynamic_cast<PlatformObject*>(objA);


				btBox2dShape* playerBox = dynamic_cast<btBox2dShape*>(player->getCollisionObject()->getCollisionShape());
				btVector3 playerHalf = playerBox->getHalfExtentsWithoutMargin();

				btBox2dShape* platformBox = dynamic_cast<btBox2dShape*>(platform->getCollisionObject()->getCollisionShape());
				btVector3 platformHalfNoMargin = platformBox->getHalfExtentsWithoutMargin();

				btVector3 platOrigin = platform->getTransform().getOrigin();
				btVector3 playerOrigin = player->getTransform().getOrigin();


				// determine what quadrant the player object is in compared to the platform

				btScalar polarityX = 1;
				btScalar polarityY = 1;
				btVector3 playerVel = player->getVelocity();

				btVector3 platformQuadrantPoint(0, 0, 0);

				if (playerVel.y() > 0) { //going up
					platformQuadrantPoint.setY( platOrigin.y() - platformHalfNoMargin.y() );
					polarityY = 1;
				}
				else {//going down
					platformQuadrantPoint.setY( platOrigin.y() + platformHalfNoMargin.y() );
					polarityY = -1;
				}
				if (playerVel.x() > 0) {
					platformQuadrantPoint.setX( platOrigin.x() - platformHalfNoMargin.x() );
					polarityX = 1;
				}
				else {
					platformQuadrantPoint.setX( platOrigin.x() + platformHalfNoMargin.x() );
					polarityX = -1;
				}
				
				//now get both possible outcomes and then determine which one is correct

				btVector3 theoreticalPositionY, theoreticalPositionX;

				btVector3 playerPrevOrigin = playerOrigin - playerVel;

				//come up with y-edge position
				//we know the desired y-coord:
				btScalar y = platformQuadrantPoint.y() - polarityY * playerHalf.y();

				btScalar m = 0;
				if (playerVel.x() != 0)
					m = (playerVel.y() / playerVel.x());

				btScalar x = 0;

				if (playerVel.x() != 0 && m)
					x = (y - playerPrevOrigin.y()) / m + playerPrevOrigin.x();
				else 
					x = playerOrigin.x();
				
				theoreticalPositionY = btVector3(x, y, 0);

				//now come up with x-edge position

				//we know the desired x-coord:
				x = platformQuadrantPoint.x() - polarityX * playerHalf.x();

				if (playerVel.y() != 0 && m)
					y = m * (x - playerPrevOrigin.x()) + playerPrevOrigin.y();
				else 
					y = playerPrevOrigin.y();

				theoreticalPositionX = btVector3(x, y, 0);

				btScalar deCollide = 0.5f; 

				//get distance to each theorypoint, the furthest 

				btVector3 xDV = (theoreticalPositionX ) - playerPrevOrigin;
				btVector3 yDV = (theoreticalPositionY ) - playerPrevOrigin;

				btScalar xD = xDV.length();
				btScalar yD = yDV.length();

				btVector3 finalPosition;

				if (xD < yD && xDV.y() ) {
					finalPosition = theoreticalPositionX - btVector3(polarityX* deCollide, 0, 0);
					player->stopX();
				
				}
				else {
					finalPosition = theoreticalPositionY - btVector3(0, polarityY * deCollide, 0);

					if (polarityY > 0) {
						player->startFalling();
					}
					else {
						player->stopFalling();
						
					}
					player->stopY();
				}

				btTransform trans;
          		trans.setIdentity();
				trans.setOrigin(finalPosition);
				player->setTransform(trans);
			}

		}
	
	}

Let me know if this is useful and you have any questions or come up with a two-velocity method.

Quote

Yes, these variables are member variables so that I do not instantiate new vectors each time the resolveCollision() function is called, which may be many times per frame. It is for performance reasons.

I see. There are some interesting considerations here, but since it's off topic, I'll just mention that if you want or need to pool vector objects, you could possibly make them static members of the 'Rectangle' class, or perhaps even implement a general-purpose pooling system (which might be preferable if you find yourself creating temporary vectors often). In any case, unless I'm missing something (which I may be), there's probably no need for them to be instance members.

h8CplusplusGuru's response may include all the info you need, but regarding the rest of your post, it's not a given that you need to take velocity into account. It really just depends on the circumstances. In some contexts, a discrete test may be adequate.

The only thing I'll mention with respect to tunneling (and you may have already thought of this) is that considering object dimensions and speed isn't necessarily sufficient; you may also need to ensure there's an upper bound on time deltas.

Quote

Is my approach to resolving collisions flawed or is it acceptable? I'm not sure if it is a problem but I have a feeling that taking the objects positions into account to determine the direction of displacement out of collision is wrong somehow or a bad way of doing it. It works of course but is it "proper"?

Although I could be misinterpreting your code, it looks like you're essentially implementing a 'minimum penetration' algorithm, which is a valid way of resolving intersections, generally speaking. As discussed earlier, with this approach you can get 'wrong' results that are different than what a continuous test would return, but whether that's an issue or not is context-dependent (see earlier in the thread for some discussion on this).

1 hour ago, Zakwayda said:

Although I could be misinterpreting your code, it looks like you're essentially implementing a 'minimum penetration' algorithm

Yes that's correct, I am calculating a Minimum Translation Vector and using it to move the objects out of collision so that they are resting against one another. What I would like to know is if the way in which I calculate this displacement vector is valid. As part of this calculation I look at each objects position to determine the direction of displacement. Is comparing positions like this a valid way of calculating the MTV or is it a flawed approach?

Quote

What I would like to know is if the way in which I calculate this displacement vector is valid. As part of this calculation I look at each objects position to determine the direction of displacement. Is comparing positions like this a valid way of calculating the MTV or is it a flawed approach?

Something I just noticed is this:

overlap.set(overlap.x < overlap.y ? overlap.x : 0, overlap.y < overlap.x ? overlap.y : 0);

It seems to me that if overlap.x and .y are equal, you'll get (0, 0), which is incorrect. As such, it seems <= should be used rather than <.

Other than that, it may be that all I can say is that your code seems correct. However, I think I missed the above issue (assuming I'm right about it being an issue) the first time I looked at the code, so it's possible I'm missing something now as well. Maybe someone else will be able and willing to offer 100% confirmation that the code is correct, but due to the risk of making a mistake myself, I'm hesitant to do so.

I certainly understand your desire for certainty that your algorithm is correct. One thing I will say is that if you don't feel sufficiently confident in your current approach, you could implement the test in a perhaps more traditional way. This might allow you to more easily check your code against other examples. Also, although I doubt it matters in practice, your code takes a 'two-phase' approach that may involve a little unnecessary work, whereas a 'traditional' approach would typically perform the separating axis tests and track/compute the MTV at the same time.

If you haven't done so already, you might be able to find some good example implementations by searching for 'sat mtv' or similar terms.

[Edit: I should probably add that using <= as I suggested could result in the intersection being resolved along both axes. The traditional approach always resolves the intersection along only a single axis (to the best of my knowledge at least). If you want to stick with your current approach, you might consider selecting an axis exclusively, as I think is more typical.]