도형 충돌, 분할 축 정리 (Separating Axis Theorem)

참고 : www.dyn4j.org/2010/01/sat/

분할 축 정리(Separating Axis Theorem)란?

 분할축 정리(Separating Axis Theorem, 이하 SAT)란 "두 물체를 투영한 구간이 겹치지 않는 축이 하나라도 존재한다면 두 물체는 교차하지 않은 상태이다."라는 명제에 관한 정리입니다. 그리고 이것을 통해 충돌을 검출해내는 알고리즘을 만들것입니다. 충돌 유무, 충돌 위치, 충돌 량을 검출하며 2D물리 시뮬레이션에서 일반적으로 사용하게 됩니다.

(http://chessire.tistory.com/entry/%EC%84%A0%EB%B6%84%EA%B3%BC-%EC%84%A0%EB%B6%84%EC%9D%98-%EC%B6%A9%EB%8F%8C-%EC%A0%95%EB%A6%AC)

 기본적인 원리는 선분충돌과 같습니다. 두 도형의 모든 선분의 직교선분에 각 도형을 투영하여 교차여부를 검출하는 방식입니다.

아래는 코드입니다.

Shape = function(count, size, rotation)
{
    var self = this;
 
    PIXI.Container.call(this);
 
    var vertices = [];
    var shape = new PIXI.Graphics();
    
    shape.beginFill(Math.random() * 0xffffff);
    shape.lineStyle(2, 0x101010, 1);
 
    var angle = 2 * Math.PI / count;
    for(var i = 0 ; i < count ; ++i)
    {
        var x = Math.cos(rotation + angle * i) * size;
        var y = Math.sin(rotation + angle * i) * size;
 
        vertices.push(new PIXI.Vector(x, y));
 
        if(i == 0)
            shape.moveTo(x, y);
        else
            shape.lineTo(x, y);
    }
    shape.lineTo(vertices[0].x, vertices[0].y);
    shape.endFill();
 
    this.addChild(shape);
 
    this.getVertexPosition = function(index)
    {
        return vertices[index].clone().add(new PIXI.Vector(this.position.x, this.position.y));
    }
 
    this.getAxes = function()
    {
        var axes = [];
        for(var i = 0 ; i < vertices.length ; ++i)
        {
            var vec = vertices[i+1 >= vertices.length ? 0 : i+1].clone().sub(vertices[i]);
            axes.push(new PIXI.Vector(vec.y, -vec.x).normalize());
        }
        
        return axes;
    }
 
    this.project = function(axis)
    {
        var posit = new PIXI.Vector(self.position.x, self.position.y);
        var min = axis.dot(vertices[0].clone().add(posit));
        var max = min;
        for(var i = 1 ; i < vertices.length ; ++i)
        {
            var p = axis.dot(vertices[i].clone().add(posit));
            if(min > p)
                min = p;
            if(max < p)
                max = p;
        }
 
        return new Projection(min, max);
    }
}

Projection = function(min, max)
{
    this.min = min;
    this.max = max;
}
 
Projection.prototype.constructor = Projection;
Projection.prototype.isOverlap = function(proj)
{
    if (proj.min < this.max && this.min < proj.max)
        return true;
 
    return false;
}
 
Projection.prototype.getOverlap = function(proj)
{
    var left = this.getOverlapLeft(proj);
    var right = this.getOverlapRight(proj);
 
    return right - left;
}
 
Projection.prototype.getOverlapLeft = function(proj)
{
    return this.min < proj.min ? proj.min : this.min;
}
 
Projection.prototype.getOverlapRight = function(proj)
{
    return this.max > proj.max ? proj.max : this.max;
}
 
Projection.prototype.getOverlapCenter = function(proj)
{
    var left = this.getOverlapLeft(proj);
    var right = this.getOverlapRight(proj);
 
    return left + (right - left) * 0.5;
}
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

function update() {     var axesA = shapeA.getAxes();     var axesB = shapeB.getAxes();       var overlap = 9999;     var smallest = null;       var overlapDistance = 9999;     var isA = false;       var isCollide = true;       for(var k = 0 ; k < axesA.length ; ++k)     {         var projA = shapeA.project(axesA[k]);         var projB = shapeB.project(axesA[k]);         if(projA.isOverlap(projB) === false)             isCollide = false;         else         {             var o = projA.getOverlap(projB);             if(overlap - 0.00001 <= o && o <= overlap + 0.00001)             {                 var dist = Math.abs(projA.getOverlapCenter(projB) - axesA[k].dot(shapeA.getVertexPosition(k)));                   if(overlapDistance > dist)                 {                     overlap = o;                     smallest = axesA[k];                     overlapDistance = dist;                     isA = true;                 }                                     }             else if(overlap > o)             {                 overlap = o;                 smallest = axesA[k];                 overlapDistance = Math.abs(projA.getOverlapCenter(projB) - axesA[k].dot(shapeA.getVertexPosition(k)));                 isA = true;             }         }     }       for(var k = 0 ; k < axesB.length ; ++k)     {         var projA = shapeA.project(axesB[k]);         var projB = shapeB.project(axesB[k]);         if(projA.isOverlap(projB) === false)             isCollide = false;         else         {             var o = projA.getOverlap(projB);             if(overlap - 0.00001 <= o && o <= overlap + 0.00001)             {                 var dist = Math.abs(projA.getOverlapCenter(projB) - axesB[k].dot(shapeB.getVertexPosition(k)));                   if(overlapDistance > dist)                 {                     overlap = o;                     smallest = axesB[k];                     overlapDistance = dist;                     isA = false;                 }             }             else if(overlap > o)             {                 overlap = o;                 smallest = axesB[k];                 overlapDistance = Math.abs(projA.getOverlapCenter(projB) - axesB[k].dot(shapeB.getVertexPosition(k)));                 isA = false;             }         }     }       if(isCollide)     {         smallest.multiplyScalar(overlap);         if (shapeA.dragging ^ isA)             smallest.multiplyScalar(-1);           if(shapeA.dragging)         {             shapeB.position.x += smallest.x;             shapeB.position.y += smallest.y;         }         else         {             shapeA.position.x += smallest.x;             shapeA.position.y += smallest.y;         }     } } Colored by Color Scripter

cs