SAT AABB and Right-Angle Triangles

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

Recommended Posts

Hey all, Through jyk's help I've been able to implement AABB SAT in a platformer that I'm working on. I'm looking to add ramps by adding collision between AABB and right-angle triangles, but am completely stumped. Is anyone able to give me a hand and walk me through what needs to be calculated and how? I'm very math illiterate and would prefer to be talked to like a six year old if possible. ;) If it helps, the triangles will never be moving. Here's the code for AABB MTD calculations:
		public static Vector2 Intersect(Box left, Box right)
{
Vector2 result = Vector2.Zero;

float diff, minDiff;
int axis, side;

// Left
diff = left.Max.X - right.Min.X;
if (diff < 0.0f)
{
return Vector2.Zero;
}
minDiff = diff;
axis = 0;
side = -1;

// Right
diff = right.Max.X - left.Min.X;
if (diff < 0.0f)
{
return Vector2.Zero;
}
if (diff < minDiff)
{
minDiff = diff;
side = 1;
}

// Down
diff = left.Max.Y - right.Min.Y;
if (diff < 0.0f)
{
return Vector2.Zero;
}
if (diff < minDiff)
{
minDiff = diff;
axis = 1;
side = -1;
}

// Up
diff = right.Max.Y - left.Min.Y;
if (diff < 0.0f)
{
return Vector2.Zero;
}
if (diff < minDiff)
{
minDiff = diff;
axis = 1;
side = 1;
}

// Intersection occurred
// Y axis.
if(axis == 1)
result.Y = (float)side * minDiff;
else
result.X = (float)side * minDiff;

return result;
}


Thanks.

Share on other sites
Not sure if you understand how the SAT really works. If you did, you would know that a AABB / AABB test, a triangle / triangle test, or a polygon / triangle test, or whatever comvex polygon you wanna use work the same way.

The code above looks familliar, and is just an optimisation of the SAT (reducing the number of calculations).

Have you looked at this?

http://www.harveycartel.org/metanet/tutorials/tutorialA.html

Share on other sites
My understanding is this:
You find out which side the objects are penetrating. You then calculate the minimum translation distance (MTD) to separate the two objects. Is that not correct?

Code similar to that was provided by jyk, is it yours Oliii? I know you're well known for your polygon collision work.

I am very familiar with the site you've linked to. Unlike others on the board, I struggle a lot with my maths and I find that site very unforgiving for those like me. The only code provided is ActionScript, which makes it nigh impossible to play around with it and see how it works.

I think I understand what you're saying though -- the problem isn't in the SAT logic but in my failure to know how to test if a triangle overlaps with an AABB to calculate the MTD? Is that correct?

Share on other sites
Quote:
 Original post by GroZZleRCode similar to that was provided by jyk, is it yours Oliii?
No, that's my code - IIRC it was something I typed off the top of my head for a post or PM here on GDNet. However, most SAT code is going to look pretty similar (there are only so many ways to implement the algorithm).

Anyway, as oliii said, the SAT algorithm works in exactly the same way for all polytopes - aligned boxes, triangles (right or otherwise), line segments, points, etc. The reason code for certain pairs of shapes ends up looking different than code for other pairs is that, depending on the shapes in question, certain shortcuts and optimizations may be incorporated. This can often obscure what's really going on, and can make it harder to see what the algorithm is actually doing.

The code above is an example of this, more or less; because it exploits the axis-aligned nature of AABBs, it only works for AABBs, and it looks different than SAT code for other pairs of shapes.

Now, assuming collision detection is not your bottleneck, you might do well to implement the algorithm in a completely generic and unoptimized way. It won't be quite as fast for some shapes, but you'll be able to use it for any pair of polytopes (such as your AABB vs. right triangle example) without having to tackle each pair as a 'new problem', as you're doing now.

As oliii suggested, implementing a generic version may require a deeper understanding of the SAT than you have currently. This post is long enough for now, but if you really get stuck, post back and we can try to clear it up. However, this algorithm has been covered in exquisite detail by oliii, myself, and others on these forums, so you should be able to piece things together, I think. I know oliii has posted a list of links to relevant threads before - maybe if he has those readily available he can post them again, as I think they probably contain much if not all of the information you're needing.

Share on other sites
Thanks everyone for the help. I've decided to tackle the issue from a different perspective and it's working out beautifully.

Rate++ all around.

Share on other sites

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

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

• Forum Statistics

• Total Topics
628654
• Total Posts
2984055

• 10
• 9
• 9
• 10
• 21