Tutorial Frustum Culling: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
(Etwas Vorarbeit)
K (Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.)
Zeile 17: Zeile 17:
 
Wir werden das Frustum Culling mit Hilfe einer handlichen, TFrustum genannten Klasse implementieren um die Dinge etwas einfacher zu machen.Hier die Klassendeklaration :
 
Wir werden das Frustum Culling mit Hilfe einer handlichen, TFrustum genannten Klasse implementieren um die Dinge etwas einfacher zu machen.Hier die Klassendeklaration :
  
<pascal>
+
<source lang="pascal">
 
TFrustum = object
 
TFrustum = object
 
   Frustum : array[0..5,0..3] of Single;
 
   Frustum : array[0..5,0..3] of Single;
Zeile 24: Zeile 24:
 
   procedure Calculate;
 
   procedure Calculate;
 
   end;
 
   end;
</pascal>
+
</source>
  
 
== Etwas Vorarbeit ==
 
== Etwas Vorarbeit ==
Zeile 30: Zeile 30:
 
Als Erstes brauchen wir für unsere Klasse einige Konstanten, die uns das Leben deutlich einfacher machen. Im Grunde selbsterklärend:
 
Als Erstes brauchen wir für unsere Klasse einige Konstanten, die uns das Leben deutlich einfacher machen. Im Grunde selbsterklärend:
  
<pascal>
+
<source lang="pascal">
 
const
 
const
 
   Right  = 0;
 
   Right  = 0;
Zeile 42: Zeile 42:
 
   C      = 2;
 
   C      = 2;
 
   D      = 3;
 
   D      = 3;
</pascal>
+
</source>
  
 
Jetzt kommt Mathematik ins Spiel. Wir müssen noch eine Funktion definieren, in der wir die berechneten Planes des Frustums normalisieren:
 
Jetzt kommt Mathematik ins Spiel. Wir müssen noch eine Funktion definieren, in der wir die berechneten Planes des Frustums normalisieren:
  
<pascal>
+
<source lang="pascal">
 
procedure NormalizePlane(var pFrustum: TFrustum; pPlane: Integer);
 
procedure NormalizePlane(var pFrustum: TFrustum; pPlane: Integer);
 
var
 
var
Zeile 57: Zeile 57:
 
   pFrustum.Frustum[pPlane][D] := pFrustum.Frustum[pPlane][D] / Magnitude;
 
   pFrustum.Frustum[pPlane][D] := pFrustum.Frustum[pPlane][D] / Magnitude;
 
end;
 
end;
</pascal>
+
</source>
  
 
== Das Frustum berechnen(procedure Calculate) ==
 
== Das Frustum berechnen(procedure Calculate) ==
Zeile 63: Zeile 63:
 
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.
 
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.
  
<pascal>
+
<source lang="pascal">
 
procedure TFrustum.Calculate;
 
procedure TFrustum.Calculate;
 
var
 
var
Zeile 103: Zeile 103:
 
               ModM[14]*ProjM[11] + ModM[15]*ProjM[15];
 
               ModM[14]*ProjM[11] + ModM[15]*ProjM[15];
 
{...}
 
{...}
</pascal>
+
</source>
  
  
Zeile 111: Zeile 111:
 
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.
 
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.
  
<pascal>
+
<source lang="pascal">
 
   Frustum[Right][A] := clip[ 3] - clip[ 0];
 
   Frustum[Right][A] := clip[ 3] - clip[ 0];
 
   Frustum[Right][B] := clip[ 7] - clip[ 4];
 
   Frustum[Right][B] := clip[ 7] - clip[ 4];
Zeile 148: Zeile 148:
 
   NormalizePlane(self, Front);
 
   NormalizePlane(self, Front);
 
end;
 
end;
</pascal>
+
</source>
  
 
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.
 
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.
Zeile 158: Zeile 158:
 
Um dies zu berechnen, nutzen wir folgende einfache Formel :
 
Um dies zu berechnen, nutzen wir folgende einfache Formel :
  
<pascal> Distance := (A*x) + (B*y) + (C*z) + D </pascal>
+
<source lang="pascal"> Distance := (A*x) + (B*y) + (C*z) + D </source>
  
 
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.
 
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.
  
<pascal>
+
<source lang="pascal">
 
function TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean;
 
function TFrustum.IsPointWithin(const pX, pY, pZ : Single) : Boolean;
 
   var
 
   var
Zeile 176: Zeile 176:
 
     end;
 
     end;
 
end;
 
end;
</pascal>
+
</source>
  
 
== Kugel im Frustum? ==
 
== Kugel im Frustum? ==
Zeile 183: Zeile 183:
 
Diese Funktion ersetzt also ganz einfach den Distanztest <=0 mit einem Distanztest gegen den negativen Radius der Kugel, also ziemlich einfach, oder?
 
Diese Funktion ersetzt also ganz einfach den Distanztest <=0 mit einem Distanztest gegen den negativen Radius der Kugel, also ziemlich einfach, oder?
  
<pascal>
+
<source lang="pascal">
 
function TFrustum.IsSphereWithin(const pX, pY, pZ,
 
function TFrustum.IsSphereWithin(const pX, pY, pZ,
 
                     pRadius : Single) : Boolean;
 
                     pRadius : Single) : Boolean;
Zeile 198: Zeile 198:
 
     end;
 
     end;
 
end;
 
end;
</pascal>
+
</source>
  
  
Zeile 210: Zeile 210:
 
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.
 
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.
  
<pascal>
+
<source lang="pascal">
 
function TFrustum.IsBoxWithin
 
function TFrustum.IsBoxWithin
 
     (const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
 
     (const pX, pY, pZ, pB, pH, pT : Single) : Boolean;
Zeile 246: Zeile 246:
 
   end;
 
   end;
 
end;
 
end;
</pascal>
+
</source>
  
 
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.
 
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.

Version vom 10. März 2009, 19:12 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.

Tutorial Frustum Culling01.jpg


Autor: Sascha Willems