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.

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.

public sealed class MeshTriangleData
{
  private Vector3[] vertices;

  private ushort[] indicesShort;
  private uint[] indicesInt;
  private bool use32BitIndices = false;

  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]);
    }
  }

  public void CalculateBoundingBox(out BoundingBox boundingBox)
  {
    boundingBox = BoundingBox.CreateFromPoints(this.vertices);
  }

  public void CalculateBoundingSphere(out BoundingSphere boundingSphere)
  {
    boundingSphere = BoundingSphere.CreateFromPoints(this.vertices);
  }

  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;
    }
  }
}

Um die einzelnen Ray-Triangle-Schnittpunkte berechnen zu können bietet die folgende Helfer Klasse eine entsprechende Methode welche von der oberen Klasse auch verwendet wird.

/// <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 diese Klassen und ihre Methoden möglichst performant sind wurde die Anzahl an Methodenaufrufen durch Inlining möglichst minimiert und es wird Call by Reference und Rückgabeparameter verwendet.