• 判斷是兩個形狀是否相交一-SAT分離軸理論
  • 原文位址
  • 簡介
  • 凸多邊形
  • 投影
  • 算法描述
    • 不相交
    • 相交
    • 得到分離軸
    • 找到MTV
    • 曲邊圖形
    • 包含
  • 其他需要注意的事情

判斷是兩個形狀是否相交(一)-SAT分離軸理論

原文位址

簡介

分離軸理論，簡稱SAT（ SeparatingAxisTheorem ），是一個判斷兩個凸多邊形是否碰撞的理論。此理論可以用于找到最小的滲透向量（感覺應該是模最小的），此向量在實體模拟和其他很多應用中很有用。SAT是一種高效的算法，能夠出去每種形狀對（譬如圓和圓，圓和多邊形，多邊形和線段）對碰撞檢測代碼的需求進而減少代碼減輕維護壓力。

凸多邊形

SAT 就像以前說過的一樣，是一個檢測兩個凸多邊形是否相交的方法。對于一個形狀，如果對于所有的穿過這個形狀的線，這條線隻和這個形狀至多相交兩次。如果多餘兩次，這個形狀就是一個非凸多邊形或者說凹多邊形。看維基百科的定義 和數學世界的定義來了解更多的數學和官方定義。讓我們來看一些例子

上圖形被看做凸多邊形因為不存在一條穿過它而且和他相交兩次的直線。

這一個存在，是以其實一個凹多邊形。

SAT隻能處理凸多邊形，不多問題不大，因為非凸多邊形可以被分解為凸多邊形，如上圖示。是以如果我們将圖示2中的凹多邊形分解我們可以得到兩個凸多邊形。然後我們就可以使用SAT對整個形狀進行檢測了。

投影

SAT使用的下一個概念叫做投影。想象一下如果你有一個全是平行光的光源。如果你将這個光投向一個物體它就會在一個平面上産生一個陰影。一個陰影是一個三維（3d）物體的二維（2d）的投影。一個二維物體的投影是一個一維“陰影”。具體如下圖示

算法描述

SAT描述為：如果兩個凸多邊形沒有相交，那麼存在這兩個物體在一個軸上的投影不重疊。

不相交

首先讓我們讨論一下SAT如何判斷兩個形狀沒有相交。在下圖中我們可以看出這兩個形狀沒有相交。可以劃出一條線來展示出來。

如果我們選擇一條和圖示中分割線垂直的線，将這兩個凸多邊形相對于這條垂線投影就會看出，投影沒有重疊。那麼這條垂線就被稱作一條分離軸。在下圖中深灰色的線既是一個分離軸，而且各自對應顔色的線就是這兩個多邊形想這條分離軸的投影。注意：在下圖中投影沒有重疊，是以根據SAT我們可以得出結論這兩個多邊形沒有相交。

SAT可能會測試多個軸來判斷是否重疊，如果找到一個軸兩個多邊形對應的投影沒有重疊，那麼這個算法立馬可以得出結論這兩個多邊形沒有相交。因為這個前提，SAT對于一些物體很多碰撞很少的應用（遊戲，模拟，等等）都是非常理想的。

為了更好地展示這個算法，給出一些僞代碼：

Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = ; i < axes.length; i++) {
  Axis axis = axes[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  }
}
           

相交

如果對于所有的軸，兩個多邊形的投影都相交，那麼我們就可以得出結論這兩個多邊形相交。下圖展示出了這種情況。

