SAT bouncing resolution

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

Recommended Posts

Heyho,

for a game I managed to get SAT-collision testing working by mixing some examples and codes I've found. My problem now is that while resolving my collision I want my object ( only 1 moving object, all others are static ) to bounce from the edge of the collided polygon. My code looks like this:
 static public void ResolveCollisions() { GameObject currentObj; for (int i = 0; i < _Objects.Count; i++) { currentObj = _Objects; for (int x = 0; x < _Objects.Count; x++) { if (currentObj != _Objects[x]) { if (!currentObj.IsStatic) { Vector2 Collision = CollisionCheck.Collide(currentObj.Polygon, _Objects[x].Polygon); if (Collision != Vector2.Zero) { currentObj.Velocity *= Vector2.Normalize(Collision); } } } } } }

 public static Vector2 Collide(Polygon A, Polygon B) { if (A.Points.Count > 0 && B.Points.Count > 0) { List<Vector2> Axis = new List<Vector2>(); for (int i = 0; i < A.Points.Count; i++) { Vector2 a, b; a = A.Points; if (i + 1 >= A.Points.Count) b = A.Points[0]; else b = A.Points[i + 1]; Axis.Add(b - a); } for (int i = 0; i < B.Points.Count; i++) { Vector2 a, b; a = B.Points; if (i + 1 >= B.Points.Count) b = B.Points[0]; else b = B.Points[i + 1]; Axis.Add(b - a); } Vector2 CollisionNormal = Vector2.Zero; foreach (Vector2 axis in Axis) { Vector2 normal = Vector2.Normalize(new Vector2(-axis.Y, axis.X)); float minA = 0, minB = 0, maxA = 0, maxB = 0; ProjectPolygon(normal, A, ref minA, ref maxA); ProjectPolygon(normal, B, ref minB, ref maxB); float gap = GapWidth(minA, maxA, minB, maxB); if (gap > 0) { return Vector2.Zero; } else { CollisionNormal = normal; } } return CollisionNormal; } else return Vector2.Zero; } static private float GapWidth(float minA, float maxA, float minB, float maxB) { if (minA < minB) return minB - maxA; else return minA - maxB; } static private void ProjectPolygon(Vector2 Axis, Polygon Polygon, ref float min, ref float max) { float dotProduct = Vector2.Dot(Axis, Polygon.Points[0]); min = dotProduct; max = dotProduct; for (int i = 0; i < Polygon.Points.Count; i++) { dotProduct = Vector2.Dot(Polygon.Points, Axis); if (dotProduct < min) min = dotProduct; else if (dotProduct > max) max = dotProduct; } }

