Sorry!, Smiley=Humor at least imho, kommt nicht wieder vor.

Hab mal ein wenig mit timeGetTime zeitgemessen, ich revidiere daher ein wenig. MAX_TRIANGLES_IN_NODE habe ich nämlich vorher mal auf 5000 hochgestellt, wobei der Aufbau des Octrees ~21s dauert. bei MAX_TRIANGLES_IN_NODE = 2500 dauerts auf meinem 2600+ bereits ~100s, was doch zu viel ist, besonders in Anbetracht dessen dass MAX_TRIANGLES_IN_NODE irgendwo bei 1024 liegen sollte (je nach Graka).

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Hast du ne erklärung für die miese Perfomance?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Tippe einfach mal darauf dass du zu viele Berechnungen machst. Werde morgen mal mit meiner Octree-Implementation vergleichen (bei selbem Polycount) und mir den Source dann mal genauer ansehen, evtl. finde ich dann den Hemmschuh.

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Hab dein Code mal laufen lassen.
function TOctreeNode.PolyInNode(const Poly : PTriangle):Boolean; wurde 341'835'776 mal ausgefuehrt.

Hier rufst du im Falle von StoreFoundInNode=true PolyInNode fuer jedes Polygon 2 mal auf, das koennte man sicher noch anderst loesen.

Die Frage ist, warum man bei einer Heightmap einen Octtree benutzt. Ein Quadtree wäre völlig ausreichend. Bei dem Quadtree und der Heightmap ist die Zuordnung zu den Nodes auch sofort klar, ohne daß etwas gerechnet werden müßte.
Anstelle von dynamischen Arrays bietet sich auch TList an.
Die Sache mit dem PTriangle=array[0..2] of PFullVertex find ich ziemlich seltsam gelöst.
Beim Destructor fehlt das override. Er wird daher bei Free nicht aufgerufen.
Das array kids, kann man fest mit 0..7 deklarieren, dann kann man sich das setlength sparen.
Das Erstellen von den tempnodes kostet natürlich auch Zeit.
Die Methode PolyInNode ist falsch, weil hier nur getestet wird, ob ein Punkt im Würfel liegt.

NumPolysInNode scheint die meiste Zeit zu kosten.

Das mit dem Quadtree für ein Terrain stimmt schon, aber man weiß ja nicht was Flash da vorhat. Wenn er (ich gehe mal davon aus) ein RTS machen will, dann kann er wenn er nen Octree verwendet auch gleich Gebäude und andere statische Objekte mit in den Octree packen. Da würde dann bei einer festen isometrischen perspektive allerdings auch ein Quadtree reichen, da man ja immer quasi keinen Sichtbarkeitstest auf der Höhenachse vollführen muss.

Aber du hast da in deinem Code einige recht unnötige Schleifen, wo du z.B. zwei Schleifen nutzt, um Sachen zu tun die man auch in einer Schleife machen könnte. Hab mal (ausser der oben von mir erwähnten direkten Nutzung des dynamisches Arrays, statt des Pointers) einige Optimierungen vorgenommen und konnte die Zeit so von ~21 auf ~15s verbessern, aber ich glaube du hast da eher ein grundlegendes Problem beim Aufbau des Octrees an sich.

Siehe z.B. dein (von obigen Postern angesprochenes) NumPolysInNode. Da wäre es doch viel angebrachter und performanter, direkt beim Erstellen des Octrees die Zahl der im Knoten vorhandenen Dreiecke anzupassen, statt diese später über eine rechenintensive Funktion zu ermitteln. Wenn ein Polygon also einem Knoten zugewiesen wird, einfach dessen NumOfPolys-Variable erhöhen, und die angesprochene Funktion kannst du dir ganz sparen.

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Zum Frustum Culling dürfe es ja auch so ausreichen die Dreiecke gleich bei der Erstellung aus der Heightmap zu 16x16 oder 32x32 Objekten zu gruppieren und dann nur aus diesen Objekten einen Baum zu bauen.Die Dreiecke haben ja schon eine gewisse Struktur. Es bringt ja nichts, wenn man sie auseinander reißt um danach teuer mit dem Octtree wieder Nodes zu bauen.
Allerdings hat das nichts damit zu tun, dass der Octtree zu langsam ist. Eventuell alles löschen und nochmal komplett neu anfangen.