所有的軸必須都在考慮範圍之内，跟改後的僞代碼為：

Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = ; i < axes.length; i++) {
  Axis axis = axes[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  }
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;
           

得到分離軸

當我使用這個算法的時候第一個問題就是，我怎麼知道去測試哪些軸。其實這個東西很簡單：

你要測試的軸就是每個邊的法向量。邊的法向量可以通過對換x，y然後對其中的一個取負就行了。

舉例說明

Vector[] axes = new Vector[shape.vertices.length];
// loop over the vertices
for (int i = ; i < shape.vertices.length; i++) {
  // get the current vertex
  Vector p1 = shape.vertices[i];
  // get the next vertex
  Vector p2 = shape.vertices[i +  == shape.vertices.length ?  : i + ];
  // subtract the two to get the edge vector
  Vector edge = p1.subtract(p2);
  // get either perpendicular vector
  Vector normal = edge.perp();
  // the perp method is just (x, y) => (-y, x) or (y, -x)
  axes[i] = normal;
}
           

在上面的方法中，我們傳回的是多邊形的每個邊的垂直向量。也就是法向量。這些向量并沒有被機關化（将其模置為機關長度）。如果你隻是想要得到一個布爾結果從SAT算法中這樣會有小，但是如果你想要得出碰撞的具體資訊（這個東西将會在MTV部分讨論），那麼這些法向量需要被機關化。

對每個形狀執行上面的操作能夠得到兩組軸。那麼就會再次需要我們更該僞代碼：

Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();
// loop over the axes1
for (int i = ; i < axes1.length; i++) {
  Axis axis = axes1[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  }
}
// loop over the axes2
for (int i = ; i < axes2.length; i++) {
  Axis axis = axes2[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  }
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;
           

将形狀A向一個軸投影：

另一個沒有很清晰的事情就是如何将一個圖形向一個軸投影。将一個圖形向一個軸投影其實是一個很簡單的事情。循環所有的頂點執行和待測試軸的點乘，存儲下最小值和最大值。

double min = axis.dot(shape.vertices[]);
double max = min;
for (int i = ; i < shape.vertices.length; i++) {
  // NOTE: the axis must be normalized to get accurate projections
  double p = axis.dot(shape.vertices[i]);
  if (p < min) {
    min = p;
  } else if (p > max) {
    max = p;
  }
}
Projection proj = new Projection(min, max);
return proj;
           

找到MTV

到目前為止我們隻能判斷這兩個形狀是否相交。除此之外，SAT可以傳回一個MTV（Minimum Translation Vector 最小分離向量）。MTV是一個最小量級的将兩個相交的圖形分離的向量。如果我們回顧一下圖示7就會發現 軸C 有着最小的投影重疊。那個軸和那個重疊就是MTV，那個軸訓示出MTV的方向，重疊就是這個系數（翻譯者注：重疊指的是重疊的長度，是一個标量，軸訓示方向，可以了解為一個機關矢量，這樣就組成了向量的一種表示方式，機關向量和長度）。

為了确定兩個形狀是否相交，我們必須要測試完所有的軸，即兩個形狀的所有的邊的所有的法向量，而且同時我們還能求出最小的重疊和軸。如果我們更改我們的僞代碼将這我們所說的包含其中我們就可以傳回MTV當這兩個形狀相交的時候：

double overlap = // really large value;
Axis smallest = null;
Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();
// loop over the axes1
for (int i = ; i < axes1.length; i++) {
  Axis axis = axes1[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  } else {
    // get the overlap
    double o = p1.getOverlap(p2);
    // check for minimum
    if (o < overlap) {
      // then set this one as the smallest
      overlap = o;
      smallest = axis;
    }
  }
}
// loop over the axes2
for (int i = ; i < axes2.length; i++) {
  Axis axis = axes2[i];
  // project both shapes onto the axis
  Projection p1 = shape1.project(axis);
  Projection p2 = shape2.project(axis);
  // do the projections overlap?
  if (!p1.overlap(p2)) {
    // then we can guarantee that the shapes do not overlap
    return false;
  } else {
    // get the overlap
    double o = p1.getOverlap(p2);
    // check for minimum
    if (o < overlap) {
      // then set this one as the smallest
      overlap = o;
      smallest = axis;
    }
  }
}
MTV mtv = new MTV(smallest, overlap);
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return mtv;
           

曲邊圖形

我們已經看到了多邊形如何使用SAT進行測試,但是像圓這種曲邊圖形如何被測試呢?曲邊圖形向SAT提出了挑戰,因為曲邊圖形有着無限多的待測試軸.解決這種問題的通常辦法就是将圓形和圓形,圓形和多邊形分解,通過做一些特殊的操作.另一個可選擇的操作不在所有的情況下都是用曲邊圖形,而是用多定點的多邊形取代她.第二中選擇方案對我們之前寫的僞代碼不會造成影響,但是我在這裡想介紹第一種方法.

讓我們首先看一下圓形和圓形,通常情況下,你會做如下的事情:

Vector c1 = circle1.getCenter();
Vector c2 = circle2.getCenter();
Vector v = c1.subtract(c2);
if (v.getMagnitude() < circle1.getRadius() + circle2.getRadius()) {
  // then there is an intersection
}
// else there isnt
           

我們知道當兩個圓形的圓心距小于各自的半徑之和時兩個圓形相交.這其實就是一個SAT測試.為了得到結果我們這樣進行SAT測試:

Vector[] axes = new Vector[];
if (shape1.isCircle() && shape2.isCircle()) {
  // for two circles there is only one axis test
  axes[] = shape1.getCenter().subtract(shape2.getCenter);
}
// then all the SAT code from above
           

多邊形和圓形會帶來更多的問題, 圖心和圖心在多邊形的待測試軸上的測試并不奏效,事實上會得到意想不到的錯誤結果.在這種情況下,你必須要包含另一個軸:那個從距離圓形最近的頂點到圓心的軸.多邊形上最近的頂點的求法有很多種,理想的解決辦法是Voronoi區域算法,但是不會在這篇文章中涉及.

其他的曲邊圖形會帶來更多的問題,必須要使用各自特定的解決辦法.例如一個膠囊形狀可以被分解為一個矩形和兩個半圓.

包含

一個很多開發者選擇忽略的問題就是包含.一個圖形包含另一個圖形會發生什麼麼?這個問題并不會帶了巨大的影響因為絕大多數的應用都不會讓這種情況發生.首先讓我介紹一下這個問題然後是如何解決它.然後我會介紹為什麼我們要将他置于考慮範圍之内.

如果一個圖形被另一個圖形包含,在我們現有的僞代碼中,SAT會傳回不對的MTV.方向和量級都有可能不對.下圖展示了在軸上的投影的重疊不能夠将兩個圖形分離開來.

是以我們需要做的是在重疊測試中檢測有沒有包含.在上面的SAT代碼中加上if語句:

if (!p1.overlap(p2)) {
  // then we can guarantee that the shapes do not overlap
  return false;
} else {
  // get the overlap
  double o = p1.getOverlap(p2);
  // check for containment
  if (p1.contains(p2) || p2.contains(p1)) {
    // get the overlap plus the distance from the minimum end points
    double mins = abs(p1.min - p2.min);
    double maxs = abs(p1.max - p2.max);
    // NOTE: depending on which is smaller you may need to
    // negate the separating axis!!
    if (mins < maxs) {
      o += mins;
    } else {
      o += maxs;
    }
  }
  // check for minimum
  if (o < overlap) {
    // then set this one as the smallest
    overlap = o;
    smallest = axis;
  }
}
           

将包含加入其中的原因:

1. 遊戲中給兩個如此定義的形狀是有可能的.不解決這個問題會要求我們根據兩個形狀的大小進行兩次或者更多的SAT循環來解決這種特殊的碰撞.
2. 如果你準備支援其他形狀的線段分割,你有必要這樣做,因為在一些情況下投影的重疊值可能為零,這是因為一個線段的分割是一個極小的圖形這個事實(譯者注:這些東西後面的翻譯中會有).

其他需要注意的事情

1. 被測試軸的數量可以通過不測試平行軸的方式減少.這就是為什麼一個長方形可以隻測試兩個軸.
2. 之前的分離軸可以作為下一次SAT循環的基礎,這樣這個算法在兩個形狀不想交的時候就會使O(1)的時間複雜度.
3. SAT在3D情況下就會有可能要測試要非常多的軸.
4. 我不是一個專家,是以請原諒我的糟糕的幾何.