給定一個邊界框和一條直線（兩個點），確定直線是否與方框相交

Question

給定一個邊界框，其中定義爲bounds.min.(x/y/z),bounds.max.(x/y/z)和三維空間中的兩個點（表示爲Vector3對象），如何才能確定兩點產生的線是否與邊界框相交？

Answer 1

讓我谷歌爲你：Line Box Intersection（http://www.3dkingdoms.com/weekly/weekly.php?a=3）

另一個鏈接，用了很多的相交測試引用（和代碼）：http://www.realtimerendering.com/intersections.html

如果您想了解更多關於相交測試，這一個是聖經：Real-Time Collision Detection (Amazon)

編輯：在這個paper算法（「一種高效，強大的雷盒交法」，艾米·威廉姆斯和史蒂夫Barrus和R.基思·莫雷和彼得·雪莉;圖形學報，GPU ， 一個nd遊戲工具，卷。 10（1），49-54,2005）看起來特別簡潔，並附帶（C++）源代碼。

Answer 2

您可以將邊界框表示爲12個三角形（每個面6個）。然後你可以檢查你的線與每個線的交點。我有一個線三角相交函數，但它是爲我自己的軟件渲染引擎編寫的，而不是D3D。如果您需要代碼，我可以嘗試將其轉換。

Answer 3

如果您想自己進行數學運算，可以使用以下一種方法：將邊界與由邊界框創建的6個平面中的每一個相交。

該行的向量表示爲X = B + t * D，其中B是基點（例如，您的第一個點）的元組（x，y，z），D是行的方向，再次表示爲一個元組（dx，dy，dz）。如果你有點P1（x1，y1，z1）和P2（x2，y2，z2），那麼D = P2-P1和B = P1，這意味着你可以通過減去其中一個點來得到方向。 =（x2-x1，y2-y1，z2-z1）。我們將調用這個向量dx，dy和dz的元素。

該平面的參數表示爲x + y + z = c。因此，將您的邊界框轉換爲此表示形式，然後使用線條的參數表示形式，例如三個方程x = x1 + t dx，y = y1 + t dy，z = y1 + t * dz，用平面方程中的x，y和z代替。解決t。由於你的6個飛機中的每一個都將與由2個軸創建的飛機平行，所以你的問題變得更容易;例如對於與由x和y軸創建的平面平行的平面，平面方程簡單地變爲z = c，而c是您的一個邊界框點的z座標，依此類推。

現在使用t來計算線與您的飛機的交點。 （如果t是< 0或> 1，那麼你的直線與P1-P2的外部相交，如果t> = 0且t < = 1，那麼你的直線與P1和P2之間的某個平面相交）

現在，還沒完成。平面方程爲您提供了一個平面，而不是矩形，因此與平面的交點可能實際上位於矩形的外部，但由於您現在具有交點的座標（x = x1 + t * dx等），因此，您可以輕鬆查看該點是否位於您的邊界框的矩形內。您的問題現在減少了，以檢查2D空間中的點是否在邊界框矩形內，這很容易檢查。

當然，如果你真正使用這個解決方案，你應該做的第一件事就是檢查這條線是否也沿着一條軸線對齊，因爲在這種情況下，你的交叉代碼變得微不足道，它也會處理該線不與某些平面相交，例如大量或微小的數量，甚至可能超過或下溢。

我敢打賭，有更快的方法來做到這一點，但它會奏效。

Answer 4

這裏是一個似乎是工作的代碼，從格雷格小號的回答轉換成C＃：

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit) 
{ 
    if (L2.x < B1.x && L1.x < B1.x) return false; 
    if (L2.x > B2.x && L1.x > B2.x) return false; 
    if (L2.y < B1.y && L1.y < B1.y) return false; 
    if (L2.y > B2.y && L1.y > B2.y) return false; 
    if (L2.z < B1.z && L1.z < B1.z) return false; 
    if (L2.z > B2.z && L1.z > B2.z) return false; 
    if (L1.x > B1.x && L1.x < B2.x && 
     L1.y > B1.y && L1.y < B2.y && 
     L1.z > B1.z && L1.z < B2.z) 
    { 
     Hit = L1; 
     return true; 
    } 
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)) 
     || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit) 
{ 
    if ((fDst1 * fDst2) >= 0.0f) return false; 
    if (fDst1 == fDst2) return false; 
    Hit = P1 + (P2 - P1) * (-fDst1/(fDst2 - fDst1)); 
    return true; 
} 

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis) 
{ 
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true; 
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true; 
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true; 
    return false; 
} 

Answer 5

JavaScript版本的基礎上，SpikeX答案，glMatrix：

// all args are Vec3, Hit will be filled by this algo 
function checkLineBox(B1, B2, L1, L2, Hit) 
{ 
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false; 
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false; 
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false; 
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false; 
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false; 
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false; 
    if (L1[0] > B1[0] && L1[0] < B2[0] && 
     L1[1] > B1[1] && L1[1] < B2[1] && 
     L1[2] > B1[2] && L1[2] < B2[2]) 
    { 
     vec3.set(L1, Hit); 
     return true; 
    } 

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)) 
     || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

var temp = vec3.create(); 
function getIntersection(fDst1, fDst2, P1, P2, Hit) 
{ 
    if ((fDst1 * fDst2) >= 0) return false; 
    if (fDst1 == fDst2) return false; 

    vec3.subtract(P2, P1, temp); 
    vec3.scale(temp, (-fDst1/(fDst2 - fDst1))); 
    vec3.add(temp, P1, Hit); 

    return true; 
} 

function inBox(Hit, B1, B2, Axis) 
{ 
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true; 
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    return false; 
}