Jump to content
  • Advertisement
Sign in to follow this  
Bombshell93

[FIXED] Resolving SAT collision, coming up short

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

stupid me accidentally posted this on Graphics programming -.-''

EDITEDIT:
Okay I managed to get SAT working for detection but resolving collisions is acting strangely.

EDITEDITEDIT:
I fixed it, yet another problem with my Vector 2 class, when normalizing I forgot the square root.


public static Vector2 resolveColliding(Shape a, Shape b)
{
Vector2 temp1, temp2;

Vector2[] Axis = new Vector2[a.v.length + b.v.length];

for (int i = 0; i < a.v.length; i++)
{
Axis = Vector2.Normalize(Vector2.Perp(Vector2.Sub(a.v, a.v[i == a.v.length-1 ? 0 : i+1])));
}
for (int i = 0; i < b.v.length; i++)
{
Axis[i + a.v.length] = Vector2.Normalize(Vector2.Perp(Vector2.Sub(b.v, b.v[i == b.v.length-1 ? 0 : i+1])));
}

Vector2 MinAxis = Vector2.Zero;
double MinLength = Double.MAX_VALUE;

for (int i = 0; i < Axis.length; i++)
{
double T1, T2;
temp1 = a.Project(Axis);
temp2 = b.Project(Axis);

if (temp1.x > temp2.y || temp2.x > temp1.y) { return Vector2.Zero; }
T1 = temp1.x - temp2.y;
T2 = temp1.y - temp2.x;
if (Math.abs(T1) < Math.abs(T2))
{
if (Math.abs(T1) < Math.abs(MinLength))
{
MinLength = T1;
MinAxis = Axis;
}
}
else
{
if (Math.abs(T2) < Math.abs(MinLength))
{
MinLength = T2;
MinAxis = Axis;
}
}
}

return Vector2.Mul(MinAxis, -MinLength);
}

private Vector2 Project(Vector2 Axis)
{
Vector2 temp = new Vector2(0, 0);
double projected = 0;
temp.x = temp.y = Vector2.Dot(Vector2.Add(v[0], pos), Axis);
for (int i = 1; i < v.length; i++)
{
projected = Vector2.Dot(Vector2.Add(v, pos), Axis);
if (projected < temp.x) { temp.x = projected; } else
if (projected > temp.y) { temp.y = projected; }
}

return temp;
}


The direction of resolve is perfect. The length however is very very tiny. Any clues as to why?

Any and all help appreciated,
Thanks in advanced,
Bombshell

Share this post


Link to post
Share on other sites
Advertisement
Here is what happens when approaching corners at certain angles.
Its note worthy that the same thing happens all over bar the corners if the triangle is defined clockwise.
In most cases its just sucked into the triangle and spat back out. But at certain angles the shape may be pulled straight through to the other side.
If the triangle is defined clockwise the AABB will get sucked in and spasm about until (with user input) the AABB is pushed out of the triangle.
[attachment=7059:Err.png]

Share this post


Link to post
Share on other sites
I've reworked my implementation, though it still seems broken in ways that don't even make sense!

edit
Shape.v = array of vertices
Shape.pos = position

public static boolean isColliding(Shape a, Shape b)
{
Shape s1, s2;
double temp, s1Min, s1Max, s2Min, s2Max;
Vector2 Axis;

if (a.v.length < b.v.length)
{ s1 = a; s2 = b; }
else
{ s1 = b; s2 = a; }

for (int i = 0; i < s1.v.length; i++)
{
Axis = Vector2.Sub(s1.v, s1.v[i == i-1 ? 0 : i]).Normalize().Perp();

s1Min = s1Max = s1.v[0].Dot(Axis);
for (int v = 1; v < s1.v.length; v++)
{
temp = s1.v[v].Dot(Axis);
if (temp < s1Min) { s1Min = temp; } else
if (temp > s1Max) { s1Max = temp; }
}

s2Min = s2Max = s2.v[0].Dot(Axis);
for (int v = 1; v < s2.v.length; v++)
{
temp = Vector2.Add(s2.v[v], s2.pos.Sub(s1.pos)).Dot(Axis);
if (temp < s2Min) { s1Min = temp; } else
if (temp > s2Max) { s1Max = temp; }
}

if (s1Max < s2Min || s2Max < s1Min) { return false; }
}

for (int i = 0; i < s2.v.length; i++)
{
Axis = Vector2.Sub(s2.v, s2.v[i == i-1 ? 0 : i]).Normalize().Perp();

s1Min = s1Max = s1.v[0].Dot(Axis);
for (int v = 1; v < s1.v.length; v++)
{
temp = s1.v[v].Dot(Axis);
if (temp < s1Min) { s1Min = temp; } else
if (temp > s1Max) { s1Max = temp; }
}

s2Min = s2Max = s2.v[0].Dot(Axis);
for (int v = 1; v < s2.v.length; v++)
{
temp = Vector2.Add(s2.v[v], s2.pos.Sub(s1.pos)).Dot(Axis);
if (temp < s2Min) { s1Min = temp; } else
if (temp > s2Max) { s1Max = temp; }
}

if (s1Max < s2Min || s2Max < s1Min) { return false; }
}
return true;
}


Now I have no clue whats going on but if I try to use this a completely unrelated method doesn't function?!?
The draw function.
First I tried drawing the shapes after the colour was changed in reaction to this method in the update method. Neither shapes were drawn?
Next I tried drawing the shapes in reaction to this method in the draw method, if iscolliding true, draw blue else draw black. only shape B was drawn.
If I do not run this method, both shapes draw perfectly.

I'm completely lost. What is going on!?

