Version vom 23. Juli 2009, 16:11 Uhr

Continuous Level of Detail fur Heightmaps

Einführung

Hi,

Ich habe in meinem ersten Heightmap Tutorial im Nachwort erzahlt, dass ich vielleicht ein Tutorial uber Level of Detail (LOD) fur Heightmaps schreibe. Ich will hiermit mein Versprechen einlosen, will euch aber auch gleich warnen, es ist nicht so leicht, wie man eigentlich denken konnte, denn viele Probleme stellen sich einem in den Weg, z.B. Cracks im Mesh.

Erkundigt man sich unter Spieleentwicklern nach LOD fur Heightmaps, wird man in den meisten Fallen wohl auf den Begriff ROAMing stosen. Dieser wird z.B. in einem meiner Lieblingsgames Tribes 2 verwendet. Mich hat dieser Algorithmus nicht wirklich angesprochen und ich habe weitergesucht. Nach einiger Zeit bin ich auf den Algorithmus aufmerksam geworden, der im Spiel Aquanox sein Konnen zeigt. Genauer gesagt bin ich uber das Virtual Terrain Project darauf gestosen. Das Original Script von Stefan Rottger findet sich direkt auf seiner Homepage unter Terrain Rendering: Real-Time Generation of Continuous Levels of Detail for Height Fields Ich kann euch wirklich warmstens empfehlen, dieses Script sich einmal genauer anzuschauen - sehr interessant. In diesem Tutorial werde ich das Schriftstuck etwas genauer beleuchten und ein paar Hilfestellungen dazu geben, in der Hoffnung, dass ihr es mir gleich tut und diesen Algorithmus selbst einmal nachbaut.

Quadtree

Der Ganze Algorithmus basiert auf einem Quadtree. Dieser wird durch eine Boolean Matrix(fur die Delpher, die immer noch nicht wissen, was eine Matrix ist: Wir reden uber ein 2 Dimensionales Array[0..n,0..n] of Boolean) reprasentiert, so kann man sich eine Menge Pointer(und damit Speicherplatz) und viel Rechenarbeit sparen. Wir gehen davon aus, dass die Matrix eine Grose von (2n+1)x(2n+1) hat. Idealerweise hat die verwendete Heightmap die gleichen Ausmase. Die Hauptnode sitzt in der Mitte der Matrix, die 4 Kinder... Bevor ich in Erklarungsnote komme, hier einfach ein Bild, das den Sachverhalt verdeutlichen soll:

Ok, wir wissen nun, wie die Matrix aufgebaut ist, wie die Mutter Kind Verhaltnisse des Quadtrees sind, etc., nur ist noch immer nicht klar, wozu diese Matrix. Wie bereits gesagt, handelt es sich um eine Boolean Matrix. Die Werte, die die Matrix annehmen kann, sind True oder False :-). Diese sagen aus, ob eine Node gesetzt ist und damit gezeichnet wird, oder eben nicht. Unsere Ziele sind also zum einen die Matrix rendern und zum andern die Matrix berechnen

Rendern der Heightmap

Unsere Landschaft wird gerendert, indem wir den Quadtree rekursiv entlanggehen und immer wenn ein Endpunkt des Baums erreicht wird, wird ein kompletter oder teile eines Dreieck Fans gezeichnet. Diese Fans sind besonders gut dazu geeignet, ohne Locher und Cracks im Mesh ein Heighfield darzustellen:

Das linke Bild stellt eine Beispiel Matrix dar, das rechte die dazu passende Triangulation. Ihr konnt gerne nach Stellen suchen, an denen die Moglichkeit besteht, dass dort ein Crack ist. Ihr werdet keine finden. Zuerst wird einmal davon ausgegangen, dass der Levelunterschied im Quadtree zweier benachbarter Blocke niemals mehr als 1 betragt. Diese Bedingung wird beim Berechnen der Matrix abgesichert, dazu spater mehr. Das Zentrum eines Fans, ist immer auch das Zentrum eines Quadtree Blattes. Vier Vertieces bilden die Ecken des Blocks und weitere 4 bilden jeweils die Mittelpunkte der Seiten des Blattes:

Es werden also hochstens 8 Dreiecke gezeichnet. Hat eine Seite keinen benachbarten Block gleichen Levels, so wird das Vertex in der Mitte der Seite einfach ubersprungen, was zur obigen Beispiel Triangulation fuhrt.

Erzeugen der Matrix

LOD besagt, dass Gegenstande in groser Entfernung mit einer niedrigeren Auflosung angezeigt werden, als nahe Objekte. Daneben werden auch bei groserer Entfernung bestimmte Teile eines Meshes mit hoherer Auflosung angezeigt, deren Oberflache besonders uneben ist, wodurch die Bildqualitat stark erhoht wird.

