Octree erstellen und befüllen - Optimierungen?

[Tiwaz]

Moinsen,

 

ich hab seit ner gefühlten Ewigkeit endlich mal wieder ein kleines bisschen Zeit gefunden an meiner VoxelEngine weiter zu arbeiten ^^

Dabei hab ich rausgefunden, dass beim Generieren des Octrees noch deutlicher Optimierungsbedarf besteht. Das sollte so performant wie möglich sein, weil hier unglaublich viel Zeit drauf geht.

 

Liegt daran, dass ich damals sehr naive Ansätze implementiert habe, um es einfach mal zum laufen zu bringen, also die Densities werden z.B. für jeden Voxel und jede Corner neu berechnet (nichts gebuffered)

Außerdem wird der Octree rekursiv Top-Down gebaut, was aber momentan noch nicht so krass ins Gewicht fällt.. Wäre aber auch hier offen für bessere Alternativen. Ist Morton Order da das richtige Stichwort?

 

Das Ganze ist bisher natürlich wahnsinnig ineffizient und ich würde das gerne in der kommenden Zeit verbessern, wobei ich mir grade irgendwie einfach keinen geeigneten Buffer vorstellen kann.

Ist ein einfaches (3D) Array am besten oder gibt es bessere Datenstrukturen?

Und wie befülle ich den Buffer am besten? Sollte ich für den kompletten Octree alle Densities zum Generieren buffern oder doch anders? Layer by Layer z.B.?

Wäre da die GPU sinnvoll bzw. wie könnte ich überhaupt ein 3D Array auf der Grafikkarte befüllen lassen? Kann ich dazu Compute Shader benutzen oder brauch ich Plugins oder andere Tools?

Fragen über Fragen, die ich auch nach ein paar Stunden Recherche nicht ohne weiteres beantworten kann, deswegen versuche ich mal mein Glück im Forum, vllt weiß jemand was gutes dazu

 

Das Erstellen der Octrees muss hald so schnell wie möglich gehen, weil oft Chunks (und somit Octrees) nach oder neu geladen werden und sich das dann schnell bemerkbar macht..

 

Vielen Dank im Voraus

 

@edit:

Hab jetzt mal einen kleinen obligatorischen, temporären 3D Buffer für die Densities eingebaut und spar mir momentan bei einem 16x16 Chunks (à 16³ Voxel) Terrain satte 35% an (Gesamt-)Zeit, ohne zusätzlich Speicher zu verbrauchen.

Könnte ich die Densities jetzt noch irgendwie auf der GPU berechnen lassen, wäre der Zeitgewinn sicher noch größer ^^

Aber nicht mehr heute..

[Mark]

D hasts schon angesprochen, Morton Order/Z Kurven, versuche es einfach mal Mit Lookup Tables rocken die derb.

[Tiwaz]

Okay, da muss ich mich noch mehr einlesen ^^

Aber ich versteh irgendwie nicht wie ich die Morton Order zur Octree Construction nutzen kann, weshalb ich bisher auch noch nicht wirklich ernsthaft damit beschäftigt hab.

Ich hätte da ein paar Fragen zum Verständnis..

 

Wenn ich das richtig verstanden hab, kann man ja mit der Morton Order Elemente eines n-dimensionalen Raums (Octree-Leaves) in einem eindimensionalen Buffer abbilden und später durch Bit Interleaving gegebener Weltkoordinaten eines Leafs auf die Position im Buffer schließen, richtig?

 

