Frustum « 3DCoding.de

Die Form eines Frustums mit wichtigen Kennzahlen

Das Wort Frustum bedeutet wörtlich aus dem englischen übersetzt “Kegelstumpf” und bezeichnet somit einen der Spitze beraubten Kegel. In der 3D-Grafik versteht man unter einem Frustum den sichtbaren Bereich einer 3-dimensionalen Szene. Die Form entsteht durch die Fluchtpunktprojektion. Dadurch, dass der Frustum mit größerer Entfernung breiter wird, werden die Objekte dadurch mit größerer Entfernung kleiner.

Die Form des Pyramidenstumpfes ergibt sich aus drei Tatsachen:

Der Bildschirm ist rechteckig. Daher handelt es sich um eine Pyramide. Wäre der Bildschirm rund hätten wir es mit einem Kegel zu tun.
Es gibt eine größte Z-Koordinate die noch sichtbar ist. Dies ist die Seite der Pyramide wo die Spitze sitzen würde.
Es gibt eine kleinste Z-Koordinate die noch sichtbar ist. Dies ist der Fuss der Pyramide.

Die Seitenansicht des Frustums

Der Beobachter blickt immer in Richtung des größer werdenden Pyramidenquerschnitts, also von der Spitze aus in Richtung des Fußes. Der Abstand in Blickrichtung von der Kamera zum Beginn des sichtbaren Bereichs wird wird $z_{near}$ genannt. Der Abstand von der Kamera zum Ende des sichtbaren Bereiches $z_{far}$ . Das Verhältnis von Breite zu Höhe wird “aspect” oder auch “Seitenverhältnis” genannt und beträgt bei einem Standard-Bildschirm 4:3. Der sichtbare Bereich kann über den Sichtwinkel verändert werden – während 45 bis 60 Grad in etwa den normalen Bereich darstellen, bilden Winkel über 60 Grad den Effekt eines Weitwinkelobjektivs nach.

Die Koordinaten einer 3D-Szene durchlaufen bei der OpenGL Bibliothek zwei Matrizen: Die Modelview- und die Projektionsmatrix. Während die Modelview-matrix dafür gedacht ist die Szene wie gewünscht zu positionieren führt die Projektionsmatrix die Perspektivprojektion durch. Technisch betrachtet verhalten sich die beiden Matrizen nicht unterschiedlich – ihnen wurden lediglich andere Aufgaben zugewiesen.

OpenGL bietet eine Methode an um die Projektionsmatrix zu erstellen: glFrustum(…) Die Methode benötigt als Parameter folgende Angaben: $left_{near}$ , $right_{near}$ , $top_{near}$ , $bottom_{near}$ , near, far. Diese Werte definieren einen Frustum zwar eindeutig, sind aber nicht intuitiv klar und daher nicht direkt eingebbar. Um eine bestimmte Projektion festzulegen ist noch etwas Rechenarbeit nötig.

Die Form eines Frustums mit wichtigen Kennzahlen

Berechnung der Frustumparameter für OpenGL

Der Aufruf zum Aktivieren eines Frustums in OpenGL lautet wie folgt:

void glFrustum( GLdouble left,
GLdouble right,
GLdouble bottom,
GLdouble top,
GLdouble nearVal,
GLdouble farVal);

Wir benötigen die left, right, top und bottom-Werte nur für die near-Plane da die entsprechenden Werte für die far-Plane durch die Werte $z_{near}$ und $z_{far}$ direkt daraus folgen. Die Werte für left und right erhalten wir über den Tangens des Sichtwinkels welcher die halbe Breite des Frustums auf der near-Plane liefert:

$\tan \frac{\alpha}{2} = \frac{right}{near}$

durch Umformen erhalten wir

$right = near \tan \frac{\alpha}{2}$

und da der Frustum symmetrisch aufgebaut ist gilt auch

$left = -right$

Der Frustum als Ansicht von oben

Um die Werte für top und bottom zu bekommen verwenden wir das Seitenverhältnis und machen uns wieder die Tatsache zunutze, dass der Frustum symmetrisch aufgebaut ist:

$aspect = \frac{width}{height}$

damit erhalten wir

$top = \frac{right}{aspect}$

und ausserdem gilt durch die Symmetrie:

$bottom = -top$

