Sign in to follow this  

Use SAT to "unpenetrate" objects but limit direction of minimum translation vector?

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

Hey guys, this is a problem that's been plauging me for the past couple of days.
I developed a sidescrolling platformer where one of the objectives is to move crates around to reach a goal. I found that even though it is a platformer, I needed a collision handling mechanism to move the boxes, so I settled with the Separating Axis Theorem.
Now I've been testing low FPS situations and high gravity, and I've found instances where the avatar drops straight through a thin platform due to tunneling. Here is a diagram that demonstrates what I mean - the hexagon is meant to represent the avatar:
[img]http://img98.imageshack.us/img98/9704/46202955.png[/img]
Afterwards, I spent some time figuring out how to fix it and I had the grand idea to try to use what 3D games call movement volumes where there's a polygon meant to represent the space an object goes through between two endpoints, except it's more like a movement area for me because my game is only 2D. The area encompasses the area of the avatar at the beginning of the frame; the area of the avatar at the end of the frame after all user input was handled and gravity's effect was calculated; and the area in between. Now this worked for some cases, like right here:
[img]http://img600.imageshack.us/img600/7601/12026171.png[/img]
getting pushed out like this:
[img]http://img819.imageshack.us/img819/9910/78204618.png[/img]
so that the end position becomes this:
[img]http://img41.imageshack.us/img41/6984/60022820.png[/img]
But I found the way I implemented SAT, whenever more than half the movement area polygon was below the platform, the polygon chose to be pushed out through that route since it requires the least change in position (the smallest minimum translation vector). Here is the movement area polygon:
[img]http://img405.imageshack.us/img405/5118/79474259.png[/img]
And here is the polygon after the collision:
[img]http://img440.imageshack.us/img440/6520/59905604.png[/img]
And finally the final location of the avatar itself:
[img]http://img210.imageshack.us/img210/1771/43135583.png[/img]
You can guess that this is not supposed to happen, and instead, the end position after the collision is supposed to remain on the same side of the platform as the start position was on before the collision. As you can see, I obviously lacked the foresight to consider a case like this when I started working on that movement area implementation. And now I'm lamenting over the fact that I spent so much time on something that could possibly have been useless.
Before I pull out more of my hair, I wanted to know has anyone ever tried something like this before? Can I add constraints to the SAT so that it only can return a minimum translation vector whose direction is on the side of the platform that contained the polygon from the start position? Is this a job that shouldn't be handled with SAT? I tried using a continuous/swept/dynamic, but I kept failing in adapting Oliii's, so I gave up. I figured it would be useful to figure out the time of impact so I can just split up the timestep at the time right before the avatar collides so the movement area polygon is mostly above the platform instead of below.
Here is my SAT method (and a helper method), written in Java (that means no parameters can be passed by reference) and uses the Vector2f class from LWJGL and a custom Polygon class. I'm sure the method names are self explanatory though. The passed Polygon "a" is the platform's polygon and Polygon "b" is the movement area polygon of the avatar, but I can easily change the method signature to pass the start position polygon and the end position polygon along with it if it need be.
[code]
private static float intervalDistance(float minA, float maxA, float minB, float maxB) {
if (minA < minB)
return minB - maxA;
else
return minA - maxB;
}