Und prinzipiell kann man damit auch einen Octree aufbauen, sofern man seine Density Map hat, richtig? (Auch wenn ich noch nicht genau weiß wie, aber ich hab's schon paar mal gelesen)

Also ich könnte dann z.B. die Density Map/den Density Buffer des Octrees auf der GPU berechnen/füllen lassen (theoretisch.. kA ob das in Unity geht?) und auf Grund des Werte im Buffer dann den Octree mittels Z-Kurven aufbauen?

 

Und kann ich dann Octrees genau so leicht bearbeiten wie wenn ich sie Top-down erzeuge?

Bzw. hilft mir der Morton Code dann auch dabei an einen bestimmten Leaf-node zu kommen wenn ich dort Daten verändern will? Oder geht's da schneller wenn ich mir einfach die Referenz auf den Root halte und da schnell zum Leaf "traversiere"?

[Mark]

Puhhh ich hab schon ewig nichts mehr damit gemacht, aber im Grunde war es so dass du je nach Stelle der Bits ein Level im Octree hast. Merke grade dass ich echt kaum noch was dadrüber weiß, daher schmeiß ich einfach mal alles was ich an Quellcode dazu habe hier rein:

 

http://ideone.com/zQcMmB

http://ideone.com/0xXccf

 

Je nach Level im Octree kannst die ersten (Dimension * Level) Bits weg maskieren. Aber mir fehlt da viel Wissen :/

[Tiwaz]

Huiuiui, ich find so Bitshifting Gedöns auf den ersten Blick immer sehr kryptisch, vorallem wenn dann auch noch so Hexadezimale Bitmasks dran gebastelt werden ^^

Aber danke dafür Ich versuch mal es zu verstehen, wenn ich mehr über die Morton Order und Morton Code weiß

 

Ich kann die Morton Order nur leider bis dato irgendwie noch nicht so ganz einordnen.. Also wie mein Programmablauf dann aussehen muss und wo ich die MO dann brauche. Momentan baue ich ja, wie gesagt, den Octree Top-Down und generiere die Densities on-the-fly..

Wenn ich mir das richtig überlegt habe, müsste ich aber die Density Berechnung strikt von der Octree Construction trennen und davor schieben, was ich jetzt wohl auch als erstes machen werde, weil ich das so oder so noch machen wollte ^^

 

Naja, ich schau einfach bei Zeiten mal aber whs erst frühestens iwann nächste Woche, weil jetzt noch 2 Prüfungen anstehen ^^

 

Da gibt's dann sowieso noch einiges zu optimieren, auch was den Programmablauf selbst angeht habe ich gemerkt und zu guter letzt (irgendwann wenn der Rest passt) muss ich auch noch die Meshing Funktion mal weiter entwickeln, damit da LOD sauber läuft..

Jaja, das Ding wird noch ne Weile eine Baustelle bleiben

 

Was mich hald jetzt im Moment noch sehr interessiert ist eben, ob ich die Densities irgendwie auf der GPU berechnen lassen kann oder ob das überhaupt sinnvoll ist. Ginge das mit Compute Shadern?

Ich hab ja so ne Density-Funktion, die ich unabhängig von einander X-tausend mal pro Chunk aufrufe.. Das schreit mich irgendwie förmlich an es auf der GPU laufen zu lassen.

 

@edit:

Ich hab grade ein bisschen was zu Compute Shadern gelesen und ich glaube, dass man die Octree Construction grade in Verbindung mit Morton Code brutalst schnell machen kann..

Da werde ich mich in Zukunft mal noch besser informieren und versuchen das umzusetzen.

[Tiwaz]

Wow, ich hab jetzt noch hier und da ein bisschen rumgewerkelt aber eigentlich nichts großartiges geändert, also ich hab keinen neuen Algorithmus implementiert und zwecks der Morton Order hab ich leider auch noch nicht mal Zeit gefunden mich da richtig einzulesen.

 

Jedenfalls hab ich das Projekt testweise ein paar Mal gebuildet und laufen lassen und während im Editor ein Chunk ca. 18ms braucht, läuft ein Chunk im Build bei 8-9ms durch komplett..

Für 4737 Chunks (1km x 1km großes Terrain) dauert das Generieren knappe 36Sek und das Meshen 7sek (Verts + Triangles berechnen und Mesh + Collider generieren)

Macht ca. 9ms pro Chunk.

Singlethreaded (also es läuft alles im Unity Main thread) und ohne LOD btw.

Und ich glaube ich könnte die Generierungszeit durch ein paar Tweaks am Programmablauf nochmal ziemlich drücken. Hab mir zumindest eingebildet, dass da noch ein paar Redundanzen drin sind..

 

Und falls es jemanden interessiert:

Die Menge an Chunks braucht übrigens ~1GB RAM, allerdings hab ich bisher nur geschaut die Performance zu optimieren, also geht da auch noch einiges ^^