The collisions are detected correct, the resoultion is really weird, though. In some cases it works ( even if the leaving angle isn't correct imo ). In others the object just stopps moving. Here I have a pictures showing the behaviour:

[attachment=6001:UnbenannteZeichnung.png]

Is there anything I did wrong? ( The idea with multiplying the velocity by the normal I read on a yt video comment :S )

Share on other sites

Is there anything I did wrong? ( The idea with multiplying the velocity by the normal I read on a yt video comment :S )

Hi,
This multiplication does seem a bit fishy.In general what you want to do with collision normal depends a lot how do you want to resolve the collision. Good first bet would be to reflect the velocity using the normal, so that would be:currentObj.Velocity = currentObj.Velocity - 2*dot(currentObj.Velocity,Collision) * Collision;http://mathworld.wol...Reflection.html

Share on other sites

[quote name='xbaalx' timestamp='1320593128' post='4881074']
Is there anything I did wrong? ( The idea with multiplying the velocity by the normal I read on a yt video comment :S )

Hi,
This multiplication does seem a bit fishy.In general what you want to do with collision normal depends a lot how do you want to resolve the collision. Good first bet would be to reflect the velocity using the normal, so that would be:currentObj.Velocity = currentObj.Velocity - 2*dot(currentObj.Velocity,Collision) * Collision;http://mathworld.wol...Reflection.html
[/quote]

Hello,

I've adjusted my collision detection code based on an example I found on the internet. I also added your reflection code. It looks like this now:
 static public void ResolveCollisions() { GameObject currentObj; for (int i = 0; i < _Objects.Count; i++) { currentObj = _Objects; for (int x = 0; x < _Objects.Count; x++) { if (currentObj != _Objects[x]) { if (!currentObj.IsStatic) { CollisionInfo Collision = CollisionCheck.Collide(currentObj.Polygon, _Objects[x].Polygon, currentObj.Velocity); if (Collision.WillCollide) { currentObj.Velocity = currentObj.Velocity - 2 * Vector2.Dot(currentObj.Velocity, Collision.Normal) * Collision.Normal; currentObj.Position = currentObj.PreviousPosition + currentObj.Velocity; Console.WriteLine(Collision); } } } } } } struct CollisionInfo { public CollisionInfo(bool collided) { Collided = collided; WillCollide = false; Gap = 0; Normal = Vector2.Zero; TranslationVector = Vector2.Zero; } public bool Collided; public bool WillCollide; public float Gap; public Vector2 Normal; public Vector2 TranslationVector; public override string ToString() { string ret = "Collided: " + Collided + " | Will Collide: " + WillCollide + " | Normal: " + Normal + " | Translation Vector: " + TranslationVector; return ret; } } static class CollisionCheck { public static CollisionInfo Collide(Polygon A, Polygon B, Vector2 relativeVelocity) { if (A.Points.Count > 0 && B.Points.Count > 0) { List<Vector2> Axis = new List<Vector2>(); for (int i = 0; i < A.Points.Count; i++) { Vector2 a, b; a = A.Points; if (i + 1 >= A.Points.Count) b = A.Points[0]; else b = A.Points[i + 1]; Axis.Add(b - a); } for (int i = 0; i < B.Points.Count; i++) { Vector2 a, b; a = B.Points; if (i + 1 >= B.Points.Count) b = B.Points[0]; else b = B.Points[i + 1]; Axis.Add(b - a); } CollisionInfo CollisionInfo = new CollisionInfo(); Vector2 translationAxis = Vector2.Zero; foreach (Vector2 axis in Axis) { //Step 1 Vector2 normal = Vector2.Normalize(new Vector2(-axis.Y, axis.X)); float minA = 0, minB = 0, maxA = 0, maxB = 0; ProjectPolygon(normal, A, ref minA, ref maxA); ProjectPolygon(normal, B, ref minB, ref maxB); float gap = GapWidth(minA, maxA, minB, maxB); if (gap > 0) { return new CollisionInfo(false); } else { CollisionInfo.Collided = true; if (Math.Min(gap, CollisionInfo.Gap) < CollisionInfo.Gap) { CollisionInfo.Gap = gap; CollisionInfo.Normal = normal; } } //Step 2 float velocityProjection = Vector2.Dot(axis, relativeVelocity); if (velocityProjection < 0) minA += velocityProjection; else maxA += velocityProjection; //Repeat Step 1 with the new min/max gap = GapWidth(minA, maxA, minB, maxB); if (gap > 0) CollisionInfo.WillCollide = false; else CollisionInfo.WillCollide = true; if (!CollisionInfo.Collided && !CollisionInfo.WillCollide) break; CollisionInfo.Gap = Math.Abs(gap); if (CollisionInfo.Gap < float.PositiveInfinity) { translationAxis = axis; Vector2 d = A.Center - B.Center; if (Vector2.Dot(d, translationAxis) < 0) translationAxis = -translationAxis; } } return CollisionInfo; } else { return new CollisionInfo(false); } } static private float GapWidth(float minA, float maxA, float minB, float maxB) { if (minA < minB) return minB - maxA; else return minA - maxB; } static private void ProjectPolygon(Vector2 Axis, Polygon Polygon, ref float min, ref float max) { float dotProduct = Vector2.Dot(Axis, Polygon.Points[0]); min = dotProduct; max = dotProduct; for (int i = 0; i < Polygon.Points.Count; i++) { dotProduct = Vector2.Dot(Polygon.Points, Axis); if (dotProduct < min) min = dotProduct; else if (dotProduct > max) max = dotProduct; } } } 

The resolution works perfect for 1/4 of all edges, but is messed up for all the others. The following images shows the working edges ( green ones ):

[attachment=6004:UnbenannteZeichnung(2).png]
You can download the binary here ( http://dl.dropbox.co...375/Release.rar ), I hope its okay to post it. You can turn debug draw on by pressing "T" ( to see the polygons )

Share on other sites
Hi again,

I'm not sure the exact source of your problems but normals from your debug output look a bit strange.
For example both vertical sides of the large rectangle in the bottom of the screen give (1, 0) normal. One of them (left I think) should have a (-1, 0) normal.

Share on other sites

Hi again,

I'm not sure the exact source of your problems but normals from your debug output look a bit strange.
For example both vertical sides of the large rectangle in the bottom of the screen give (1, 0) normal. One of them (left I think) should have a (-1, 0) normal.

I've tried to reduce the whole collision checking to a minimum now. ( ProjectPlygon() and GapWidth() stayed the same )

 static public void ResolveCollisions() { GameObject currentObj; for (int i = 0; i < _Objects.Count; i++) { currentObj = _Objects; for (int x = 0; x < _Objects.Count; x++) { if (currentObj != _Objects[x]) { if (!currentObj.IsStatic) { CollisionInfo Collision = CollisionCheck.Collide(currentObj.Polygon, _Objects[x].Polygon, currentObj.Velocity); if (Collision.Collided) { currentObj.Velocity = (currentObj.Velocity - 2 * Vector2.Dot(currentObj.Velocity, Collision.Normal) * Collision.Normal * 0.9f); currentObj.Position = currentObj.PreviousPosition; ((Player)currentObj).Acceleration = Vector2.Zero; Console.WriteLine(Collision.Normal); } } } } } }
public static CollisionInfo Collide(Polygon A, Polygon B, Vector2 relativeVelocity) { if (A.Points.Count > 0 && B.Points.Count > 0) { List<Vector2> Axis = new List<Vector2>(); for (int i = 0; i < A.Points.Count; i++) { Vector2 a, b; a = A.Points; if (i + 1 >= A.Points.Count) b = A.Points[0]; else b = A.Points[i + 1]; Axis.Add(b - a); } for (int i = 0; i < B.Points.Count; i++) { Vector2 a, b; a = B.Points; if (i + 1 >= B.Points.Count) b = B.Points[0]; else b = B.Points[i + 1]; Axis.Add(b - a); } CollisionInfo CollisionInfo = new CollisionInfo(); Vector2 TranslationAxis = Vector2.Zero; foreach (Vector2 axis in Axis) { Vector2 Normal = Vector2.Normalize(new Vector2(-axis.Y, axis.X)); float minA = 0, minB = 0, maxA = 0, maxB = 0; ProjectPolygon(Normal, A, ref minA, ref maxA); ProjectPolygon(Normal, B, ref minB, ref maxB); float Gap = GapWidth(minA, maxA, minB, maxB); if (Gap > 0) { return new CollisionInfo(false); } else { CollisionInfo.Collided = true; if (Math.Min(Gap, CollisionInfo.Gap) < CollisionInfo.Gap) { CollisionInfo.Gap = Gap; CollisionInfo.Normal = Normal; } } } return CollisionInfo; } else { return new CollisionInfo(false); } }

Now its sometimes stuck inside another polygon and still resolves wrong.

Share on other sites

[quote name='barsiwek' timestamp='1320624164' post='4881203']
Hi again,

I'm not sure the exact source of your problems but normals from your debug output look a bit strange.
For example both vertical sides of the large rectangle in the bottom of the screen give (1, 0) normal. One of them (left I think) should have a (-1, 0) normal.

I've tried to reduce the whole collision checking to a minimum now. ( ProjectPlygon() and GapWidth() stayed the same )

 static public void ResolveCollisions() { GameObject currentObj; for (int i = 0; i < _Objects.Count; i++) { currentObj = _Objects; for (int x = 0; x < _Objects.Count; x++) { if (currentObj != _Objects[x]) { if (!currentObj.IsStatic) { CollisionInfo Collision = CollisionCheck.Collide(currentObj.Polygon, _Objects[x].Polygon, currentObj.Velocity); if (Collision.Collided) { currentObj.Velocity = (currentObj.Velocity - 2 * Vector2.Dot(currentObj.Velocity, Collision.Normal) * Collision.Normal * 0.9f); currentObj.Position = currentObj.PreviousPosition; ((Player)currentObj).Acceleration = Vector2.Zero; Console.WriteLine(Collision.Normal); } } } } } }
public static CollisionInfo Collide(Polygon A, Polygon B, Vector2 relativeVelocity) { if (A.Points.Count > 0 && B.Points.Count > 0) { List<Vector2> Axis = new List<Vector2>(); for (int i = 0; i < A.Points.Count; i++) { Vector2 a, b; a = A.Points; if (i + 1 >= A.Points.Count) b = A.Points[0]; else b = A.Points[i + 1]; Axis.Add(b - a); } for (int i = 0; i < B.Points.Count; i++) { Vector2 a, b; a = B.Points; if (i + 1 >= B.Points.Count) b = B.Points[0]; else b = B.Points[i + 1]; Axis.Add(b - a); } CollisionInfo CollisionInfo = new CollisionInfo(); Vector2 TranslationAxis = Vector2.Zero; foreach (Vector2 axis in Axis) { Vector2 Normal = Vector2.Normalize(new Vector2(-axis.Y, axis.X)); float minA = 0, minB = 0, maxA = 0, maxB = 0; ProjectPolygon(Normal, A, ref minA, ref maxA); ProjectPolygon(Normal, B, ref minB, ref maxB); float Gap = GapWidth(minA, maxA, minB, maxB); if (Gap > 0) { return new CollisionInfo(false); } else { CollisionInfo.Collided = true; if (Math.Min(Gap, CollisionInfo.Gap) < CollisionInfo.Gap) { CollisionInfo.Gap = Gap; CollisionInfo.Normal = Normal; } } } return CollisionInfo; } else { return new CollisionInfo(false); } }

Now its sometimes stuck inside another polygon and still resolves wrong.
[/quote]

I solved this problem by rewriting the whole code. I can'T say what it was but I think I messed up something critical in my previous code.

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• Forum Statistics

• Total Topics
633653
• Total Posts
3013167
×