Soweit ich das sehe, wird das Ganze extrem langsam, weil bei jedem Node sämtliche Polygone wieder überprüft werden, ob sie drin liegen oder nicht - das ist natürlich unnötig, und macht die Sache mit jedem Rekursionsschritt um ein Vielfaches langsamer, da die Polygone von Kindnodes logischerweise nur aus deren jeweiligem Elternnode stammen können. Ganz allgemein würde ich sagen, dass die Vorlage eher als Orientierungshilfe zu sehen ist, als dass man tatsächlich eine eigene Implementierung daraus ableiten sollte - die Sache mit den einzelnen Zeigern für jeden Schnittpunkt verhindert die Verwendung von VBOs oder Vertex Arrays und verkompliziert die Sache unnötig, mal abgesehen davon, dass du spätestens weitere Probleme bekommst, wenn du diese Struktur speichern möchtest.

Wenn ich dir einen Tipp geben darf: überleg dir, wie ein Octree funktioniert (das Prinzip wird ja auch im Tutorial nicht schlecht erklärt) und schreib die Klasse neu. Im BaseLevelBaker verwende ich z.B. überhaupt keine Zeiger, weder für die Nodes des Octrees, noch für die Schnittpunkte aus denen die Dreiecke zusammengesetzt werden, sondern verwende in beiden Fällen Indizes in ein eindimensionales Feld. Erstens kann ich so Vertex Arrays nutzen, zweitens lässt sich das ganze sehr leicht speichern und drittens genügt eine einfache For Schleife, wenn irgendwelche Operationen mit jedem Node durchgeführt werden sollen. Außerdem ließen sich PVS Informationen nicht in einer Bittabelle ablegen, wenn nicht jeder Node über einen eindeutigen Index referenziert werden würde.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Ich würde ja sowieso vom Occtree abraten, oder zumindest vom reinen Occtree. Für einzelne Objekte mag das ja z.B. zur Geschwindigkeitssteigerung bei der Kollision (UT2003) eine Möglichkeit sein, aber bei einem ganzen Level sind die regelmäßigen Unterteilungen einfach zu willkürlich und passen auch nicht zur Geometrie. Die acht Unterknoten machen das ganze zusätzlich noch aufwändig, wenn man z.B. von vorne nach hinten rendern will, wie man es sollte. Es reicht doch völlig aus, wenn man die ganze Polygonmenge, falls man wirklich nur freie Dreiecke hat, in zwei annähernd gleich große Hälfen teilt, die durch irgendeine passende Ebene getrennt sind.
Auch einen Occtree mit Zeigern auf die Knoten kann man in einem Durchgang Laden bzw. Speichern, ohne dass man eine zusätzliche Liste benötigt um die Referenzen aufzulösen, denn die Links gehen ja üblicherweise nur in eine Richtung. Außerdem sind Zeiger zur Laufzeit schneller als ein Index in einer Liste.
viewtopic.php?t=1527&highlight=occtree+speichern

Verderbe dir nur ungern den Spaß, aber habe es grade mit einer von mir verwendeten Octree-Implementation getestet, die auf der von http://www.gametutorials.com basiert, und da brauche ich um deine Heightmap (da die Dreiecke dort zerteilt werden sinds am Ende fast 400.000) in einen Octree zu pflanzen grade mal 0,5s. Die Zahl der maximalen Dreiecke pro Knoten lagen bei 256.

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Hmm, es zwingt einen ja niemand den Octree direkt beim Durchlaufen zu rendern - man kann z.B. die sichtbaren Knoten (wenn zusätzlich noch PVS Informationen drinne stecken, sollten dies ja gar so viele ohnehin nicht sein) auch auffangen und nach Belieben von vorne nach hinten (oder auch nach Renderstates) sortieren. Auch für mehrere 100 Knoten fällt der hierfür benötigte Rechenaufwand kaum bis gar nicht ins Gewicht. Ebenso ist es mit der Auflösung eines Index in ein Array: ob das jetzt einen oder zwei Taktzyklen mehr (für einen zusätzlichen Schiebebefehl oder Multiplikation vor der Dereferenzierung) benötigt, ist an sich bereits bei einem 486er völlig egal - schließlich werden diese Operationen maximal einige 1000 mal pro Frame ausgeführt - genausogut könnte man sagen, dass ein Feld Cache effizienter ist, als irgendwelche Daten, die wild verstreut im Speicher herumliegen - zumal Kindnodes dann meist direkt hinter den Elternnodes im Feld liegen, aber das ist dann wirklich Haarspalterei .

