Tutorial Octree: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
K (Der Ausdruck ''\{\{DateiLink\|'' wurde ersetzt mit ''{{ArchivLink|''.)
K (Im TNode: "numv" wurde zu "nump" umgeändert (es werden Polygone gezählt, nicht Vektoren), TNode.HowManyPolygons -> Add-Abfrage außerhalb der for-Schleife)
Zeile 123: Zeile 123:
 
     pos      : TVertex;
 
     pos      : TVertex;
 
     size      : glfloat;
 
     size      : glfloat;
     numv     : Integer;
+
     nump     : Integer;
 
     numc      : Byte;
 
     numc      : Byte;
 
     poly      : array of PPolygon;
 
     poly      : array of PPolygon;
Zeile 145: Zeile 145:
 
*seinen Mittelpunkt --> Vektor
 
*seinen Mittelpunkt --> Vektor
 
*seine Größe --> glFloat
 
*seine Größe --> glFloat
*die Anzahl der Vektoren, die sich in ihm befinden --> Integer
+
*die Anzahl der Polygonen, die sich in ihm befinden --> Integer
 
*die Anzahl an Würfeln (maximal 8), die aus ihm entstehen, wenn er mehr als MAX_TRIANGLES_IN_NODE Vektoren in sich hat --> Byte
 
*die Anzahl an Würfeln (maximal 8), die aus ihm entstehen, wenn er mehr als MAX_TRIANGLES_IN_NODE Vektoren in sich hat --> Byte
 
*ein Array für die Polygone --> array of TPolygon
 
*ein Array für die Polygone --> array of TPolygon
Zeile 273: Zeile 273:
 
       setLength(children,numc);
 
       setLength(children,numc);
 
       children[numc-1]:=TempNodes[i];
 
       children[numc-1]:=TempNodes[i];
       if children[numc-1].numv < MAX_TRIANGELS_IN_NODE then
+
       if children[numc-1].nump < MAX_TRIANGELS_IN_NODE then
 
       begin
 
       begin
 
         children[numc-1].smallest:=TRUE;
 
         children[numc-1].smallest:=TRUE;
Zeile 325: Zeile 325:
 
   i:Integer;
 
   i:Integer;
 
begin
 
begin
   numv:=0;
+
   nump := 0;
  for i:=0 to High(polygons) do
+
 
   if PolygonIn(polygons[i])then
+
   if Add then
 
   begin
 
   begin
     Inc(numv);
+
     for i := 0 to High(polygons) do
    if Add then
+
      if PolygonIn(polygons[i]) then
    begin
+
      begin
      setLength(poly,numv);
+
        Inc(nump);
      poly[numv-1]:=polygons[i];
+
        SetLength(poly, numv);
    end;
+
        poly[nump-1] := polygons[i];
   end;
+
      end;
   Result:=numv;
+
   end
 +
  else
 +
    for i := 0 to High(polygons) do
 +
      if PolygonIn(polygons[i]) then
 +
        Inc(nump);
 +
 
 +
   Result := nump;
 
end;
 
end;
 
</source>
 
</source>
Zeile 348: Zeile 354:
 
Die Funktion "PolygonIn" überprüft ob ein Polygon sich in einem Node befindet (wie der Name schon sagt).
 
Die Funktion "PolygonIn" überprüft ob ein Polygon sich in einem Node befindet (wie der Name schon sagt).
  
"HowManyPolygons" greift darauf zu und gibt die Anzahl der Polygone, die sich in dem Node befinden zurück und speichert diese in der Node Variablen "numv". Wenn der Parameter Add auf TRUE gesetzt wurde, dann werden alle Polygone in das Array des Nodes gespeichert.
+
"HowManyPolygons" greift darauf zu und gibt die Anzahl der Polygone, die sich in dem Node befinden zurück und speichert diese in der Node Variablen "nump". Wenn der Parameter Add auf TRUE gesetzt wurde, dann werden alle Polygone in das Array des Nodes gespeichert.
 
HINWEIS: Hierzu ist zu sagen, dass die Funktion "PolygonIn" nicht perfekt ist. Wenn sich mindestens ein Vektor des Polygons im Node befindet, dann wird das Polygon angenommen. Polygone, die unseren Node schneiden, aber trotzdem außerhalb liegen, werden nicht erkannt. Allerdings hatte ich damit bis jetzt keine Probleme.
 
HINWEIS: Hierzu ist zu sagen, dass die Funktion "PolygonIn" nicht perfekt ist. Wenn sich mindestens ein Vektor des Polygons im Node befindet, dann wird das Polygon angenommen. Polygone, die unseren Node schneiden, aber trotzdem außerhalb liegen, werden nicht erkannt. Allerdings hatte ich damit bis jetzt keine Probleme.
 
Das zweite Problem bei dieser Funktion ist, dass Polygone, die sich in mehreren Nodes befinden, auch allen zugeordnet werden und dann eventuell mehrmals gezeichnet werden. Allerdings fand ich noch nicht die Zeit diese Probleme zu beheben.
 
Das zweite Problem bei dieser Funktion ist, dass Polygone, die sich in mehreren Nodes befinden, auch allen zugeordnet werden und dann eventuell mehrmals gezeichnet werden. Allerdings fand ich noch nicht die Zeit diese Probleme zu beheben.
Zeile 364: Zeile 370:
 
   i,j:Integer;
 
   i,j:Integer;
 
begin
 
begin
   if numv = 0 then exit;
+
   if nump = 0 then exit;
 
   glBegin(GL_TRIANGLES);
 
   glBegin(GL_TRIANGLES);
     for i := 0 to numv-1 do
+
     for i := 0 to nump-1 do
 
     for j := 0 to 2 do
 
     for j := 0 to 2 do
 
     with poly[i].v[j]^ do
 
     with poly[i].v[j]^ do

Version vom 4. Mai 2011, 15:28 Uhr

Octree-Tutorial

by Shadow

Einleitung

Herzlich Willkommen zu meinem ersten Tutorial für die Delphi OpenGL Community.


Schon mal vorweg: Dieses Tutorial hat weniger mit OpenGL-technischen Verfahren zu tun, sondern viel mehr mit der Programmiersprache und ist absolut nicht an Anfänger in Sachen Delphi gerichtet, da schon für Einsteiger komplizierte Verfahren, wie z.B. sich selbst aufrufende Prozeduren, genutzt werden. Aber ich möchte niemanden erschrecken, denn dies ist ein freies Land und jeder darf tun und lassen was er will ;-). Es ist ratsam dass von mir geschriebene selbst zu schreiben und nicht mit Strg+C & Strg+V in sein Programm zu kopieren, da man dabei nicht sehr viel lernt. Ich will die Sache schnell hinter mich bringen, also fang ich gleich mal an, denn wir haben viel Arbeit vor uns (was jetzt nicht heißen soll dass ich alles überfliege, ich versuch so gut wie möglich alles zu erklären).


Stellt euch vor, ihr habt eine riesige Landschafts-Szene die aus 512x512 Vertices besteht. Jedes dieser Vertices besitzt nun auch noch Textur-Koordinaten, Normalen, usw. Dass alles zu rendern würde eine große Rechenleistung benötigen. Aber höchstwahrscheinlich sieht der Spieler nur immer einen Teil der Landschaft, also warum alles darstellen, wenn nur ein Teil gesehen wird? Frustum-Culling (d.h. jedes Polygon auf Sichtbarkeit zu überprüfen) würde den gesamten Performance-Bedarf auf die CPU übertragen und wäre somit bei ca. 500x500 Polygonen auch nicht hilfreich. An dieser Stelle hilft uns ein Octree. "Octree", dass werden schon viele von euch gehört haben, aber was dass genau ist, das wird wohl nicht jeder wissen. Ich werd mal versuchen zu erklären was dass genau ist und wofür man dieses Ding braucht.


Was ist ein Octree

Nun das Wort "Octree" kommt aus dem Lateinischen oder so.... ;-) "Oct" steht für "Acht" und "Tree" bedeutet im Englischen "Baum". Was soll das nun heißen? ... ACHT-BAUM? Ein Octree kann man sich folgendermaßen vorstellen : Ein Würfel, der in 8 kleine Würfel unterteilt wird. Jeder dieser Würfel wird dann noch einmal in 8 kleine Würfel geteilt usw. Kann man vergleichen mit einem Baum, der 8 große Zweige hat, diese Zweige haben wieder 8 Zweige usw. Deswegen „Baum“. Beim Octree heißen diese Würfel „Nodes“, was übersetzt „Knoten“ heißt (fragt mich bitte nicht warum [Weil ein binärer Baum nunmal Knoten hat, nämlich dort wo sich "Äste" verzweigen - Anmerkung des Lektors, SoS]).


Wie funktioniert ein Octree

Nun dies ist nicht mit einem Satz zu erklären. Aber ich versuch es mal mit ein "paar" Sätzen:

Tutorial Octree mainnode.jpg
Die gesamte Szene wird in einen großen Würfel gepackt. Dazu überprüft man alle Vertices auf ihre größten und kleinsten Werte. Ist z.B. die y-Koordinate von Vertex a die Größte und die z-Koordinate von Vertex b die Kleinste, so ist die Länge unseres Würfels: a.y - b.z Am Mittelpunkt der Szene wird dann der Würfel mit diesen Seitenlängen berechnet. Dieser Würfel, wird dann in 8 kleinere Würfel geteilt und diese wiederum in 8 kleinere usw. Alle Nodes, die leer sind fallen dabei weg, da sie für uns überflüssig sind.







Tutorial Octree nodes.jpg
Auf dem Bild links seht ihr nun die Szene mit mehreren Nodes.

Dies kann man nun so oft man will wiederholen, aber Vorsicht : Es benötigt viel Rechenzeit alle kleinen Nodes noch mal zu teilen, und diese noch mal, weil dabei immer überprüft werden muss, ob sich Vertices in ihnen befinden. Außerdem ist es ab einer Gewissen Anzahl von Nodes nicht mehr sehr sinnvoll, da z.B. zu viele Nodes sich eher negativ auf die Performance auswirken würden.





Deswegen machen wir folgendes: Wir speichern die Anzahl der Vertices bzw. Polygone, die sich in unserem Node befinden, und teilen nur so lange sich diese Zahl über einer bestimmen Limit befindet, z.B. 500 Polygone. So werden Nodes, die weniger als 500 Polygone besitzen, nicht mehr geteilt. Wenn dies alles erledigt ist, dann muss man beim Rendern der Szene folgendes beachten:

Es wird per Frustum-Culling überprüft, ob sich die großen Nodes im Blickfeld befinden. Von denen, die sichtbar sind, wird überprüft, ob deren kleinere Würfel sichtbar sind und deren Unterknoten usw. Ist ein Node nicht sichtbar, so werden auch seine Kindwürfel nicht überprüft. Wenn man beim kleinsten Node angekommen ist, was dank dieses Algorithmus sehr schnell geschieht, werden nur die Polygone gezeichnet, die sich in ihm befinden.

Wie ihr euch wahrscheinlich denken könnt, bringt dieses Verfahren eine Menge Geschwindigkeit.


Was brauch ich dafür

  • Nun da ich aus Zeitgründen das Frustum-Culling nicht erklären kann, müsst ihr eine Unit haben, die den Frustum berechnet und ein Würfel auf

Sichtbarkeit überprüfen kann. Sehr empfehlenswert ist die von SoS (nette Grüße) auf www.delphigl.de.

  • Außerdem müsst Ihr euren Terrain/Objekte laden und in einer Polygon-Array speichern. Am besten aus einer Bitmap-Datei, so wie ich es mache.


Let's get started

Auf in den Kampf:


Am besten erstellt/benutzt eine Unit in der die Haupttypen definiert sind. Bei mir sieht diese folgendermaßen aus:

unit Globals;

interface

uses
  Windows, Messages, dglOpenGL, FrustumC;

type
  PVertex     = ^TVertex;
  TVertex     = record
     x,y,z    : GlFloat;
  end;
  PFullVertex = ^TFullVertex;
  TFullVertex = record
    ver,n     : TVertex;
    u,v       : GlFloat;
  end;
  PPolygon    = record
    v         : array [0..2] of PFullVertex;
  end;
  TPolygon    = record
    v         : array [0..2] of TFullVertex;
  end;

var
  Frustum:TFrustum;


Die Typen die ihr deklariert, solltet ihr in eurem Hauptprogramm auch benutzt wenn ihr eurer Vektoren laden wollt, damit es nicht zu Problemen zwischen der Octree-Klasse und euren Arrays kommt.

Nun fangen wir mit der Typdefinition in der Octree-Unit an. Oben definieren wir eine Konstante, die angibt ab welcher Vektorenanzahl ein Knoten nicht mehr geteilt wird:


unit Octree;

interface

uses
  Windows, Messages, dglOpenGL, Globals;

Const
  MAX_TRIANGLES_IN_NODE = 500;


Wir überlegen uns mal was wir so alles für Typen definieren müssen ...hmmmmmmm am besten:

  • Einen Knoten als Objekt, da Prozeduren und Funktionen hinzukommen werden
  • und den Octree als Klasse, damit wir Konstructor und Destruktor entsprechend nutzen können


Hier das Node-Objekt:


type   PNode = ^TNode;
  TNode = object
    pos       : TVertex;
    size      : glfloat;
    nump      : Integer;
    numc      : Byte;
    poly      : array of PPolygon;
    children  : array of PNode;
    smallest  : Boolean;
    function HowManyPolygons(const polygons : array of PPolygon;Add:Boolean):Integer;
    function PolygonIn(p:PPolygon):Boolean;
    Procedure Divide(const polygons : array of PPolygon);
    procedure DrawPolygons;
    procedure Check;
    procedure Draw;
    procedure Clear;
  end;


Ich denke, dass das alles sehr selbsterklärend ist, aber um sicher zugehen dass ihr das alle versteht:


Erstmal einen Pointer auf die Knoten, und folgende Informationen für einen Knoten :

  • seinen Mittelpunkt --> Vektor
  • seine Größe --> glFloat
  • die Anzahl der Polygonen, die sich in ihm befinden --> Integer
  • die Anzahl an Würfeln (maximal 8), die aus ihm entstehen, wenn er mehr als MAX_TRIANGLES_IN_NODE Vektoren in sich hat --> Byte
  • ein Array für die Polygone --> array of TPolygon
  • und anschließend ein Array für die untergeordneten Nodes --> array of PNode
  • ob es der kleinste Node ist, also ob sich weniger als MAX_TRIANGLES_IN_NODE in ihm befinden --> Boolean, denn dann erst speichern wir in das Array die Polygone, damit wir diese anzeigen können, und auch dann erst wird er wieder geteilt.
  • Die Funktion "HowManyPolygons" überprüft, wie viele Polygone in dem Node sind und der Parameter "Add" entscheidet, ob die Polygone in das Array des Nodes aufgenommen werden sollen. Dies brauchen wir, weil nur in die kleinsten Nodes die Polygone aufgenommen

werden müssen, da wir sonst alle Polygone öfter zeichnen würden; und nicht genau wissen, welches Polygon bereits gezeichnet wurde und welches nicht.

  • "PolygonIn" testet, ob ein Polygon im Node ist und liefert dann TRUE zurück.
  • "Divide" teilt den Node in 8 kleine Würfel.
  • "Check" überprüft den Node auf Sichtbarkeit und zeichnet dann seine Polygone.
  • "Draw" zeichnet den Node selbst.
  • "Clear" löscht den Node.


So, jetzt das Objekt für den ganzen Octree :


TOctree = class
  public
    mainnode  : PNode;
    procedure drawOctree(drawPol,drawNodes:Boolean);
    Constructor Create(const polygons : array of PPolygon);
    Destructor Destroy;
  end;


MainNode ist der oberste Würfel. Mehr brauchen wir nicht, da die restlichen Nodes diesem untergeordnet werden.

Die Parameter in "DrawOctree" geben an, ob die Polygone im Node gezeichnet werden sollen und ob der Node dargestellt werden soll (eigentlich unwichtig, aber zur Veranschaulichung sehr nützlich).

Die zu überprüfenden Polygone werden als Pointer übergeben.


Nun kommen wir zu der Initialisierungs-Prozedur, die den obersten Würfel um die ganze Szene berechnet:

Constructor TOctree.Create(const polygons : array of PPolygon);
var
  i,j:Integer;
  maxSize,minSize:Glfloat;
begin
  inherited Create;
  maxsize:=polygons[0].v[0].ver.x;
  minsize:=polygons[0].v[0].ver.x;
  for i:=0 to High(polygons) do
  for j:=0 to 2 do
  with polygons[i].v[j].ver do
  begin
    if x > maxSize then maxSize:=x;
    if y > maxSize then maxSize:=y;
    if z > maxSize then maxSize:=z;

    if x < minSize then minSize:=x;
    if y < minSize then minSize:=y;
    if z < minSize then minSize:=z;
  end;
  New(mainnode);
  MainNode.pos.x:=(maxSize+minSize)/2;
  MainNode.pos.y:=(maxSize+minSize)/2;
  MainNode.pos.z:=(maxSize+minSize)/2;
  MainNode.size:=(maxSize-minSize)/2;
  MainNode.smallest:=FALSE;
  MainNode.Divide(polygons);
end;


Es ist logisch, dass vor der Initialisierung des Octrees die Landschaft erst einmal geladen werden muss; damit das Polygon-Array die richtigen Werte hat.

Also zur Prozedur : Alle Vertices werden auf ihre größte und kleinste Komponente überprüft, die gesuchten Werte lassen uns dann den Mittelpunkt und die Größe unseres Nodes berechnen. Mit "New()" wird im Speicher ein TNode angelegt, da MainNode nur ein Pointer ist und dieser erst einmal erstellt werden muss. Da müsst ihr beachten, dass ihr den Speicher dann am Ende mit "Dispose()" wider freigebt, aber ich werde euch noch daran erinnern.


Die untenstehende Prozedur teilt den Node in 8 kleine Würfel und überprüft, ob diese leer sind. Hier die Divide-Prozedure:

Procedure TNode.Divide(const polygons : array of PPolygon);
var
  TempNodes:array[0..7] of PNode;
  i:Integer;
begin
  for i:=0 to 7 do New(TempNodes[i]);
  numc:=0;
  TempNodes[0].pos.x:=pos.x-size/2;
  TempNodes[0].pos.y:=pos.y+size/2;
  TempNodes[0].pos.z:=pos.z-size/2;

  TempNodes[1].pos.x:=pos.x+size/2;
  TempNodes[1].pos.y:=pos.y+size/2;
  TempNodes[1].pos.z:=pos.z-size/2;

  TempNodes[2].pos.x:=pos.x+size/2;
  TempNodes[2].pos.y:=pos.y+size/2;
  TempNodes[2].pos.z:=pos.z+size/2;

  TempNodes[3].pos.x:=pos.x-size/2;
  TempNodes[3].pos.y:=pos.y+size/2;
  TempNodes[3].pos.z:=pos.z+size/2;

  TempNodes[4].pos.x:=pos.x-size/2;
  TempNodes[4].pos.y:=pos.y-size/2;
  TempNodes[4].pos.z:=pos.z-size/2;

  TempNodes[5].pos.x:=pos.x+size/2;
  TempNodes[5].pos.y:=pos.y-size/2;
  TempNodes[5].pos.z:=pos.z-size/2;

  TempNodes[6].pos.x:=pos.x+size/2;
  TempNodes[6].pos.y:=pos.y-size/2;
  TempNodes[6].pos.z:=pos.z+size/2;

  TempNodes[7].pos.x:=pos.x-size/2;
  TempNodes[7].pos.y:=pos.y-size/2;
  TempNodes[7].pos.z:=pos.z+size/2;
  for i:=0 to 7 do
  begin
    TempNodes[i].size:=size/2;
    TempNodes[i].smallest:=FALSE;
  end;
  for i:=0 to 7 do
  begin
    if TempNodes[i].HowManyPolygons(polygons,FALSE)>0 then
    begin
      inc(numc);
      setLength(children,numc);
      children[numc-1]:=TempNodes[i];
      if children[numc-1].nump < MAX_TRIANGELS_IN_NODE then
      begin
        children[numc-1].smallest:=TRUE;
        children[numc-1].HowManyPolygons(polygons,TRUE);
      end;
    end else Dispose(TempNodes[i]);
  end;
  for i:=0 to numc-1 do
    if children[i].smallest=FALSE then children[i].Divide(polygons);
end;


Es werden erst einmal die 8 Nodes neu im Speicher angelegt und dann in Abhängigkeit zum Node berechnet. Dann wird für jeden dieser TempNodes mit der Funktion VerticesIn überprüft, wie viele Polygone sich in ihm befinden. Der zweite Parameter bestimmt, ob die Polygone in das Array des Nodes gespeichert werden sollen. Dies wollen wir erst einmal nicht. Diese Prozedur zeige ich euch gleich etwas genauer. Wichtig ist, dass wenn sich Polygone im Node befinden, er erst dann zum Kind des Nodes wird. Sind weniger Polygone als unsere Konstante MAX_TRIANGLES_IN_NODE in unserem Kindknoten, dann ist er der kleinste, d.h. er wird nicht mehr geteilt und wir können die Polygone in seinem Array speichern.

Befindet sich kein Polygon im TempNode, so wird dieser nicht als Kindknoten aufgenommen und mit Dispose() aus dem Speicher entfernt.

Wenn alle Nodes überprüft worden sind, so werden die, die als Kinder aufgenommen wurden, auch mit dieser Prozedur geteilt und überprüft, aber nur wenn sie weniger als MAX_TRIANGELS_IN_NODE (smallest=FALSE) Polygone in sich haben.


Wie ihr wahrscheinlich merkt, ist dies die Haupt-Prozedur. Sie hört erst auf, wenn alle Nodes weniger als MAX_TRIANGLES_IN_NODE Polygone in sich haben.


Nun schauen wir uns mal die "HowManyPolygons" und die "PolygonIn"-Funktion an:


function TNode.PolygonIn(p:PPolygon):Boolean;
var
  i:Integer;
begin
  Result := FALSE;
  for i := 0 to 2 do
  if not Result then
  with p.v[i].ver do
  begin
    if(x >= pos.x - size) and
      (y >= pos.y - size) and
      (z >= pos.z - size) and
      (x <= pos.x + size) and
      (y <= pos.y + size) and
      (z <= pos.z + size) then Result:=TRUE;
  end;
end;
function TNode.HowManyPolygons(const polygons : array of PPolygon; Add:Boolean):Integer;
var
  i:Integer;
begin
  nump := 0;

  if Add then
  begin
    for i := 0 to High(polygons) do
      if PolygonIn(polygons[i]) then
      begin
        Inc(nump);
        SetLength(poly, numv);
        poly[nump-1] := polygons[i];
      end;
  end
  else
    for i := 0 to High(polygons) do
      if PolygonIn(polygons[i]) then
        Inc(nump);

  Result := nump;
end;


[EDIT 12.03.2005 vom Autor] Habe was SEHR wichtiges vergessen. Anstatt alle Polygone zu überprüfen, ist es sehr(und ich meine SEHR) viel schneller, nur die Polygone, des übergeordneten Nodes zu testen. Ein Implentation sollte nicht all zu schwer sein: Einfach für jedes Node einen Pointer auf den Mother-Node setzten und die Polygone immer in die Array speichern, und dann bei der Überprüfung sich auf die polygon-array des Mother-Nodes beziehen. Sollte die Performance deutlich steigern. Ich endschuldige mich für meinen Fehler ;) [/EDIT]


Die Funktion "PolygonIn" überprüft ob ein Polygon sich in einem Node befindet (wie der Name schon sagt).

"HowManyPolygons" greift darauf zu und gibt die Anzahl der Polygone, die sich in dem Node befinden zurück und speichert diese in der Node Variablen "nump". Wenn der Parameter Add auf TRUE gesetzt wurde, dann werden alle Polygone in das Array des Nodes gespeichert. HINWEIS: Hierzu ist zu sagen, dass die Funktion "PolygonIn" nicht perfekt ist. Wenn sich mindestens ein Vektor des Polygons im Node befindet, dann wird das Polygon angenommen. Polygone, die unseren Node schneiden, aber trotzdem außerhalb liegen, werden nicht erkannt. Allerdings hatte ich damit bis jetzt keine Probleme. Das zweite Problem bei dieser Funktion ist, dass Polygone, die sich in mehreren Nodes befinden, auch allen zugeordnet werden und dann eventuell mehrmals gezeichnet werden. Allerdings fand ich noch nicht die Zeit diese Probleme zu beheben. Falls jemand eine bessere Methode hat, so kann er diese Prozeduren einfach erweitern (verbessern). Ich würde mich sehr über Ratschläge freuen. Eine Möglichkeit ist es, das Polygon an den Nodes in zwei Polygone zu schneiden (Auch Splitting genannt).


Nun habt ihr die Berechnung eures Octrees. Es fehlt lediglich das Anzeigen und die Entfernung aus dem Speicher.


So zeichnet ihr die Polygone eures Nodes:

procedure TNode.drawPolygons;
var
  i,j:Integer;
begin
  if nump = 0 then exit;
  glBegin(GL_TRIANGLES);
    for i := 0 to nump-1 do
    for j := 0 to 2 do
    with poly[i].v[j]^ do
    begin
      glNormal3fv(@n);
      glTexCoord2f(u,v);glVertex3fv(@ver);
    end;
  glEnd;
end;
procedure TNode.check;
var
  i:Integer;
begin
  if Frustum.IsBoxWithin(
     pos.x,pos.y,pos.z,
     size,size,size)=TRUE then
  begin
    if smallest then drawPolygons;
    for i:=0 to numc-1 do
      if not smallest then children[i].check;
  end;
end;


Die erste Prozedur zeichnet alle Vektoren in einem Node. Hier tue ich das mit Hilfe einer einfachen Schleife. Displaylisten oder VBOs würden das ganze noch ein wenig beschleunigen, aber die Erklärung dafür würde den Umfang dieses Tutorials zu sehr vergrößern.


Interessanter und komplizierter ist die "check"-Prozedur, die überprüft, mit welchen Nodes dies geschehen soll.

Eure Octree-Klasse muss Zugriff zu eurer Frustum-Culling-Variablen und seiner Unit haben. Es wird überprüft ob der Node sichtbar ist (IsBoxWithin). Ist dies nicht der Fall, so passiert nichts (auch seine Kinder werden dann nicht überprüft). Ist er sichtbar, so werden seine Polygon gezeichnet (falls er der kleinste Node ist). Außerdem werden dann alle seine Kinder dem selbem Test unterzogen (falls er nicht der kleinste ist). Dies geschieht jetzt mit allen Nodes, die in einem sichtbaren Node sind.

Dank unseres Baum-Schemas werde alle Nodes, die sich in einem nicht sichtbaren Node befinden erst gar nicht überprüft. Eure FPS-Zahlen können sich dann sehen lassen.


So dies zeichnet die Polygone. Jetzt zum zeichnen des Baumes selbst:

procedure TNode.draw;
var
  i:Integer;
begin
  if Frustum.IsBoxWithin(
     pos.x,pos.y,pos.z,
     size,size,size)=FALSE then exit;
  with pos do
  begin
    glBegin(GL_LINES);
      glVertex3f(x-size,y-size,z-size);
      glVertex3f(x+size,y-size,z-size);
      glVertex3f(x-size,y+size,z-size);
      glVertex3f(x+size,y+size,z-size);
      glVertex3f(x-size,y-size,z+size);
      glVertex3f(x+size,y-size,z+size);
      glVertex3f(x-size,y+size,z+size);
      glVertex3f(x+size,y+size,z+size);

      glVertex3f(x+size,y+size,z+size);
      glVertex3f(x+size,y-size,z+size);
      glVertex3f(x+size,y+size,z-size);
      glVertex3f(x+size,y-size,z-size);
      glVertex3f(x-size,y+size,z+size);
      glVertex3f(x-size,y-size,z+size);
      glVertex3f(x-size,y+size,z-size);
      glVertex3f(x-size,y-size,z-size);

      glVertex3f(x+size,y+size,z+size);
      glVertex3f(x+size,y+size,z-size);
      glVertex3f(x+size,y-size,z+size);
      glVertex3f(x+size,y-size,z-size);
      glVertex3f(x-size,y-size,z+size);
      glVertex3f(x-size,y-size,z-size);
      glVertex3f(x-size,y+size,z+size);
      glVertex3f(x-size,y+size,z-size);
    glEnd;
  end;
  if Length(children) > 0 then
  for i:=0 to Length(children)-1 do children[i].draw;
end;
procedure TOctree.drawOctree(drawPol,drawNodes:Boolean);
begin
  if drawPol then
  begin
    glEnable(GL_TEXTURE_2D);
    glEnable(GL_LIGHTING);
    MainNode.check;
  end;
  if drawNodes then
  begin
    glDisable(GL_TEXTURE_2D);
    glDisable(GL_LIGHTING);
    glColor3f(1,1,0);
    MainNode.draw;
    glColor3f(1,1,1);
  end;
end;


In den ersten Prozeduren gibt es nichts zu beachten, dort wird lediglich ein Node, wenn er sichtbar ist, veranschaulicht, indem er gezeichnet wird und der selbe Test wird mit seinen untergeordneten Nodes durchgeführt. In einer Engine ist das Anzeigen des Nodes ja eher Nebensache.

Die zweite Prozedur ist nun die "drawOctree" Prozedure. Sie überprüft, ob ihr die Polygone und/oder den Octree zeichnen wollt. Dies wird getrennt durchgeführt, damit wir die vielen StateChanges (glEnable..) vermeiden, da dies unnötig Performance kostet. Sie führt dann die jeweilige Überprüfung mit dem MainNode durch, da unsere oberen Prozeduren dann voll automatisch weiter machen (ist dies nicht wunderbar).


Eigentlich wär's das, ihr müsstet nur noch eure Nodes am Ende des Programms aus dem Speicher entfernen. Da ihr alle Nodes mit der Prozedur New() erstellt habt müsst ihr diese nun mit Dispose() für ein und alle mal "vernichten" (auch "Speicherfreigabe" genannt):

Procedure TNode.clear;
var
  i:Integer;
begin
  if Length(children) > 0 then
  for i:=0 to Length(children)-1 do children[i].clear;
  setLength(children,0);
  Dispose(@self);
end;
Destructor TOctree.Destroy;
begin
  MainNode.clear;
  inherited Destroy;
end;


Hier seht ihr wieder eine sich selbst aufrufende Prozedur. Mit "Octree.destroy" wird der MainNode als erster zur Vernichtung geschickt.

Der Algorithmus in "clear" sorgt dafür, dass ein Node erst gelöscht wird, wenn seine Children gelöscht wurden. Diese werden erst gelöscht, wenn deren Children gelöscht wurden usw.


Das wars ihr habt einen voll funktionsfähigen Octree.

In eurem Programm müsst ihr nur noch auf folgendes achten:

  • ihr müsst eine Variable erstellen z.B. "octree : TOctree"
  • erst müsst ihr am Anfang des Programms eure Vektordaten laden
  • diese müssen dann in ein Array gespeichert werden : in eine Polygon-Array "polygons" (TPolygon)
  • dann könnt ihr erst euren Octree initialisieren, da die Daten der Vektoren für die Berechnung nötig sind


Beim Zeichnen nur noch darauf achten, dass erst die Kamera positioniert wird (glTranslatef und glRotatef), dann muss das Frustum berechnet werden und dann könnt ihr ohne Sorge "octree.drawOctree" aufrufen, dieses zeichnet dann die Polygone. Falls ihr Texturen wünscht, dann diese vorher einbinden.

Schluss

Wie ihr seht war dies ein ganzes Stück Arbeit und dieses Tutorial ist letztendlich doch noch zu seinem Ende gekommen.

Es wird sicher Alles nicht sofort bei euch klappen, da es auch eine Rolle spielt, wie euer Programm aufgebaut ist.

Ich bitte um viel Feedback, damit ich sehe wo es Probleme in meiner Formulierung gab. Es würde mich freuen, wenn es wenigstens bei einer Person klappt, denn dann hat sich meine Mühe für dieses Tut gelohnt.

Also wenn es bei euch läuft sagt mir Bescheid. Mich würde auch der Frame Unterschied zu vorher interessieren.

Wenn ihr Probleme habt, ich bin für euch da ;-) Eshat_at_gmx.net


Euer

Eshat aka SoulChild (shadow3d.delphigl.com)

Dateien


Vorhergehendes Tutorial:
-
Nächstes Tutorial:
-

Schreibt was ihr zu diesem Tutorial denkt ins Feedbackforum von DelphiGL.com.
Lob, Verbesserungsvorschläge, Hinweise und Tutorialwünsche sind stets willkommen.