Jump to content
  • Advertisement
Sign in to follow this  
shahmirj

Polygon Collision going wrong

This topic is 3614 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

The concept of this algorithm is taken from below http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx What im trying to do here is to see if there is a seperating axis between the two polygons. I have tried many methods and im completely lost in where im going. Please also note this function is inside one polygon and its comparing it self to another polygon which is refrenced by "obj->poly[x]->". Instead of building edges every time.. This algorithm builds the edges as they are needed Please let me know if you dont understand any part of the code and il try to answer your questions.
int polysize = points.size() + obj->poly[x]->points.size();

for (int i = 0; i < polysize; i++){
		
	Vector p1, p2, edge;

	//Building Edges
	if (i >= points.size()){
			
		int counter = i - points.size();

		p1 = obj->poly[x]->points[counter];

		if (counter + 1 == obj->poly[x]->points.size()){ p2 = obj->poly[x]->points[0]; }
		else { p2 = obj->poly[x]->points[counter + 1]; }
	}
	else{
			
		if (i + 1 == points.size()){ p2 = points[0]; }
		else { p2 = points[i + 1]; }
	}

	edge = p2 - p1;
		
	Vector axis(-edge.y, edge.x);
	axis.Normalize();
		
	ProjectPolygon(axis);
	obj->poly[x]->ProjectPolygon(axis);

	if (IntervalDistance(min, max, obj->poly[x]->min, obj->poly[x]->max) > 0){ return false; }
}

Share this post


Link to post
Share on other sites
Advertisement
Correct me if I am wrong, but while you are constructing edges from your first polygon (i.e. while i<points.size() so while the else clause is being executed), you are not setting any value for p1, only p2.

So all your edges for this first phase are duff - either random, or from each point to origin depending on your Vector default constructor.

As an aside, to do SAT you only actually need to project onto all the axes that are unique - i.e. not running parrallel - if two axes are parrallel but in two different directions, you still only need to test against one (Sorry - I lack the math vocab to explain that better [smile]).

For this reason, it may be more sensible to figure out your axes first. My SAT implementation pregenerated the test axes (as normals) for each shape, then updated them when the shape was rotated. This moved anywhere between none to quite a lot of logic out of the actual per-loop test depending on how much rotation of the objects was going on.

Share this post


Link to post
Share on other sites
Quote:
so while the else clause is being executed
im guessing you are wondering WHY not WHILE.

Well the idea is that we are comparing two polygons and that the projection is carried out for each polygons's perpendicular edge so the first if is for the 'obj->poly[x]' and the 'else' is for the poly we are inside.


if (i >= points.size()){

int counter = i - points.size();

p1 = obj->poly[x]->points[counter];

if (counter + 1 == obj->poly[x]->points.size()){ p2 = obj->poly[x]->points[0]; }

else { p2 = obj->poly[x]->points[counter + 1]; }

}

else{

p1 = points; //Fixed mistake

if (i + 1 == points.size()){ p2 = points[0]; }

else { p2 = points[i + 1]; }

}



The p1 deceleration i realized that fixed it. still gave me similar problems

Let me send you a very primitive version of this code. see if you got any ideas



//get the min and max for the X and Y axis
//This is used for the early escape test
//Note: A[0].x == min of A, A[0].y == max of A... on the X axis
//^WHERE A[1].x is min of A on the Y Axis

deque<Vector> A = AABB();
deque<Vector> B = obj->poly[x]->AABB();

if (IntervalDistance(A[0].x, A[0].y, B[0].x, B[0].y) > 0){
return false;
}

if (IntervalDistance(A[1].x, A[1].y, B[1].x, B[1].y) > 0){
return false;
}

#pragma region Seperating Axis

for (int i = 0; i < points.size(); i++){

Vector p1, p2, edge;

p1 = getPvalue(i);

if (i + 1 == points.size()){ p2 = getPvalue(0); }
else { p2 = getPvalue(i + 1); }

edge = p2 - p1;

Vector axis(-edge.y, edge.x);
axis.Normalize();

ProjectPolygon(axis);
obj->poly[x]->ProjectPolygon(axis);

if (IntervalDistance(min, max, obj->poly[x]->min, obj->poly[x]->max) > 0){ return false; }
}


This one how ever is only projecting on the perpendicular of its own edges and not dealing with the other polygon.

Quote:
As an aside, to do SAT you only actually need to project onto all the axes that are unique - i.e. not running parrallel - if two axes are parrallel but in two different directions, you still only need to test against one (Sorry - I lack the math vocab to explain that better ).


I understand the calculation of the unique one's but for testing purposes it shouldnt matter if i test parallel edges..Should it?

