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, kann man unter Umständen Modelle auch "picken" wenn man sie eigentlich gar nicht angeklickt hat.

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 Geschwindigkeits-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 * meshPart.VertexBuffer.VertexDeclaration.VertexStride, 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);

Mesh Data befindet sich im ObjectSpace

Die Mesh Daten die von der MeshTriangleData Klasse ausgelesen werden, also die Positionen der Vertices, befinden sich im Object Space, also im Koordinatensystem des Objekts. Zur Veranschaulichung: Der Object Space entspricht dem Koordinatensystem der Modellierungssoftware, so liegt der Nullpunkt (also x,y,z = 0) eines Würfels in diesem System z.B. für gewöhnlich in seiner Mitte. In der Spielwelt wird dagegen im sogenannten World Space gearbeitet welcher über ein eigenes Koordinatensystem verfügt. So kann der World Space z.B. für ein Spielbrett das Zentrum in die linke obere Ecke legen während die darauf befindlichen Figuren anhand verschiedener Translationen auf den einzelnen Feldern des Spielbretts positioniert werden. Diese Translationen entsprechen dann den Positionen der Figuren in der Welt. Wenn man sich dieser Tatsache bewusst ist kann man sie gewinnbringend einsetzen.

Instantiierung pro Asset genügt

Da sich die Mesh Daten der MeshTriangleData Klasse im Object Space befinden werden die Daten für ein bestimmtes Asset bzw. Modell immer die selben bleiben, egal wo sich dieses Modell später in der Spielwelt befindet, also egal welche Translation, Rotation oder Skalierung im World Space darauf angewandt wird. Dies bringt den Vorteil dass die Mesh Daten nicht für jede Instanz eines Modells separat ausgelesen werden müssen sondern es genügt die Mesh Daten für ein Modell einmal am Anfang beim Laden des Assets zu erzeugen und dann können sie für jede Instanz zum Berechnen von Ray-Mesh-Intersections verwendet werden. Die Unterscheidung für welche Instanz des Modells die Schnittpunkte berechnet werden sollen findet allein beim Aufruf der Intersect()-Methode statt indem der Strahl vorher vom World Space in den Object Space des Modells umgerechnet wird.

Transformation des Rays in den Object Space

Da sich die Mesh Daten im Object Space befinden müsste man jedesmal bevor man einen Schnittpunkt mit dem Mesh berechnen kann den kompletten Triangle Mesh (also jeden einzelnen Vertice davon) zuvor in den World Space transformieren, also mit der World Matrix multiplizieren. Da ein Mesh für gewöhnlich aus vielen Vertices besteht würde das jedesmal eine Vielzahl an Operationen bedeuten was die Performance extrem belasten würde da dies komplett auf der CPU berechnet werden würde. (Anmerkung: Zum zeichnen der Welt wird dies von der GPU gemacht.)

Anstatt nun also jedesmal den kompletten Mesh in den World Space zu transformieren kann man auch einfach den umgekehrten Weg nehmen und den einzelnen Strahl vom World Space in den Object Space des Objekts transformieren. Dazu muss man den Strahl lediglich mit der inversen World Matrix des Models multiplizieren. Wie in den Kommentaren der Intersect()-Methode der MeshTriangleData Klasse bereits steht muss dies mit dem Strahl gemacht werden bevor er dieser Methode übergeben wird damit das richtige Ergebnis zurückgegeben wird. Im Code könnte dies wie folgt aussehen:

//we have
GameObject object; //some object which uses a model which we want to check for a ray intersection
Ray ray; //the intersecting ray, as usual in the world space

//now we transform the ray into object space:
Ray objectRay = new Ray();
//1) calculate the inverse world matrix of the object
Matrix worldMatrix = object.WorldMatrix; //(the world matrix is just the combined scale, orientation and translation matrix of the object)
Matrix objectSpaceMatrix;
Matrix.Invert(ref worldMatrix, out objectSpaceMatrix);
//2) transform the position and direction with the inverse world
Vector3.Transform(ref ray.Position, ref objectSpaceMatrix, out objectRay.Position);
Vector3.TransformNormal(ref ray.Direction, ref objectSpaceMatrix, out objectRay.Direction);
objectRay.Direction.Normalize();

Das Codebeispiel erzeugt mit objectRay einen neuen Strahl welcher dem originalen Strahl im Object Space des Models entspricht. Dieser kann dann mit der Intersect()-Methode der MeshTriangleData Klasse verwendet werden.

Rücktransformation der Ergebnisdistanz in den World Space

Da der Strahl zur Schnittpunktberechnung in den Object Space des entsprechenden Models transformiert wurde erhält man als Ergebnis der Intersect()-Methode der MeshTriangleData Klasse entsprechend die Distanz auf dem Strahl ebenfalls im Object Space des Modells! Damit man diese nun mit den Schnittdistanzen von anderen Modellen vergleichen kann um den nahsten Schnittpunkt für das Ray Tracing zu bestimmen muss man die erhaltenen Distanzen für jedes einzelne Modell (Innerhalb eines Modells, also für die einzelnen Meshes und Mesh Parts, kann man natürlich die Distanzen im Object Space vergleichen da sich diese alle im selben Object Space befinden) vorher wieder zurück in den World Space transformieren. Dies kann man wie folgt implementieren:

//we have
GameObject object; //some object which uses a model which we want to check for a ray intersection
Ray ray; //the intersecting ray, as usual in the world space
Ray objectRay; //the intersecting ray in the object space of the model
float? result; //the distance of the intersection point on the ray in the object space of the model

//we will get
float? worldResult = null; //the distance of the intersection point on the ray in world space or null if there was no intersection

if (result.HasValue)
{
  //calculate the intersection point in the object space
  Vector3 intersectionPoint = objectRay.Position + objectRay.Direction * result.Value;
  //transform the intersection point into world space
  Vector3.Transform(ref intersectionPoint, ref object.worldMatrix, out intersectionPoint); //(the world matrix is just the combined scale, orientation   and translation matrix of the object)
  //intersectionPoint now contains the intersection point of the ray and the object in world space, you might want to return it if you need it at some time
  //calculate the distance from the ray position to the intersection point as the distance in world space
  Vector3 rayOriginToIntersectionPoint = intersectionPoint - ray.Position;
  worldResult = rayOriginToIntersectionPoint.Length();
}

Die so berechnete Entfernung im World Space kann dann ganz normal unter den einzelnen Modellen verglichen werden um den nahsten Schnittpunkt und damit das vom Strahl getroffende Objekt zu bestimmen. Nebenbei erhält man auch den Schnittpunkt des Strahls und des Objekts im World Space und kann diesen direkt weiterverwenden ohne ihn später erneut aus der Distanz berechnen zu müssen um z.B. einen Effekt am Auftreffpunkt zu erzeugen.