Nun haben wir schon alle Angaben für den Aufruf des glFrustum()-Kommandos zusammen.

Doch dadurch wird nun lediglich die Fluchtpunktprojektion definiert. Es fehlt noch die Matrix die eine freie Kameraposition möglich macht. Diese wird dafür sorgen dass eine 3D-Szene von jedem beliebigen Ort aus betrachtet werden kann. Das werde ich nun als nächstes beschreiben.

Eine freie Kameraposition realisieren

Die nun zu berechnende matrix soll dafür sorgen, dass alle Elemente die OpenGL zeichnet aus einer frei definierten Kameraperspektive zu sehen sind. Wenn OpenGL ohne eine Modelview-Matrix eine Szene zeichnet, so wird nur der Bereich mit dem Beobachter an der Position (0,0,0) und mit Blick in Richtung der negativen Z-Achse gezeichnet. Es muss nun also eine Matrix erstellt werden die die Szene in diesen Bereich transformiert so dass es so aussieht als wäre die Kamera verschoben worden.

Wie im Matrix-Artikel beschrieben stellen Matrizen Koordinatensysteme dar und man kann diese anhand der Spalten der Matrix direkt ablesen: Die Spalten enthalten die X-Achse, die Y-Achse und die Z-Achse sowie den Koordinatenursprung des durch die Matrix festgelegten Koordinatensystems. Daraus folgt, dass wir direkt die Matrix angeben können wenn wir das Koordinatensystem der Kamera kennen:

Berechnung des Kamerasystems

Die Berechnung basiert auf den folgenden, gegebenen Werten:

$\vec P_{camera}$	Position der Kamera / des Beobachters
$\vec P_{lookat}$	Punkt auf den der Frustum ausgerichtet wird: Der Punkt den der Beobachter ansehen soll

Der Vektor in Blickrichtung des Frustums muss auf die Länge 1 normiert werden damit die Mittelpunkte der near und far-Plane berechnet werden können.

$\vec{dir}=(\vec P_{lookat} - \vec P_{camera}) / |\vec P_{lookat} - \vec P_{camera}|$

Wir errechnen den Mittelpunkt der near-Plane:

$\vec P_{nearPlaneCenter} = \vec P_{camera} + near \times \vec {dir}$

und den Mittelpunkt der far-plane:

$\vec P_{farPlaneCenter} = \vec P_{camera} + far \times \vec {dir}$

Nun werden die Achsen des Kamerasystems bestimmt. Da OpenGL ein rechtshändiges System verwendet, muss die positive Z-Achse aus dem Bildschirm heraus zeigen – also entgegengesetzt der Blickrichtung, oder einfach:

$\vec z_{axis} = - \vec {dir}$

Die X-Achse ermitteln wir über das Kreuzprodukt mit dem Vektor $\bigl( \begin{smallmatrix} 0 \\ 1 \\ 0 \end{smallmatrix} \bigr)$ :

$\vec x_{axis} = \vec {dir} \times \bigl( \begin{smallmatrix} 0 \\ 1 \\ 0 \end{smallmatrix} \bigr)$

Durch die Verwendung des Vektors $\bigl( \begin{smallmatrix} 0 \\ 1 \\ 0 \end{smallmatrix} \bigr)$ garantieren wir, dass die Kamera immer “aufrecht” steht. Dies führt jedoch zu der Beschränkung, dass eine Kamera niemals genau senkrecht nach unten sehen darf. Das Kreuzprodukt würde dann den Nullvektor ergeben. Diese Beschränkung ist aber in der Regel akzeptabel.

Die Y-Achse errechnen wir ebenfalls mit dem Kreuzprodukt:

$\vec y_{axis} = \vec x_{axis} \times \vec{dir}$

Nun sorgen wir dafür, dass die Achsen alle die Länge 1 haben:

$\vec x_{axis} = \vec x_{axis} \frac{1}{|\vec x_{axis}|}$
$\vec y_{axis} = \vec y_{axis} \frac{1}{|\vec y_{axis}|}$
$\vec z_{axis} = \vec z_{axis} \frac{1}{|\vec z_{axis}|}$

Damit haben wir das Koordinatensystem komplett. Der Ursprung des Systems entspricht der Kameraposition. Die Matrix lautet damit wie folgt:

