Bei der Auswahl von Objekten via Mauszeiger gibt es generell ein Problem: Die Mauszeigerkoordinaten haben nur zwei Dimensionen. Die x- und y-Koordinaten sind für unsere flachen Bildschirme ausreichend, aber für einen dreidimensionalen Punkt benötigen wir die dritte Dimension.
Problembeschreibung
In der obigen Abbildung ist das Problem noch einmal verdeutlicht: Von der Mauszeigerposition auf dem Bildschirm aus verläuft ein Strahl „in den Bildschirm hinein“. Je nachdem, wo sich der Mauszeiger gerade befindet, verschiebt sich auch der Startpunkt des Strahls.
Das allein ist zwar noch nicht problematisch, aber der Strahl bzw. seine Länge ist das Problem:
Wie lang genau soll dieser Strahl sein, wenn seine Länge nicht bekannt ist, weil sie nicht aus den 2D-Koordinaten des Mauszeigers abgelesen werden kann?
Die Länge ist demnach frei wählbar.
Hier gibt es je nach Anwendungsfall drei Herangehensweisen:
- Auf der Höhe jedes zu prüfenden Objekts wird eine zur Bildschirmfläche parallele Ebene aufgespannt und der Schnittpunkt des Strahls mit dieser Ebene gemessen. Liegt dieser Schnittpunkt dann innerhalb des Objekts, liegt der Mauszeiger über dem Objekt.
- Man weiß bereits, dass der Mauszeiger nicht direkt auf Objekte zeigen, sondern vielmehr eine Position auf einer Fläche angeben soll. Das ist zum Beispiel bei Spielen mit isometrischer Ansicht der Fall (Diablo, Sim City, usw.). In diesem Fall berechnet man den Schnittpunkt des Strahls mit einer Ebene auf der Höhe der Fläche.
- Man verleiht dem Strahl eine unendliche Länge und prüft für jedes Objekt, ob der Strahl durch dessen Hitbox (z.B. in Form einer Kugel) verläuft. Dies ist genau dann sinnvoll, wenn einfach nur geprüft werden soll, ob sich der Mauszeiger generell auf einem der auf dem Bildschirm abgebildeten Objekte befindet.
Dieser Beitrag thematisiert die ersten beiden Ansätze, da sich die dafür benötigten Rechenschritte relativ ähnlich sind. Es gibt auch noch einen vierten Ansatz, das „Framebuffer Picking“, was aber Teil eines ganz anderen Lösungsansatzes ist und nicht auf analytischer Geometrie beruht.
Benötigtes Vorwissen
In der Spieleprogrammierung wird eine 3D-Welt modelliert, in der alle Objekte dreidimensionale Koordinaten haben.
Anschließend werden alle Koordinaten mit Hilfe von Matrixmultiplikationen vom dreidimensionalen Raum („world space“) in den zweidimensionalen Raum übersetzt, damit sie auf dem Bildschirm angezeigt werden können. Diese Übersetzung besteht aus zwei Schritten:
- Zunächst werden die Objektkoordinaten in Relation zur Kamera neu ausgerichtet. Denn je nach Kameraposition befinden sich Objekte mal vor und mal hinter der Kamera. Diese „Neuausrichtung“ wird erreicht, indem man die Objektkoordinaten mit einer bestimmten Matrix (bestehend aus vier Zeilen und vier Spalten) multipliziert. Diese Matrix nennt man auch „view matrix“, weil sie Informationen bzgl. der Kameraposition, ihres Blickwinkels und der Blickrichtung enthält.
- Danach werden die neu berechneten Koordinaten mit einer weiteren Matrix multipliziert, der sogenannten „projection matrix“. Dieser Schritt erzeugt drei (für die Monitordarstellung benötigte) Angaben:
- Die horizontale Position des Objekts in Relation zu den Bildschirmgrenzen,
- die vertikale Position des Objekts in Relation zu den Bildschirmgrenzen und
- die Entfernung zwischen Kamera und Objekt entlang der Kamerablickrichtung.
// Alle Beispiele nutzen die Klassen der
// OpenTK-Bibliothek für C#:
using OpenTK.Mathematics;
// Dieser Vektor gibt an, welche der Achsen des
// Koordinatensystems für ‚oben‘ steht:
static Vector3 WorldUpDirection = new Vector3(0, 1, 0);
// Hier wird das Seitenverhältnis gespeichert:
static float MonitorAspectRatio = 16.0f / 9.0f;
static void Main(string[] args)
{
// Dieses Objekt soll in Monitorkoordinaten umgerechnet werden:
// (die vierte Komponente des Vektors muss für die Umrechnung
// immer den Wert 1 haben, aber die eigentlichen Koordinaten
// des Objekts sind (-4|+2|-5) ):
Vector4 objectPosition = new Vector4(-4, 2, -5, 1);
// Angaben zur Kameraposition und das anvisierte Kameraziel:
Vector3 cameraPosition = new Vector3(25, 25, 25);
Vector3 cameraTarget = new Vector3(0, 0, 0);
Matrix4 viewMatrix = Matrix4.LookAt(
cameraPosition, cameraTarget, WorldUpDirection);
Matrix4 projectionMatrix =
Matrix4.CreatePerspectiveFieldOfView(
MathHelper.DegreesToRadians(45), // Blickfeld in °
MonitorAspectRatio, // Seitenverhältnis
1, // Kameranahgrenze
100); // Kameraferngrenze
// Rechnet die Objektposition (‚world space‘) in
// Kamerakoordinaten um (‚view space‘):
Vector4 objectPosViewSpace = Transform(ref objectPosition, ref viewMatrix);
// Rechnet die Objektposition im ‚view space‘ in die
// Monitorkoordinaten (‚screen space‘) um:
Vector4 objectPosScreenSpace = Transform(ref objectPosViewSpace, ref projectionMatrix);
// Die Objektposition liegt nun als Bildschirmkoordinate vor.
// Jetzt wird sie noch in den sogenannten ‚clip space‘
// transformiert, indem die drei ersten Komponenten des Vektors
// durch die vierte Komponente geteilt werden:
Vector3 objectPosClipSpace = objectPosScreenSpace.Xyz / objectPosScreenSpace.W;
// Die x- und y-Komponenten des Vector3-Objekts sind nun
// normalisiert. Liegen ihre x- und y-Werte im Bereich [-1;+1],
// so sind sie auf dem Bildschirm zu sehen.
// Andernfalls müssen sie nicht gezeichnet werden, da sie eh
// nicht auf dem Monitor zu sehen sind.
// Die z-Komponente enthält die Entfernung des Objekts zur
// Kameraposition entlang der Kamerablickrichtung.
// Diese Koordinaten nennt man auch „normalized device
// coordinates (NDC)“.
}
// Diese Hilfsmethode bildet die Multiplikation eines Vektors
// mit einer Matrix ab:
private static Vector4 Transform(ref Vector4 i, ref Matrix4 m)
{
float x = i.X * m.M11 + i.Y * m.M21 + i.Z * m.M31 + i.W * m.M41;
float y = i.X * m.M12 + i.Y * m.M22 + i.Z * m.M32 + i.W * m.M42;
float z = i.X * m.M13 + i.Y * m.M23 + i.Z * m.M33 + i.W * m.M43;
float w = i.X * m.M14 + i.Y * m.M24 + i.Z * m.M34 + i.W * m.M44;
return new Vector4(x, y, z, w);
}
Umrechnen der Mauszeigerkoordinaten in 3D-Koordinaten
Jetzt verstehen wir, wie dreidimensionale Positionen in zweidimensionale Koordinaten auf unseren Bildschirmen umgerechnet werden. Und wenn die Konvertierung von 3D in 2D möglich ist, dann geht es auch in die andere Richtung.
Noch einmal zur Wiederholung:
- 3D-Objektkoordinaten sind drei Angaben: X, Y, und Z
- Nach der Umrechnung erhalten wir die Objektkoordinaten im „clip space“. Diese Koordinaten enthalten auch drei Informationen:
- Die x-/y-Koordinaten des Objekts auf dem Bildschirm und
- die Entfernung des Objekts entlang der Kamerablickrichtung als z-Komponente.
- Bei Mauszeigerkoordinaten fehlt uns jedoch genau diese z-Komponente. Wir haben lediglich die x-/y-Koordinaten in Pixeln – mehr nicht. Eine vollständige Rekonstruktion ist deshalb nicht möglich. Wir müssen vielleicht ein wenig tricksen…
Es folgen die Schritte zur Rekonstruktion der Mauszeigerposition in der 3D-Welt:
Schritt #1:
Normalisierung der Mauszeigerkoordinaten
Mauszeigerkoordinaten liegen als Pixelkoordinaten vor. Die obere linke Ecke des Bildschirms hat die Koordinaten (0|0), und die untere rechte Ecke hätte (bei einem FullHD-Bildschirm) die Koordinaten (1919|1079).
Da der durch die „projection matrix“ erzeugte „clip space“ aber mit normalisierten Koordinaten arbeitet, müssen wir die Pixelkoordinaten in den Bereich [-1;+1] umrechnen.
public static Vector2 GetNormalizedMouseCoords(
int mousex, int mousey,
int windowposx, int windowposy
int screenwidth, int screenheight)
{
float x = mousex - windowposx;
float y = mousey - windowposy;
x = (2.0f * x) / screenwidth - 1.0f;
y = 1.0f - (2.0f * y) / screenheight;
return new Vector2(x, y);
}
Schritt #2:
Berechnung der Strahlrichtung
Als nächster Schritt muss die Richtung des Strahls bestimmt werden. Hier werden die „view matrix“ und die „projection matrix“ aus dem Vorwissen-Abschnitt benötigt.
public static Vector3 GetMouseRayNormalized(
Vector2 normalizedMouseCoords,
Matrix4 viewMatrix,
Matrix4 projectionMatrix)
{
// Invertiere beide Matrizen:
// Wenn Punkte mit den invertierten Matrizen multipliziert
// werden, werden die durch die Matrizen zuvor erzeugten
// Transformationen rückgängig gemacht.
Matrix4 viewMatrixInv = Matrix4.Invert(viewMatrix);
Matrix4 projectionMatrixInv = Matrix4.Invert(projectionMatrix);
// Generiere einen temporären Punkt mit den Mauszeigerkoordinaten
// und multipliziere diesen Punkt mit der invertierten Projektions-
// matrix. Dieser Vorgang konvertiert den 2D-Punkt wieder in
// den "view space" der Kamera.
Vector4 ray_clip = new Vector4(
normalizedMouseCoords.X,
normalizedMouseCoords.Y,
-1,
1);
Vector4 ray_eye = Transform(ref ray_clip, ref projectionMatrixInv);
// Da wir einen Strahl brauchen, der von der Kamera aus in den
// Bildschirm verläuft, muss die z-Komponente negativ sein.
// Eine positive z-Komponente, würde einen Strahl in die
// entgegengesetzte Blickrichtung erzeugen.
ray_eye.Z = -1;
// Die w-Komponente kann 0 sein, weil wir lediglich die Richtung
// des Strahls benötigen. Wenn die w-Komponente 0 ist, wird der
// Translationspart der Matrix nicht berücksichtigt.
ray_eye.W = 0;
// Multipliziere die invertierte "view matrix" mit dem konstruierten
// Vektor um den Blickrichtungsvektor in 3D-Weltkoordinaten ("world
// space") zu erhalten:
Vector4 ray_world = viewMatrixInv * ray_eye;
// Da Richtungsvektoren immer Einheitsvektoren sind, normalisieren
// wir den Ergebnisvektor. Die w-Komponente spielt in 3D-Weltkoordinaten
// keine Rolle mehr.
Vector3 ray_world3 = Vector3.Normalize(ray_world.xyz);
return ray_world3;
}
Schritt #3:
Bestimmung des Schnittpunkts zwischen Strahl und einer Ebene
Zum Schluss benötigen wir eine Methode, die folgende Parameter übergeben bekommt und den Schnittpunkt zurückgibt:
- Die Strahlrichtung,
- den Ursprung des Strahls (z.B. die Kameraposition),
- den Zielpunkt (z.B. den Mittelpunkt des zu prüfenden Objekts) und
- den Ebenenvektor auf dem dieser Zielpunkt liegt.
public static bool LinePlaneIntersection(
Vector3 rayDirection,
Vector3 rayStart,
Vector3 surfaceNormal,
Vector3 pointOnSurface,
out Vector3 contactPoint)
{
contactPoint = Vector3.Zero;
// Wenn Strahl und Ebene parallel verlaufen,
// gibt es i.d.R. keinen Schnittpunkt:
if (Vector3.Dot(surfaceNormal, rayDirection) == 0)
return false;
// Bestimme den Schnittpunkt (contactPoint):
float d = Vector3.Dot(surfaceNormal, pointOnSurface);
float x = d - Vector3.Dot(surfaceNormal, rayStart) /
Vector3.Dot(surfaceNormal, rayDirection);
contactPoint = cameraPos + rayDirection * x;
return true;
}
Im Prinzip spannt diese Funktion in Höhe des Würfelmittelpunkts eine temporäre Ebene auf (in der Abbildung gelb markiert). Diese Ebene liegt parallel zur Kameraebene.
Der rot eingezeichnete Strahl bewegt sich nun in Blickrichtung auf die Ebene zu. Der Schnittpunkt des Strahls mit der (gelben) Ebene ist das Ergebnis der Methode.
Beispiel für die Verwendung:
int x = 400; // Beispiel für die Mausposition (x-Achse des Bildschirms)
int y = 600; // Beispiel für die Mausposition (y-Achse des Bildschirms)
int windowstartX = 0; // Position der linken Fensterkante auf dem Bildschirm
int windowstartY = 0; // Position der oberen Fensterkante auf dem Bildschirm
// Achtung:
// Weiterhin müssen "view matrix" und "projection matrix" und
// die Kameraposition vorliegen!
Vector2 normalizedMouseCoords = GetNormalizedMouseCoords(x, y, windowstartX, windowstartY, 1920, 1080);
Vector3 mouseRay = GetMouseRayNormalized(normalizedMouseCoords, currentViewMatrix, currentProjectionMatrix);
// Die Ebene kann eine beliebige Ebene sein. In diesem Beispiel ist die Ebene Parallel zur Bildschirmebene:
Vector3 normalForPlaneThatRayShouldCross = -mouseRay;
// Die Ebene wird um den Punkt (0|0|0) aufgespannt.
// Der Punkt ist frei wählbar und könnte z.B. der Mittelpunkt
// eines Objekts in der 3D-Welt sein:
Vector3 pointOnPlaneThatRayShouldCross = new Vector3(0, 0, 0);
bool result = LinePlaneIntersection(
mouseRay,
cameraPos,
normalForPlaneThatRayShouldCross,
pointOnPlaneThatRayShouldCross,
out Vector3 contact);
// Jetzt enthält 'contact' den Schnittpunkt.
Schreibe einen Kommentar