# Point of Intersection using SAT?

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

## Recommended Posts

So awhile ago i was recommended by some users on this forum to use SAT to calculate collison between two rotating Rectangles.

 public void CheckCollision(Graphics2D g){ for (int K = 0 ; K < RectList.size(); K++){ RectList.get(K).SetRotatedVertices(); double AURx = RectList.get(K).getRTopRightX();//R means "Rotated vertices" 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); /*g.drawRect((int)PAURx,(int) PAURy, 5, 5); g.drawRect((int)PAULx,(int) PAULy, 5, 5); g.drawRect((int)PALRx,(int) PALRy, 5, 5); g.drawRect((int)PALLx,(int) PALLy, 5, 5); g.drawRect((int)PBURx,(int) PBURy, 5, 5); g.drawRect((int)PBULx,(int) PBULy, 5, 5); g.drawRect((int)PBLRx,(int) PBLRy, 5, 5); g.drawRect((int)PBLLx,(int) PBLLy, 5, 5);*/ //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); /*g.setPaint(Color.GREEN); g.drawRect((int)PAURx,(int) PAURy, 5, 5); g.drawRect((int)PAULx,(int) PAULy, 5, 5); g.drawRect((int)PALRx,(int) PALRy, 5, 5); g.drawRect((int)PALLx,(int) PALLy, 5, 5); g.drawRect((int)PBURx,(int) PBURy, 5, 5); g.drawRect((int)PBULx,(int) PBULy, 5, 5); g.drawRect((int)PBLRx,(int) PBLRy, 5, 5); g.drawRect((int)PBLLx,(int) PBLLy, 5, 5);*/ //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); /* g.setPaint(Color.RED); g.drawRect((int)PAURx,(int) PAURy, 5, 5); g.drawRect((int)PAULx,(int) PAULy, 5, 5); g.drawRect((int)PALRx,(int) PALRy, 5, 5); g.drawRect((int)PALLx,(int) PALLy, 5, 5); g.drawRect((int)PBURx,(int) PBURy, 5, 5); g.drawRect((int)PBULx,(int) PBULy, 5, 5); g.drawRect((int)PBLRx,(int) PBLRy, 5, 5); g.drawRect((int)PBLLx,(int) PBLLy, 5, 5); */ //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); /*g.setPaint(Color.ORANGE); g.drawRect((int)PAURx,(int) PAURy, 5, 5); g.drawRect((int)PAULx,(int) PAULy, 5, 5); g.drawRect((int)PALRx,(int) PALRy, 5, 5); g.drawRect((int)PALLx,(int) PALLy, 5, 5); g.drawRect((int)PBURx,(int) PBURy, 5, 5); g.drawRect((int)PBULx,(int) PBULy, 5, 5); g.drawRect((int)PBLRx,(int) PBLRy, 5, 5); g.drawRect((int)PBLLx,(int) PBLLy, 5, 5);*/ //Moment of Truth.... 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).getXvel(); System.out.println("BeforeSwap..."); System.out.print("RECA : Xvel =" + RectList.get(K).getXvel() +"Yvel ="+ RectList.get(K).getYvel() +"\n"); System.out.print("RECB : Xvel =" + RectList.get(J).getXvel() +"Yvel ="+ RectList.get(J).getYvel() +"\n"); RectList.get(K).setXvel(RectList.get(J).getXvel()); RectList.get(K).setYvel(RectList.get(J).getYvel()); RectList.get(J).setXvel(-1*SwapX); RectList.get(J).setYvel(-1*SwapY); System.out.println("AferSwap..."); System.out.print("RECA : Xvel =" + RectList.get(K).getXvel() +"Yvel ="+ RectList.get(K).getYvel() +"\n"); System.out.print("RECB : Xvel =" + RectList.get(J).getXvel() +"Yvel ="+ RectList.get(J).getYvel()+"\n"); } }//Next J }//NEXT K }//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; } 

I'll need the point of intersection between the the two colliding bodies in order to calculate the physics properly.
Is this even possible using SAT?

Here is what My collision looks like so far : http://www.youtube.c...nel_video_title

##### Share on other sites

Is this even possible using SAT?

Yes, it's possible. The general approach is to identify the supporting features of the boxes (vertices or edges in this case) along with the axis of intersection (which is the axis corresponding to the MTD for the discrete test, and the 'last' axis of intersection for the continuous test), and then clip them together to yield the contact manifold.

In your image, for example, the axis of intersection is parallel to the normals of the longer edges of the blue box, and the supporting features are an edge of the blue box and a vertex of the green box. Clipping these features together yields the point P in your image.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634151
• Total Posts
3015817
×