//returns the minimum translation vector, or null if no collision was made.
public static Vector2f collision(Polygon a, Polygon b) {
Vector2f axis = new Vector2f(1, 1);
Vector2f translationAxis = new Vector2f(0, 0);
float minIntervalDistance = Float.POSITIVE_INFINITY;
float intervalDist;
float tmp, maxA, minA, minB, maxB;
for (int i = 0; i < a.getVertexCount(); ++i) {
Vector2f edge = a.getEdges()[i];
axis = new Vector2f(-edge.getY(), edge.getX());
axis.normalise();
minA = maxA = Vector2f.dot(a.getVertices()[0], axis);
for (int j = 1; j < a.getVertexCount(); ++j) {
tmp = Vector2f.dot(a.getVertices()[j], axis);
if (tmp > maxA)
maxA = tmp;
else if (tmp < minA)
minA = tmp;
}
minB = maxB = Vector2f.dot(b.getVertices()[0], axis);
for (int j = 1; j < b.getVertexCount(); ++j) {
tmp = Vector2f.dot(b.getVertices()[j], axis);
if (tmp > maxB)
maxB = tmp;
else if (tmp < minB)
minB = tmp;
}
intervalDist = intervalDistance(minA, maxA, minB, maxB);
if (intervalDist > 0) {
return null;
} else {
intervalDist = Math.abs(intervalDist);
if (intervalDist < minIntervalDistance) {
minIntervalDistance = intervalDist;
translationAxis = axis;
}
}
}
for (int i = 0; i < b.getVertexCount(); ++i) {
Vector2f edge = b.getEdges()[i];
axis = new Vector2f(-edge.getY(), edge.getX());
axis.normalise();
minB = maxB = Vector2f.dot(axis, b.getVertices()[0]);
for (int j = 1; j < b.getVertexCount(); ++j) {
tmp = Vector2f.dot(axis, b.getVertices()[j]);
if (tmp > maxB)
maxB = tmp;
else if (tmp < minB)
minB = tmp;
}
minA = maxA = Vector2f.dot(a.getVertices()[0], axis);
for (int j = 1; j < a.getVertexCount(); ++j) {
tmp = Vector2f.dot(a.getVertices()[j], axis);
if (tmp > maxA)
maxA = tmp;
else if (tmp < minA)
minA = tmp;
}
intervalDist = intervalDistance(minA, maxA, minB, maxB);
if (intervalDist > 0) {
return null;
} else {
intervalDist = Math.abs(intervalDist);
if (intervalDist < minIntervalDistance) {
minIntervalDistance = intervalDist;
translationAxis = axis;
}
}
}
Vector2f d = Vector2f.sub(a.getCenter(), b.getCenter(), null);
if (Vector2f.dot(d, translationAxis) > 0.0f)
translationAxis.negate();
translationAxis.scale(minIntervalDistance); //this becomes our minimum translation vector
return translationAxis;
}
[/code]

EDIT: clarified some points and simplified some of the code. Edited by GoldenKevin

Share this post


Link to post
Share on other sites
Most commercial games use a fixed time step, meaning that they only advance the physics engine by a fixed interval. If the game is running at a low frame rate, then the physics engine will be advanced multiple times per frame instead of being advanced only once. It is possible that the user's PC is not capable of running the physics in real time in which case you have to use a larger time step, but this should never happen for PCs which surpass the minimum requirements that you intend to support.

I believe that most physics engines run discrete collision detection multiple times per physics frame to get more accurate results and handle fast-moving objects better.

Using either of those along with careful design of the levels should avoid problems caused by the use of discrete collision detection.

The alternative is to make your physics engine do all of the collision detection continuously and to not use approximations that become worse with larger time steps. However, this is more difficult to implement and commercial physics engines do not do this so you are not likely to be able to implement it properly. Edited by sundersoft

Share this post


Link to post
Share on other sites
[quote name='sundersoft' timestamp='1343688280' post='4964635']
Most commercial games use a fixed time step, meaning that they only advance the physics engine by a fixed interval. If the game is running at a low frame rate, then the physics engine will be advanced multiple times per frame instead of being advanced only once. It is possible that the user's PC is not capable of running the physics in real time in which case you have to use a larger time step, but this should never happen for PCs which surpass the minimum requirements that you intend to support.
I believe that most physics engines run discrete collision detection multiple times per physics frame to get more accurate results and handle fast-moving objects better.
Using either of those along with careful design of the levels should avoid problems caused by the use of discrete collision detection.
The alternative is to make your physics engine do all of the collision detection continuously and to not use approximations that become worse with larger time steps. However, this is more difficult to implement and commercial physics engines do not do this so you are not likely to be able to implement it properly.
[/quote]
Yeah, I've heard at least some first person shooters use CCD, but I never realized other games actually just split the timestep. I guess you can approximate the appropriate amount of slices based on the radii of the objects, but I guess a better approach would be to try to get swept SAT working so I can get an exact timestep.

[quote name='Volgogradetzzz' timestamp='1343716601' post='4964734']
You can use swept SAT. It's exactly your case:
[url="http://volgogradetzzz.blogspot.com/2011/05/swept-sat.html"]http://volgogradetzz.../swept-sat.html[/url]
[/quote]
I actually took a look at your tutorial before but was completely confused. After spending a lot of time searching on Google, learning much more about how SAT works in the process, and finally returning back here, I actually think I have an idea on how to implement this in my own code. Thanks nonetheless!



The thing is, I tried my best to prevent having to increase the complexity of each frame by how ever many slices I need to make of a timestep. I thought there was a way where I could've chosen a translation axis that was closest oriented to the center of the start polygon, but it didn't quite work as I expected.

