Hallo,

bei meinem aktuellen Projekt stehe ich vor einem ernsten Geschwindigkeitsproblem.
Die Situation ist folgende: Ich habe ein Raster aus Würfeln (100x100x100 bisher) was sich recht oft (alle 100ms oder öfter) ändert und sich teilweise sehr stark vom vorherigen Zustand unterscheidet. Jeder Würfel gehört dabei zu einem von mehren Materialien und hat dementsprechend eine andere Textur. Dann gibt es noch eine oder mehrere Gruppen von Würfeln die sich unabhängig voneinander bewegen. Die Positionen der Würfeln in einer Gruppe sind untereinander fest, sonst könnte ich sie auch nicht zusammenfassen.
Das Problem ist jetzt, wie ich das ganze schneller zeichnen kann als bisher.

Im Moment gehe ich so vor, dass ich das Raster in größere Quader zerlege und die mit dem Immediate-Modus zeichne. Ich hatte es auch probiert alle Würfel in ein VBO zu packen, aber das Füllen dauert länger als das aufteilen in die Quader. Natürlich könnte ich auch die Quader dann in ein VBO packen, aber das Problem sind vielmehr diese Zeitpunkte an denen sich das Raster ändert. Dann hatte ich die Idee mit Hilfe von Geometrie-Shadern die Würfel aus einzelnen Punkten heraus zu entwickeln. Zum Test hatte ich mal nur einen Punkt pro Würfel in das VBO geschrieben, was allerdings auch langsamer war als die erste Variante.

Dann sind da noch die bewegten Würfel. Die werden in ein VBO geschrieben, weil es davon (meistens) nur wenige gibt. Da würde sich ein Geometrie-Shader wohl lohnen, wobei ich mich damit aber noch ein bischen beschäftigen muss, weil ich noch nie einen verwendet habe.

Also besonders beim ersten Teil bedarf noch einiges an Optimierung, da dort ein Viertel der gesamten Rechenzeit verloren geht, beim Teil mit den bewegten Würfeln etwa 20%. Im Moment läuft das ganze noch relativ flüssig, auch wenn man eben immer Mikroruckler drin hat, wenn gerechnet wird. Allerdings war es Anfangs so gedacht, dass das Raster um ein vielfaches größer ist.

Ich würde erstmal versuchen, die Würfel nach Texturen bzw. Materialien zu sortieren, damit du die an in größeren Stücken zeichnen kannst. Dann würde ich weiterhin auf VBOs setzen und die aktualisierungen mittels glBufferSubData durchführen, sodass du nicht dauernd das komplette VBO neu schreiben musst. Eventuell lohnt es sich auch, die VBOs nach Materialien aufzuteilen oder die Materialinfos per Vertexattribute zu übergeben und den rest vom Shader erledigen lassen.

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Ich nehme mal an das du bei deinen 1 Mio Würfel (!) bereits einen hierarchischen Sicherbarkeitstest durchführst, oder? (Gut ich weiß jetzt nicht genau wie die sich bewegen, wenn du ständig den Baum aktualisieren musst, bringt der Sichtbarkeitstest natürlich nix)

Bevor du mit Geometrie-Shadern anfängst solltest du Instancing in Betracht ziehen. Du renderst alle gleichartigen Würfel in einem Rutsch. Im Vertexshader ließt du die ModelViewMatrix aus einem Texturbuffer-Objekt oder wenn möglich baust du dir die Matrix erst im Shader.
Beim Geometrieshader sollte die Menge der Input-Geometrie in der Größenordnung ungefähr genauso groß wie die Menge der Output-Geometrie sein. In deinem Fall erzeugst du aber aus einem Vertex gleich 24 Vertices (TringleStrips: 6 * 4 Vertices). => Instancing ist sicher schneller.

Da die ModelViewMatrizen in einem Textur-Bufferobjekt sind, könntest du dieses auch direkt auf der Grafikkarte verändern. Also die Postionsberechnungen für die Würfel auf der GPU machen. (Wie gesagt ich weiß nicht was du da genau machst...)

_________________
Yeah!

Danke erstmal für die Antworten.

