2D polygon collision not working correctly

Math and Physics Programming

Started by Boonio February 07, 2008 02:01 PM

3 comments, last by Boonio 16 years, 2 months ago

128

Author

February 07, 2008 02:01 PM

Hi, I've been trying to get 2D polygon collision working properly for the past week or so, I've been using a tutorial from another site so the code might look familiar (based on the Sperating Axis Theorem). It is almost working, but for some reason the Minimum Translation vector returned by CheckCollision() function will sometimes be pointing the wrong way. This means than when an object collides with my 2D terrain it will often get sucked down into the floor. I've been tearing my hair out for days with this and I just cannot figure out why this is happening. Here's the collision detection code:

[source lang = "cpp"]

// Calculate the projection of a polygon onto an axis
int cCollisionManager::PolygonProjection(D3DXVECTOR2 _vAxis, cPolygon *_pPolygon, float &min, float &max)

{
	D3DXVECTOR2 *pVerts = _pPolygon->GetWorldVertices();

	// Use the dotproduct to project an point on an axis
	float dotProduct = D3DXVec2Dot(&_vAxis, &pVerts[0]);

	// Set the default min and max of the projection
	min = dotProduct;
	max = dotProduct;

	for (int count = 0; count < _pPolygon->GetNumVertices(); count++) 
	{
		// Get the projection of the next point 
		dotProduct = D3DXVec2Dot(&pVerts[count], &_vAxis);

		// Update the min/max
		if (dotProduct < min) 
			min = dotProduct;
		else 
			if (dotProduct> max) 
				max = dotProduct;
	}

	return 1;
}

// Calculate the distance between two intervals of an axis
float cCollisionManager::IntervalDistance(float _minA, float _maxA, float _minB, float _maxB)

{
	// Calculate the distance
	if (_minA < _minB)
		return _minB - _maxA;
	else
		return _minA - _maxB;
}

/////////////////////////////
// Public functions
//////////////////////////

// Check for collision between two cPolygons
sCollisionResult cCollisionManager::CheckCollision(cPolygon *_pPoly1, cPolygon *_pPoly2, D3DXVECTOR2 _pVelocity)

{
	sCollisionResult tempResult;
	float minIntervalDistance = std::numeric_limits<float>::infinity();

	D3DXVECTOR2 translationAxis;
	D3DXVECTOR2 edge;

	tempResult.isIntersected = true;
	tempResult.willIntersect = true;

	// Loop through all the edges of both polygons
	for (int edgeIndex = 0; edgeIndex < _pPoly1->GetNumVertices() + _pPoly2->GetNumVertices(); edgeIndex++) 
	{
		// Get the correct edge
		if (edgeIndex < _pPoly1->GetNumVertices()) 
			_pPoly1->GetEdge(edgeIndex, &edge);
		else 
			_pPoly2->GetEdge(edgeIndex - _pPoly1->GetNumVertices(), &edge);

		// Find the axis perpendicular to the current edge
		D3DXVECTOR2 axis = D3DXVECTOR2(-edge.y, edge.x);
		//	D3DXVec2Normalize(&axis, &axis);


		float minA = 0; 
		float minB = 0; 
		float maxA = 0; 
		float maxB = 0;

		// Find the projection of the polygon on the current axis
		PolygonProjection(axis, _pPoly1, minA, maxA);
		PolygonProjection(axis, _pPoly2, minB, maxB);

		// Check if the projection are currently intersecting
		if (IntervalDistance(minA, maxA, minB, maxB) > 0)
			tempResult.isIntersected = false;

		// Now find if the polygons *will* intersect

		// Project the velocity on the current axis
		float velocityProjection = D3DXVec2Dot(&axis, &_pVelocity);

		// Get the projection of polygon A during the movement
		if (velocityProjection < 0) 
			minA += velocityProjection;
		else
			maxA += velocityProjection;


		// Do the same test as above for the new projection
		float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
		if (intervalDistance > 0) 
			tempResult.willIntersect = false;

		// If the polygons are not intersecting and won't intersect, exit the loop
		if (!tempResult.isIntersected && !tempResult.willIntersect) 
			break;

		// Check if the current interval distance is the minimum one. If so store
		// the interval distance and the current distance.
		// This will be used to calculate the minimum translation vector
		intervalDistance = fabs(intervalDistance);

		if (intervalDistance < minIntervalDistance) 
		{
			minIntervalDistance = intervalDistance;
			translationAxis = axis;

			D3DXVECTOR2 d = _pPoly1->GetPosition() - _pPoly2->GetPosition();

			if (D3DXVec2Dot(&d, &translationAxis) < 0)
				translationAxis = -translationAxis;
		}
	}

	// The minimum translation vector
	// can be used to push the polygons appart.
	if (tempResult.willIntersect)
		tempResult.vMTD = translationAxis * minIntervalDistance;



	return tempResult;
}

