Instancing Buffer in Compute Shader generieren

Für Fragen zu Grafik APIs wie DirectX und OpenGL sowie Shaderprogrammierung.
Antworten
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Ich möchte Vegetation rendern und das per Instancing machen. Die Idee ist, dass ich ein großes Terrain habe und eine Textur soll für jedes instanziierte Modell (Grasbüschel, Stein, Blume, Äste, etc.) die Dichte des Bewuchs angeben (z.b. als Instanzen pro m^2). Ich will dann in jedem Frame per Compute Shader anhand der aktuellen Kameraposition die entsprechend tatsächlich sichtbaren Instanzen generieren und rendern. Also z.B. 1000 Grasbüschel im Vordergrund des Sichtfeldes generieren.
Die Idee ist, dass ich ein Gitter von vielen möglichen Positionen durchgehe und für jede Position zufällig, aber nach Wahrscheinlichkeiten aus der Dichtetextur eine Instanz erzeuge. D.h. ich speichere nirgendwo eine Liste aller Positionen aller Instanzen und wähle die nähesten n aus, sondern ich generiere die Positionen zur Laufzeit. Die Dichtetextur muss also nicht hoch aufgelöst sein, und das Terrain kann beliebig groß sein, bei konstanter Laufzeit und konstantem Speicherbedarf, weil immer nur Positionen in der Nähe der Kamera on-the-fly generiert werden. Das erfordert etwas Trickserei damit die beim Bewegen der Kamera stabil bleiben und nichts flimmert, aber das sollte lösbar sein.

Eigentlich ist also alles klar, aber an einer Stelle bin ich mir unsicher, wie man es richtig implementieren würde. Sagen wir, mein Gitter hat 1024^2 Positionen und ein Compute Shader soll jetzt für jede Position anhand der Dichte entscheiden, ob eine Instanz erzeugt werden soll oder nicht. Am Ende will ich z.B. 1000 Blumen rendern, verteilt gemäß der Dichtetextur. Ich habe also ganz viele Compute-Shader Threads aber nur ein Bruchteil davon erzeugt tatsächlich Instanzen (und berechnet dafür eine Position, eine Farbe, eine Skalierung, etc.). Wie befülle ich dann den Instancing-Buffer? Die Werte müssen ja alle hintereinander im Speicher liegen.
Das Offensichtliche wäre ein Atomic-Counter, mit dem kann ich für jeden Thread den nächsten freien Eintrag finden und habe am Ende einen dichten Buffer. Aber krieg ich damit dann nicht wahnsinnige Probleme was Parallelität angeht? Wie effizient sind diese Atomic-Counter? Denn jeder Compute-Shader Thread muss ja nur sehr wenig berechnen, und wenn ein signifikanter Teil davon (das finden des richtigen Speicherblocks) rein sequentiell abläuft ist der Ansatz vielleicht eine schlechte Idee.

Ist das ganze also praktikabel? Oder ist die Idee, das vielleicht nur jeder hunderste Thread eine Instanz erzeugt tatsächlich eine sehr schlechte? Wäre indirect Rendering (also das erzeugen von neuen Draw-Calls im Shader) an dieser Stelle effizienter als Instancing? Oder muss ich das Problem doch ganz anders angehen?
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8261
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Krishty »

Jonathan hat geschrieben: 15.11.2022, 22:21Das Offensichtliche wäre ein Atomic-Counter, mit dem kann ich für jeden Thread den nächsten freien Eintrag finden und habe am Ende einen dichten Buffer. Aber krieg ich damit dann nicht wahnsinnige Probleme was Parallelität angeht?
Wurde AppendStructuredBuffer() nicht für genau sowas eingeführt? Das läuft AFAIK mit maximaler Performance.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Matthias Gubisch
Establishment
Beiträge: 471
Registriert: 01.03.2009, 19:09

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Matthias Gubisch »

Also unter glsl wirst du an einem Atomic Counter nicht vorbeikommen.
Der Sync Punkt ist ja relativ klein. Du kannst ja alle Entscheidungen treffen, dann wenn nötig die BufferPosition aus dem Counter holen und das schreiben in den Buffer läuft dann ja wieder parallel.

