# finding MTD with SAT

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

## 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++){ //RectList.get(J).SetRotatedVertices(); 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); if(Axis3.Collision){ //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(Axis4.Collision){ //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(J).getXvel()); RectList.get(K).setYvel(RectList.get(J).getYvel()); RectList.get(J).setXvel(SwapX); RectList.get(J).setYvel(SwapY); 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 }//NEXT }//END METHOD 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:
[media]
[/media]
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 on other sites
Ok, you really need to use a vector library - there is no hope in hell of debugging that

I've never liked SAT; I just cannot visualise the thing - instead I use minkowski difference... The maths is the same anyway. Have a read though my article on collision detection step by step:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Cheers, Paul.

##### Share on other sites
I've never liked SAT; I just cannot visualise the thing - instead I use minkowski difference[/quote]

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

##### 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.
[/quote]

Interesting!

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

Cheers, Paul.

##### Share on other sites
This is pretty intuitive.

But I agree, that's a debugging hell. The OP should at least break the big beast into separate functions. Such as cross/dot-product, normalization, etc.

##### Share on other sites

So?

Tell me how you visual that test using SAT

##### 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 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 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

1. 1
2. 2
Rutin
19
3. 3
khawk
15
4. 4
5. 5
A4L
13

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633744
• Total Posts
3013654
×