碰撞檢測

碰撞檢測是 3D 遊戲中的基本元件之一。它對於遊戲的真實外觀至關重要，需要快速且穩健的碰撞檢測演算法。如果您的遊戲中不使用某種碰撞檢測，您將無法檢查玩家面前是否有牆壁，或者玩家是否會撞到其他物體。

包圍球

首先我們需要回答問題“什麼是包圍球？”包圍球是指一個球體，它與被球體包圍的物體的中心點幾乎相同。包圍球由其中心點和半徑定義。

在碰撞檢測中，包圍球通常用於球形物體，如懸崖、小行星或宇宙飛船。

讓我們看看當兩個球體接觸時會發生什麼。影像顯示，每個球體的半徑現在也定義了其中心點到對面球體表面的距離。中心點之間的間距等於半徑 1 + 半徑 2。如果距離更大，則兩個球體不會接觸，但如果距離更小，則球體將相交。

確定兩個具有包圍球的物體之間是否發生碰撞的一種可行方法是，只需找到它們中心點之間的距離，然後檢視該距離是否小於它們包圍球半徑之和。

使用包圍球的另一種方法是使用物體的平衡點作為包圍球的中心點。因此，您使用所有頂點的中點作為包圍球的中心點。該演算法為您提供了比第一種方法更精確的中點。

XNA 包圍球

微軟 XNA 提供了一個模型供您使用，透過開發您自己的名為“BoundingSphere”的遊戲。XNA 為您提供了這一點，因此無需您進行計算。XNA 中的模型由一個或多個網格組成。在進行碰撞時，您希望有一個包圍整個模型的球體。這意味著在模型載入時，您需要遍歷模型中的所有網格，並擴充套件一個主要的模型球體。

foreach (ModelMesh mesh in m_model.Meshes)
{
    m_boundingSphere=BoundingSphere.CreateMerged(base.m_boundingSphere, mesh.BoundingSphere);
    ...

為了檢視兩個球體是否發生碰撞，Xna 為我們提供了以下使用方法

bool hasCollided=sphere.Intersects(otherSphere);

包圍矩形或包圍盒

在使用矩形進行碰撞檢測處理時，您希望檢視兩個矩形區域是否以任何方式接觸或重疊。因此，我們需要使用包圍盒。包圍盒只是一個包圍 3D 物件的所有幾何圖形的盒子。我們可以透過簡單地遍歷所有頂點，找到最小和最大的 x、y 和 z 值，輕鬆地從一組頂點計算出一個包圍盒。

要在模型空間中建立圍繞我們模型的包圍盒，您需要計算中點和我們要包圍的矩形的四個角點。然後，您需要構建一個矩陣，並使用給定的旋轉值圍繞中點旋轉四個點。之後，我們需要遍歷模型中的所有頂點，跟蹤最小和最大的 x、y 和 z 位置。這將為我們提供盒子的兩個角點，從中可以計算出所有其他角點。

XNA 包圍盒

由於每個模型都是由多個網格組成的，因此我們需要為每個網格計算頂點位置的最小值和最大值。XNA 中的“ModelMesh”物件被分成幾部分，這些部分提供對緩衝區的訪問，該緩衝區儲存著頂點的資料 (VertexBuffer)，我們可以使用GetData呼叫從該緩衝區獲得頂點的副本。

public BoundingBox CalculateBoundingBox()
{

// Create variables to keep min and max xyz values for the model
Vector3 modelMax = new Vector3(float.MinValue, float.MinValue, float.MinValue);
Vector3 modelMin = new Vector3(float.MaxValue, float.MaxValue, float.MaxValue);

foreach (ModelMesh mesh in m_model.Meshes)
{
  //Create variables to hold min and max xyz values for the mesh
   Vector3 meshMax = new Vector3(float.MinValue, float.MinValue, float.MinValue);
   Vector3 meshMin = new Vector3(float.MaxValue, float.MaxValue, float.MaxValue);

  // There may be multiple parts in a mesh (different materials etc.) so loop through each
  foreach (ModelMeshPart part in mesh.MeshParts)
   {
     // The stride is how big, in bytes, one vertex is in the vertex buffer
     int stride = part.VertexBuffer.VertexDeclaration.VertexStride;

     byte[] vertexData = new byte[stride * part.NumVertices]; 
     part.VertexBuffer.GetData(part.VertexOffset * stride, vertexData, 0, part.NumVertices, 1); // fixed 13/4/11

     // Find minimum and maximum xyz values for this mesh part
     // We know the position will always be the first 3 float values of the vertex data
     Vector3 vertPosition=new Vector3();
     for (int ndx = 0; ndx < vertexData.Length; ndx += stride)
      { 
         vertPosition.X= BitConverter.ToSingle(vertexData, ndx);
         vertPosition.Y = BitConverter.ToSingle(vertexData, ndx + sizeof(float));
         vertPosition.Z= BitConverter.ToSingle(vertexData, ndx + sizeof(float)*2);

         // update our running values from this vertex
         meshMin = Vector3.Min(meshMin, vertPosition);
         meshMax = Vector3.Max(meshMax, vertPosition);
     }
   }

   // transform by mesh bone transforms
   meshMin = Vector3.Transform(meshMin, m_transforms[mesh.ParentBone.Index]);
   meshMax = Vector3.Transform(meshMax, m_transforms[mesh.ParentBone.Index]);

   // Expand model extents by the ones from this mesh
   modelMin = Vector3.Min(modelMin, meshMin);
   modelMax = Vector3.Max(modelMax, meshMax);
}

// Create and return the model bounding box
return new BoundingBox(modelMin, modelMax);
}

地形碰撞

不規則地形

地形與物體之間的碰撞檢測與物體之間的碰撞不同。

首先，您必須檢測當前玩家 (物體) 的座標。地形的高度圖為您提供一個“間隙值”，該值標識兩個連續頂點之間的距離。當您將座標位置除以這些“間隙值”時，您可以檢測到您位置處的頂點。您可以從高度圖緩衝區獲取您所在的 4 個頂點正方形。使用這些資料以及您在該正方形中的位置，您可以計算出到地形的最佳間距，以便不會與地形發生碰撞。

碰撞效能

有時碰撞檢測會減慢遊戲速度。它是應用程式中最耗時的元件。因此，存在四叉樹和八叉樹等資料結構。

四叉樹 (2D)

四叉樹是一種樹形結構，它使用稱為“空間區域性性”的原理來加快查詢所有可能碰撞的過程。物體只能與靠近它們的東西發生碰撞。為了提高效能，您應該避免再次測試遠離的物體。

檢查碰撞的最簡單方法是將要檢查的區域劃分為一個一致的網格，並使用所有與網格單元格相交的物體宣告每個物體。四叉樹試圖透過遞迴地將碰撞空間劃分為更小的子區域來克服這種弱點。每個區域恰好被劃分為 4 個相同大小的更小區域，因此您最終將擁有多個具有不同解析度的網格，其中區域中的單元格數量每次提高解析度都會增加 2 的冪。因此，每個物體都駐留在具有最高可能解析度的單元格 (稱為四叉節點或象限) 中。搜尋從物體的節點開始，向上爬到根節點。