$\left( \begin{array}{cccc} xaxis_x & yaxis_x & zaxis_x & \vec P_{camera_x} \\ xaxis_y & yaxis_y & zaxis_y & \vec P_{camera_y} \\ xaxis_z & yaxis_z & zaxis_z & \vec P_{camera_z} \\ 0 & 0 & 0 & 1 \end{array} \right)$

Diese Matrix konvertiert nun Punkte die sich im Ursprungssystem befinden in das Kamerasystem – dies ist aber nicht was wir hier benötigen: OpenGL zeichnet ja nur das Ursprungssystem welches die Beobachterposition $\bigl( \begin{smallmatrix} 0 \\ 0 \\ 0 \end{smallmatrix} \bigr)$ besitzt und in Richtung der negativen Z-Achse blickt. Daher brauchen wir nicht die Matrix die die zu zeichnende Szene aus dem Ursprungssystem in das Kamerasystem transportiert, sondern deren Inverse: Da die Szene aus der Sicht der Kamera gezeichnet werden soll müssen wir dafür sorgen, dass das Kamerasystem mit dem Ursprungssystem zusammenfällt.

Mit der invertierten Matrix können wir nun OpenGL so einstellen, dass wir unsere Szenen aus beliebigen Positionen betrachten und in beliebige Richtungen blicken können (ausser natürlich: senkrecht nach unten und oben funktioniert wie oben erwähnt nicht).

 /**
 * Updates the values for the frustum.
 *
 * This gets called before each get...-Method to make sure the only updated values
 * are returned and to eliminate updating the frustum data when they are not needed.
 */
 protected void update() {
 if ( !changed ) return;

// The centers of the near and far-Ebenen
 final vector deltaFront = vector.mul(direction, near);
 final Vector deltaBack = Vector.mul(direction, far);
 centerFront = Vector.add(position, deltaFront);
 final Vector centerBack = Vector.add(position, deltaBack);

// The width and height of the frustum on the near and far plane
 final double fovHalf = (fov * Math.PI / 360.0) / 2.0;
 nearWidth = 2.0 * near * Math.tan(fovHalf);
 final double farWidth = 2.0 * far * Math.tan(fovHalf);
 final double nearHeight = nearWidth / aspect;
 final double farHeight = farWidth / aspect;

// the coordinate system of the frustum
 camZ = Vector.mul(direction, -1);
 camX = Vector.cross(new Vector(0,1,0), camZ);
 try {
 camX.normalize();
 } catch (final VectorException e) {
 // Can only occurr when the frustum is exactly facing up- or downward
 e.printStackTrace();
 }

camY = Vector.cross(camZ, camX);
 try {
 camY.normalize();
 } catch (final VectorException e) {
 // Can only occurr when the frustum is exactly facing up- or downward
 e.printStackTrace();
 }

calculateEdges(centerBack, farWidth, nearHeight, farHeight);
 calculatePlanes();

matrix = new Matrix();

// I need a matrix that projects the coordinates of the scene elements in a way
 // that makes the scene looks like being viewed from the defined frustum. To get this
 // I need a matrix that projects the frustum back to the OpenGL default-frustum. To
 // achieve this, I first create a matrix that project the OpenGL default-frustum to the
 // new frustum. This is done by placing the coordinate-System into the matrix' columns:
 matrix.replaceCol(0, camX);
 matrix.replaceCol(1, camY);
 matrix.replaceCol(2, camZ);
 matrix.replaceCol(3, position);
 matrix.replaceRow(3, new Vector(0,0,0,1));

// but since we need the reverse projection we have to invert the matrix
 matrix.invert();

changed = false;
 }

/**
 * Installs a Frustum to a given GL context.
 *
 * @param gl the OpenGL context to use
 * @param frustum the frustum object to install
 */
 public static void installFrustum(GL gl, Frustum frustum) {

gl.glMatrixMode(GL.GL_PROJECTION);
 gl.glLoadIdentity();

double extend = frustum.getNearWidth();
 double aspect = frustum.getAspect();
 double right = extend / 2.0;

// Scale the top value by the aspect
 double top = extend / 2.0 / aspect;

// Create the Frustum projection
 gl.glFrustum(-right, right, -top, top, frustum.getNear(), frustum.getFar());

// Setup the Modelview matrix to let the scene be viewed from the cameras point of view
 gl.glMatrixMode(GL.GL_MODELVIEW);
 gl.glLoadIdentity();
 glMultMatrix(gl, frustum.getMatrix());
 }

