Jump to content
  • Advertisement
Sign in to follow this  
tharuin

SAT bouncing resolution

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

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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,

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 )

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!