Triangle Intersection

Gerade für Picking kann es sehr interessant sein beim Raytracing direkt die Triangles eines Modells für den Schnittpunkttest zu verwenden um dsa Picking sehr genau zu machen. Wenn man lediglich eine Bounding Box verwendet pickt man komplexere Modelle auch wenn man sie eigentlich garnicht anklickt.

Schnittberechnung Strahl - Triangle

Die Berechnung der Schnittpunkte eines Strahls mit verschiedenen Bounding Volumes ist in XNA in den entsprechenden Structs bereits implementiert. Die Schnittberechnung eines Strahls mit den Triangles eines Model Meshs muss man manuell implementieren. Die folgende Helfer-Klasse bietet dafür eine Methode. Diese Methode wird auch in den weiteren Code Samples zum Berechnen der Schnittpunkte verwendet.

/// <summary>
/// Provides additional intersection functions for the ray casting.
/// </summary>
public static class IntersectionHelper
{
  /// <summary>
  /// Intersects a ray with a triangle.
  /// </summary>
  /// <param name="ray">The ray which is to be intersected. CAUTION: It must be in the same coordinate system as the triangle!</param>
  /// <param name="vertex1">The first vertex of the triangle which is to be intersected.</param>
  /// <param name="vertex2">The second vertex of the triangle which is to be intersected.</param>
  /// <param name="vertex3">The third vertex of the triangle which is to be intersected.</param>
  /// <param name="result">The result of the intersection test. If the triangle is hit, this value gets the distance to the intersection point on the ray, else it gets <c>null</c>.</param>
  internal static void RayTriangleIntersect(ref Ray ray, ref Vector3 vertex1, ref Vector3 vertex2, ref Vector3 vertex3, out float? result)
  {
    // Compute vectors along two edges of the triangle.
    Vector3 edge1 = new Vector3();
    Vector3 edge2 = new Vector3();

    //edge1 = vertex2 - vertex1;
    edge1.X = vertex2.X - vertex1.X;
    edge1.Y = vertex2.Y - vertex1.Y;
    edge1.Z = vertex2.Z - vertex1.Z;
    //edge2 = vertex3 - vertex1;
    edge2.X = vertex3.X - vertex1.X;
    edge2.Y = vertex3.Y - vertex1.Y;
    edge2.Z = vertex3.Z - vertex1.Z;

    // Compute the determinant.
    //directionCrossEdge2 = ray.Direction X edge2;
    Vector3 directionCrossEdge2 = new Vector3();
    directionCrossEdge2.X = ray.Direction.Y * edge2.Z - ray.Direction.Z * edge2.Y;
    directionCrossEdge2.Y = ray.Direction.Z * edge2.X - ray.Direction.X * edge2.Z;
    directionCrossEdge2.Z = ray.Direction.X * edge2.Y - ray.Direction.Y * edge2.X;

    //determinant = edge1 ° directionCrossEdge2;
    float determinant = edge1.X * directionCrossEdge2.X + edge1.Y * directionCrossEdge2.Y + edge1.Z * directionCrossEdge2.Z;

    // If the ray is parallel to the triangle plane, there is no collision.
    if (determinant > -float.Epsilon && determinant < float.Epsilon)
    {
      result = null;
      return;
    }

    float inverseDeterminant = 1.0f / determinant;

    // Calculate the U parameter of the intersection point.
    //distanceVector = ray.Position - vertex1;
    Vector3 distanceVector = new Vector3();
    distanceVector.X = ray.Position.X - vertex1.X;
    distanceVector.Y = ray.Position.Y - vertex1.Y;
    distanceVector.Z = ray.Position.Z - vertex1.Z;

    //triangleU = (distanceVector ° directionCrossEdge2) * inverseDeterminant;
    float triangleU = (distanceVector.X * directionCrossEdge2.X + distanceVector.Y * directionCrossEdge2.Y + distanceVector.Z * directionCrossEdge2.Z) * inverseDeterminant;

    // Make sure it is inside the triangle.
    if (triangleU < 0 || triangleU > 1)
    {
      result = null;
      return;
    }

    // Calculate the V parameter of the intersection point.
    //distanceCrossEdge1 = distanceVector X edge1;
    Vector3 distanceCrossEdge1 = new Vector3();
    distanceCrossEdge1.X = distanceVector.Y * edge1.Z - distanceVector.Z * edge1.Y;
    distanceCrossEdge1.Y = distanceVector.Z * edge1.X - distanceVector.X * edge1.Z;
    distanceCrossEdge1.Z = distanceVector.X * edge1.Y - distanceVector.Y * edge1.X;

    //triangleV = (ray.Direction ° distanceCrossEdge1) * inverseDeterminant;
    float triangleV = (ray.Direction.X * distanceCrossEdge1.X + ray.Direction.Y * distanceCrossEdge1.Y + ray.Direction.Z * distanceCrossEdge1.Z) * inverseDeterminant;

    // Make sure it is inside the triangle.
    if (triangleV < 0 || triangleU + triangleV > 1)
    {
      result = null;
      return;
    }

    // Compute the distance along the ray to the triangle.
    //rayDistance = (edge2 ° distanceCrossEdge1) * inverseDeterminant;
    float rayDistance = (edge2.X * distanceCrossEdge1.X + edge2.Y * distanceCrossEdge1.Y + edge2.Z * distanceCrossEdge1.Z) * inverseDeterminant;

    // Is the triangle behind the ray origin?
    if (rayDistance < 0)
    {
      result = null;
      return;
    }

    result = rayDistance;
  }
}

