Triangle Intersection: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen Versionsunterschied
VisuellWikitext
Florian (Diskussion | Beiträge)
sopra
555 Bearbeitungen
Florian (Diskussion | Beiträge)
sopra
555 Bearbeitungen
Keine Bearbeitungszusammenfassung
 
(12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Stub}}
{{review}}


__TOC__
__TOC__


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 <tt>BoundingBox</tt> verwendet pickt man komplexere Modelle auch wenn man sie eigentlich garnicht anklickt.
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 <tt>BoundingBox</tt> verwendet, kann man unter Umständen Modelle auch "picken" wenn man sie eigentlich gar nicht angeklickt hat.


== Schnittberechnung Strahl - Triangle ==
== Schnittberechnung Strahl - Triangle ==


Die Berechnung der Schnittpunkte eines Strahls mit verschiedenen Bounding Volumes ist in XNA in den entsprechenden [[Struct]]s 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.
Die Berechnung der Schnittpunkte eines Strahls mit verschiedenen [[Bounding Volume]]s ist in XNA in den entsprechenden [[Struct]]s 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.


<source lang="csharp">
<source lang="csharp">
Zeile 107: Zeile 107:
</source>
</source>


Damit die Methode möglichst performant ist wurde die Anzahl an Methodenaufrufen durch Inlining möglichst minimiert und es werden [[Parameterübergabe#Call_by_Reference | Call by Reference]] und [[Parameterübergabe#Rückgabeparameter | 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.
Damit die Methode möglichst performant ist wurde die Anzahl an Methodenaufrufen durch Inlining möglichst minimiert und es werden [[Parameterübergabe#Call_by_Reference | Call by Reference]] und [[Parameterübergabe#Rückgabeparameter | 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. [[Kategorie:Code-Beispiele]]


== Auslesen des Meshs eines Models ==
== Auslesen des Meshs eines Models ==
Zeile 164: Zeile 164:
     //get the vertex data
     //get the vertex data
     this.vertices = new Vector3[meshPart.NumVertices];
     this.vertices = new Vector3[meshPart.NumVertices];
     meshPart.VertexBuffer.GetData<Vector3>(meshPart.VertexOffset, this.vertices, 0, meshPart.NumVertices, meshPart.VertexBuffer.VertexDeclaration.VertexStride);
     meshPart.VertexBuffer.GetData<Vector3>(meshPart.VertexOffset * meshPart.VertexBuffer.VertexDeclaration.VertexStride, this.vertices, 0, meshPart.NumVertices, meshPart.VertexBuffer.VertexDeclaration.VertexStride);
     //transform the vertex data
     //transform the vertex data
     for (int i = 0; i < this.vertices.Length; ++i)
     for (int i = 0; i < this.vertices.Length; ++i)
Zeile 258: Zeile 258:


==== Instantiierung pro Asset genügt ====
==== Instantiierung pro Asset genügt ====
Da sich die Mesh Daten der <tt>MeshTriangleData</tt> 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 <tt>Intersect()</tt>-Methode statt indem der Strahl vorher vom World Space in den Object Space des Modells umgerechnet wird.


==== Transformation des Rays in den Object Space ====
==== Transformation des Rays in den Object Space ====


[[Kategorie:Code-Beispiele]]
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 <tt>Intersect()</tt>-Methode der <tt>MeshTriangleData</tt> 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:
 
<source lang="CSharp">
//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();
</source>
 
Das Codebeispiel erzeugt mit <tt>objectRay</tt> einen neuen Strahl welcher dem originalen Strahl im Object Space des Models entspricht. Dieser kann dann mit der <tt>Intersect()</tt>-Methode der <tt>MeshTriangleData</tt> 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 <tt>Intersect()</tt>-Methode der <tt>MeshTriangleData</tt> 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:
 
<source lang="CSharp">
//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();
}
</source>
 
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.
 
[[Kategorie:Code-Beispiele]][[Kategorie:Tutorials]]
[[Kategorie:MS02]]
[[Kategorie:MS03]]
[[Kategorie:MS04]]
Abgerufen von „https://sopranium.de/Triangle_Intersection“