Share this post


Link to post
Share on other sites
Use the method you have right above, and do another loop, looping for the points of the second polygon. So you'll have two for() loops.


#pragma region Seperating Axis

for (int i = 0; i < points.size(); i++)
{
Vector p1, p2, edge;

p1 = getPvalue(i);

if (i + 1 == points.size()){ p2 = getPvalue(0); }
else { p2 = getPvalue(i + 1); }

edge = p2 - p1;

Vector axis(-edge.y, edge.x);

axis.Normalize();

ProjectPolygon(axis);

obj->poly[x]->ProjectPolygon(axis);

if (IntervalDistance(min, max, obj->poly[x]->min, obj->poly[x]->max) > 0){ return false; }
}

for (int i = 0; i < obj->poly[x]->points.size(); i++)
{
Vector p1, p2, edge;

p1 = obj->poly[x]->getPvalue(i);

if (i + 1 == obj->poly[x]->points.size()){ p2 = obj->poly[x]->getPvalue(0); }
else { p2 = obj->poly[x]->getPvalue(i + 1); }

edge = p2 - p1;

Vector axis(-edge.y, edge.x);

axis.Normalize();

ProjectPolygon(axis);

obj->poly[x]->ProjectPolygon(axis);

if (IntervalDistance(min, max, obj->poly[x]->min, obj->poly[x]->max) > 0){ return false; }
}



BTW, you should not have to normalise the axis.

if you want less code duplication, create a function that does all the dirty work, something like



Vector Polygon::GetEdge(int i)
{
int j = i + 1;
if(j >= points.size()) { j = 0; }
Vector p1, p2;
Vector edge;
p1 = getPvalue(i);
p2 = getPvalue(j);
edge = p2 - P1;
return edge:
}

Vector Polygon::GetEdgePerpendicular(int i)
{
Vector edge:
Vector perp;
edge = GetEdge(i);
perp = Vector(-edge.y, edge.x);
return perp;
}

bool Polygon::AxisOverlap(Vector axis, Polygon* poly)
{
ProjectPolygon(axis);
poly->ProjectPolygon(axis);

if (IntervalDistance(min, max, poly->min, poly->max) > 0){ return false; }
else { return true: }
}

bool Polygon::Intersect(Polygon* poly)
{
for (int i = 0; i < points.size(); i++)
{
Vector perp;
perp = GetEdgePerpendicular(i);

if (AxisOverlap(perp, poly) == false) { return false; }
}

for (int i = 0; i < poly->points.size(); i++)
{
Vector perp;
perp = poly->GetEdgePerpendicular(i);

if (AxisOverlap(perp, obj) == false) { return false; }
}

return true;
}

Share this post


Link to post
Share on other sites
Thanks guys..

You wouldn't believe it.. Guess what i was defining one of my polygons wrong. Im sorry for that.. just realized it( Stupid Me :) ). But im sure all of you have faced similar problems in the past.. again Sorry my bad.

Olii on http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx this guy is normalizing.. i don't understand why it does not matter?

oh and in my code i am doing 2 for loops.. I didn't put them up in the post above just to not make things confusing. But i get the idea that we have to project on each of the polygon's edges

Share this post


Link to post
Share on other sites
When you project on the SAT axis, both the min and max values for both polygons will be equally scaled by the axis length (due to the dot product you perform for the point projections).

So when you do the comparaisons between the min and max values to detect separation, they are still valid (if a < b, then a * d < b * d, if d > 0).

This is less true when you start to look for the MTD between the two polygons. For that, you will be comparing the min, max intervals of each axeis against one another, and take the minimum interval overlap as your MTD.

The min and max values for each axes wont be uniformely scaled (as each axis will have different lengths), so you cannot compare each interval overlap against one another. A normalisation of each axis is necessary (so every min, max interval will not be scaled and everything will be uniform) .

However, you can work with squared axis lengths, and you can revert back to a uniform scaling for all axis results, and avoid normalisation.

Share this post


Link to post
Share on other sites
awesome olii.. every thing is working nice. I mean i have to sort out the Circle to Poly Collision but that shouldn't be a prob after this solution.

Ive looked at the theorem for that on 'N Tutorials'. Same solution with a little difference.

One more question. What about impulse. Please just guide me to the right link. Cause you guys have helped alot already. Il figure it out from there.

Thanks

Share this post


Link to post
Share on other sites
For collision reponse, your best bet is Chris Hecker's tutorials on physics.

I have some examples for response and collision detection. It's the swept SAT, which introduces the linear displacement to predict the tme of collision.

clicky

The collision response is based on Chris Hecker's stuff.

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!