Version vom 25. November 2008, 22:09 Uhr

Frustum Culling

Einleitung

Wenn man dabei ist eine 3D-Engine auf eigene Faust zu programmieren, wird man irgendwann damit konfrontiert das mit steigender Szenenkomplexität alles langsamer wird, und dies obwohl immer nur ein Teil der Umgebung sichtbar ist.

Moderne Grafikkarten besitzen einen Z-Puffer und andere Techniken um festzustellen, ob ein Pixel gesetzt wird oder nicht, aber bevor sie dies feststellen können, brauchen sie die Geometriedaten der Szene.Dann erst macht die Grafikkarte ihre Sichtbarkeitsoptimierungen und Tiefentests. Wenn ein Objekt hinter einem anderen liegt, oder ausserhalb des Sichtbereiches ist, wird die Grafikkarte so schlau sein und dies merken.Aber selbst wenn das Objekt dann nicht gezeichnet wird, drückt es die Geschwindigkeit, da dessen Geometriedaten erstmal über den Bus zur Grafikkarte gelangen müssen.

Frustum Culling ist nun eine einfache Methode um VOR dem Senden der Geometriedaten festzustellen, ob ein Objekt im Sichtfeld liegt oder nicht.Dies spart jede Menge Bandbreite und bedeutet Arbeitsersparnis für den 3D-Beschleuniger.

In diesem Tutorial werde ich deshalb zeigen wie man Frustum Culling implementiert und nutz.Es ist wirklich wenig Arbeit, aber eine sehr effiziente Art seine Rendergeschwindigkeit drastisch zu erhöhen.

Die TFrustum Klasse

Wir werden das Frustum Culling mit Hilfe einer handlichen, TFrustum genannten Klasse implementieren um die Dinge etwas einfacher zu machen.Hier die Klassendeklaration :