Das Schöne am Octree ist halt, dass man sich überhaupt nicht um die Geometrie kümmern muss - gute Teilungsebenen findet man ansonsten nur bei Daten die in irgendeiner Weise systematisch sind (was bei einem Heightfield natürlich der Fall ist) - und wenn man sich keinen aufwändigen Leveleditor (der z.B. mit konvexen Brushes arbeitet) schreiben möchte, wirds wahrscheinlich ziemlich rechenaufwändig. Inwieweit ein Octree für weitere KI brauchbar ist (Physik und Kollisionserkennung sollten gut funktionieren, bei Pathfinding bin ich mir nicht so sicher - immerhin tue ich mir z.B. recht leicht, herauszufinden, ob ein Objekt von einem anderen Objekt aus gesehen überhaupt sichtbar sein kann), hängt natürlich auch von der jeweiligen Anwendung ab.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Ok, wenn es an den Indizes hängen sollte hat man vermutlich auch noch ganz andere ernsthaftere Probleme im Programm. Trotzdem würde ich eher die Zeiger bzw. Objekte bevorzugen, weil man dann nur eben einen Zeiger hat, den man weitergeben muß und nicht das Array und den Index.
Bei so freien Kugeln ist das natürlich was anderes, aber die meisten Spieleszenen haben irgendeine Struktur. Das Problem ist, daß so eine Unterteilung dann z.B. genau vor eine Wand fallen kann, es sei denn man baut in 2er Potenzen, und dann ist der Bereich vor und hinter der Wand im gleichen Knoten, obwohl er nicht zusammengehört. Mit den Teilungsebenen meinte ich Ebenen aus der Gemetrie selber, oder aus den BBoxen der Objekte, falls vorhanden, so daß man da Schnitte ziehen kann, die ungefähr die Struktur wiederspiegeln.

Hmmm...also für mich heißt dass erstmal "Code wegwerfen, als Praxisnahe Übung verbuchen und nochmal schreiben."

War mein erster Octree. Ich hoffe die nachfolgenden sind schneller. Ich hab einfach versucht, Shadows COde auf meine Datenstruktur umzubauen. Das Prinzip is bei mir rübergekommen, aber die intelligente Optimierung is dabei wohl untergegangen.

Gibts paar generelle Tips, wie man am besten einen Octree(is ja nicht viel anders, als ein Quadtree) aufbaut, damit man damit Landschaften/Karten günstig speichern und rendern kann?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Sehe ich auch so.

Wie wäre es wenn du ausgehend von deinem größten Dreieck(durch LODkannst du ja einige zusammenfassen) das Bild von anfang an her in Lauter Qudrat ische Bereiche unterteilst. Und ihre Polygonzahl in einer Eigenschaft/Funktion festhälst.(Vielleicht auch noch in abhängigkeit eines Faktors).
Dann werden immer 4 solcher Grupperungen als Unterknoten eines obern genommen, falls sie nicht schon eine gewisse Polygonzahl erreichen. Das ganze machst du dann immer weiter bis du nur noch einen/den letzen Knoten hast.

Vielleicht wäre es sogar vorteilhaft erst die Knoten zu bilden(vom Überkonten zu Unterknoten), und ihnen nacher die Dreiecke zuzuweisen. Und diese nacher nach der oben beschrieben Regel zusammenzufassen, wobei du die Knoten ansich nie löscht. Stattdessen werden sie einfach so wie sie sind zeichnest, allerdings als Einheit überprüft.

Eine 512*512 Highmap zerlegst du dan so:
1
4
16//Stopp. da GesamteMaximaleAnzahl/16 zu wenig ist. Die gesamte Maximale Anzahl könntest du villeicht so berechnen: (512-1)² *2

Nun werden die einzelen Knoten auf Basis der Highmap Größe gebilet:
Erster Knoten 0..512 und 0..512
Wenn du diesen Unterteilst hast du 0..256 und 0..256 als ersten Knoten, 0..256 und 256..512 als zweitenn Knoten usw.

Müßte eigentlich klar sein wie das geht...
MfG
IFlo

_________________
Danke an alle, die mir (und anderen) geholfen haben.
So weit... ...so gut