3D: Kameraposition bewegen, um Elemente ins Sichtfeld zu bekommen

[PatkIllA]

Folgende Situation:
Ich habe eine perspektivische Kamera, die von oben auf eine Szene blickt.

Jetzt möchte ich die Kameraposition so verschieben, dass eine Menge von Punkten (maximal 4) im Blickfeld der Kamera liegen.
Mir kommt gerade nur ein größeres Gleichungssystem in den Sinn.

[Neomi]

Die Anleitung basiert auf der Annahme, daß du ein Koordinatensystem verwendest, bei dem aus Sicht der Kamera die lokale X-Achse nach rechts zeigt, die Y-Achse nach oben und die Z-Achse in den Bildschirm hinein. Wenn du ein anderes System verwendest, mußt du eben entsprechend umstellen. Alle Berechnungen geschehen in Cameraspace...

Die linke und rechte Clippingplane des Viewfrustrums schneidest du mit der Ebene "y = 0", damit bekommst du zwei Schnittlinien, deren Richtungsvektor du benötigst. Für jeden der Punkte (natürlich immer noch in Cameraspace transformiert) nimmst du jetzt den Vektor der aus der linken Clippingplane stammt und erhälst damit eine Linie (wichtig ist nur die Ebene "y = 0", also quasi eine 2D-Linie), die du mit den Linien schneidest, die die anderen drei Punkte mit dem Vektor aus der rechten Clippingplane bilden. Bei 4 Punkten wären das 12 Schnittpunktberechnungen, die jeweils XZ-Koordinaten liefern. Davon benötigt werden die XZ-Koordinaten mit dem kleinsten Z-Wert, also der Kamera am weitesten nach hinten rausgeschoben.

Mit der oberen und unteren Clippingplane machst du nochmal genau das gleiche, nur eben in der Ebene "x = 0". Es gibt wieder maximal 12 Schnittpunktberechnungen und du merkst dir die YZ-Koordinaten mit dem kleinsten Z-Wert.

Jetzt hast du einmal XZ- und einmal YZ-Koordinaten. Von den ersten übernimmst du den X-Wert, von den zweiten den Y-Wert und als Z-Wert nimmst du den kleineren der beiden. Das Ergebnis ist ein 3D-Vektor in Cameraspace, mit dem du die Kamera an die "perfekte" Position verschieben kannst.

PS: ein großes Gleichungssystem ist dafür ungeeignet, weil du vorher nicht weißt, welche Punkte auf welchen Clippingplanes liegen. Du hättest damit nur Bedingungen mit >= und <=, aber eben keine Gleichungen.

Noch eine kleine Ergänzung: die Schnittpunkte alleine reichen unter bestimmten Umständen nicht aus. Hat einer der Punkt mit dem kleinsten Z-Wert einen kleineren Z-Wert als der jeweils ausgesuchte Schnittpunkt (das gilt für den horizontalen und den vertikalen Teilschritt jeweils einzeln), dann sind die XZ- bzw. YZ-Koordinaten des Punktes für diesen Teilschritt zu nehmen.

[Asmodeus]

Wäre nicht auch folgendes denkbar:

Man bildet den räumlichen Mittelpunkt der Punktmenge und legt eine "virtuelle" Kugel mit entsprechendem Radius um die Puntmenge, so dass alle Punkte innerhalb der Kugel liegen. Dann muss man nur noch mittels Phytagoras ausrechnen, wie weit der Kamerapunkt vom Mittelpunkt der Kugel entfernt sein muss, damit die durch den FOV-Winkel vorgegebenen Planes die Kugel tangentiell schneiden. Somit müßte man dann eine weitere virtuelle Kugel haben, auf deren Oberfläche die Kamera beliebig plaziert werden könnte (immer mit Blickrichtung Kugelmittelpunkt) und es wären immer alle Punkte sichtbar.

Gruß, Carsten.

[Neomi]

So ein Umkugelmodell hätte zwar Vor- und Nachteile, bei den Anforderungen würden aber die Vorteile komplett wegfallen und nur noch die Nachteile übrig bleiben. Da die Kamera von oben auf die Szene schauen soll und deshalb nicht gedreht, sondern nur verschoben werden soll, ist die freie Positionierbarkeit weg.