EDIT: actually, performance may be for the better if I ever get this implemented. For most cases, I would only need to run the SAT once per two objects like I always have been doing for a quadratic time (yeah, I haven't implemented a broad-phase yet). I would need to calculate the movement area polygon in linear time every frame, and the algorithm could reach cubic complexity in worst case and used some trig versus just a few square roots in SAT. Considering that I can remove this routine if I implement swept SAT, and redoing the SAT for every tunneled object is also linear time but only iterates over one or two objects, using swept SAT might actually improve my game's performance. Edited by GoldenKevin

Share this post


Link to post
Share on other sites
[quote name='Volgogradetzzz' timestamp='1343716601' post='4964734']
You can use swept SAT. It's exactly your case:
[url="http://volgogradetzzz.blogspot.com/2011/05/swept-sat.html"]http://volgogradetzz.../swept-sat.html[/url]
[/quote]

Volgogradetzzz, do you have any code samples? Maybe in calculating E or L, I can reuse my method "intervalDistance(float minA, float maxA, float minB, float maxB)"? I'm not sure what E or L are supposed to equal to since you gave three different expressions. And when you mention [b]vr[/b] and [b]d[/b], you mean the magnitude of each right?

I put this at the top of the method now:
[code]
public static CollisionResult collision(Polygon a, Velocity vA, Polygon b, Velocity vB) {
Vector2f d = Vector2f.sub(a.getCenter(), b.getCenter(), null);
float dm = d.length(); // ||d|| magnitude of distance between a and b
float vr = Vector2f.sub(vA.asVector(), vB.asVector(), null).length(); // ||vA - vB|| magnitude of velocity of object A relative to B
[/code] Edited by GoldenKevin

Share this post


Link to post
Share on other sites
Oh, it was so long, so I can't remember why it's three expression for E and L. Actually you should use E = minB – maxA and L = maxB – minA. [b]vr[/b] and [b]d[/b] - is projections too. Here're some methods code for Body class. Hope this helps.
[CODE]public function collide(b:Body):CollisionInfo {
_collInfo.tEnter = NaN;
_collInfo.tLeave = NaN;

var d:VVector2 = b.position.subtractReturn(position);
var vRel:VVector2 = velocity.subtractReturn(b.velocity);

var numVerticesA:int = vertices.length;
var numVerticesB:int = b.vertices.length;

for (var i:int = 0, j:int = numVerticesA - 1; i < numVerticesA; j = i, i++) {
var side:VVector2 = _vertices[i].subtractReturn(_vertices[j]);
var normal:VVector2 = side.normal();
normal.normalize();

var isCollide:Boolean = getIntersection(this, b, d, normal, numVerticesA, numVerticesB, vRel);
if (!isCollide) {
return null;
}
}

d.scale( -1);
vRel.scale( -1);
for (i = 0, j = numVerticesB - 1; i < numVerticesB; j = i, i++) {
side = b.vertices[i].subtractReturn(b.vertices[j]);
normal = side.normal();
normal.normalize();

isCollide = getIntersection(b, this, d, normal, numVerticesB, numVerticesA, vRel);
if (!isCollide) {
return null;
}
}

return _collInfo;
}

private function getIntersection(a:Body, b:Body, d:VVector2, normal:VVector2, numVerticesA:int, numVerticesB:int, vRel:VVector2):Boolean {
findInterval(a, b, d, normal, numVerticesA, numVerticesB);
var velDP:Number = normal.dot(vRel);

var t0:Number = (_minB - _maxA) / velDP;
var t1:Number = (_maxB - _minA) / velDP;
_collInfo.normal = normal;

if(t0 > t1) {
var temp:Number = t0;
t0 = t1;
t1 = temp;

_collInfo.normal.scale( -1);
}

if (t1 < 0 || t0 > 1) {
return false;
}

if (isNaN(_collInfo.tEnter)) {
_collInfo.tEnter = t0;
_collInfo.tLeave = t1;
} else {
if(t0 > _collInfo.tLeave || t1 < _collInfo.tEnter) {
return false;
}

if (t0 > _collInfo.tEnter) {
_collInfo.tEnter = t0;
}

if (t1 < _collInfo.tLeave) {
_collInfo.tLeave = t1;
}
}

return true;
}

private function findInterval(a:Body, b:Body, d:VVector2, normal:VVector2, numVerticesA:int, numVerticesB:int):void {
var dProj:Number = normal.dot(d);

_minA = _maxA = normal.dot(a.vertices[0]);
for (var j:int = 1; j < numVerticesA; j++) {
var dp:Number = normal.dot(a.vertices[j]);
if (dp > _maxA) {
_maxA = dp;
} else if (dp < _minA) {
_minA = dp;
}
}

_minB = _maxB = normal.dot(b.vertices[0]);
for (j = 0; j < numVerticesB; j++) {
dp = normal.dot(b.vertices[j]);
if (dp > _maxB) {
_maxB = dp;
} else if (dp < _minB) {
_minB = dp;
}
}

_maxB += dProj;
_minB += dProj;
}[/CODE]

Share this post


Link to post
Share on other sites

This topic is 1965 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this