碰撞检测

碰撞检测是 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 的幂。因此，每个物体都驻留在具有最高可能分辨率的单元格 (称为四叉节点或象限) 中。搜索从物体的节点开始，向上爬到根节点。