Jump to content
  • Advertisement
Sign in to follow this  

finding MTD with SAT

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

This is my first attempt at SAT.I've managed to detect collision for rotating Rectangles using SAT. But now I'm wondering how to find MTD.
Apparently im supposed to find the difference of overlap on each Axis to find MTD according to this tutorial : http://www.metanetso.../tutorialA.html
This is what i've got so far for collision:
The tutorial i've followed to achive this is here: http://www.gamedev.n...collision-r2604

public void CheckCollision(Graphics2D g){
for (int K = 0 ; K < RectList.size(); K++){
double AURx = RectList.get(K).getRTopRightX();//R is short for "Rotated"
double AURy = RectList.get(K).getRTopRightY();
double AULx = RectList.get(K).getRTopLeftX();
double AULy = RectList.get(K).getRTopLeftY();
double ALRx = RectList.get(K).getRBottomRightX();
double ALRy = RectList.get(K).getRBottomRightY();
double ALLx = RectList.get(K).getRBottomLeftX();
double ALLy = RectList.get(K).getRBottomLeftY();
Vector2D Axis1 = new Vector2D(AURx-AULx,AURy-AULy);
Vector2D Axis2 = new Vector2D(AURx-ALRx,AURy-ALRy);
for(int J = K+1; J< RectList.size(); J++){
double BURx = RectList.get(J).getRTopRightX();
double BURy = RectList.get(J).getRTopRightY();
double BULx = RectList.get(J).getRTopLeftX();
double BULy = RectList.get(J).getRTopLeftY();
double BLRx = RectList.get(J).getRBottomRightX();
double BLRy = RectList.get(J).getRBottomRightY();
double BLLx = RectList.get(J).getRBottomLeftX();
double BLLy = RectList.get(J).getRBottomLeftY();
Vector2D Axis3 = new Vector2D(BULx-BLLx,BULy-BLLy);//Axis1 is of type vector2D, the class holds the direction of the vector (X aka(RUN) and Y aka RISE)
Vector2D Axis4 = new Vector2D(BULx-BURx,BULy-BURy);
//HardCoded Projections to axis1 using vectors from Rect A and B
* Variable Naming:
* [PAURx] "P"= projected/"A" = RectList.get(K)/ "UR" =UpperRight Vertex/ "x" = (X,?)
double PAURx =(((AURx * Axis1.X)+(AURy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PAURy =(((AURx * Axis1.X)+(AURy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PAULx =(((AULx * Axis1.X)+(AULy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PAULy =(((AULx * Axis1.X)+(AULy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PALRx =(((ALRx * Axis1.X)+(ALRy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PALRy =(((ALRx * Axis1.X)+(ALRy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PALLx =(((ALLx * Axis1.X)+(ALLy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PALLy =(((ALLx * Axis1.X)+(ALLy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PBURx =(((BURx * Axis1.X)+(BURy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PBURy =(((BURx * Axis1.X)+(BURy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PBULx =(((BULx * Axis1.X)+(BULy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PBULy =(((BULx * Axis1.X)+(BULy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PBLRx =(((BLRx * Axis1.X)+(BLRy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PBLRy =(((BLRx * Axis1.X)+(BLRy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
double PBLLx =(((BLLx * Axis1.X)+(BLLy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.X;
double PBLLy =(((BLLx * Axis1.X)+(BLLy * Axis1.Y))/((Axis1.X*Axis1.X)+(Axis1.Y*Axis1.Y))) * Axis1.Y;
//HardCoded Scalar Projections to axis1 using vectors from Rect A and B
double DPAUR =((PAURx * Axis1.X)+(PAURy * Axis1.Y));
double DPAUL =((PAULx * Axis1.X)+(PAULy * Axis1.Y));
double DPALR =((PALRx * Axis1.X)+(PALRy * Axis1.Y));
double DPALL =((PALLx * Axis1.X)+(PALLy * Axis1.Y));
double ScalarValuesForRectA[] = {DPAUR,DPAUL,DPALR,DPALL};
double MinA = Min(ScalarValuesForRectA);
double MaxA = Max(ScalarValuesForRectA);
double DPBUR =((PBURx * Axis1.X)+(PBURy * Axis1.Y));
double DPBUL =((PBULx * Axis1.X)+(PBULy * Axis1.Y));
double DPBLR =((PBLRx * Axis1.X)+(PBLRy * Axis1.Y));
double DPBLL =((PBLLx * Axis1.X)+(PBLLy * Axis1.Y));
double ScalarValuesForRectB[] = {DPBUR,DPBUL,DPBLR,DPBLL};
double MinB = Min(ScalarValuesForRectB);
double MaxB = Max(ScalarValuesForRectB);
Axis1.Collision = IsColliding(MinA, MaxA, MinB, MaxB);

if(Axis1.Collision){ <----This could be bad variable naming... Replace Collision with Overlapping.
//HardCoded Projections to axis2 using vectors from Rect A and B
PAURx =(((AURx * Axis2.X)+(AURy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PAURy =(((AURx * Axis2.X)+(AURy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PAULx =(((AULx * Axis2.X)+(AULy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PAULy =(((AULx * Axis2.X)+(AULy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PALRx =(((ALRx * Axis2.X)+(ALRy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PALRy =(((ALRx * Axis2.X)+(ALRy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PALLx =(((ALLx * Axis2.X)+(ALLy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PALLy =(((ALLx * Axis2.X)+(ALLy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PBURx =(((BURx * Axis2.X)+(BURy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PBURy =(((BURx * Axis2.X)+(BURy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PBULx =(((BULx * Axis2.X)+(BULy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PBULy =(((BULx * Axis2.X)+(BULy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PBLRx =(((BLRx * Axis2.X)+(BLRy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PBLRy =(((BLRx * Axis2.X)+(BLRy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;
PBLLx =(((BLLx * Axis2.X)+(BLLy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.X;
PBLLy =(((BLLx * Axis2.X)+(BLLy * Axis2.Y))/((Axis2.X*Axis2.X)+(Axis2.Y*Axis2.Y))) * Axis2.Y;

DPAUR =((PAURx * Axis2.X)+(PAURy * Axis2.Y));
DPAUL =((PAULx * Axis2.X)+(PAULy * Axis2.Y));
DPALR =((PALRx * Axis2.X)+(PALRy * Axis2.Y));
DPALL =((PALLx * Axis2.X)+(PALLy * Axis2.Y));
double ScalarValuesForRectA2[] = {DPAUR,DPAUL,DPALR,DPALL};
MinA = Min(ScalarValuesForRectA2);
MaxA = Max(ScalarValuesForRectA2);
DPBUR =((PBURx * Axis2.X)+(PBURy * Axis2.Y));
DPBUL =((PBULx * Axis2.X)+(PBULy * Axis2.Y));
DPBLR =((PBLRx * Axis2.X)+(PBLRy * Axis2.Y));
DPBLL =((PBLLx * Axis2.X)+(PBLLy * Axis2.Y));
double ScalarValuesForRectB2[] = {DPBUR,DPBUL,DPBLR,DPBLL};
MinB = Min(ScalarValuesForRectB2);
MaxB = Max(ScalarValuesForRectB2);
Axis2.Collision = IsColliding(MinA, MaxA, MinB, MaxB);

if (Axis2.Collision){
//HardCoded Projections to axis3 using vectors from Rect A and B
PAURx =(((AURx * Axis3.X)+(AURy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PAURy =(((AURx * Axis3.X)+(AURy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PAULx =(((AULx * Axis3.X)+(AULy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PAULy =(((AULx * Axis3.X)+(AULy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PALRx =(((ALRx * Axis3.X)+(ALRy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PALRy =(((ALRx * Axis3.X)+(ALRy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PALLx =(((ALLx * Axis3.X)+(ALLy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PALLy =(((ALLx * Axis3.X)+(ALLy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PBURx =(((BURx * Axis3.X)+(BURy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PBURy =(((BURx * Axis3.X)+(BURy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PBULx =(((BULx * Axis3.X)+(BULy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PBULy =(((BULx * Axis3.X)+(BULy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PBLRx =(((BLRx * Axis3.X)+(BLRy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PBLRy =(((BLRx * Axis3.X)+(BLRy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;
PBLLx =(((BLLx * Axis3.X)+(BLLy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.X;
PBLLy =(((BLLx * Axis3.X)+(BLLy * Axis3.Y))/((Axis3.X*Axis3.X)+(Axis3.Y*Axis3.Y))) * Axis3.Y;

DPAUR =((PAURx * Axis3.X)+(PAURy * Axis3.Y));
DPAUL =((PAULx * Axis3.X)+(PAULy * Axis3.Y));
DPALR =((PALRx * Axis3.X)+(PALRy * Axis3.Y));
DPALL =((PALLx * Axis3.X)+(PALLy * Axis3.Y));
double ScalarValuesForRectA3[] = {DPAUR,DPAUL,DPALR,DPALL};
MinA = Min(ScalarValuesForRectA3);
MaxA = Max(ScalarValuesForRectA3);
DPBUR =((PBURx * Axis3.X)+(PBURy * Axis3.Y));
DPBUL =((PBULx * Axis3.X)+(PBULy * Axis3.Y));
DPBLR =((PBLRx * Axis3.X)+(PBLRy * Axis3.Y));
DPBLL =((PBLLx * Axis3.X)+(PBLLy * Axis3.Y));
double ScalarValuesForRectB3[] = {DPBUR,DPBUL,DPBLR,DPBLL};
MinB = Min(ScalarValuesForRectB3);
MaxB = Max(ScalarValuesForRectB3);
Axis3.Collision = IsColliding(MinA, MaxA, MinB, MaxB);

//HardCoded Projections to axis4 using vectors from Rect A and B
PAURx =(((AURx * Axis4.X)+(AURy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PAURy =(((AURx * Axis4.X)+(AURy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PAULx =(((AULx * Axis4.X)+(AULy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PAULy =(((AULx * Axis4.X)+(AULy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PALRx =(((ALRx * Axis4.X)+(ALRy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PALRy =(((ALRx * Axis4.X)+(ALRy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PALLx =(((ALLx * Axis4.X)+(ALLy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PALLy =(((ALLx * Axis4.X)+(ALLy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PBURx =(((BURx * Axis4.X)+(BURy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PBURy =(((BURx * Axis4.X)+(BURy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PBULx =(((BULx * Axis4.X)+(BULy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PBULy =(((BULx * Axis4.X)+(BULy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PBLRx =(((BLRx * Axis4.X)+(BLRy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PBLRy =(((BLRx * Axis4.X)+(BLRy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;
PBLLx =(((BLLx * Axis4.X)+(BLLy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.X;
PBLLy =(((BLLx * Axis4.X)+(BLLy * Axis4.Y))/((Axis4.X*Axis4.X)+(Axis4.Y*Axis4.Y))) * Axis4.Y;

DPAUR =((PAURx * Axis4.X)+(PAURy * Axis4.Y));
DPAUL =((PAULx * Axis4.X)+(PAULy * Axis4.Y));
DPALR =((PALRx * Axis4.X)+(PALRy * Axis4.Y));
DPALL =((PALLx * Axis4.X)+(PALLy * Axis4.Y));
double ScalarValuesForRectA4[] = {DPAUR,DPAUL,DPALR,DPALL};
MinA = Min(ScalarValuesForRectA4);
MaxA = Max(ScalarValuesForRectA4);
DPBUR =((PBURx * Axis4.X)+(PBURy * Axis4.Y));
DPBUL =((PBULx * Axis4.X)+(PBULy * Axis4.Y));
DPBLR =((PBLRx * Axis4.X)+(PBLRy * Axis4.Y));
DPBLL =((PBLLx * Axis4.X)+(PBLLy * Axis4.Y));
double ScalarValuesForRectB4[] = {DPBUR,DPBUL,DPBLR,DPBLL};
MinB = Min(ScalarValuesForRectB4);
MaxB = Max(ScalarValuesForRectB4);
Axis4.Collision = IsColliding(MinA, MaxA, MinB, MaxB);

//if (Axis1.Collision && Axis2.Collision && Axis3.Collision && Axis4.Collision ){
RectList.get(K).Hit = true;
RectList.get(J).Hit = true;
double SwapX = RectList.get(K).getXvel();
double SwapY = RectList.get(K).getYvel();

RectList.get(K).setXvel(RectList.get(K).getXvel() + MTDX);
RectList.get(K).setYvel(RectList.get(K).getYvel() + MTDY);

//}//Collision Code
}//Axis 4 Test
}//Axis 3 Test
}//Axis2 Test
}//Axis1 Test
}//Next J

public double Min(double Numbers[]){
double Min = Numbers[0];
for (int K = 0; K < Numbers.length; K++){
if ( Numbers[K] < Min){
Min = Numbers[K];
return Min;
public double Max(double Numbers[]){
double Max = Numbers[0];
for (int K = 0; K < Numbers.length; K++){
if ( Numbers[K] > Max){
Max = Numbers[K];
return Max;
public boolean IsColliding(double MinA, double MaxA ,double MinB, double MaxB){
if(MaxB > MinA){
if(MinB < MaxA ){
return true;
return false;

This is what my app looks like right now:
Basically I need someone here to tell me how to or direct me to someone who can calculate MTD step by step and explain the math. I'm new to vector math as grade 11's don't really learn vector math until next year.
I'm also wondering if i did the math correctly in my code. If someone can confirm that would be very helpful.

Share this post

Link to post
Share on other sites

I've never liked SAT; I just cannot visualise the thing - instead I use minkowski difference

really? I find that SAT is infinitely easier to visualise.


So, how do you visual the SAT for computing the TOI of a moving sphere vs triangle, for example? :)

Cheers, Paul.

Share this post

Link to post
Share on other sites
Sorry about the massive amount of hard coding.
I will rewrite the same method using a vector class and loops to shorten the code and then
ill post here. It shouldn't take too long... then maybe you guys could have a look.

Share this post

Link to post
Share on other sites
Just a little note. If you didn't use these abbreviations, maybe someone else could have a word in the topic. I have no farking idea what MTD is, but I've done pretty much SAT. And the OP shouldn't force me to look into what that means, because I won't.

It's cool to use those all the time, but I just ignore those threads most of the time (and there are many), but maybe I could help.

I realized that I linked the same thing as the OP.....

Share this post

Link to post
Share on other sites

Just a little note. If you didn't use these abbreviations, maybe someone else could have a word in the topic. I have no farking idea what MTD is, but I've done pretty much SAT. And the OP shouldn't force me to look into what that means, because I won't.

It's cool to use those all the time, but I just ignore those threads most of the time (and there are many), but maybe I could help.

I realized that I linked the same thing as the OP.....

My bad, I just assumed most people on the math and physics forum would know what that means.
MTD = Minimum Translational Distance
I need to find this vector to prevent overlap.
Problem is i don't know how to find it ,with sat, because the main article i was using didn't say how

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!