Ich hab damit Culling auf der GPU implementiert und ich kann dir sagen dass der Counter vermutlich erstmal nicht dein Performance Problem sein wird.
Für HLSL klingt Krishty's Lösung nach dem was du suchst, da kann ich aber nix genaueres dazu sagen weil ich HLSL nicht wirklich benutzte.

Unter Vulkan und afaik DirectX12 sollte Instancing vs drawcall per Instanz keinen großen Unterschied machen (sofern man DrawIndirect benutzt) unter OpenGL und älteren DX Versionen kann ich es nicht sagen.

Allerdings musst du den DrawCommandBuffer ja auch auf der GPU füllen, also Buffer füllen musst du sowieso.
Bevor man den Kopf schüttelt, sollte man sich vergewissern einen zu haben
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Wurde AppendStructuredBuffer() nicht für genau sowas eingeführt? Das läuft AFAIK mit maximaler Performance.
Ugh, ich seh ich habe komplett vergessen zu erwähnen, dass ich Open GL verwende. Anfängerfehler :D

AppendStructuredBuffer sieht interessant aus. Ich habe versucht ein OpenGL Äquivalent zu finden, aber hab auf die schnelle nichts gefunden. Zumindest diese Antwort
https://stackoverflow.com/questions/320 ... ute-shader
suggeriert, dass vielleicht doch Atomic Counters eben jenes Äquivalent ist. Hm. Ich könnte mir schon vorstellen, dass ein spezielles BufferAppend wesentlich effizienter umgesetzt werden kann als ein Atomic Counter, aber ka.
Zuletzt geändert von Jonathan am 16.11.2022, 09:27, insgesamt 1-mal geändert.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Matthias Gubisch hat geschrieben: 16.11.2022, 09:13 Also unter glsl wirst du an einem Atomic Counter nicht vorbeikommen.
Der Sync Punkt ist ja relativ klein. Du kannst ja alle Entscheidungen treffen, dann wenn nötig die BufferPosition aus dem Counter holen und das schreiben in den Buffer läuft dann ja wieder parallel.
Ah, ok. Dann scheinen ja Atomic Counters durchaus ein gängiges Mittel für dieses Problem zu sein. Dann werd ich das mal ausprobieren.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Ich habs mal implementiert:
Orchard_kdVkAjhM7m.jpg
Gut, der Screenshot ist erzhässlich, aber was man hier sieht ist ein Instancing Buffer der 32x32 Elemente fasst, aber auf einem 64x64 Grid im Compute-Shader evaluiert wird. Und es funktioniert, weil für weniger als 1/4 der Positionen tatsächlich eine Instanz in den Buffer geschrieben wird.

Viel mehr gibt es dazu nicht zu sagen. Ich benutze halt einen Atomic Counter. Aber dieser Screenshot ist für mich persönlich wichtig, weil er bereits alles enthält, was ich hierfür das erste mal neu machen, d.h. lernen musste. Der Rest - nette Verteilung per Dichtetextur, zufällige Rotation, Skalierung und Offsets, emittierte Instanzen nur im Kamerasichtfeld erzeugen - ist alles ziemlich klar. Das einzige was etwas Denkarbeit erfordern könnte ist, dass die Objekte stabil sind. D.h. es werden immer nur Objekte direkt vor der Kamera erzeugt, aber natürlich sollen Objekte nicht hin und her springen, wenn man die Kamera leicht bewegt. Aber auch da sehe ich kein fundamentales Problem.

Ich bin schon sehr gespannt, wie sich das ganze bald ingame machen wird :)
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Matthias Gubisch
Establishment
Beiträge: 471
Registriert: 01.03.2009, 19:09

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Matthias Gubisch »