An dieser Stelle haben wir unser wichtigstes Ziel erreicht: Eine beliebig positionierbare Kamera. In späteren Kapiteln werden jedoch noch mehr Informationen des Frustums benötigt um z.B. das Frustum Culling zu realisieren. Daher errechnen wir jetzt noch weitere nützliche Details.

Eckpunkte des Frustums

Um den Frustum als Drahtgittermodell zeichnen zu können oder ihm eine Kugel umschreiben zu können benötigen wir alle 8 Eckpunkte. Die vier Punkte auf der near-plane bekommen wir durch Linearkombinationen des near Plane center Punktes mit der X-Achse und Y-Achse des Kamerasystems. Für die Punkte auf der far-Ebene skalieren wir die Achsen noch mit dem Verhältnis far/near da der Frustum hinten um diesen Faktor breiter ist als vorne.

$\vec P_{top left near} = \vec P_{near center} + left \vec x_{axis} + top \vec y_{axis}$
$\vec P_{top right near} = \vec P_{near center} + right \vec x_{axis} + top \vec y_{axis}$
$\vec P_{bottom left near} = \vec P_{near center} + left \vec x_{axis} + bottom \vec y_{axis}$
$\vec P_{bottom right near} = \vec P_{near center} + right \vec x_{axis} + bottom \vec y_{axis}$
$\vec P_{top left far} = \vec P_{near far} + \frac{far}{near}left \vec x_{axis} + \frac{far}{near}top \vec y_{axis}$
$\vec P_{top right far} = \vec P_{near far} + \frac{far}{near}right \vec x_{axis} + \frac{far}{near}top \vec y_{axis}$
$\vec P_{bottom left far} = \vec P_{near far} + \frac{far}{near}left \vec x_{axis} + \frac{far}{near}bottom \vec y_{axis}$
$\vec P_{bottom right far} = \vec P_{near far} + \frac{far}{near}right \vec x_{axis} + \frac{far}{near}bottom \vec y_{axis}$

Das Frustum-Volumen

Das Frustum-Volumen wird exakt durch sechs Ebenen definiert: Vorne, hinten, oben, unten, links, rechts.

Die Ebenen die den Frustum begrenzen

Diese sechs Ebenen ermitteln wir über jeweils einen Punkt der Ebene (ein Eckpunkt des Frustums) sowie dessen Normalen. Die Normale wird durch das Kreuzprodukt zweier Kanten ermittelt. Sehr wichtig ist, dass alle Normalen gleichermassen ausgerichtet sind: Entweder zeigen sie alle nach aussen oder nach innen. Dies ist wichtig wenn später Punkte auf ihre Lage bezüglich des Frustums getestet werden sollen.

In den folgenden Formeln verwende ich für die Indizes Abkürzungen: Zum Beispiel: ltn = left top near und
rbf = right bottom far

$e_{left}: (\vec x - \vec P_{lbn}) \Big( (\vec P_{ltn} - \vec P_{lbn}) \times (\vec P_{ltf} - \vec P_{ltn}) \Big) = 0$
$e_{right}: (\vec x - \vec P_{rbn}) \Big( (\vec P_{rtf} - \vec P_{rtn}) \times (\vec P_{rtn} - \vec P_{rbn}) \Big) = 0$

$e_{top}: (\vec x - \vec P_{ltn}) \Big( (\vec P_{rtn} - \vec P_{ltn}) \times (\vec P_{ltf} - \vec P_{ltn}) \Big) = 0$
$e_{bottom}: (\vec x - \vec P_{lbn}) \Big( (\vec P_{lbn} - \vec P_{rbn}) \times (\vec P_{rbf} - \vec P_{rbn}) \Big) = 0$

$e_{near}: (\vec x - \vec P_{near center}) (-\vec {dir}) = 0$
$e_{far}: (\vec x - \vec P_{far center}) (\vec {dir}) = 0$

Die Ebenengleichungen sind so aufgestellt, dass die Normalen nach aussen zeigen. Sobald ein zu testender Punkt nun auf der Vorderseite einer Ebene liegt ist sicher, dass er nicht im Frustum liegen kann; liegt er aber hinter allen Ebenen so befindet er sich innerhalb des Frustums.