@Lord Horazont:
Sortiert werden die Würfel schon, das Problem war vielmehr die Menge der Geometry. Die Idee mit "glBufferSubData" könnte da schon helfen, besonders bei dem großen Raster. Außerdem kann ich wirklich das eine paar Texturkoordinaten (für die Markierungen an den Würfelkanten) aus der Position generieren und könnte das im Shader machen.

@Coolcat:
Also von den 1Mio möglichen Würfeln werden sicher nicht alle gezeichnet. zB sind einige aus "Luft", d.h. vollständig transparent und brauchen nicht gezeichnet zu werden. So reduziert sich die Anzahl bei meinem Testbeispiel auf etwa 40000, was aber eher eine untere Grenze ist.
Am Anfang hatte ich die Würfel in einem OcTree drin, das ging bei dem Raster recht gut. Allerdings ist das relativ sinnlos, wenn trotzdem sehr viele Würfel gezeichnet werden, sodass ich auf die Unterteilung in Blöcke umgestiegen bin. Das geht jetzt auch (noch) ganz gut ohne Sichtbarkeitstest weil die Geometrie recht einfach ist.

Instancing ist auch so eine Sache die ich noch nie probiert hatte. Aber wenn du sagst, dass das schneller sein wird, werd' ich das mal als nächstes versuchen, besonders da meine Versuche mit Geometry-Shadern noch nicht so erfolgreich waren.

Diese Gruppen von Würfeln die sich bewegen, haben eigentlich nur eine Lebensdauer von 100ms. Danach werden sie gelöscht. Im folgenden Rechenschritt wird möglicherweise eine neue Gruppe erzeugt die vollständig aus den alten Würfeln besteht. Es kann aber genauso sein, dass neue hinzukommen oder alte entfernt werden. Für Variable größen bei denen die obere Schranke zu hoch ist, ist mir aber nichts besseres eingefallen als immer das VBO neu zu erzeugen.

Aber auf alle Fälle werde ich mir das mal mit Instancing anschauen. Mal sehn wie ich das für mein Problem verwenden kann.

Noch so eine Idee:
Deine VBOs ändern sich wenn dann nur alle 100 ms, richtig? Wäre es möglich das schreiben der VBOs bzw. die Berechnungen über mehrere Frames zu verteilen, oder in einen anderen Thread zu verlagern? Das würde diese "Mikroruckler" vermindern, weil die Frames gleichmäßiger sind.

(Achtung: OpenGL ist nicht multithread-fähig, alle OpenGL-Zugriffe müssen im selben Thread erfolgen bzw. du musst selbst für die Synchronisation sorgen!)

_________________
Yeah!

Wenn man 40.000 Würfel zeichnet, ist die Wahrscheinlichkeit, dass sie alle gleichzeitig zu sehen sind, doch recht klein. Also ich meine, sie werden einander verdecken, oder? Da fällt mir ein Stichwort ein: Occlusion Culling.

http://www.gamasutra.com/features/20020717/bacik_01.htm
http://www.gamasutra.com/features/19991109/moller_haines_01.htm

@Coolcat:
Also eigentlich kann sich auch häufiger etwas ändern. Ich hab mir auch schon überlegt ob ich die Änderungen durch den Benutzer aufsammel oder die "eigenständigen" Aktionen des Computers nur zu bestimmten Zeitpunkten erfolgen lasse. Dann hätte ich nur alle 100ms die Berechnungen zu erledigen. Mit deiner Idee würde das natürlich einiges ausmachen.
Dann bräuchte ich eine Kopie der Daten und würde im HauptThread nur noch die VBOs aktualisieren oder?

Ich hab' auch mal nach Tutorials zu Instancing gesucht. Leider scheint es da nicht viel zu geben oder ich hab' die falschen Suchbegriffe verwendet.
Wenn ich das richtig verstanden habe gibt es bei OpenGL 2.1 noch kein richtiges Instancing? Von Nvidia gibt es ein Paper zu "Pseudo-Instancing", wobei ich das schon ziemlich pseudo finde. Entweder ich brauche für jeden Würfel einen eigenen DrawCall oder ich pack' mehrere (gleiche) Würfel in ein VBO. Dann hätte aber einige Würfel dabei die zu viel sind? Die könnte ich natürlich einfach degenerieren, sodass sie nicht sichtbar sind.
Oder hab' ich da was falsch verstanden?

