Tutorial Octree - Versionsgeschichte

Komoluna: Rechtschreibkorrektur des Edits vom 12.03.2005

2015-06-14T17:17:10Z

Rechtschreibkorrektur des Edits vom 12.03.2005

Thebubble: Im TNode: "numv" wurde zu "nump" umgeändert (es werden Polygone gezählt, nicht Vektoren), TNode.HowManyPolygons -> Add-Abfrage außerhalb der for-Schleife

2011-05-04T14:28:36Z

Im TNode: "numv" wurde zu "nump" umgeändert (es werden Polygone gezählt, nicht Vektoren), TNode.HowManyPolygons -> Add-Abfrage außerhalb der for-Schleife

DGLBot: Der Ausdruck ''\{\{DateiLink\|'' wurde ersetzt mit ''{{ArchivLink|''.

2009-05-17T09:02:12Z

Der Ausdruck ''\{\{DateiLink\|'' wurde ersetzt mit ''{{ArchivLink|''.

Flash: /* Dateien */

2009-05-02T19:17:42Z

‎Dateien

Flo: Abschnitt "Dateien" hinzugefügt.

2009-05-02T15:46:35Z

Abschnitt "Dateien" hinzugefügt.

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:13:54Z

Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.

Nico Michaelis: /* Let's get started */ Pascal Tags repariert

2007-02-13T08:56:05Z

‎Let's get started: Pascal Tags repariert

Flash: /* Schluss */ Navigation hinzugefügt

2006-01-18T12:43:51Z

‎Schluss: Navigation hinzugefügt

La Boda am 1. Januar 2006 um 19:25 Uhr

2006-01-01T19:25:46Z

Neue Seite

=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:

[[Bild:Tutorial Octree mainnode.jpg|left]] 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.
 
 
 
 
 
 
[[Bild:Tutorial Octree nodes.jpg|left]] 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:

<pascal>
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;
</pascal>

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:

<pascal>
unit Octree;

interface

uses
Windows, Messages, dglOpenGL, Globals;

Const
MAX_TRIANGLES_IN_NODE = 500;
</pascal>

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:

<pascal>
type PNode = ^TNode;
TNode = object
pos : TVertex;
size : glfloat;
numv : 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;
</pascal>

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 Vektoren, 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 :

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

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:

<pascal>
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;
</pascal>

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:

<pascal>
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].numv < 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;
</pascal>

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:

<pascal>
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;
</pascal>

</pascal>
function TNode.HowManyPolygons(const polygons : array of PPolygon; Add:Boolean):Integer;
var
i:Integer;
begin
numv:=0;
for i:=0 to High(polygons) do
if PolygonIn(polygons[i])then
begin
Inc(numv);
if Add then
begin
setLength(poly,numv);
poly[numv-1]:=polygons[i];
end;
end;
Result:=numv;
end;
</pascal>

[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 "numv". 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:

<pascal>
procedure TNode.drawPolygons;
var
i,j:Integer;
begin
if numv = 0 then exit;
glBegin(GL_TRIANGLES);
for i := 0 to numv-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;
</pascal>

<pascal>
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;
</pascal>

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:

<pascal>
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;
</pascal>

<pascal>
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;
</pascal>

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):

<pascal>
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;
</pascal>

<pascal>
Destructor TOctree.Destroy;
begin
MainNode.clear;
inherited Destroy;
end;
</pascal>

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 ([http://shadow3d.delphigl.com shadow3d.delphigl.com])

@@ Zeile 534: / Zeile 534: @@
 == Dateien ==
-* {{DateiLink|file=tut_octree_vcl|text=Delphi-VCL-Quelltext mit Windows Binaries}}
+* {{ArchivLink|file=tut_octree_vcl|text=Delphi-VCL-Quelltext mit Windows Binaries}}
 {{TUTORIAL_NAVIGATION|-|-}}
 [[Kategorie:Tutorial|Octree]]

@@ Zeile 534: / Zeile 534: @@
 == Dateien ==
-* [[Datei:tut_octree_vcl|Delphi-VCL-Quelltext mit Windows Binaries]]
+* {{DateiLink|file=tut_octree_vcl|text=Delphi-VCL-Quelltext mit Windows Binaries}}
 {{TUTORIAL_NAVIGATION|-|-}}
 [[Kategorie:Tutorial|Octree]]

@@ Zeile 533: / Zeile 533: @@
 Eshat aka SoulChild ([http://shadow3d.delphigl.com shadow3d.delphigl.com])
+== Dateien ==
 {{TUTORIAL_NAVIGATION|-|-}}
 [[Kategorie:Tutorial|Octree]]

← Nächstältere Version		Version vom 18. Januar 2006, 12:43 Uhr
Zeile 533:		Zeile 533:

	Eshat aka SoulChild ([http://shadow3d.delphigl.com shadow3d.delphigl.com])		Eshat aka SoulChild ([http://shadow3d.delphigl.com shadow3d.delphigl.com])
		+
		+
		+	{{TUTORIAL_NAVIGATION\|-\|-}}
		+
		+	[[Kategorie:Tutorial\|Octree]]

@@ Zeile 348: / Zeile 348: @@
 [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 ;)
+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 Implementation 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 entschuldige mich für meinen Fehler ;)
 [/EDIT]

@@ Zeile 123: / Zeile 123: @@
      pos       : TVertex;
      size      : glfloat;
-     numv      : Integer;
+     nump      : Integer;
      numc      : Byte;
      poly      : array of PPolygon;
@@ Zeile 145: / Zeile 145: @@
 *seinen Mittelpunkt --> Vektor
 *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
 *ein Array für die Polygone --> array of TPolygon
@@ Zeile 273: / Zeile 273: @@
        setLength(children,numc);
        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
          children[numc-1].smallest:=TRUE;
@@ Zeile 325: / Zeile 325: @@
    i:Integer;
 begin
-   numv:=0;
+   nump := 0;
-  for i:=0 to High(polygons) do
-   if PolygonIn(polygons[i])then
+   if Add then
    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
 end;
 </source>
@@ Zeile 348: / Zeile 354: @@
 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.
 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;
 begin
-   if numv = 0 then exit;
+   if nump = 0 then exit;
    glBegin(GL_TRIANGLES);
-     for i := 0 to numv-1 do
+     for i := 0 to nump-1 do
      for j := 0 to 2 do
      with poly[i].v[j]^ do

@@ Zeile 61: / Zeile 61: @@
 Am besten erstellt/benutzt eine Unit in der die Haupttypen definiert sind. Bei mir sieht diese folgendermaßen aus:
-<pascal>
+<source lang="pascal">
 unit Globals;
@@ Zeile 88: / Zeile 88: @@
 var
    Frustum:TFrustum;
-</pascal>
+</source>
@@ Zeile 96: / Zeile 96: @@
-<pascal>
+<source lang="pascal">
 unit Octree;
@@ Zeile 106: / Zeile 106: @@
 Const
    MAX_TRIANGLES_IN_NODE = 500;
-</pascal>
+</source>
@@ Zeile 118: / Zeile 118: @@
-<pascal>
+<source lang="pascal">
 type   PNode = ^TNode;
    TNode = object
@@ Zeile 136: / Zeile 136: @@
      procedure Clear;
    end;
-</pascal>
+</source>
@@ Zeile 162: / Zeile 162: @@
-<pascal>
+<source lang="pascal">
 TOctree = class
    public
@@ Zeile 170: / Zeile 170: @@
      Destructor Destroy;
    end;
-</pascal>
+</source>
@@ Zeile 182: / Zeile 182: @@
 Nun kommen wir zu der Initialisierungs-Prozedur, die den obersten Würfel um die ganze Szene berechnet:
-<pascal>
+<source lang="pascal">
 Constructor TOctree.Create(const polygons : array of PPolygon);
 var
@@ Zeile 211: / Zeile 211: @@
    MainNode.Divide(polygons);
 end;
-</pascal>
+</source>
@@ Zeile 222: / Zeile 222: @@
 Die untenstehende Prozedur teilt den Node in 8 kleine Würfel und überprüft, ob diese leer sind. Hier die Divide-Prozedure:
-<pascal>
+<source lang="pascal">
 Procedure TNode.Divide(const polygons : array of PPolygon);
 var
@@ Zeile 283: / Zeile 283: @@
      if children[i].smallest=FALSE then children[i].Divide(polygons);
 end;
-</pascal>
+</source>
@@ Zeile 300: / Zeile 300: @@
-<pascal>
+<source lang="pascal">
 function TNode.PolygonIn(p:PPolygon):Boolean;
 var
@@ Zeile 318: / Zeile 318: @@
    end;
 end;
-</pascal>
+</source>
-<pascal>
+<source lang="pascal">
 function TNode.HowManyPolygons(const polygons : array of PPolygon; Add:Boolean):Integer;
 var
@@ Zeile 338: / Zeile 338: @@
    Result:=numv;
 end;
-</pascal>
+</source>
@@ Zeile 359: / Zeile 359: @@
 So zeichnet ihr die Polygone eures Nodes:
-<pascal>
+<source lang="pascal">
 procedure TNode.drawPolygons;
 var
@@ Zeile 375: / Zeile 375: @@
    glEnd;
 end;
-</pascal>
+</source>
-<pascal>
+<source lang="pascal">
 procedure TNode.check;
 var
@@ Zeile 391: / Zeile 391: @@
    end;
 end;
-</pascal>
+</source>
@@ Zeile 407: / Zeile 407: @@
 So dies zeichnet die Polygone. Jetzt zum zeichnen des Baumes selbst:
-<pascal>
+<source lang="pascal">
 procedure TNode.draw;
 var
@@ Zeile 449: / Zeile 449: @@
    for i:=0 to Length(children)-1 do children[i].draw;
 end;
-</pascal>
+</source>
-<pascal>
+<source lang="pascal">
 procedure TOctree.drawOctree(drawPol,drawNodes:Boolean);
 begin
@@ Zeile 469: / Zeile 469: @@
    end;
 end;
-</pascal>
+</source>
@@ Zeile 479: / Zeile 479: @@
 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):
-<pascal>
+<source lang="pascal">
 Procedure TNode.clear;
 var
@@ Zeile 489: / Zeile 489: @@
    Dispose(@self);
 end;
-</pascal>
+</source>
-<pascal>
+<source lang="pascal">
 Destructor TOctree.Destroy;
 begin
@@ Zeile 497: / Zeile 497: @@
    inherited Destroy;
 end;
-</pascal>
+</source>