Tolle Sache.
Wie siehts mit der Performance aus? Zufrieden bisher?
Bevor man den Kopf schüttelt, sollte man sich vergewissern einen zu haben
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Matthias Gubisch hat geschrieben: 03.12.2022, 19:47 Wie siehts mit der Performance aus? Zufrieden bisher?
Habs tatsächlich noch nicht unter realistischen Umständen testen können, da noch viele Features fehlen. Aktuell ist halt keine Verlangsamung spürbar, aber halt für Fälle, wo absolut keine Verlangsamung zu erwarten ist. D.h. es ist zumindest nicht absurd langsam, naja :D
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Ich arbeite gerade daran, die Instanzpositionen abhängig von der Kamera vor der Kamera zu positionieren. Das ganze ist gar nicht mal so trivial wie zunächst gedacht:

Wichtigstes Kriterium ist Stabilität: Instanzen dürfen sich nicht mit der Kamera mitbewegen und nicht im Vordergrund plötzlich aufploppen. Sprich, auf eine gewisse Art darf ich keine Positionen generieren, sondern muss sie von einem vorgegebenen Gitter von sich nie verändernden Positionen auswählen.
Ich könnte einfach für jede mögliche Instanz eine Position generieren und im Shader ein View-Frustum Test machen und an entsprechend sichtbaren Punkten Instanzen erzeugen. Aber ich würde gerne ohne vorgenerierte Punkte auskommen, denn dann ist die Laufzeit unabhängig von der Terraingröße. D.h. ich könnte sogar sagen, dass man in Bodennähe Kieselsteine sieht, die nur wenige cm groß sind. Man muss immer höchstens tausend davon rendern (mehr passen nicht auf den Bildschirm ohne dass sie so klein werden dass man sie nicht mehr als einzelne Objekte wahrnehmen kann), und wenn man diese tausend Positionen "generieren" und nicht "auswählen" muss, kann man theoretisch Milliarden Instanzen haben, ohne dass es teurer wird. Und das klingt irgendwie so nett, dass ich es umsetzen möchte.

Meine aktuelle Planung für den Algorithmus:

Gitter definieren.
Ich definiere eine Auflösung, z.B. ein Baum pro Quadratmeter. Jede Gitterposition dient als Seed für einen RNG der Offset / Jitter, Skalierung, Rotation, usw. der Instanz definiert. Eine Instanz wird für jeden Punkt erzeugt, wenn deren Zufallszahl über einem Dichte-Schwellwert multipliziert mit einer Verteilungstextur (die sich z.B. über das ganze Terrain erstreckt) liegt. D.h. man kann steuern wo Instanzen sind, und wie dicht diese sind. Aus Effizienzgründen will man vermutlich die Parameter (Dichte, Gitterauflösung usw.) so wählen, dass von z.B. 100 Samples mindestens einer übrig bleibt (weil alle Positionen ja unter Umständen in jedem Frame neu generiert werden müssen).

Bounding Box definieren.
Alle Kandidaten innerhalb der BB werden geprüft, alle außerhalb nicht (wodurch das virtuelle Gitter beliebig groß sein kann).
Man könnte jetzt denken, es reicht die 4 Eckstrahlen des View Frustums mit dem Terrain zu schneiden. Aber man könnte ja z.B. Links und rechts im Sichtfeld einen Hügel haben, und dazwischen in die Ferne sehen können. Letztendlich muss die BB also so groß sein, dass jeder sichtbare Pixel des Terrains darin liegt. Das ist erstmal kniffelig, weil nicht konvex und all das.
Ich brauche vermutlich sowas wie ein konvexes Bounding Volume, oder so. Der Einfachheit halber nehme ich erstmal die Bounding Box des Terrains, d.h. die Größe der Heightmap in X/Y Richtung und deren maximalen und minimalen Wert in Z Richtung. Das ist die konservative Lösung die meistens zu groß sein wird, aber zumindest ist garantiert, dass alle sichtbaren Instanzen innerhalb dieser BB liegen. Es sollte besser funktionieren, je flacher das Terrain ist, das muss ich irgendwie im Auge behalten.
Ich komme letztendlich also auf insgesamt 8 Schnittpunkte. Da mein Gitter (o.B.d.A.) achsenausgerichtet ist und nicht rotiert werden kann (wegen der benötigten Stabilität der Punkte), nehme ich Komponentenweise die minimalen und maximalen Werte in X/Y und runde die Werte auf Vielfache der Gitterauflösung. Jetzt habe ich meine Kandidaten die ich im Compute Shader durchiterieren kann.
Ein Problem gibt es aber noch: Obiges vorgehen funktioniert ganz gut für die Vogelperspektive. Aber wenn ich die Kamera horizontal ausrichte, wird die Bounding Box schnell unendlich groß. Natürlich will ich eine maximale Distanz für Instanzen definieren können. Also muss ich beim Berechnen der 8 Schnittpunkte die maximale Entfernung berücksichtigen und den Schnittpunkt ggf. passend zurück Richtung Kamera schieben.
Das schlimmste was passieren kann ist wenn man von einem Hügel ins Tal blickt und eine sehr große Brennweite verwendet. Dann würde obiger Algorithmus ergeben, dass Instanzen schon unmittelbar vor der Kamera anfangen müssen, obwohl man in Wahrheit vielleicht nur Terrain sieht, dass zwischen 500 m und 600 m entfernt ist. Andererseits könnte ja trotzdem tatsächlich eine einzelne Instanz im Vordergrund noch hoch genug sein um ins Sichtfeld zu ragen. Vielleicht muss man Terrains mit extremen Höhenunterschieden einfach nochmal in mehrere Blöcke unterteilen...