Share this post


Link to post
Share on other sites
you're not projecting onto the axis properly and not subtracting the half-widths projection lengths from the center projecting lengths either to determine intersection.

projection vector of vector A onto vector B is (A dot B) / (B length Squared) * B. use this against the B center to A center vector, and the half-width/height vectors of both to get their projection vector, so you can get their projection lengths. If the sum of the half-width/height lengths - center length > 0, there is a possible collision on thix axis, if its < 0, there is no collision at all, since from this axis they are not colliding (which is a return condition). Basically you're testing for overlap in the projections. if the centers are far enough apart, there is no overlap, so subtracing the center projection length is less than zero. If the centers are too close, their center projection length is smaller than their combined half-width/height projection lengths and therefore when the center length is subtracted it will be positive, indicating that they are overlaping, meaning from this axis an overlap is possible.

I have a journal about an SAT implementation for tilemaps that may offer some guidance.

Share this post


Link to post
Share on other sites
Actually projection onto a axis providing the axis is normalized is
Projection = Dot Product of Vector and Axis
I've already got that to work fine as well as get it to resolve collisions fairly accurately, though when trying to test my revised version after making my own Vector class to allow looping (the one above) I ran into the weird not drawing problem,
which is actually my main concern.

Share this post


Link to post
Share on other sites
all fixxed! implementation is working completely!
for anyone in need of help on this here is my Shape class, it should be easy enough to read.

import java.awt.Graphics;
public class Shape {

public Vector2 pos;
public Vector2[] v;

public Shape(Vector2 Pos, Vector2[] Vecs)
{
pos = Pos;
v = Vecs;
}

public static boolean isColliding(Shape a, Shape b)
{
Shape s1, s2;
Vector2 temp1, temp2;

s1 = new Shape(a.pos, a.v.clone());
s2 = new Shape(b.pos, b.v.clone());

Vector2[] Axis = new Vector2[s1.v.length + s2.v.length];

for (int i = 0; i < s1.v.length; i++)
{
Axis = Vector2.Normalize(Vector2.Perp(Vector2.Sub(s1.v, s1.v[i == s1.v.length-1 ? 0 : i+1])));
}
for (int i = 0; i < s2.v.length; i++)
{
Axis[i + s1.v.length] = Vector2.Normalize(Vector2.Perp(Vector2.Sub(s2.v, s2.v[i == s2.v.length-1 ? 0 : i+1])));
}
for (int i = 0; i < Axis.length; i++)
{
temp1 = s1.Project(Axis);
temp2 = s2.Project(Axis);

if (temp1.x > temp2.y || temp2.x > temp1.y) { return false; }
}

return true;
}

private Vector2 Project(Vector2 Axis)
{
Vector2 temp = new Vector2(0, 0);
double projected = 0;
temp.x = temp.y = Vector2.Dot(Vector2.Add(v[0], pos), Axis);
for (int i = 1; i < v.length; i++)
{
projected = Vector2.Dot(Vector2.Add(v, pos), Axis);
if (projected < temp.x) { temp.x = projected; } else
if (projected > temp.y) { temp.y = projected; }
}

return temp;
}

public void Draw(Graphics g)
{
for (int i = 0; i < v.length; i++)
{
g.drawLine((int)(v.x + pos.x), (int)(v.y + pos.y), (int)(v[i == v.length - 1 ? 0 : i+1].x + pos.x), (int)(v[i == v.length - 1 ? 0 : i+1].y + pos.y));
}
}
}

Share this post


Link to post
Share on other sites
Okay I managed to get SAT working for detection but resolving collisions is acting strangely.


public static Vector2 resolveColliding(Shape a, Shape b)
{
Vector2 temp1, temp2;

Vector2[] Axis = new Vector2[a.v.length + b.v.length];

for (int i = 0; i < a.v.length; i++)
{
Axis = Vector2.Normalize(Vector2.Perp(Vector2.Sub(a.v, a.v[i == a.v.length-1 ? 0 : i+1])));
}
for (int i = 0; i < b.v.length; i++)
{
Axis[i + a.v.length] = Vector2.Normalize(Vector2.Perp(Vector2.Sub(b.v, b.v[i == b.v.length-1 ? 0 : i+1])));
}

Vector2 MinAxis = Vector2.Zero;
double MinLength = Double.MAX_VALUE;

for (int i = 0; i < Axis.length; i++)
{
double T1, T2;
temp1 = a.Project(Axis);
temp2 = b.Project(Axis);

if (temp1.x > temp2.y || temp2.x > temp1.y) { return Vector2.Zero; }
T1 = temp1.x - temp2.y;
T2 = temp1.y - temp2.x;
if (Math.abs(T1) < Math.abs(T2))
{
if (Math.abs(T1) < Math.abs(MinLength))
{
MinLength = T1;
MinAxis = Axis;
}
}
else
{
if (Math.abs(T2) < Math.abs(MinLength))
{
MinLength = T2;
MinAxis = Axis;
}
}
}

return Vector2.Mul(MinAxis, -MinLength);
}

private Vector2 Project(Vector2 Axis)
{
Vector2 temp = new Vector2(0, 0);
double projected = 0;
temp.x = temp.y = Vector2.Dot(Vector2.Add(v[0], pos), Axis);
for (int i = 1; i < v.length; i++)
{
projected = Vector2.Dot(Vector2.Add(v, pos), Axis);
if (projected < temp.x) { temp.x = projected; } else
if (projected > temp.y) { temp.y = projected; }
}

return temp;
}



The direction of resolve is perfect. The length however is very very tiny. Any clues as to why?

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!