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 )

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 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,

first of all: thanks for your reply!
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 )

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.

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 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.