프로그래밍/알고리즘

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

Cat체셔 2016. 6. 26. 02:40


참고 : 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)

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




아래는 코드입니다.


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
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);
    }
}
cs





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
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;
}
 
cs




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;
        }
    }
}
cs