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 das Picking sehr genau zu machen. Wenn man lediglich eine BoundingBox 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 Meshes muss man dagegen 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 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 VertexBuffer und IndexBuffer 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 BoundingBox oder BoundingSphere für die Triangles zu erstellen. Ebenfalls implementiert ist eine Intersect()-Methode um den Schnittpunkt eines Strahls mit den Triangles berechnen zu können. Diese funktioniert genauso 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;
    }
  }
}

Verwendung der MeshTriangleData Klasse

Bei der Verwendung der MeshTriangleData Klasse gibt es einige Punkte die man Wissen bzw. beachten muss.

Erzeugung

Die MeshTriangleData Klasse basiert jeweils nur auf einem ModelMeshPart. Um Triangle Intersection für ein komplettes Modell zu ermöglichen muss man also für jedes ModelMeshPart des Modells eine eigene Instanz der MeshTriangleData Klasse erstellen. Wenn man sicher weiss dass das Modell nur aus einem ModelMesh und dieser wiederrum nur aus einem ModelMeshPart besteht kann man auf diese auch einfach über den Index 0 der ModelMeshCollection und der ModelMeshPartCollection der Model Klasse zugreifen (e.g. model.Meshes[0].MeshParts[0]). Hat man komplexere Modelle oder ist sich über deren Aufbau nicht sicher erstellt man am besten eine Zwischenklasse welche automatisch über alle ModelMeshes und ModelMeshParts des Modells iteriert und die entsprechende MeshTriangleData für jedes ModelMeshPart erzeugt, verwaltet und eine Schnittstelle für den Zugriff auf deren Intersect()-Methoden bereitstellt.

Abfragen der absoluten Bone Transformationen

Der Konstruktor der MeshTriangleData Klasse benötigt ein Matrix-Array mit den absoluten Bone Transformationen des Modells, dieses kann man wie folgt aus der Model Klasse abfragen:

Model model;

//get the absolute bone transforms of the model
Matrix[] absoluteBoneTransforms = new Matrix[model.Bones.Count];
model.CopyAbsoluteBoneTransformsTo(absoluteBoneTransforms);