Als Nachteil bleibt, daß man mit der Kamera fast nie soweit rankommt, wie tatsächlich möglich wäre. Wenn aus Kamerasicht zwei Punkte horizontal weit voneinander entfernt sind, würde das zu einer Umkugel führen, die auch in den meist kleineren vertikalen Ausdehnungen (schon bei 4:3 gegeben, bei Breitbildformaten erst recht) noch Platz finden muß. Als Extrembeispiel gibt es noch das Zielen per Kimme und Korn, also zwei Punkte hintereinander. Je länger das Gewehr wird, desto größer wird die Umkugel und desto weiter muß das virtuelle Augo von der Kimme weg, wobei man dann kaum noch sauber zielen könnte.

[PatkIllA]

Ich möchte eigentlich nur ein Auswahldreieck mit der Maus ziehen und dann halt in den Bereich reinzoomen.
Ergeben sich dadurch noch Vereinfachungen?

[Neomi]

Ja, sogar erhebliche Vereinfachungen. Die Punkte werden dann wohl alle in einer Ebene liegen, also sich nicht relativ zueinander bewegen, wenn die Kamera bewegt wird. Bei dem Ansatz oben bin ich von dreidimensional platzierten Punkten und entsprechender Parallaxenverschiebung bei Kamerabewegung ausgegangen.

In dem Fall reicht es, um die Punkte im Cameraspace eine 2D-Boundingbox zu ermitteln. Die Kamera kannst du dann in dieser Ebene auf den Mittelpunkt der Boundingbox schieben. Da du die Ausdehnung der Boundingbox hast, kannst du den nötigen Abstand dazu per Strahlensatz ganz leicht ausrechnen, der Abstand ist proportional zur Ausdehnung. Wenn die horizontale Ausdehnung kleiner ist als die vertikale Ausdehnung multipliziert mit dem Seitenverhältnis (Breite/Höhe) der Kamera, dann nimmst du dafür die vertikale Ausdehnung, ansonsten die horizontale.

[PatkIllA]

In Weltkorrdinaten liegen die alle auf einer Ebene.
Die Kamerakoordinaten hab ich eh schon für das Auswahlrechteck.
x- und y-Koordinaten im Kameraspace für den Mittelpunkt ist auch kein Problem.
Höhe muss ich noch mal nachvollziehen.
Und den Punkt dann einfach mit der inversen Projektionsmatrix transformieren
Ergebnis durch W-komponente teilen und dann xyz-Koordinaten als Kameraposition übernehmen?

[Neomi]

Dann nochmal mit allen Details...

Gegeben:
- maximal vier Punkte p0, p1, p2, p3, es gilt "p0.y == p1.y == p2.y == p3.y"
- Cameraspace ist vx = (1, 0, 0), vy = (0, 0, 1), vz = (0, -1, 0), also Blick nach unten
- hFoV und vFoV sind der horizontale und vertikale Blickwinkel

Zu berechnen:
- x0 = min(p0.x, p1.x, p2.x, p3.x)
- x1 = max(p0.x, p1.x, p2.x, p3.x)
- z0 = min(p0.z, p1.z, p2.z, p3.z)
- z1 = max(p0.z, p1.z, p2.z, p3.z)
- dyh = (x1 - x0) / (2 * tan(hFoV / 2))
- dyv = (z1 - z0) / (2 * tan(vFoV / 2))
- pCam = (0.5 * (x0 + x1), p0.y + max(dyh, dyv), 0.5 * (z0 + z1))

Wenn der Cameraspace um die globale Y-Achse gedreht ist, muß diese Drehung natürlich noch kompensiert werden.

[PatkIllA]

Blick direkt nach unten ist nur in Ausnahmefällen gegeben.

[Neomi]

Nach dem Startposting dachte ich, du meinst "von oben" und nicht "meistens ungefähr von oben". Dann nochmal das ganze umgeformt auf den allgemeinen Fall...

Gegeben:
- ViewMat (4x4-Matrix, die von Worldspace in Cameraspace transformiert)
- p0w, p1w, p2w, p3w (3D-Positionen in Worldspace)

Zu berechnen (Teil 1):
- p0 = p0w * ViewMat
- p1 = p1w * ViewMat
- p2 = p2w * ViewMat
- p3 = p3w * ViewMat

Bedingung:
- p0.z == p1.z == p2.z == p3.z, quasi alle in einer Ebene

Zu berechnen (Teil 2):
- x0 = min(p0.x, p1.x, p2.x, p3.x)
- x1 = max(p0.x, p1.x, p2.x, p3.x)
- y0 = min(p0.y, p1.y, p2.y, p3.y)
- y1 = max(p0.y, p1.y, p2.y, p3.y)
- dzh = (x1 - x0) / (2 * tan(hFoV / 2))
- dzv = (y1 - y0) / (2 * tan(vFoV / 2))
- CamOffset = (0.5 * (x0 + x1), 0.5 * (y0 + y1), p0.z - max(dzh, dzv))
- ViewMatInv = ViewMat^-1
- WorldOffset = CamOffset * ViewMatInv