An implementation of the above is:



		for(int sectcount = 0; sectcount < 199; sectcount++)
		{
			tempCollision = CollisionManager.CheckCollision(&PolyTerrain[sectcount], &Square, D3DXVECTOR2(0,0));

			if(tempCollision.isIntersected)
			{
				SquarePos = SquarePos - tempCollision.vMTD;

				
			}
		}

This loops through a randomised 2D terrain checking collision against the Square object. Any help is much appreciated, and let me know if this too vague or whatever, I just didn't want to paste in tonnes of code. Thanks.

flounder

100

February 08, 2008 12:05 AM

The problem is probably being caused because 2 sides of the square will return the same transition distance since they're parallel, and due to rounding error either side can be chosen in different situations.

If all that you're checking is square vs terrain, you can probably get away with just reversing the normal if it doesn't push the terrain and square's centers away:
(assuming the terrain is made up of lines)

if (normal.dot(square_center-line_center)<0.0f){     normal=-normal;}

you might need to change the "<0.0f" to ">0.0f", and with this method you're going to have to assume either the polygon or the terrain will always do the pushing.

edit: if you saw the post before the edit, ignore what i said. it's actually a lot more involved than that.

[Edited by - flounder on February 8, 2008 9:05:15 AM]

agogsoft

Boonio

128

Author

February 08, 2008 02:31 PM

Hi,

Thanks for the response, much appreciated.

I'm already doing that at the bottom of the CollisionCheck() function (source below), but it does sound like what you say. I'll keep messing around with that.

It works for the majority of the blocks in my terrain but for some (and it's the same ones every time) it just refuses to give the translation vector facing the right way. This is the most annoying coding problem I've ever had I think.

		intervalDistance = fabs(intervalDistance);		if (intervalDistance < minIntervalDistance) 		{			minIntervalDistance = intervalDistance;			translationAxis = axis;			D3DXVECTOR2 d = _pPoly1->GetPosition() - _pPoly2->GetPosition();			if (D3DXVec2Dot(&d, &translationAxis) < 0.0f)			{				translationAxis = -translationAxis;			}		}

I'll try and think of something else to add which might be affecting it.

Thanks.

flounder

100

February 08, 2008 03:37 PM

Ack! should have actually looked at your code...

Well then i can give you the solution that i came up with when i was fed up with that algorithm. It should work for any polygon so long as the center is within the polygon.

In addition to recording the minimum and maximum shadows for the SAT collision, record the vertices that were associated with the shadow, in your code:

// Get the projection of the next point 		dotProduct = D3DXVec2Dot(&pVerts[count], &_vAxis);		// Update the min/max		if (dotProduct < min) 			min = dotProduct;                        vmin=count;		else 			if (dotProduct> max) 				max = dotProduct;                                vmax=count;

if the new mtd turns out to be the shortest mtd, record the vertex used in the mtd, as well as the polygon the vertex was on:

		if (intervalDistance < minIntervalDistance) 		{			minIntervalDistance = intervalDistance;			translationAxis = axis;                        mtd_polygon=edgeIndex<_pPoly1->GetNumVertices()?_pPoly1:_pPoly2;                        mtd_vertex=//the vertex of the minimum or maximum shadow, whichever was shorter;			D3DXVECTOR2 d = _pPoly1->GetPosition() - _pPoly2->GetPosition();			if (D3DXVec2Dot(&d, &translationAxis) < 0)				translationAxis = -translationAxis;		}

The actual min/max vertex that you choose will have to be flipped depending on if you're checking the vertices of polygon A or B.
My code for determining the mtd looks like:

d0=min1-offset+max2;//signs are probably messed upd1=min2-max1+offset;//signs are probably messed upif (d0>0.0f || d1>0.0f){return}if (d0>mtd_dist)//since they are negative, greater is smaller{     mtd_polygon=...whichever one isn't creating the axis;     mtd_vertex=min_vert;//might be max, depends on which polygon is being checked     mtd_dist=d0;}if (d1>mtd_dist)//since they are negative, greater is smaller{     mtd_polygon=...whichever one isn't creating the axis;     mtd_vertex=max_vert;//might be min, depends on which polygon is being checked     mtd_dist=d1;}

when you believe you have the mtd vector, change the current vector flipping check to:

if ((mtd_polygon->vertex[mtd_vertex]-mtd_polygon->center).dot(mtd_normal)<0.0f){mtd_normal=-mtd_normal;}

This assumes that everything is in world coordinates. If you're using rotation matrices you're going to have to apply them to the normal or the vertex.

Most of this is off the top of my head, i'm just trying to explain the concept.

agogsoft

Boonio

128

Author

February 08, 2008 05:19 PM

It works!

The problem was with the normal flipping as you originally said, the world positions of the polygons where being calculated wrong and that was causing the odd behaviour. I never would have spotted it without the help.

Thanks a lot, much appreciated. Now I can sleep!

2D polygon collision not working correctly

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

2D polygon collision not working correctly

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines