[gelöst] Batching-Strategie

[Haiaiai]

Edit: Lösung weiter unten: http://zfx.info/viewtopic.php?p=5422#p5422

Hallo Grafik-Gurus,

ich hab da mal ein Problem: Für meine kleine Engine (vgl. Vorstellungsbereich) arbeite ich zur Zeit mit Quake3-BSPs. Das kann sich irgendwann ändern, das Welt-Modul der Engine kann einfach ausgetauscht werden, weil objekt-orientiert und so. Das Format versorgt mich aufgrund des Alters von vornherein mit wenigen Polygonen, Frustum-Culling und PVS tragen dazu auch ganz gut bei. Trotzdem: Langsam wie Sau! Wer das Format kennt, wird ahnen wieso: Ich render die sogenannten Faces. Das heißt für einmal Welt zeichnen gerne mal 1300 DrawIndexedWhatever-Calls, wahrscheinlich in bestimmten Karten noch einiges mehr.

Meine X700 (Shader 2.0) Grafikkarte ist damit natürlich arg belastet, nur Welt rendern drückt stellenweise auf 15 Frames runter. Eine bessere Karte ist aber grade keine Option und ohnehin nicht die Lösung des Problems. Die Lösung ist, ich brauche besseres Batching, oder anders: mehr Polygone pro Draw-Call.

Ich muss also die Faces zu Batches zusammenfassen, da bleibt aber die Frage, nach welchem Schema?
1. Grundlegend natürlich getrennt nach Material, also pro Batch das gleiche Material, sonst müßte ich halt mehr Material-Handling machen und das auch noch den Shadern aufzwingen. Da diese konzeptionell getrennt sind von der eigentlichen Engine soll das nicht geschehen, also bleibts bei 1 Material pro Batch.
2. Quake3 hat Lightmaps in den BSPs. Zwar keine moderne Technik mehr, aber ein angenehmer Effekt für wenig aufwand, warum also nicht nutzen? Aber Lightmaps sind getrennt von Materialien. Gleiche Frage: 1 Lightmap pro Batch oder das Handling mehrer Lightmaps zu den Shadern weitergeben? Hier bin ich etwas unentschieden, tendiere aber wie zu der 1-je-Batch-Variante. Oder keine Lightmaps und alles aus den restlichen Daten beleuchten. Da fehlt mir allerdings Kenntnis ob die Lichter, mit denen die Lightmaps erzeugt wurden, noch vollständig in den Entities vorhanden sind. Auch könnte es sein, dass Faces mit gleichem Material oft die gleiche Lightmap verwenden, d.h. die 1-je-Batch-Variante wäre fast optimal, weil sie nur wenig mehr Batches hätte als Varianten mit mehr Lightmaps.
3. Batchgröße, sowohl in der Welt als auch nach Vertex/Triangle-Count. Größere Batches machen natürlich weniger Drawcalls, dafür mehr Dreiecke, die gar nicht zu sehen sind, aber der reine Vertex/Triangle-Count ist nicht das problem glaube ich. Batche ich aber zuviel zusammen, kann ich mir bald das Frustum- und Occlusion-Culling sparen, weil ich annähernd das halbe Level zeichen wenn vor mir eine gewisse Auswahl an Materialien zu sehen ist.

Vor allem zu 2. und 3. wäre ich über Erfahrungsberichte und Einschätzungen dankbar. Noch als Denkhilfe: Mit ca 500 Draw-Calls pro Frame schaff ich 60 Fps, aber das Budget sinkt sicher noch wegen Rendertarget-Switches etc. Das ganze muss dann noch aufgeteilt werden, da Welt und Entities ja für die Shadowmaps nochmals gerendert werden, zum Teil wahrscheinlich mehrmals. Ich rechne ganz grob mit weniger als 50 Calls Budget zum Zeichnen der Welt, natürlich mit wenigen Lichtern die Schatten werfen.

Ein Vergleich mit anderen Levelformaten wäre auch ganz nett, gibts da was wo das Batching schon besser organisiert ist? Ich würde langfristig wahrscheinlich auch portal-basiert rendern, es muss also kein PVS haben.

[Schrompf]

Mach mal einen Test: ignoriere den kompletten BSP-Tree und rendere stattdessen *alle* Flächen mit demselben Materials und derselben LightMap in einem Rutsch. Du wirst überrascht sein, welches Tempo man damit erreichen kann... selbst auf so schwachbrüstigen Karten wie der Radeon700. Soweit ich weiß, sind Q3-Level sehr polygonarm, verglichen mit heutigen Szenen. Da könnte sowas glatt funktionieren.

Wir bestimmen die Sichtbarkeit bei uns nach AABBs, also schlichten Quadern in Weltkoordinaten. Die sind für das Terrain in der Nähe so 25^3 m groß, in der Entfernung bis 250^3 m. Objekte wie Pflanzen, Waffen, Häuser, Monster usw... sind sehr verschieden groß, von 10cm bis 50m. Bei den großen Objekten könnten wir ein bisschen was rausholen, wenn wir die weiter aufteilen würden, aber nach meiner Erfahrung bringt das kaum was... kleiner als 5000 Flächen wird nur unterteilt, wenn die Umstände es erfordern. Bei Deiner Graka ist die Grenze vielleicht eher bei 500 bis 1000 Dreiecken anzusetzen, aber alles darunter ist definitiv Verschwendung. Wir haben dann sehr viel mehr Arbeit investiert, um den DrawCall-Count zu senken. Massen von Kleinstobjekten wie z.B. Bodenbewuchs wird über Instancing zusammengefasst, ab einer gewissen Entfernung werden auch größere Objekte wie ganze Waldsegmente vortransformiert in statische Meshes verpackt, und wir versuchen, über Blocker und Portale möglichst viele Objekte von vornherein vom Rendern auszuschließen. Das geht aufgrund der reichlich groben AABB-Tests nur für kleine Objekte oder größere Strukturen wirklich gut, aber hilft vor allem bei Kontrastszenen InHaus/AußerHaus sehr viel.

Wir kommen in einer Standardszene mit einzelner Sonnen-ShadowMap auf 1500 DrawCalls bei ca. 1Mio Dreiecken. Damit erreichen wir je nach Grafikkarte und CPU durchaus spielbare Framerates - z.B. auf durchschnittlichen Athlon 4000+ und einer Geforce7800GT 20 bis 30fps. Wir sind aber auf allen größeren Grafikkarten nur noch CPU-beschränkt... Du müsstest da mit einem Deferred Renderer eigentlich weiter kommen als wir, weil Du pro DrawCall viel weniger Setup betreiben musst und dementsprechend auch viel besser sortieren können müsstest.

[Haiaiai]

Ein Batch je Material und Lightmap wird wahrscheinlich auch mein erster Ansatz, ganz einfach um den Batch-Bastel-Code zu testen, und ich trau das meiner GraKa durchaus zu. Nur kommt mir das halt unelegant vor, weils eben nur heißt das Problem mit Power zu lösen. Alles Rendern, Bämm! Wenn sich Format aber ändert, ist evtl. Schluss mit polygonarm und dann fehlt das Culling.

Dass ich zum Batchen gewissen Overhead in Kauf nehmen muss ist mir schon klar; nur ist das quasi das entgegengesetzte Extrem zu dem, was ich jetzt habe: viele kleine Batches zum Teil à 2 Dreiecke.

[Schrompf]

"Unelegant" ist Geschmackssache. Du weißt, dass die winzigen Nodes mit jeweils einer Handvoll Dreiecken ein Problem sind. Also tu was dagegen. Z.B. indem Du Endknoten des BSPs zusammenfasst, bis Du bei ein paar tausend Dreiecken pro Knoten bist. Eine Alternative über AABBs habe ich Dir ja auch genannt. Das Alles-Zusammenfassen war ja nur als Experiment gedacht, das ist nur für die alten Q3-Levels wirklich benutzbar.

[Haiaiai]

Harhar, ich bin wieder da!

Is 'ne Weile her seit ich hier war, hatte erstmal wenig Zeit ins Programm gesteckt; vor paar Wochen dann erstmal den Source-Code etwas (== nur die Hälfte) umgestellt und dies und das, und weil ich das dann in einem großen Rutsch gemacht hab, verliefen sich die entstandenen Fehler durchs gesamte Programm. Das brauchte nochmals Zeit. Nun aber läufts, und das sogar korrekt.

Soweit dazu, aber ich schreibe hier, weil ich die Batching-Strategie, die ich inzwischen entwickelt und eingebaut habe, mal kurz beschreiben wollte.

Zum ersten habe ich natürlich erstmal die haufenweise Polygone vereint. Das ist bei Triangle-Lists ja net schwer. Gruppiert habe ich nach Material und "Cluster". Cluster ist im Q3-BSP eine Menge von Leafes. Diese Guppierung besteht hauptsächlich, um das PVS zu schrumpfen, aber bietet mir einen Anhaltspunkt für räumliche Nähe. Es gibt also erstmal pro Material pro Cluster einen Batch, vorrausgesetzt es gibt überhaupt ein Polygon dass sich einer bestimmten Kombination aus Material/Cluster zuordnen läßt.

Diese Batches habe ich dann in Gruppen zusammengefaßt, für jedes Material eine Gruppe. Ich kann also die Batches einer Gruppe theoretisch zeichnen, ohne zwischendurch der Grafikkarte neue Parameter (Matrizen, Texturen etc) zukommen zu lassen. Vor dem zeichnen werden durch Trace durch den BSP die zu zeichnenden Batches und deren Gruppen markiert. Soweit so gut, aber nicht sonderlich kreativ, auch wenn der Effekt schon ziemlich spürbar ist (im Sinne von DrawCalls).

Was jetzt kommt ist etwas, das ich mir selbst ausgedacht habe, wenn ichs benennen müßte würde ich auf sowas wie "batch chaining" kommen :D Wahrscheinlich hat das aber schon irgendwer mal gemacht oder von gehört, erscheint mir im Nachhinein fast offensichtlich; aber für mich wars neu.

Worum es geht: Innerhalb einer Gruppe habe ich die Batches, bzw deren Indizes, normalisert auf den gleichen Offset (bei DrawXYPrimitve ist das der FirstVertex-Parameter). Weiterhin stehen die Batches einer Gruppe in einem Indexbuffer (unabhänging ob der nur für die Gruppe ist oder geteilt wird) hintereinander. Der Effekt dessen: Zeichne ich eine Gruppe, und werden darin zwei hintereinander angeordnete Batches gezeichnet, so kann ich diese zu einem Batch vereinen, indem ich einfach die Parameter (zB Anzahl der Indizes) vereine. Da zwei Batches so zu einem werden, läßt sich das mit einem dritten Batch vorsetzen, und so weiter. Sobald kein zu zeichnender Batch folgt werden die gesammelten ("gechainten"???) Batches dann mit einem DrawCall gezeichnet. Dann gehe ich weiter durch die Liste der Batches der Gruppe und sammle wieder, etc...

Wieviel bringt das in der Praxis? (Mal abgesehen von den nicht zeitgemäßen Datenmengen ;), ich kann auch problemlos die gesamte Gruppe in einem Rutsch zeichnen, ist noch schneller )

In meinem Standardtestlevel hab ich mal an mehreren Stellen mitgezählt, wie viele DrawCalls tatsächlich gemacht wurden und wie viele anreiht wurden. D.h. die Anzahl der DrawCalls ohne Chaining wäre die Summe.

DrawCalls / Angereiht / Verhältnis Drawcalls:Summe
86 / 312 / 0,21
58 / 177 / 0,24
41 / 61 / 0.40 (da hab ich gegen eine Außenmauer des Levels geblickt, wenig zu zeichnen)
91 / 357 / 0,20

Ich würde sagen, das lohnte sich schon. Es scheint weiterhin effektiver zu werden je mehr gezeichnet wird, was auch logisch ist, da es öfters vorkommt, dass aneinander liegende Batches gezeichnet werden. Grade das gefällt mir an dieser Technik, gerade in Engpässen hauts mehr rein. Und zum Vergleich, meine GraKa verläßt den 60-Frames bereich ab ca 500 DrawCalls.

Mögliche Verbesserungen:
Zum Einen könnte man sich etwas besseres ausdenken als die Gruppierung der Polygone nach Clustern. Es stellte sich heraus, dass in den BSPs oft Leafs aus verschiedenen Clustern das gleiche Polygon zeichnen. Dies dient wahrscheinlich dazu, dass die Geometrie beim Aufbau des BSP-Trees nicht zerstückelt wird. Aber das ist ein Problem, das speziell meine Daten betrifft. Allgemein ist natürlich die Auswahl nach einer gewissen Nähe am sinnvollsten.

Zweitens ist die Reihenfolge der Batches in einer Gruppe im Moment einfach die, in der die Batches ihr zugeordnet werden. Am besten wäre aber eine, die für hohe Wahrscheinlichkeiten sorgt, dass auch der folgende Batch gezeichnet wird, wenn ein bestimmter Batch gezeichnet wird, sodaß sich längere Ketten ergeben. Definiere ich also als Kosten die Wahrscheinlichkeit, das ein folgender Batch NICHT gezeichnet wird, kann ich einen vollständigen Graphen bauen (Kosten = Kantengewicht) und meine gesuchte Anordnung ist der kürzeste Hamilton-Pfad (vergleichbar mit Travelling-Salesman, das kürzester Hamilton-Kreis ist). Das ist zwar NP-vollständig, aber es geht ja um Verbesserung, also muß erstmal nicht der allerbeste Pfad gefunden werden. (Das ist im Prinzip schon implementiert, aber durch die Umordnung hab ich kleine Probleme beim Markieren-zum-Zeichnen; daher aktuell nicht implementiert, aber dauert net lang). Die Wahrscheinlichkeit, hintereinander gemalt zu werden, ist btw auch nicht trivial, daher wär das beste zuwieso nicht akkurat.

Ferner könnte man Materialien für den Fall, dass Schatten gezeichnet werden (Shadow-Maps), abstrahieren, sodass dafür weniger Materialien vorhanden sind, die dann in einer zweiten Gruppen-Menge vereint werden, sodaß also für Schatten nochmals weniger DrawCalls benötigt werden.

Bestehende "Probleme":
1. Der Indexbuffer wird um einiges größer, da viele Sachen in die Batches vervielfältigt werden.
2. Der Vertexbuffer wird wenig Cache-freundlich benutzt, aber das läßt sich durch Umordnen lösen, also ist das mehr ein TODO

So, das wars. Wenn was unklar ist, bitte fragen. Nett wäre eine Einschätzung, wieweit sich das eurer Meinung nach auf heutige Daten (Indoor, Terrain) anwenden ließe.

[glassbear]

FYI: Quake3 benutzt Portal Culling und nicht den BSP zum Rendern.