» Du bist hier: STARTSEITE » Die Tutorials » Viewing Frustum Detection


 

» Viewing Frustum Detection

 

Kompiliert mit: Delphi 5.0 und Jedi-Headers für DX8
Beispiel downloaden: VFD.zip (216K)

Trotz Grafikkarten, die mehrere Millionen Polygone in der Sekunde zeichnen können, hilft es alles nichts, wenn man sein Spiel nicht in irgend einer Weiße optimiert.

Warum Viewing Frustum Detection (vfd)?
Bei VFD geht es darum, die Objekte zu ermitteln, die überhaupt nicht auf dem Bildschirm sind und folglich auch gar nicht erst gerendert werden müssen. Ohne VFD kommt man heute nicht mehr weit. Man stelle sich nur mal eine Scene mit tausenden Objekten vor. Das würde jede Grafikkarte in die Kniee zwingen, doch wenn man nur die Objekte zeichnet, die auch wirklich im Sichtfeld der Kamera sind, dann gehts erstmal richtig ab.

VFD ist zusätzlich noch ein Muß, wenn man Binary Space Partitions oder Quadtrees benutzt. Dies sind Methoden der Landschafts/Raum Darstellung. Moderne Spiele könnten überhaupt nicht solche tausend Polygonlandschaften einbauen, wenn sie mit VFD die nicht-sichtbaren Polys aussortieren.

Die Methode, die in diesem Tutorial beschrieben wird, ist sowas von extrem schnell, das es sich auf jeden Fall lohnt, ein Objekt auf Sichtbarkeit zu prüfen, bevor man es zeichnet, auch wenn es nur ein paar Polygone besitzt.

Die Vorgehensweiße:
Die Überprüfung geht folgendermaßen von statten. Eine Box, die immer ein Objekt vollständig umschließt, wird auf Sichtbarkeit geprüft. Um eine Box zu beschreiben, reicht ein minimaler und ein maximaler Punkt. Denn zwei Punkte beschreiben immer einer Box.

Zunächst bildet man die Planes, die das Field of View der Kamera umschreibt. Man kann sich das so vorstellen, das die Planes die Grenzen des Bildschirmes sind. Soll heißen, alles was hinter diesen Planes ist ist außerhalb der Kamera. Um nun eine ganze Box zu überprüfen, reicht es wenn man drei Überprüfungen durchführt. Liegt der minimale Punkt außerhalb der Planes, dann liegt die ganze Box außerhalb der Kamera und man kann das Objekt komplett wegfallen lassen. Liegt der maximale Punkt in den Planes, so liegt auch die gesamte Box im Sichtbereich der Kamera. Liegt dagegen der minimale Punkt, aber nicht der maximale Punkt in den Planes, so ist die Box teilweise sichtbar und sollte auch gezeichnet werden.

Jetzt gehts los:
Also bevor wir irgendetwas überprüfen können, müssen wir zunächst die Planes ermitteln, die das FOV der Kamera umschreiben. Legt dazu erstmal eine Type-Deklaration an:


TPlane = object
    m_normal: TD3DXVector3;
    m_distance: Single;
    procedure normalize;
    function DistanceToPoint(pt: TD3DXVector3): TD3DValue;
  end;

...und ein Array vom Typ TPlane:


var
  m_frustumPlanes: array [0..5] of TPlane;

Nun habt ihr erstmal die Grundvorraussetzungen. Als nächstes legt ihr eine Prozedur extractplanes an. Diese Prozedur ermittelt zunächst die View und die Projection Matrix und bildet daraus die sechs Ebenen:


procedure extractplanes;
var combomatrix, matview, matproj: TD3DXMatrix;
begin
  D3DDev8.GetTransform(D3DTS_VIEW, matView);
  D3DDev8.GetTransform(D3DTS_PROJECTION, matProj);
  D3DXMatrixMultiply(comboMatrix, matView, matProj);

  // Left clipping plane
  m_frustumPlanes[0].m_normal.x := -(comboMatrix._14 + comboMatrix._11);
  m_frustumPlanes[0].m_normal.y := -(comboMatrix._24 + comboMatrix._21);
  m_frustumPlanes[0].m_normal.z := -(comboMatrix._34 + comboMatrix._31);
  m_frustumPlanes[0].m_distance := -(comboMatrix._44 + comboMatrix._41);
  m_frustumPlanes[0].normalize;

  // Right clipping plane
  m_frustumPlanes[1].m_normal.x := -(comboMatrix._14 - comboMatrix._11);
  m_frustumPlanes[1].m_normal.y := -(comboMatrix._24 - comboMatrix._21);
  m_frustumPlanes[1].m_normal.z := -(comboMatrix._34 - comboMatrix._31);
  m_frustumPlanes[1].m_distance := -(comboMatrix._44 - comboMatrix._41);
  m_frustumPlanes[1].normalize;

  // Top clipping plane
  m_frustumPlanes[2].m_normal.x := -(comboMatrix._14 - comboMatrix._12);
  m_frustumPlanes[2].m_normal.y := -(comboMatrix._24 - comboMatrix._22);
  m_frustumPlanes[2].m_normal.z := -(comboMatrix._34 - comboMatrix._32);
  m_frustumPlanes[2].m_distance := -(comboMatrix._44 - comboMatrix._42);
  m_frustumPlanes[2].normalize;

  // Bottom clipping plane
  m_frustumPlanes[3].m_normal.x := -(comboMatrix._14 + comboMatrix._12);
  m_frustumPlanes[3].m_normal.y := -(comboMatrix._24 + comboMatrix._22);
  m_frustumPlanes[3].m_normal.z := -(comboMatrix._34 + comboMatrix._32);
  m_frustumPlanes[3].m_distance := -(comboMatrix._44 + comboMatrix._42);
  m_frustumPlanes[3].normalize;

  // Near clipping plane
  m_frustumPlanes[4].m_normal.x := -(comboMatrix._14 + comboMatrix._13);
  m_frustumPlanes[4].m_normal.y := -(comboMatrix._24 + comboMatrix._23);
  m_frustumPlanes[4].m_normal.z := -(comboMatrix._34 + comboMatrix._33);
  m_frustumPlanes[4].m_distance := -(comboMatrix._44 + comboMatrix._43);
  m_frustumPlanes[4].normalize;

  // Far clipping plane
  m_frustumPlanes[5].m_normal.x := -(comboMatrix._14 - comboMatrix._13);
  m_frustumPlanes[5].m_normal.y := -(comboMatrix._24 - comboMatrix._23);
  m_frustumPlanes[5].m_normal.z := -(comboMatrix._34 - comboMatrix._33);
  m_frustumPlanes[5].m_distance := -(comboMatrix._44 - comboMatrix._43);
  m_frustumPlanes[5].normalize;
end;

Die Erstellung der Ebenen ist recht einfach wie man im oberen Quellcode sieht. Aus dem Mathematikunterricht wißt ihr noch, das es nur einen Normalvektor und einen Wert D (Abstand zum Koordinatenursprung) benötigt, um eine Ebene zu beschreiben. Wie ihr seht werden die Ebenen aber noch normalisiert. Dies ist wichtig, damit sie alle eine Einheitsgröße bekommen. Die Prozedur normalize ist bereits in der Typedeklaration eingebunden. Ihr müßt also nur noch folgendes hinzufügen:


procedure TPlane.normalize;
var denom: Single;
begin
  denom := 1 / sqrt(sqr(m_normal.x) + sqr(m_normal.y) + sqr(m_normal.z));
  m_normal.x := m_normal.x * denom;
  m_normal.y := m_normal.y * denom;
  m_normal.z := m_normal.z * denom;
  m_distance := m_distance * denom;
end;

Ihr habt jetzt die Ebenen erstellt. Fügt nun folgende Funktion hinzu:


function CullAABB(aabbMin, aabbMax: TD3DXVector3): integer;
var minExtreme, maxExtreme: TD3DXVector3;
    intersect: boolean;
    i: integer;
begin
  extractplanes;
  intersect := false;

  for i := 0 to 5 do
  begin
    if m_frustumPlanes[i].m_normal.x >= 0 then
    begin
      minExtreme.x := aabbMin.x;
      maxExtreme.x := aabbMax.x;
    end
    else
    begin
      minExtreme.x := aabbMax.x;
      maxExtreme.x := aabbMin.x;
    end;

    if m_frustumPlanes[i].m_normal.y >= 0 then
    begin
      minExtreme.y := aabbMin.y;
      maxExtreme.y := aabbMax.y;
    end
    else
    begin
      minExtreme.y := aabbMax.y;
      maxExtreme.y := aabbMin.y;
    end;

    if m_frustumPlanes[i].m_normal.z >= 0 then
    begin
      minExtreme.z := aabbMin.z;
      maxExtreme.z := aabbMax.z;
    end
    else
    begin
      minExtreme.z := aabbMax.z;
      maxExtreme.z := aabbMin.z;
    end;

    if m_frustumPlanes[i].DistanceToPoint(minExtreme) > 0 then
    begin
      result := 0;
      exit;
    end;  
    if m_frustumPlanes[i].DistanceToPoint(maxExtreme) >= 0 then intersect := true;
  end;

  if intersect then result := 1 else result := 2;
end;

Diese Funktion (CullAABB) ist das Herzstück des VFD. Übergeben werden zwei Punkte. Der Minimalpunkt und der Maximalpunkt. Die Funktion erstellt zunächst die Ebenen, da sich diese bei jeder Kamerabewegung ändern. Danach überprüft sie, wo die zwei Punkte liegen. Ist DistanceToPoint(minExtreme) > 0, so liegt der Minimumpunkt außerhalb und die Funktion gibt 0 zurück. Ist die Distanz des Maximumpunktes größer 0, so liegt die Box teilweise im Sichtbereich und die Funktion gibt 1 zurück. Ist jedoch keines der Fall, so liegt die Box vollständig im Sichtbereich und die Funktion gibt 2 zurück.
Für die Abstandsberechnung (DistanceToPoint) braucht ihr noch folgende Funktion, die ebenfalls in der Plane Deklaration eingebunden ist:


function TPlane.DistanceToPoint(pt: TD3DXVector3): Single;
begin
  result := D3DXVec3Dot(m_normal, pt) + m_distance;
end;

Das wars im Endeffekt schon, aber es bleiben sicher noch einige Fragen offen...

Wie ermittle ich die Min und Max Punkte für CullAABB?
Wir möchten jetzt nochmal genauer auf die Box eingehen, die man der Funktion CullAABB übergeben muss. Fakt ist das man ja zwei Punkte benötigt, aber wie ermittelt man diese aus einem gegebenen Objekt? Vorraussetzung dafür ist, das man die Vertices des Objektes besitzt. Mit folgender Anweisung ermittelt ihr daraus die kleinsten und größten Werte:


var min, max: TD3DXVector3;
...
//Die min und max Werte erstmal mit Objektdaten füllen
min := d3dxvector3(objekt.vertices[0].x, objekt.vertices[0].y, objekt.vertices[0].z);
max := min;

//Nun die wirklichen min und max Punkte ermitteln
for i := 0 to objekt.numvertices - 1 do
begin
  if objekt.vertices[i].x < min.x then min.x := objekt.vertices[i].x;
  if objekt.vertices[i].y < min.y then min.y := objekt.vertices[i].y;
  if objekt.vertices[i].z < min.z then min.z := objekt.vertices[i].z;

  if objekt.vertices[i].x > max.x then max.x := objekt.vertices[i].x;
  if objekt.vertices[i].y > max.y then max.y := objekt.vertices[i].y;
  if objekt.vertices[i].z > max.z then max.z := objekt.vertices[i].z;
end;
...

Ihr habt nun die zwei Punkte, die ihr benötigt. Den oberen Algorithmus müßt ihr nur einmal ausführen. Allerdings gibt es dabei etwas zu beachten. Wenn sich euer Objekt bewegt, so sind die Min und Max Werte nicht mehr aktuell. Es hilft auch nichts die Prozedur zu wiederholen, denn die Min und Maxwerte sind immer an der selben Stelle, da sie relativ zum Objekt stehen. Ihr müßt deshalb die min und max Werte (Vektoren), die ihr ermittelt habt, jedesmal mitbewegen, wenn ihr CullAABB aufruft. Dies ist aber nicht weiter wild. Was ihr braucht ist die World Matrix eures Objektes und diese Funktion:


function Vec3TransformCoord(src: TD3DXVector3; mat: TD3DXMatrix): TD3DXVector3;
begin
  result.x := Src.x*mat._11 + Src.y*mat._21 + Src.z*mat._31 + mat._41;
  result.y := Src.x*mat._12 + Src.y*mat._22 + Src.z*mat._32 + mat._42;
  result.z := Src.x*mat._13 + Src.y*mat._23 + Src.z*mat._33 + mat._43;
end;

Diese Funktion ist ein sehr hilfreiches Tool. Ihr übergebt eine Matrix und einen Vektor und die Funktion transformiert den Vektor entlang der Matrix.

Eine Anwendung des gesamten CullAABB Algorithmuses würde dann so aussehen:


var newmin, newmax: TD3DXVector3;
begin
  newmin := Vec3TransformCoord(min, objekt.worldmatrix);
  newmax := Vec3TransformCoord(max, objekt.worldmatrix);
  if cullAABB(newmin, newmax) > 0 then objekt.render;
end;

Ihr seht, wenn man erstmal die ganze Vorbereitung hinter sich hat, dann ist es ein Kinderspiel die Sichtbarkeit zu überprüfen. Im oberen Beispiel werden die Min und Max Punkte zunächst mittels der Objektmatrix transformiert und der Function CullAABB übergeben. Ist der Rückgabewert größer 0, so ist die Box entweder teilweise sichtbar oder vollständig sichtbar. In beiden Fällen sollte das Objekt gezeichnet werden.

Einschränkungen des VFD Algorithmuses:
Der VFD Algo hat zwei grundlegende Einschränkungen. Erstens sind für den Computer Objekte auch sichtbar, wenn diese hinter einer Wand stehen, aber trotzdem im Sichtfeld der Kamera wären. Das kontrolliert dieser Algo natürlich nicht.
Und zweitens: Der Algo überprüft nur mit Axis Aligned Boxen. Das bedeutet, das die Boxen, die man übergibt immer parallel zu den 3 Koordinatenachsen sind. Das heißt, selbst wenn sich das Objekt dreht, und man transformiert die min und max Punkte mit der Matrix mit, so würde sich die Box um das Objekt nicht mitdrehen, sondern lediglich größer werden. Das ist im Endeffekt kein Problem, denn Fakt ist das die zwei Punkte IMMER das Objekt vollständig einschließen. Es würde sich lediglich in der Genauigkeit äußern, also wenn das Objekt fast sichtbar wäre, dann würde der Algo schon ein "sichtbar" zurückliefern. Das äußert sich aber auf keinen Fall auf die Geschwindigkeit aus und was viel wichtiger ist, das Problem tritt nicht andersherum auf, also der Algo wird niemals ein "nicht-sichtbar" zurückliefern, obwohl das Objekt noch sichtbar wäre.

Schlusswort:
Ihr habt mit diesem Tutorial ein mächtiges Werkzeug in der Hand und solltet das auch nutzen. Es heißt, lieber einmal mehr eine Sichtbarkeitsprüfung gemacht als ein Objekt zu viel gerendert :)


» Zurück zur Tutorial Startseite

 


 

The Neobrothers:   Neo  Netzerfetzer

Besucherstatistik:

Besucherzähler