TFrustum = object
   Frustum : array[0..5,0..3] of Single;
   function IsPointWithin(const pX, pY, pZ : Single) : Boolean;
   function IsBoxWithin(const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
   procedure Calculate;
  end;

Etwas Vorarbeit

Als Erstes brauchen wir für unsere Klasse einige Konstanten, die uns das Leben deutlich einfacher machen. Im Grunde selbsterklärend:

const
  Right  = 0;
  Left   = 1;
  Bottom = 2;
  Top    = 3;
  Back   = 4;
  Front  = 5;
  A      = 0;
  B      = 1;
  C      = 2;
  D      = 3;

Jetzt kommt Mathematik ins Spiel. Wir müssen noch eine Funktion definieren, in der wir die berechneten Planes des Frustums normalisieren:

procedure NormalizePlane(var pFrustum: TFrustum; pPlane: Integer);
var
  Magnitude: Single;
begin
  Magnitude := Sqrt(Sqr(pFrustum.Frustum[pPlane][A]) + Sqr(pFrustum.Frustum[pPlane][B]) + Sqr(pFrustum.Frustum[pPlane][C]));
  pFrustum.Frustum[pPlane][A] := pFrustum.Frustum[pPlane][A] / Magnitude;
  pFrustum.Frustum[pPlane][B] := pFrustum.Frustum[pPlane][B] / Magnitude;
  pFrustum.Frustum[pPlane][C] := pFrustum.Frustum[pPlane][C] / Magnitude;
  pFrustum.Frustum[pPlane][D] := pFrustum.Frustum[pPlane][D] / Magnitude;
end;

Das Frustum berechnen(procedure Calculate)

Zu aller Erst der wichtigste Teil der TFrustum Klasse : Die Berechnung des Selbigen.Bevor wir also feststellen könne, ob ein Objekt im Frustum liegt oder nicht, müssen wir zuerst dessen 6 Flächen berechnen.

procedure TFrustum.Calculate;
var
  ProjM, ModM, Clip : array[0..15] of Single;
begin
  glGetFloatv(GL_PROJECTION_MATRIX, @ProjM);
  glGetFloatv(GL_MODELVIEW_MATRIX, @ModM);
  Clip[ 0] := ModM[ 0]*ProjM[ 0] + ModM[ 1]*ProjM[ 4] +
              ModM[ 2]*ProjM[ 8] + ModM[ 3]*ProjM[12];
  Clip[ 1] := ModM[ 0]*ProjM[ 1] + ModM[ 1]*ProjM[ 5] +
              ModM[ 2]*ProjM[ 9] + ModM[ 3]*ProjM[13];
  Clip[ 2] := ModM[ 0]*ProjM[ 2] + ModM[ 1]*ProjM[ 6] +
              ModM[ 2]*ProjM[10] + ModM[ 3]*ProjM[14];
  Clip[ 3] := ModM[ 0]*ProjM[ 3] + ModM[ 1]*ProjM[ 7] +
              ModM[ 2]*ProjM[11] + ModM[ 3]*ProjM[15];
  Clip[ 4] := ModM[ 4]*ProjM[ 0] + ModM[ 5]*ProjM[ 4] +
              ModM[ 6]*ProjM[ 8] + ModM[ 7]*ProjM[12];
  Clip[ 5] := ModM[ 4]*ProjM[ 1] + ModM[ 5]*ProjM[ 5] +
              ModM[ 6]*ProjM[ 9] + ModM[ 7]*ProjM[13];
  Clip[ 6] := ModM[ 4]*ProjM[ 2] + ModM[ 5]*ProjM[ 6] +
              ModM[ 6]*ProjM[10] + ModM[ 7]*ProjM[14];
  Clip[ 7] := ModM[ 4]*ProjM[ 3] + ModM[ 5]*ProjM[ 7] +
              ModM[ 6]*ProjM[11] + ModM[ 7]*ProjM[15];
  Clip[ 8] := ModM[ 8]*ProjM[ 0] + ModM[ 9]*ProjM[ 4] +
              ModM[10]*ProjM[ 8] + ModM[11]*ProjM[12];
  Clip[ 9] := ModM[ 8]*ProjM[ 1] + ModM[ 9]*ProjM[ 5] +
              ModM[10]*ProjM[ 9] + ModM[11]*ProjM[13];
  Clip[10] := ModM[ 8]*ProjM[ 2] + ModM[ 9]*ProjM[ 6] +
              ModM[10]*ProjM[10] + ModM[11]*ProjM[14];
  Clip[11] := ModM[ 8]*ProjM[ 3] + ModM[ 9]*ProjM[ 7] +
              ModM[10]*ProjM[11] + ModM[11]*ProjM[15];
  Clip[12] := ModM[12]*ProjM[ 0] + ModM[13]*ProjM[ 4] +
              ModM[14]*ProjM[ 8] + ModM[15]*ProjM[12];
  Clip[13] := ModM[12]*ProjM[ 1] + ModM[13]*ProjM[ 5] +
              ModM[14]*ProjM[ 9] + ModM[15]*ProjM[13];
  Clip[14] := ModM[12]*ProjM[ 2] + ModM[13]*ProjM[ 6] +
              ModM[14]*ProjM[10] + ModM[15]*ProjM[14];
  Clip[15] := ModM[12]*ProjM[ 3] + ModM[13]*ProjM[ 7] +
              ModM[14]*ProjM[11] + ModM[15]*ProjM[15];
{...}

In Zeile [05] extrahieren wir die momentane Projektionsmatrix und speichern sie in einem 16 Single-Werte enthaltendem Array, selbiges tun wir dann in Zeile [06] mit der aktuellen Modelbetrachtungsmatrix. Diese beiden Matrizen werden dann in den Zeilen [07] bis [22] kombininert und werden als unsere Clippinmatrix gespeichert.

Die folgenden Zeilen berechnen nun endlich die sechs Flächen unserer Frustumbox.Die Namen der Flächen wurden vorher in der globalen Konstantensektion dieser Unit deklariert.

  Frustum[Right][A] := clip[ 3] - clip[ 0];
  Frustum[Right][B] := clip[ 7] - clip[ 4];
  Frustum[Right][C] := clip[11] - clip[ 8];
  Frustum[Right][D] := clip[15] - clip[12];
  NormalizePlane(self, Right);

  Frustum[Left][A] := clip[ 3] + clip[ 0];
  Frustum[Left][B] := clip[ 7] + clip[ 4];
  Frustum[Left][C] := clip[11] + clip[ 8];
  Frustum[Left][D] := clip[15] + clip[12];
  NormalizePlane(self, Left);

  Frustum[Bottom][A] := clip[ 3] + clip[ 1];
  Frustum[Bottom][B] := clip[ 7] + clip[ 5];
  Frustum[Bottom][C] := clip[11] + clip[ 9];
  Frustum[Bottom][D] := clip[15] + clip[13];
  NormalizePlane(self, Bottom);

  Frustum[Top][A] := clip[ 3] - clip[ 1];
  Frustum[Top][B] := clip[ 7] - clip[ 5];
  Frustum[Top][C] := clip[11] - clip[ 9];
  Frustum[Top][D] := clip[15] - clip[13];
  NormalizePlane(self, Top);

  Frustum[Back][A] := clip[ 3] - clip[ 2];
  Frustum[Back][B] := clip[ 7] - clip[ 6];
  Frustum[Back][C] := clip[11] - clip[10];
  Frustum[Back][D] := clip[15] - clip[14];
  NormalizePlane(self, Back);

  Frustum[Front][A] := clip[ 3] + clip[ 2];
  Frustum[Front][B] := clip[ 7] + clip[ 6];
  Frustum[Front][C] := clip[11] + clip[10];
  Frustum[Front][D] := clip[15] + clip[14];
  NormalizePlane(self, Front);
end;

Diese Berechnungen speichern ihr Ergebnis im Frustum-Array unserer TFrustum Klasse.Die Berechnung des Frustums muss nach jeder Blickwinkeländerung erfolgen.Wenn man zu faul ist, dies zu erfassen, kann man das Frustum auch einfach in jedem Frame nach dem setzen des Blickwinkels berechnen.

Punkt im Frustum?

Der einfachste Sichtbarkeitstest ist, festzustellen ob ein einzelner Punkt im Frustum liegt.Dies ist der Fall, wenn die Entfernung des Punktes zu allen sechs Flächen des Frustums positiv ist.(D.h. das der Punkt vor allen Flächen liegt.Ist die Entfernung negativ, so liegt er dahinter)

Um dies zu berechnen, nutzen wir folgende einfache Formel :

 Distance := (A*x) + (B*y) + (C*z) + D 

Die Funktion TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean durchläuft nun ganz einfache in einer Schleife alle sechs Flächen und berechnet die Entfernung des Punktes zu dieser Fläche.Wenn die Distanz negativ ist (der Punkt also dahinter liegt), liefert die Funktion False.

function TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean;
  var
   i : Integer;
begin
  Result := true;
  for i := 0 to 5 do
   if (Frustum[i][A]*pX + Frustum[i][B]*pY +
       Frustum[i][C]*pZ + Frustum[i][D]) <= 0 then
    begin
      Result := False;
      exit;
    end;
end;

Kugel im Frustum?

Nachdem wir nun feststellen können, ob ein Punkt im Frustum liegt, ist selbiges mit einer Kugel ein Leichtes.Wie man wissen sollte, lässt sich eine Kugel durch zwei Attribute darstellen : Ihren Ursprungspunkt und ihren Radius. Diese Funktion ersetzt also ganz einfach den Distanztest <=0 mit einem Distanztest gegen den negativen Radius der Kugel, also ziemlich einfach, oder?

function TFrustum.IsSphereWithin(const pX, pY, pZ,
                    pRadius : Single) : Boolean;
var
  i : Integer;
begin
  Result := true;
  for i := 0 to 5 do
    if (Frustum[i][A]*pX + Frustum[i][B]*pY +
       Frustum[i][C]*pZ + Frustum[i][D]) <= -pRadius then
    begin
      Result := False;
      exit;
    end;
end;

Dies ist der wohl meist genutzte Sichtbarkeitstest.Dies hat drei Gründe : Erstens : Dieser Test ist der schnellste, da nur sechs Berechnungen anfallen.Zweitens : Die Begrenzung der meisten Objekte lassen sich als Kugel beschreiben.Drittens : Für eine Kugel wird nur der Speicherplatz von vier Single-Werten benötigt. Wenn es also geht, sollte man diesen Test dem Quadertest vorziehen.

Quader im Frustum?

Festzustellen, ob sich ein Quader im Frustum befindet ist nicht viel schwerer als dies mit einer Kugel ist.Wie bekannt, besteht ein Quader aus acht Ecken.Also durchläuft die Funktion eine Schleife durch alle sechs Frustumflächen und prüft ob eine der Ecken vor einer der Flächen liegt.Ist dies der Fall, wird die Schleife unterbrochen.

function TFrustum.IsBoxWithin
    (const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
var
  i : Integer;
begin
  Result := true;
  for i := 0 to 5 do
  begin
    if (Frustum[i][A]*(pX-pB) + Frustum[i][B]*(pY-pH) +
        Frustum[i][C]*(pZ-pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py-pH) +
        Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py+pH) +
        Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py+pH) +
        Frustum[i][C]*(pz-pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py-pH) +
        Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py-pH) +
        Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px-pB) + Frustum[i][B]*(py+pH) +
        Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
          continue;
    if (Frustum[i][A]*(px+pB) + Frustum[i][B]*(py+pH) +
        Frustum[i][C]*(pz+pT) + Frustum[i][D]>0) then
          continue;
    Result := False;
  end;
end;

Wie vorher gesagt, benötigt dieser Test mehr Berechnungen als der Kugeltest(bis zu 48).Wenn man also eine Kugel statt eines Quaders als Begrenzung für ein Objekt nutzen kann, sollte man das tun.Dies spart jede Menge Berechnungen.

Das Beispielprogramm

Das Beispielprogramm rendert jede Menge Kugeln und prüft deren Sichtbarkeit via Frustum Culling bevor diese zur Grafikkarte gesendet werden.Mit Hilfe des Buttons kann das Frustum Culling ein- bzw. ausgeschaltet werden, um den Geschwindigkeitsunterschied leichter zu erkennen.

• Das Frustum-Culling Demo (inklusive Quellcode) herunterladen

Autor: Sascha Willems