Damit hättest du dann den Offset, um den du die Kamera verschieben mußt. Allerdings nur unter der Annahme, daß alle Punkte in Cameraspace den gleichen Z-Wert haben. Ohne diese Bedingung kommt eine Parallaxenverschiebung dazu und es gilt der komplexere Ansatz mit den Schnittpunkten.

[PatkIllA]

passt irgendwie nicht.
Hier mal mein Code

internal void ShowArea(Vector3[] positions)
{
Vector4[] posCam = new Vector4[positions.Length];

float x0 = Single.MaxValue;
float x1 = Single.MinValue;

float y0 = Single.MaxValue;
float y1 = Single.MinValue;

float z0 = Single.MaxValue;
float z1 = Single.MinValue;


for (int i = 0; i < positions.Length; i++)
{
posCam[i] = Vector4.Transform(positions[i], m_oCombinedMatrix);
posCam[i] /= posCam[i].W;

x0 = Math.Min(x0, posCam[i].X);
x1 = Math.Max(x1, posCam[i].X);

y0 = Math.Min(y0, posCam[i].Y);
y1 = Math.Max(y1, posCam[i].Y);

z0 = Math.Min(z0, posCam[i].Z);
z1 = Math.Max(z1, posCam[i].Z);
}

float vFov = m_fFieldOfView / m_fAspectRatio;
float dzh = (float)((x0 - x1) / (2 * Math.Tan(m_fFieldOfView / 2)));
float dzv = (float)((y0 - y1) / (2 * Math.Tan(vFov / 2)));


Vector3 camOffset = new Vector3(0.5f * (x0 + x1), 0.5f * (y0 + y1), z0 - Math.Max(dzh, dzv));

Matrix viewMatInv = Matrix.Invert(m_oCombinedMatrix);

Vector4 worldOffset = Vector4.Transform(camOffset, viewMatInv);
worldOffset /= worldOffset.W;

m_oPosition.X += worldOffset.X;
m_oPosition.Y += worldOffset.Y;
m_oPosition.Z -= worldOffset.Z;

OnChange();
}

[Neomi]

Bei der Berechnung des Cameraspace-Offsets wird max(dzh, dzv) doch schon abgezogen, nicht addiert. Deshalb (und weil es andersrum trotzdem falsch wäre) muß der Worldspace-Offset komplett auf die Kameraposition addiert werden, auch die Z-Komponente.

Wenn das nicht reicht und du eh schon überall die W-Komponente mit ranziehst, solltest du auch dem Cameraspace-Offset ein W von 1 mitgeben, anderenfalls wird evtl. die Translation nicht ausgeführt.

Wenn auch das nicht ausreicht, dann wäre interessant, was alles in der "Combined" Matrix kombiniert wurde, denn es sollte in diesem Fall nur die Viewmatrix herangezogen werden. Kein Worldmatrix (wobei die ja im Fall einer Kamera keinen Sinn hat und Identity sein sollte) und keine Projectionmatrix.

Wenn es auch dann noch nicht funktionieren sollte, mußt du wohl im Debugger durchsteppen und schauen, was genau schiefläuft. Und welche API nutzt du überhaupt, Direct3D oder OpenGL? Das ist wegen unterschiedlicher Koordinatensysteme durchaus relevant.

[PatkIllA]

Worldmatrix ist die Identität.
Das ist XNA. Das benutzt ein rechthändiges Koordinatensystem.

Vielleicht schaue ich mir doch mal gleich die komlexere Lösung mit den Schnittpunkten an.

[Neomi]

Worldmatrix ist die Identität.

Und was ist mit der Projektionsmatrix, die normalerweise in einer kombinierten Matrix enthalten ist? Die hat in dieser Berechnung auch nichts zu suchen.

Das ist XNA. Das benutzt ein rechthändiges Koordinatensystem.

In dem Fall wundert mich, daß du nichts auf ein rechtshändiges System umgestellt hast, die angegebenen Schritte gelten in unveränderter Form nur für ein linkshändiges System.

Vielleicht schaue ich mir doch mal gleich die komlexere Lösung mit den Schnittpunkten an.

Die komplexere Lösung ist dann sinnvoll, wenn die einfache nicht mehr ausreicht, quasi dann wenn eine zu starke Parallaxenverschiebung das Ergebnis ruiniert. Wenn aber die einfache Lösung schon an der Umsetzung scheitert, wirst du mit der komplexeren nicht mehr Glück haben.