Damit die Methode möglichst performant ist wurde die Anzahl an Methodenaufrufen durch Inlining möglichst minimiert und es werden Call by Reference und Rückgabeparameter verwendet. Diese Methode muss für jedes Triangle eines Meshes aufgerufen werden, also sogar schon bei Modellen mit wenigen Hundert Polygonen sehr oft, daher können diese Optimierungen an dieser Stelle einen bedeutenden Performance Gewinn bringen.

Auslesen des Meshs eines Models

Die einzige Möglichkeit bei XNA an die Triangles eines Modells zu gelangen ist die Vertex Buffer und Index Buffer der einzelnen Modelmeshes auszulesen. Die folgende Klasse liest diese beiden für ein Model-Mesh aus und speichert sie in Member-Variablen zwischen. Zusätzlich bietet sie Methoden um eine Bounding Box oder Bounding Sphere für die Triangles zu erstellen. Ebenfalls implementiert ist eine Intersect-Methode um den Schnittpunkt eines Strahls mit den Triangles berechnen zu können welche von genauso funktioniert wie die Intersect-Methoden der Bounding Volume und Ray Structs.

/// <summary>
/// Reads the mesh data (vertices and indices) of a ModelMeshPart and provides a method to intersect a ray with the triangles of the mesh.
/// </summary>
public sealed class MeshTriangleData
{
  /// <summary>
  /// Stores the vertices of the mesh.
  /// </summary>
  private Vector3[] vertices;

  /// <summary>
  /// Stores the indices of the mesh if they have a size of sixteen bits.
  /// </summary>
  private ushort[] indicesShort;
  /// <summary>
  /// Stores the indices of the mesh if they have a size of thirtytwo bits.
  /// </summary>
  private uint[] indicesInt;
  /// <summary>
  /// Indicates if the mesh uses thirtytwo bit indices (true) or sixteen bit indices (false).
  /// </summary>
  private bool use32BitIndices = false;