Der Code für die Berechung der Eckpunkte und der Ebenen sieht wie folgt aus:

 /**
 * Calcucates the frustum planes from the edge coordinates.
 */
 private void calculatePlanes() {
 final Vector a = Vector.sub(edges[4], edges[0]);
 final Vector b = Vector.sub(edges[5], edges[4]);
 final Vector c = Vector.sub(edges[7], edges[5]);
 final Vector mc = Vector.sub(edges[5], edges[7]);
 final Vector d = Vector.sub(edges[7], edges[3]);

final Vector n_left = Vector.cross(a,c);
 final Vector n_right = Vector.cross(d,mc);
 final Vector n_top = Vector.cross(b,a);
 final Vector n_bottom = Vector.cross(d,b);
 final Vector n_near = Vector.cross(b,mc);
 final Vector n_far = Vector.cross(b,c);

try {
 n_left.normalize();
 n_right.normalize();
 n_top.normalize();
 n_bottom.normalize();
 n_near.normalize();
 n_far.normalize();
 } catch (final VectorException e) {
 // should never happen
 e.printStackTrace();
 }

planes[FrustumPlane.PLANE_LEFT.getIndex()] = new Plane(edges[0], n_left);
 planes[FrustumPlane.PLANE_RIGHT.getIndex()] = new Plane(edges[1], n_right);
 planes[FrustumPlane.PLANE_TOP.getIndex()] = new Plane(edges[0], n_top);
 planes[FrustumPlane.PLANE_BOTTOM.getIndex()] = new Plane(edges[2], n_bottom);
 planes[FrustumPlane.PLANE_NEAR.getIndex()] = new Plane(edges[0], n_near);
 planes[FrustumPlane.PLANE_FAR.getIndex()] = new Plane(edges[4], n_far);
 }

/**
 * Calculates the edge coordinates.
 *
 * @param centerBack the center of the back side of the frustum
 * @param farWidth the width of the far side
 * @param nearHeight the height of the near side
 * @param farHeight the height of the far side
 */
 private void calculateEdges(final Vector centerBack, final double farWidth,
 final double nearHeight, final double farHeight) {
 final Vector deltaXFront = Vector.mul(camX, nearWidth / 2.0);
 final Vector deltaYFront = Vector.mul(camY, nearHeight / 2.0);
 final Vector deltaXBack = Vector.mul(camX, farWidth / 2.0);
 final Vector deltaYBack = Vector.mul(camY, farHeight / 2.0);

// Determine the edges by linear combination of the cameras' axis
 edges[FrustumEdge.EDGE_TOP_LEFT_FRONT.getIndex()] = Vector.add(Vector.sub(centerFront, deltaXFront), deltaYFront);
 edges[FrustumEdge.EDGE_TOP_RIGHT_FRONT.getIndex()] = Vector.add(Vector.add(centerFront, deltaXFront), deltaYFront);
 edges[FrustumEdge.EDGE_BOTTOM_LEFT_FRONT.getIndex()] = Vector.sub(Vector.sub(centerFront, deltaXFront), deltaYFront);
 edges[FrustumEdge.EDGE_BOTTOM_RIGHT_FRONT.getIndex()] = Vector.sub(Vector.add(centerFront, deltaXFront), deltaYFront);
 edges[FrustumEdge.EDGE_TOP_LEFT_BACK.getIndex()] = Vector.add(Vector.sub(centerBack, deltaXBack), deltaYBack);
 edges[FrustumEdge.EDGE_TOP_RIGHT_BACK.getIndex()] = Vector.add(Vector.add(centerBack, deltaXBack), deltaYBack);
 edges[FrustumEdge.EDGE_BOTTOM_LEFT_BACK.getIndex()] = Vector.sub(Vector.sub(centerBack, deltaXBack), deltaYBack);
 edges[FrustumEdge.EDGE_BOTTOM_RIGHT_BACK.getIndex()] = Vector.sub(Vector.add(centerBack, deltaXBack), deltaYBack);
 }

3DCoding.de

3D-Grafik, Spiele und sonstiger Kram der mich interessiert… ;-)

Frustum

Berechnung der Frustumparameter für OpenGL

Eine freie Kameraposition realisieren

Berechnung des Kamerasystems

Eckpunkte des Frustums

Das Frustum-Volumen

Leave a Reply Cancel reply