Oberflachenfehler

Fehler? Fehler?!? Will ich euch jetzt verarschen, ware doch dumm Fehler zu machen... Nein, die gemeinten Fehler besagen ausschlieslich, wie verfalscht eine Stelle in der Landschaft aussehen wurde, wenn man beim Hinuntergehen des Baumes an der aktuellen Stelle aufhort und zu rendern beginnt. Je hoher dieser Wert, desto wichtiger ist es, den Baum noch tiefer hinabzuschreiten.

Um diese d2 genannten Werte fur ein Quadree Blatt zu erhalten, errechnet man zuerst die Erhebungsunterschiede an den Mitten der 4 Seiten und an den 2 Diagonalen(Achtung: das sind unterschiedliche Werte). Der d2 Wert errechnet sich daraus so:

d2=(1/d)*maxi=1..6|dhi|

In Delphi konnte das ganze dann so aussehen:

  procedure CalcD2Value(X, Z, Size : Longint);
  var
    HSize : LongInt; //Hälfte der eigenen Seitenlänge
    I : LongInt;
    EdgeHeights : Array[1..4] of Single; //Höhe der Ecken
    ExpectedHeight : Single;             //Erwartete höhe zw 2 Punkten
    RealHeight : Single;                 //Tatsächliche Höhe

    DHValues : Array[1..6] of Single;    //DHWerte

  const
    //Ort der Ecken des Quads
    Edges : Array[1..4] of Array[0..1] of ShortInt = ((+1, +1),(+1, -1),(-1,-1),(-1,+1));
    //Jeweils die 2 Ecken, zwischen denen ein DHWert berechnet wird
    DHLines : Array[1..6] of Array[0..1] of Byte =
      ((1,2),(2,3),(3,4),(4,1),(1,3),(2,4));

    //Positionen der DHWerte selber
    DHPositions : Array[1..6] of Array[0..1] of ShortInt =
      ((1,0),(0,-1),(-1,0),(0,1),(0,0),(0,0));

  begin
    //Höhen der 4 Ecken
    for I := 1 to 4 do
      EdgeHeights[I] := GetHeightMapHeight(X + Size * Edges[i,0],
                          Z + Size * Edges[i,1]);

    //DHWerte berechen
    for i := 1 to 6 do
    begin
      //Erwartete Höhe zwischen 2 Punkten
      ExpectedHeight := (EdgeHeights[DHLines[i,0]] + EdgeHeights[DHLines[i,1]])/2;
      //Tatsächlich vorliegende Höhe
      RealHeight := GetHeightMapHeight(
        X + DHPositions[i,0] * Size,
        Z + DHPositions[i,1] * Size);
      //DH Wert ist |absoluter Fehler|
      DHValues[I] := Abs(ExpectedHeight - RealHeight)
    end;

    //D2Value finden und setzen
    QuadMatrix[X,Z].D2Value := Trunc(1/(2*Size) * Max(DHValues));

    //D2Values für die 4 Kinder
    if Size > 1 then
    begin
      HSize := Size div 2;
      CalcD2Value(X + HSize, Z + HSize, HSize);
      CalcD2Value(X + HSize, Z - HSize, HSize);
      CalcD2Value(X - HSize, Z + HSize, HSize);
      CalcD2Value(X - HSize, Z - HSize, HSize)
    end
  end; (*CalcD2Values*)
...
  CalcD2Value((QuadTreeLength-1) div 2, (QuadTreeLength-1) div 2,
    (QuadTreeLength-1) div 2);
...

In diesem Beispiel steht Size immer fur die Halfte der Seitenlange einer Quadtreenode. Man denke hier am Besten an den Radius eines Kreises. Die d2 Werte werden auf Bytegrose komprimiert, um wertvollen Speicher einzusparen.

Matrix erzeugen

Jetzt wollen wir uns daran machen, die furs Zeichnen unbedingt notige Matrix zu erzeugen. Gehen wir einmal davon aus, dass die Matrix bereits sauber entleert ist und damit kein Node als gesetzt gilt. Wir laufen den Quadtree wieder rekursiv hinab und entscheiden an jeder Node nach folgender Formel, ob weiter unterteilt werden muss oder nicht:

f=l/(d*C*max(c*d2, 1)

Ist der Wert von f kleiner 1, dann wird weiter unterteilt. Es gilt: C ist eine feste Konstante. Je hoher sie ist, desto hoher ist die Landschaft insgesamt aufgelost. l ist die Entfernung des Node Mittelpunkts zur Kamera und klein c kontrolliert die Auflosung in Bereichen, die einen hohen Oberflachenfehler aufweisen.

Schweizer Kase

Das bisherige Ergebnis ist doch mehr ernuchternd als erfreulich. Es sieht alles mehr nach Schweizer Kase aus. Viele Locher, aber sonst nicht viel zu bieten. In einem Spiel kann man so ganz schnell dem Spieler den Spass verderben, wir sollten also etwas dagegen unternehmen.

Um dieses Ziel zu erreichen, mussen wir ganz einfach die d2 Werte so verandern, dass Nebeneinanderliegende Blocke keinen Levelunterschied groser als 1 aufweisen (Bedingung für das Rendern der Matrix, siehe oben). Zuerst mussen also die d2 Werte einmal berechnet worden sein. Nun gehen wir den Quadtree wieder soweit herunter, bis wir genau 1 level vor dem niedrigsten sind und setzen den d2 Wert der Node neu:

QuadMatrix[X,Z].D2Value := Max(QuadMatrix[X,Z].D2Value, 
                               (d2Werte der benachbarten Nodes ein Level tiefer) * K)
K = C / (2 * (C - 1)); C groser 2

  procedure DoCrackAvoid(X, Z, Size, SizeToCheck : Longint);
  const
    Neighbours : Array[0..8] of Array[0..1] of ShortInt =
      ((+0,+0), (+3,+1),(+3,-1),(+1,-3),(-1,-3),(-3,-1),(-3,+1),(-1,+3),(+1,+3));
  var
    HSize : LongInt; //1/4 der Seitenlänge
    I : LongInt;
    D2Values : Array[0..8] of Byte;

  begin
    Assert(Size > 1);
    //Der Baum wird rekursiv abgehandlet(nicht unbedingt die
    //beste Idee. Wer Lust hat, darf sich gerne daran versuchen
    //es einmal ohne Rekursivität zu probieren!)

    HSize := Size div 2;
    //Wir haben noch nicht das gewünschte Level erreicht
    if Size > SizeToCheck then
    begin
      DoCrackAvoid(X + HSize, Z + HSize, HSize,SizeToCheck);
      DoCrackAvoid(X + HSize, Z - HSize, HSize,SizeToCheck);
      DoCrackAvoid(X - HSize, Z + HSize, HSize,SizeToCheck);
      DoCrackAvoid(X - HSize, Z - HSize, HSize,SizeToCheck)
    end
    else
    begin
      Assert(SizeToCheck = Size);
      D2Values[0] := QuadMatrix[X,Z].D2Value;
      for i := 1 to 8 do
        //Nachbarnodes holen....
        D2Values[i] := GetNode(X + HSize * Neighbours[i][0],
                               Z + HSize * Neighbours[i][1]) * K;

      QuadMatrix[X,Z].D2Value := MaxByte(D2Values)
    end
  end; (*DoCrackAvoid*)

Diesen Vorgang wiederholen wir, wobei wir immer ein Level niedriger gehen, bis wir schlieslich das Level 1 erreichen. Wenn wir nun unsere Matrix berechnen, ist unsere Bedingung erfullt und wir erhalten ein Mesh ohne Locher:

Wer glaubt hier ein paar Locher finden zu konnen liegt falsch. Die Stellen die schwarz erscheinen, werden durch das OpenGl Licht nur so unglucklich getroffen, dass sie fast schwarz erscheinen. Ist euer Monitor richtig eingestellt, sollte dagegen alles passen. Siehe dazu auch: Farbraum . Die "Kamera" befindet sich übrigens links unten im Bild, dort wo ein rotes Quad sichtbar ist.

Anmerkung: Nach Aussage von Stefan Röttger ist diese Methode um Löcher zu entfernen nicht optimal. Es genügt bei jedem Vater Knoten alle Kinder in die Berechnung einzubeziehen. Die Nachbarn müssen nicht einbezogen werden. Genaueres findet sich in diesem Forumsbeitrag.

Nachwort

Wie gehts weiter? Um die ganze Sache nun noch ein bischen weiter zu verbessern, sollte man uberlegen, ob man die Landschaft nicht vielleicht texturiert. Hier bietet sich sicher das 2. Highmap Tutorial als guter Anfang an. Auch konnte man das "Popping" unterbinden, das auftritt, wenn man sich einer Stelle nahert und plotzlich ein paar neue Dreiecke angezeigt werden. Das ganze ist bekannt unter dem Begriff Geomorphing.

Delphic

Dateien

• Delphi-VCL-Quelltext zum Tutorial
• Windows-Binary zum Tutorial