  /// <summary>
  /// Creates a new MeshTriangleData object for the ModelMeshPart-Index of the mesh.
  /// </summary>
  /// <param name="mesh">The mesh of the model.</param>
  /// <param name="modelMeshPartIndex">The index of the mesh part of the mesh.</param>
  /// <param name="absoluteBoneTransforms">The absolute bone transforms of the model to which the mesh belongs.</param>
  public MeshTriangleData(ModelMesh mesh, int modelMeshPartIndex, ref Matrix[] absoluteBoneTransforms)
  {
    ModelMeshPart meshPart = mesh.MeshParts[modelMeshPartIndex];

    Matrix absoluteBoneTransform = absoluteBoneTransforms[mesh.ParentBone.Index];

    //get the index data
    if (meshPart.IndexBuffer.IndexElementSize == IndexElementSize.SixteenBits)
    {
      this.indicesShort = new ushort[meshPart.PrimitiveCount * 3];
      meshPart.IndexBuffer.GetData<ushort>(meshPart.StartIndex * sizeof(ushort), this.indicesShort, 0, meshPart.PrimitiveCount * 3);
    }
    else if (meshPart.IndexBuffer.IndexElementSize == IndexElementSize.ThirtyTwoBits)
    {
      this.indicesInt = new uint[meshPart.PrimitiveCount * 3];
      meshPart.IndexBuffer.GetData<uint>(meshPart.StartIndex * sizeof(uint), this.indicesInt, 0, meshPart.PrimitiveCount * 3);
      this.use32BitIndices = true;
    }

    //get the vertex data
    this.vertices = new Vector3[meshPart.NumVertices];
    meshPart.VertexBuffer.GetData<Vector3>(meshPart.VertexOffset, this.vertices, 0, meshPart.NumVertices, meshPart.VertexBuffer.VertexDeclaration.VertexStride);
    //transform the vertex data
    for (int i = 0; i < this.vertices.Length; ++i)
    {
      Vector3.Transform(ref this.vertices[i], ref absoluteBoneTransform, out this.vertices[i]);
    }
  }

  /// <summary>
  /// Calculates a bounding box around the triangle mesh.
  /// </summary>
  /// <param name="boundingBox">The bounding box for the triangle mesh.</param>
  public void CalculateBoundingBox(out BoundingBox boundingBox)
  {
    boundingBox = BoundingBox.CreateFromPoints(this.vertices);
  }

  /// <summary>
  /// Calculates a bounding sphere around the triangle mesh.
  /// </summary>
  /// <param name="boundingSphere">The bounding shpere for the triangle mesh.</param>
  public void CalculateBoundingSphere(out BoundingSphere boundingSphere)
  {
    boundingSphere = BoundingSphere.CreateFromPoints(this.vertices);
  }

  /// <summary>
  /// Checks wether the current triangle mesh intersects a ray in the object space of the corresponding model.
  /// </summary>
  /// <param name="objectRay">The ray to check intersection with. CAUTION: The ray must be in the object space of the model to which the triangle mesh belongs!</param>
  /// <param name="result">Distance at which the ray intersects the triangle mesh, or <c>null</c> if there is no intersection.</param>
  public void Intersects(ref Ray objectRay, out float? result)
  {
    result = null;
    float nearestResult = float.PositiveInfinity;

    if (this.use32BitIndices)
    {
      for (int i = 0; i < this.indicesInt.Length; i += 3)
      {
        IntersectionHelper.RayTriangleIntersect(ref objectRay, ref this.vertices[this.indicesInt[i]], ref this.vertices[this.indicesInt[i + 1]], ref this.vertices[this.indicesInt[i + 2]], out result);

        if ((result.HasValue) && (result.Value < nearestResult))
        {
          nearestResult = result.Value;
        }
      }
    }
    else
    {
      for (int i = 0; i < this.indicesShort.Length; i += 3)
      {
        IntersectionHelper.RayTriangleIntersect(ref objectRay, ref this.vertices[this.indicesShort[i]], ref this.vertices[this.indicesShort[i + 1]], ref this.vertices[this.indicesShort[i + 2]], out result);

        if ((result.HasValue) && (result.Value < nearestResult))
        {
          nearestResult = result.Value;
        }
      }
    }

    if (!float.IsPositiveInfinity(nearestResult))
    {
      result = nearestResult;
    }
  }
}