@Traude:
Ich hab' die Links jetzt erstmal nur überflogen... naja zumindest die Bilder angeschaut.
Aber ich denke so den Grundgedanken habe ich schon verstanden.

Genau.


Bei Instancing führst du einen DrawCall einfach in einer Schleife aus. Der Witz dabei ist das die Schleife auf der Grafikkarte läuft und das damit quasi genauso schnell ist wie als wäre alles an einem Stück.

Die Extension heißt GL_ARB_draw_instanced. Das ganze funktioniert eigentlich ganz leicht:
Statt dem normalen DrawCall nimmst du einfach glDrawArraysInstancedARB bzw. glDrawElementsInstancedARB. Beide funktionieren genau wie die normalen Funktionen, haben nur einen Parameter mehr. Der neue letzte Parameter gibt an wie oft das Objekt gerendert werden soll.
Im Shader hast du dann eine neue Variable, nämlich gl_InstanceIDARB. Das ist einfach der Schleifenindex. Üblicherweise will man alle Objekte an einer anderen Stelle rendern, also braucht jedes Objekt seine eigene ModelViewMatrix. Sofern ein Array von Uniform-Variablen nicht ausreicht nimmt man dafür einfach ein TexturBufferObjekt (Extension: GL_ARB_texture_buffer_object) in dem du für jede "Instanz" eine Matrix speicherst. TexturBufferObjekte (TBO) sind wie 1D-Texturen, nur ohne Interpolation und mit einer erlaubten Maximalgröße von 2^27. Vom Prinzip also einfach ein Array. Du greifst einfach an der Stelle gl_InstanceIDARB auf das Array (aka TBO) zu.

Wenn du wirklich eine Matrix speichern willst und nicht nur die Position o.ä. brauchst du natürlich die Elemente 4 * gl_InstanceIDARB + 0, ...bis..., 4 * gl_InstanceIDARB + 3 jeweils vom Typ GL_RGBA32F_ARB (Extension: GL_ARB_texture_float) und musst dir daraus im Shader die Matrix zusammensetzen. Nur die Position speichern spart natürlich eine Menge beim beschreiben des TBOs.

_________________
Yeah!

Noch was zum Occlusion Culling:
In meinem Thesisprojekt ist ein Teil ebendies. Und zwar kommt da der Algorithmus CHC zum Einsatz, der dann noch ggf. zu CHC++ erweitert wird:
http://www.cg.tuwien.ac.at/research/vr/chcull/
http://www.cg.tuwien.ac.at/research/pub ... -2008-CHC/

Ich habe jetzt die Berechnung in einen eigenen Thread ausgelagert. Immerhin hat sich damit die Framerate unter Last um 50% erhöht und die Wartezeit bei Änderungen hat sich halbiert, wodurch es nicht mehr so ruckelt.

Außerdem hab ich mich mal an Instancing versucht. Es funktioniert auch soweit. Im Moment schreibe ich die Positionen noch in eine normale Floatingpoint-Textur, was aber wieder ganz schön langsam ist. Da ich das Raster mehrere male durchgehen muss damit ich die Materialien hintereinander in die Textur bekomme, produziert das eigentlich unnötigen Mehraufwand. Außerdem müssen die Daten dann ja noch in die Textur kopiert werden.
Hm, da fällt mir gerade noch eine bessere Möglichkeit ein... mal testen.

Edit: Naja gut, jetzt muss ich das Raster nur noch 2 mal durchgehen, aber so der Hammer ist das auch noch nicht.

Edit2: Mir ist noch eingefallen das meine Variante zum Zusammenfassen der Würfel zu größeren Quadern, um die Geometrie zu reduzieren, auch in den Rechen-Thread rein kann. Damit habe ich wieder einen Großteil der Rechenzeit eingespart, sodass nurnoch das VBO für die bewegten Blöcke im Hauptthread erstellt werden muss, was für die rund 10000 Würfel 7-8 ms dauert. Ich würde sagen damit ist mein Problem fürs erste gelöst.