# Separating Axis Theorem(SAT) 分離軸碰撞檢測

###### tags: `game design` `collision`

:::info
參考自：http://davidhsu666.com/archives/gamecollisiondetection/#no1
:::

## 小知識

- box2d多邊形實作為SAT

## 目的

- 以往檢測碰撞幾乎都是用bounding box，導致有部分位置無法實際計算出碰撞位置
- 透過分離軸，能夠更準確的判斷兩物體是否碰撞

### 需要的向量知識，將其刻成一個小Lib

- 內積
- 正射影(投影向量)
- 
- 向量長
- 左法向量
- 右法向量

## 分離軸檢測原理

- 兩個==凸多邊形==，在任意角度下的投影皆有重疊，代表物體發生碰撞
- **凹多邊形不適用**


## 分離線、分離軸

- 第一排的物體之間有縫隙，所以能夠輕鬆地畫出一條線來分離它們
- 第二排就不行，因為已經碰撞

- 

### 分離軸

- 與分離線垂直的一條線，透過分離軸上物體的投影，來判斷是否發生碰撞
- ==可檢查旋轉的物體==

- 

- 

---

## 如何取得分離軸上的投影

- 利用投影公式，把A、B的四個角投影在P向量上就能知道`min`、`max`
- 
- 旋轉怎辦？
- 兩物體方向不同時，只要在4個角落中選一個最小和最大的，就是min、max
- 
- 如何判斷？
- 利用正射影(投影向量)
- 
- code

        if (B.min > A.max || A.min > B.max)
            Console.log("分離");// isSeparated
        else
            Console.log("碰撞");// isCollided

---

## 旋轉問題
:::danger
你如果直接帶公式在這四個點，就會變左圖
但是其實你是想要右邊的結果
:::

- 

### 解法

- 將物體平移到原點，旋轉完後再將其平移回來
- 

> ==參考點旋轉就加到向量lib==

---

## 怎找分離軸

- 只需沿著物體==所有邊上的法向量==當作分離軸作檢查
- 綠色那條分離線，可以當作五角形守備的領域，只要有東西進到這裡，就代表碰撞
- 

### 解法
- 透過頂點來找出所有(左)法向量
- 

---

## 矩形(只需找兩個法向量，因為另外兩個只是反向)
- P、Q
- A的法向量
- R、S
- B的法向量
1. 找出四個角在法向量的投影、這時候就知道Min、Max
2. 檢查是否分離

- 

bool Box::SAT_collision(Box &other)
{
    this->setVertices();
    this->findSAT();
    other.setVertices();
    other.findSAT();


    //分離軸枚舉，只需枚舉兩個向量，因為另外兩個只是反向而已
    auto PA = getMinMax(this->SAT[0], Vertices);
    auto PB = getMinMax(this->SAT[0], other.getVertices());
    auto QA = getMinMax(this->SAT[1], Vertices);
    auto QB = getMinMax(this->SAT[1], other.getVertices());
    auto other_sat = other.getSAT();
    auto RA = getMinMax(other_sat[0], Vertices);
    auto RB = getMinMax(other_sat[0], other.getVertices());
    auto SA = getMinMax(other_sat[1], Vertices);
    auto SB = getMinMax(other_sat[1], other.getVertices());

    //檢查分離軸上投影區段是否分開
    bool sep_P = (PB.first > PA.second) || (PA.first > PB.second);
    bool sep_Q = (QB.first > QA.second) || (QA.first > QB.second);
    bool sep_R = (RB.first > RA.second) || (RA.first > RB.second);
    bool sep_S = (SB.first > SA.second) || (SA.first > SB.second);

    if (sep_P || sep_Q || sep_R || sep_S)
    {
        return false;
    }
    else
    {
        return true;
    }
}

## 多邊形 (Polygon)

- 枚舉所有邊，算出各點在SAT的最大最小值，再去比較
- `setVertices()`
- 設定旋轉過後，加上offset後的實際位置
- `findSAT()`
- 找出分離軸
- `getMinMax()`
- 找出各點在分離軸上的最小值與最大值為多少

bool Polygon::isCollide(Polygon &p)
{
    this->setVertices();
    this->findSAT();
    auto poly_a_sat = this->getSAT();
    p.setVertices();
    p.findSAT();
    auto poly_b_sat = p.getSAT();

    // poly_a_sat check
    for (int i = 0; i < poly_a_sat.size(); i++)
    {
        auto A = getMinMax(poly_a_sat[i], this->Vertices);
        auto B = getMinMax(poly_a_sat[i], p.getVertices());
        // 只要發現有一條分離線，就代表物體沒有發生碰撞
        if (B.first > A.second || A.first > B.second)
        {
            return false;
        }
    }
    // poly_b_sat check
    for (int i = 0; i < poly_b_sat.size(); i++)
    {
        auto A = getMinMax(poly_b_sat[i], this->Vertices);
        auto B = getMinMax(poly_b_sat[i], p.getVertices());

        // 只要發現有一條分離線，就代表物體沒有發生碰撞
        if (B.first > A.second || A.first > B.second)
        {
            return false;
        }
    }
    return true;
}

## 圓形&圓形

- 判斷兩圓形半徑之和，是否小於與兩個圓心的位置距離，若有則會碰撞
- $A_{r1} + B_{r2} < dis(A,B)$

## 圓形與多邊形

- 枚舉多邊形的法向量，投影至向量上
- 四邊形點的投影
- 圓心投影，加上半徑，減掉半徑
- 

## 多個物體的碰撞優化

- $O(N^2)$
- 枚舉所有object，算出結果

## Author's source code

- 我的多邊形碰撞範例: http://davidhsu666.com/downloads/Collision-SAT/ver0.2.1-polygon-merge/
- 向量函式庫 : https://github.com/md9830415/JS-Vector2D

## TODO

- AABB Tree 優化