Jump to content
  • Advertisement
Sign in to follow this  
Boxiom

Bounding box collision detection

This topic is 1294 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to make an algorithm for handling collision between two bounding boxes (my player, and some solid object) without using the sf::Rect intersects that SFML provides. Right now, this is how I detect the actual collision:

if (obstacle.GetPosition().x < p.getPlayerPosition().x + p.getPlayerSize().x &&
obstacle.GetPosition().x + obstacle.GetSize().x > p.getPlayerPosition().x &&
obstacle.GetPosition().y < p.getPlayerPosition().y + p.getPlayerSize().x &&
obstacle.GetSize().y + obstacle.GetPosition().y > p.getPlayerPosition().y)
{
// Collision
}

However, I also need to figure out on which of the obstacles four sides the player collides, so I can set the correct player position. Does anyone have any ideas on how this can be done as simple and effective as possible?

Share this post


Link to post
Share on other sites
Advertisement

The fastest I've found:

bool AabbAabb(const CAabb& _aLeft, const CAabb& _aRight) {
	return (_aLeft.m_vMin.x <= _aRight.m_vMax.x) && (_aLeft.m_vMin.y <= _aRight.m_vMax.y) && (_aLeft.m_vMin.z <= _aRight.m_vMax.z) &&
		(_aLeft.m_vMax.x >= _aRight.m_vMin.x) && (_aLeft.m_vMax.y >= _aRight.m_vMin.y) && (_aLeft.m_vMax.z >= _aRight.m_vMin.z);
}

The code below applies to the three-dimensional case, but you can convert not using the z-axis.

bool CAabbAabb::Intersect(CCollisionObject* _pcoObjectA, CCollisionObject* _pcoObjectB, CContact* _pcContact) {
	static CVector3 vAxis[3] = {
		CVector3(1.0f, 0.0f, 0.0f),
		CVector3(0.0f, 1.0f, 0.0f),
		CVector3(0.0f, 0.0f, 1.0f),
	};

	CVector3 vMinAxis(FLT_MAX, FLT_MAX, FLT_MAX);
	float fMinDistance = FLT_MAX;
	
	CVector3 vMinA;
	CVector3 vMaxA;

	CVector3 vMinB;
	CVector3 vMaxB;

	_pcoObjectA->ComputeAabb(vMinA, vMaxA);
	_pcoObjectB->ComputeAabb(vMinB, vMaxB);

	for ( unsigned int I = 0; I < 3; ++I ) {
		if ( !TestAxis( vAxis[I], vMinA[I], vMaxA[I], vMinB[I], vMaxB[I], vMinAxis, fMinDistance ) ) { return false; }
	}

	_pcContact->fDepth = ::Sqrt(fMinDistance);
	_pcContact->vNormal = ::Normalize(vMinAxis);

	return true;
}

bool CBoxBox::TestAxis(const CVector3& _vAxis, float _f32MinA, float _f32MaxA, float _f32MinB, float _f32MaxB, CVector3& _vMinAxis, float& _f32MinDistance) {
	float fAxisSqLen = ::LengthSq( _vAxis );
	if (fAxisSqLen <= 0.0f) {
		return true; 
	}

	float fDifA = _f32MaxB - _f32MinA;
	float fDifB = _f32MaxA - _f32MinB;
	if (fDifA <= 0.0f || fDifB <= 0.0f) {
		return false;
	}

	float fRealDif = ( fDifA < fDifB ) ? fDifA : -fDifB;

	CVector3 vSeparationAxis = _vAxis * (fRealDif / fAxisSqLen);
	float fSeparationSqLen = LengthSq( vSeparationAxis );
	if (fSeparationSqLen < _f32MinDistance) {
		_vMinAxis = vSeparationAxis;
		_f32MinDistance = fSeparationSqLen;
	}

	return true;
}

The intersection test it is not optimized, I haven't used for a long time, but still works.

Also, you need to correct the objects positions:

_pcoObjectA->vPos += _pcContact.fNormal * _pcContact->fDepth;
_pcoObjectB->vPos -= _pcContact.fNormal * _pcContact->fDepth;
Edited by Irlan

Share this post


Link to post
Share on other sites

It is better practice to have an AABB which has the min and max values of objects.
You need to update it whenever the object moves or changes its size.

 

[source]

struct AABB
{
    int x_min;
    int x_max;
    int y_min;
    int y_max;
};
 
bool HasCollision( const AABB &a, const AABB &b )
{
    // if there is no overlap on x axis we can return false right away
    // so we don1t have to check y axis
    if ( a.x_max < b.x_min || a.x_min > b.x_max )
    {
        return false;
    }
 
    if ( a.y_max < b.y_min || a.y_min > b.y_max )
    {
        return false;
    }
 
    return true;
}
[/source]
Edited by mandyedi

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!