Instanzen generieren.
Dieser Schritt ist eigentlich recht klar: Ich hole mir für jede 2D Position innerhalb der Bounding-Box des Gitters die Höhe aus der Heightmap und kann dann noch einen Sichtbarkeitstest durchführen.
Man könnte das vermutlich noch effizienter machen, indem man das View-Frustum mit der BB schneidet und das Ergebnis rasterisiert, so dass man immer nur Punkte innerhalb des View Frustums verarbeiten muss. Aber ich schätze mal, dass meistens gut die Hälfte der Punkte diesen Test bestehen werden und so hat man weniger Arbeit damit zu bestimmen, welcher Thread welchen Kandidaten bearbeiten soll.
Da es eine maximale Entfernung gibt, kann es passieren, dass die Instanzen irgendwie plötzlich aufhören. Ich bestimme daher für jede Instanz noch die Entfernung zur Kamera und multipliziere diese noch mit einer weiteren Zufallszahl. So kann ich im Hinteren Bereich z.B. nur noch jede 10te Instanz anzeigen. Alternativ könnten Instanzen auch transparent werden oder kleiner skaliert werden oder so. Ich muss noch testen was da am besten aussieht.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Jonathan
Establishment
Beiträge: 2381
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Instancing Buffer in Compute Shader generieren

Beitrag von Jonathan »

Ich hatte jetzt endlich mal Zeit das wie oben beschrieben umzusetzen:
Orchard_8gnP61x0nw.jpg
Es gibt noch an allen Ecken und Enden Dinge zu verbessern, aber das Grundprinzip funktioniert schon ganz gut. Beim Implementieren tauchen dann immer zig Spezialfälle auf, es kann z.B. sein, dass sich die Eckstrahlen des Viewfrustums gar nicht mit der Terrain Bounding Box schneiden, weil sie in den Himmel zeigen. Oder dass die Kamera selber niedriger ist, als die maximale Terrain Höhe. Oder dass die Kamera auf dem Kopf steht und die obere Kante einen niedrigeren Punkt betrachtet, als die untere.

Eine wichtige Einschränkung ist aktuell, dass der Compute Shader immer ein 2D Rechteck an möglichen Positionen durchtestet. Da man stabile Objektpositionen braucht kann man das Gitter nicht einfach so mit der Kamera mitdrehen. Daher kann es schnell passieren, dass z.B. der Hälfte aller generierten Positionen gar nicht im Frustum liegen, bei ungünstigen Terrainformen möglicherweise sogar noch mehr. Ich bin mir noch unsicher, ob ich irgendwie cleverer über die Punkte im Frustum iterieren sollte (was dann natürlich auch robust für jede mögliche Kamera funktionieren muss) oder einfach View Frustum Culling einbauen sollte.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Antworten