نظریه محور مجزا ساز -SAT-Separating Axis Theorem

این متد برای تشخیص برخورد اشکال محدب convex بکار میره، اما برای اشکال مقعر concave هم میشه به کار برد(تقسیم اشکال) کل الگوریتم اینو میگه که : " وقتی دو شکل  با هم برخوردی ندارن ، حد اقل یک محور وجود داره که سایه ی شکل روی اونها با هم تداخل ندارن".

در کل اینجوری میتونیم بگیم  که "دو جسم با هم برخورد دارن مگر اینکه خلافش ثابت بشه".
یا اینکه دو جسم با هم برخورد دارن اگر و فقط اگر که بر روی همه محور ها همپوشانی داشته باشند.

 

برای هر شکل یک سری محور وجود داره که باید اشکال رو روی تک تک اون محور ها تصویر کنیم اگه تصویر دو شکل روی محوری با هم تداخل نداشت یعنی برخوردی وجود نداره وباید از پردازش بیرون بیاد برناممون.

 

برای حل برخورد به یه سری پارامترای دیگه نیاز داریم، یکی مقدار نفوذ و دوم بردار جهت نفوذ که اصطلاحا میگن MTV

Minimum translation vector که برابره با محوری که کمترین مقدار تداخل روی اون رخ داده ، وبزرگی این بردار هم همین کمترین مقدار تداخله:

public function collide(shape_:Convex):MTV{

                     var shape1:Convex=this;

                     var shape2:Convex=shape_;

                     if(shape1.id==shape2.id) return null;

                     var axes1:Vector.<Vec2>=shape1.getAxes()

                     var axes2:Vector.<Vec2>=shape2.getAxes()

                     var p1:Projection,p2:Projection

                     var axis:Vec2

                     var i:int

                     var c:Boolean

                     var smallest:Vec2

                     var overlap:Number=Number.POSITIVE_INFINITY

                     //in axes1

                     var len:Number=axes1.length

                     for (i = 0; i < len; i++) {

                           axis=axes1[i]

                            p1=shape1.project(axis)

                           p2=shape2.project(axis)

                           if(!p1.overlaps(p2)) {return null;}

                           else{

                           var o:Number=p1.getOverlap(p2)

                           if(o<overlap){

                           overlap=o;

                           smallest=axis;

                           }

                           }

                     }

                     //in axes2

                     len=axes2.length

                     for (i = 0; i < len; i++) {

                           axis=axes2[i]

                            p1=shape1.project(axis)

                           p2=shape2.project(axis)

                           if(!p1.overlaps(p2)) {return null;}

                           else{

                           var o:Number=p1.getOverlap(p2)

                           if(o<overlap){

                           overlap=o;

                           smallest=axis;

                           }

                           }

                           var ca:Vec2=shape1.loc

                           var cb:Vec2=shape2.loc

                           var cacb:Vec2=cb.subOf(ca)

                           if(smallest.dot(cacb)<0){

                           smallest.reverse()

                           }

                           //smallest.scale(-1)

                     }

var mtv:MTV=new MTV(smallest, overlap, true);

return mtv;}

public function getAxes():Vector.<Vec2>{

                     var vrtx:Vector.<Vec2>=WorldVertex()

                     var len:Number=vrtx.length

                     var axes_:Vector.<Vec2>=new Vector.<Vec2>()

                     for (var i : int = 0; i <len; i++) {

                           var p1:Vec2=vrtx[i]

                           var p2:Vec2=vrtx[i+1==len?0:i+1];

                           var edge:Vec2=p1.subOf(p2);

                           var norm:Vec2=edge.normL

                            norm.normalize()

                           axes_[i]=norm

                     }

                     return axes_;}

public function project(axis:Vec2):Projection{

                     var vrtx:Vector.<Vec2>=WorldVertex()

                     var min:Number=vrtx[0].dot(axis)

                     var max:Number=min

                     var len:Number=vrtx.length

                     var p:Projection

                     for (var i : int = 0; i <len ; i++) {

                           var d:Number=vrtx[i].dot(axis)

                           if(d<min){

                           min=d;

                           }else if(d>max){

                           max=d

                           }

                           p=new Projection(min, max)

                     }

              return p

       }

package  {

       public class Projection {

              public var max:Number

              public var min:Number

              public function Projection(_min:Number,_max:Number) {

                     max=_max

                     min=_min

              }

              public function overlaps(p:Projection):Boolean{

                     return !(this.min > p.max || p.min > this.max);

              }

              public function getOverlap(p:Projection):Number{

              if (this.overlaps(p)) {

                 return Math.min(this.max, p.max) - Math.max(this.min, p.min);

                }

          return 0;

              }

       }

}

package {

       import physx.math.Vec2;

       public class MTV {

              public var dir:Vec2

              public var depth:Number

              public function MTV(dir_:Vec2,depth_:Number) {

                     dir=dir_

                     depth=depth_

              }

       }

}