github工程。
如何進行相交測試
在第一期文章中，我們最後留下來一個問題：
如何判斷一條射線和哪些物體相交
？
這個問題分為兩步來解決：
使用空間場景劃分找到可能相交的物體（粗測階段）
。（找到1，2，3這三個物體）
對上一步找到的物體進行逐個遍歷，判斷出是否相交（精測階段）
。（對1，2，3進行遍歷，最終只有1是相交的）
粗測階段
粗測階段首先需要用一個AABB把射線包裹起來。這一步很簡單，注意當射線完全垂直或者水平時需要有一個
最小寬度和最小高度
。
///
/// CreateRect By a 2 vector2 point
///
public
static
Rect
CreateRect
（
Vector2
start
，
Vector2
end
）
{
var
segment
=
end
-
start
；
var
rect
=
new
Rect
（）；
rect
。
x
=
Mathf
。
Min
（
start
。
x
，
end
。
x
）；
rect
。
y
=
Mathf
。
Min
（
start
。
y
，
end
。
y
）；
rect
。
width
=
Mathf
。
Abs
（
segment
。
x
）；
rect
。
height
=
Mathf
。
Abs
（
segment
。
y
）；
if
（
rect
。
width
==
0f
）
{
rect
。
width
=
MINRECTWIDTH
；
}
if
（
rect
。
height
==
0f
）
{
rect
。
height
=
MINRECTHEIGHT
；
}
return
rect
；
}
第二步是遍歷四叉樹，有
按廣度遍歷和按深度遍歷
兩種方法，我這裡採用按廣度遍歷。考慮到某些同學可能不知道如何按廣度遍歷，我這裡解釋一下： 比如如下二叉樹，按廣度遍歷就是8，6，10，5，7，9，11。而按深度遍歷有前序遍歷、中序遍歷、後序遍歷，這裡就不展開了。廣度遍歷的做法就是
使用一個佇列來儲存將要遍歷的節點
。遍歷到8時，把左節點6和右節點10放到佇列，遍歷到6時把左節點5和右節點7放到佇列，當一個節點是葉節點時不處理，不斷迴圈，直到佇列裡沒有東西。
在我們這裡鬆散四叉樹的情況，為了剪掉不必要的分支，
當節點的鬆散範圍不與當前檢測的AABB相交時或者它和它的所有子節點包含的物體個數為0時
，我們可以不要考慮這個節點。
最後程式碼如下：
//QuadTree。cs
public
List
<
IQuadTreeItem
>
GetItems
（
Rect
rayRect
）
{
_cacheItemsFound
。
Clear
（）；
_traverseNodeQueue
。
Clear
（）；
AddNodeToTraverseList
（
_root
，
rayRect
）；
while
（
_traverseNodeQueue
。
Count
>
0
）
{
var
currentChild
=
_traverseNodeQueue
。
Dequeue
（）；
foreach
（
IQuadTreeItem
item
in
currentChild
。
items
）
{
if
（
item
。
rect
。
Intersects
（
rayRect
）
）
{
_cacheItemsFound
。
Add
（
item
）；
}
}
if
（
currentChild
。
isLeaf
==
false
）
{
foreach
（
var
node
in
currentChild
。
childNodes
）
{
AddNodeToTraverseList
（
node
，
rayRect
）；
}
}
}
return
_cacheItemsFound
；
}
private
void
AddNodeToTraverseList
（
QuadTreeNode
node
，
Rect
rayRect
）
{
if
（
node
。
totalItemsCount
>
0
&&
node
。
looseRect
。
Intersects
（
rayRect
）
）
{
_traverseNodeQueue
。
Enqueue
（
node
）；
}
}
Rect.Intersets
是我寫的擴充套件方法，用來判斷兩個AABB是否相交，原理也很簡單，比較2個AABB的xMin，xMax，yMin，yMax。
public
static
bool
Intersects
（
this
Rect
rect
，
Rect
target
）
{
if
（
rect
。
yMin
>
target
。
yMax
）
{
return
false
；
}
if
（
rect
。
yMax
<
target
。
yMin
）
{
return
false
；
}
if
（
rect
。
xMax
<
target
。
xMin
）
{
return
false
；
}
if
（
rect
。
xMin
>
target
。
xMax
）
{
return
false
；
}
return
true
；
}
在碰撞檢測領域，AABB和AABB是否相交是最簡單的問題了，往上的還有
三角形和三角形相交，多邊形和多邊形相交，圓和多邊形相交等等
。它們會用到一個
凸體基本理論：若兩個凸體不相交，則必定存在一個平面，使兩個凸體分別處於兩邊。
這些平面通常是物體的切平面，而取平面的法向量做軸，將物體投影與這些軸上，如果有一個軸上的投影存在重疊，則兩個凸體必然相交
。這個軸就叫分離軸，這個定理叫
分離軸定理
。
（這些內容屬於擴充套件知識，平常基本用不到，但是如果面試問到了就是你裝逼的機會了。）
具體可以看這篇文章：《碰撞檢測之分離軸定理演算法講解》關於碰撞檢測更多的知識，可以看
《實時碰撞檢測演算法技術》
這本書。
（左圖不相交，右圖相交）
精測階段
經過上一步，我們可以知道射線可能相交的物體有1，2，3這三個物體。接下來逐個判斷射線是否與這三個物體是否相交。
那麼，
如何判斷射線與AABB是否相交呢？
這個問題可以轉化成
射線與AABB的四條邊是否相交
，進而轉化成
射線與線段是否相交
。 首先根據射線起點和終點求出射線方程：
var
destPoint
=
origin
+
dir
*
distance
；
//ax + by + c = 0
var
a
=
destPoint
。
y
-
origin
。
y
；
var
b
=
origin
。
x
-
destPoint
。
x
；
var
c
=
destPoint
。
x
*
origin
。
y
-
destPoint
。
y
*
origin
。
x
；
然後我以AABB的左邊舉例，把xMin代入直線方程，如果對應的y值處於yMin和yMax之間說明有交點，注意b不能等於0，因為需要
求出第一個交點在哪，所以需要計算每個交點與起點的距離，最近的那個交點就是第一個交點
：
//y = （-c - a * x ）/b
if
（
b
！=
0f
）
{
if
（
xMin
<
x2
&&
xMin
>
x1
）
{
tempHitPoint
。
x
=
xMin
；
var
y
=
（
-
c
-
a
*
xMin
）
/
b
；
if
（
y
<
yMax
&&
y
>
yMin
）
{
tempHitPoint
。
y
=
y
；
hit
=
true
；
var
dis
=
（
tempHitPoint
-
origin
）。
magnitude
；
if
（
dis
<
hitDistance
）
{
hitPoint
=
tempHitPoint
；
hitDistance
=
dis
；
}
}
}
}
其他三條邊使用相同的原理。 對應的演示場景在
Test/Scenes/RaycastAABB
。
總結
這樣，我們就能實現Unity的Raycast類似功能的方法了：
public
static
void
Raycast
（
QuadTree
quadTree
，
Vector2
origin
，
Vector2
direction
，
ref
JRaycastHitList
hitList
，
float
distance
，
int
layMask
）
{
var
hitCount
=
0
；
var
ray
=
direction
。
normalized
*
distance
；
var
destPoint
=
origin
+
ray
；
//根據射線起點和終點構造AABB
var
rayRect
=
CreateRect
（
origin
，
destPoint
）；
//粗測階段，得到可能相交的AABB列表
var
itemList
=
quadTree
。
GetItems
（
rayRect
）；
//精測階段，同時考慮layMask
foreach
（
IQuadTreeItem
item
in
itemList
）
{
var
collider
=
item
。
selfCollider
；
var
layer
=
collider
。
gameObject
。
layer
；
if
（
！
layMask
。
Contains
（
layer
）
）
{
continue
；
}
if
（
！
collider
。
gameObject
。
activeInHierarchy
）
{
continue
；
}
if
（
！
collider
。
enabled
）
{
continue
；
}
//計算一條射線與AABB是否相交
CalculateRayHit
（
collider
，
origin
，
direction
，
ref
hitList
，
distance
，
ref
hitCount
）；
}
}
這裡還用到我自己寫的一個
layerMask
功能，就是用來
設定哪些層和哪些層需要計算碰撞的功能
。如圖，Default層只和Default、Character、Platform層進行碰撞。指令碼在
Scripts\Editor\JPhysicsSettingInspector
。 使用了
EditorGUILayout.MaskField
的API。
以上就是整個2D物體系統系列文章的全部內容了。從上個月底到現在從專案原始碼和寫部落格花了大概半個多月時間了。因為時間有限只做了最基礎的功能，大家看這些文章主要還是以學習為主，實戰中需要親自搭建物理系統的需求還是少。那麼為什麼我還要寫這系列文章？
為了提高知識的廣度，從而讓自己在未來面試時有更多優勢
。像是物體相交測試的分離軸定理，在米哈遊和位元組的高階客戶端崗位面試時都可能會問到。
當每個人的業務能力差不多的時候，比拼的就是理論知識
。其實我很討厭
內卷
這個詞，不過是競爭激烈換了個說法。在如今越來越內卷的程式設計師行業，只有不斷學習和精進，才能避免自己被淘汰。
說迴文章，從第一篇的框架搭建，到第二篇的空間劃分，到這一篇的相交測試，考慮到受眾和我的時間有限，每一篇的內容其實深度都不是特別深，選擇四叉樹只是因為實現起來比較簡單，同時能複習到關於二叉樹的知識，在我的演示專案裡四叉樹效率並不高，
比unity的射線檢測差了差不多4~5倍左右吧
，
實戰中需要進一步最佳化四叉樹的查詢演算法或者選用其他更合適的資料結構
。相信大家全部看完後對於物理系統有著更深刻的理解。我是水雞，我們下期再見。
水曜日雞
，簡稱
水雞
，ACG宅。曾參與索尼中國之星專案研發，具有2D聯網多人動作遊戲開發經驗。
CSDN部落格：
https：//
blog。csdn。net/j75691537
0
知乎專欄：
https：//
zhuanlan。zhihu。com/c_12
41442143220363264
交流學習群：891809847
