Indexbuffer Performance

[dronus]

Machen indizierte Vertices das Rendern immer schneller? Natürlich hat man bei Werwendung von Indicies weniger Vertices, da muss die GPU auch weniger transformieren. Andererseits muss die GPU die Vertices nach den Indicies nachschlagen, und dabei für jede Primitive verstreute Vertices im Speicher auslesen, wärend beim Rendern mit einem reinen Vertexbuffer alles schön "am Stück" verarbeitet wird.
Macht es Sinn sowas zu testen, oder gibt es ein Argument warum Indicies immer besser sind? Was ist wenn z.B. der Vertex-Shader extrem kurz ist?

[Ingrater]

Eine Grafikkarte hat einen FIFO buffer für vertices. Benutzt du keinen Indexbuffer wird jedes mal das Vertex erneut durch den Vertex-Shader gejagt auch wenn es eigentlich mehrfach verwendet wird. Benutzt du einen Index-Buffer so schaut die Graka erst ob das Vertex bereits im Buffer ist, wenn ja nimmt es die schon berechneteten Daten, wenn nein wird das Vertex durch den Vertex-Shader gejagt und das Ergebnis in den Buffer geschrieben. Dieser Buffer hat nur eine bestimmte größe weswegen es dann spezielle Verfahren gibt die den Indexbuffer eines Meshes so optimieren dass ein Vertex möglichst oft Wiederbenutzt wird bevor es aus dem Buffer fliegt. Bei richtiger Anwendung ist es also schneller, langsamer werden sollte es dadurch nicht.

[Krishty]

Wie Ingrater schon geschriben hat, ermöglichen Index-Buffer das effizizientere Verarbeiten von Vertices. Alles, was du beim Googeln von „Vetex Cache Optimization“ findest, wird i.d.R. erst durch Index-Buffer und den Vertex-Cache möglich.

Performance-relevant wird es allerdings in den wenigsten Fällen, weil die Vertex-Transformationsrate selten das Bottleneck war / ist. Wenn die Vertex-Shader extrem kurz sind, fällt es nochmal weniger ins Gewicht.

Eine Ausnahme, wann der Vertex-Cache außer Kraft gesetzt wird, wäre, wen der Shader z.B. auf PrimitiveID o.Ä. zugreift.

Generell wird es also schneller, aber unmerklich. ALlerdings lässt sich die Datenmenge viel kleiner haltne: Wenn jedes Vertex zu sechs Dreiecken gehört, wie bei den meisten Tirangulationen, dann musst du es ohne Index-Buffer auch sechs Mal in den Vertex-Buffer schreiben.

Gruß, Ky

[dronus]

Generell wird es also schneller, aber unmerklich. ALlerdings lässt sich die Datenmenge viel kleiner haltne: Wenn jedes Vertex zu sechs Dreiecken gehört, wie bei den meisten Tirangulationen, dann musst du es ohne Index-Buffer auch sechs Mal in den Vertex-Buffer schreiben.

Ok.. unmerklich klingt aber gut :-)

Ich hab hier CPU-Code der sehr viel komplizierter und langsamer würde wenn er Indicies erzeugen muss. Ich erzeuge viele Dreiecke rekursiv, und es wäre sehr schwer die gemeinsamen Verticies von verschiedenen Dreiecken im Baum zu finden.
Das einzig blöde ist, dass ich dann auf Soft Shading verzichten muss, da ich zu jedem Vertex dann auch getrennte Normalen habe und die nicht verrechnen kann... gibts da irgendein Rezept für?

[Krishty]

Ich erzeuge viele Dreiecke rekursiv, und es wäre sehr schwer die gemeinsamen Verticies von verschiedenen Dreiecken im Baum zu finden.
Das einzig blöde ist, dass ich dann auf Soft Shading verzichten muss, da ich zu jedem Vertex dann auch getrennte Normalen habe und die nicht verrechnen kann... gibts da irgendein Rezept für?

Das kenne ich :/ Du kannst entweder die Rekursion in Iteration umwndeln (hässlich) oder eine zusätzliche Abstraktionsebene geben (langsam). Ich würde letztere Methode bevorzugen:

Du packst Vertex- und Indexbuffer in eine Geometriepuffer-Klasse. Der hat eine Funktionum ein neues Dreieck einzufügen. Wenn du die mit drei Vertices aufrufst, prüft der Puffer, ob die Vertices schon vorhanden sind und fügt in diesem Fall bloß einen neuen Index hinzu. Davon unabhängig addiert er auf alle drei Vertices den Normalenvektor des neuen Dreiecks auf.
Wenn die Geometrieerzeugung fertig ist, normalisiert der Geopuffer alle Vertex-Normalen und gibt den fertigen Vertex- und Indexbuffer aus.

Das Suchen bereits vorhandener Vertices lässt sich vielleicht optimieren, wenn du dir zuntze machst, dass bei der Rekursion liokal zusammenhängende Geometrie auch oft hintereinander im Speicher liegt oder in regelmäßigen Abständen von 3, 9, 81 Schritten.

Der Ansatz ließe sich auch erweitern, um Vertex-Buffer immer in Nähe der optimalen Vertex-Anzahl von 65536 zu füllen.

[dronus]

Du packst Vertex- und Indexbuffer in eine Geometriepuffer-Klasse. Der hat eine Funktionum ein neues Dreieck einzufügen. Wenn du die mit drei Vertices aufrufst, prüft der Puffer, ob die Vertices schon vorhanden sind und fügt in diesem Fall bloß einen neuen Index hinzu. Davon unabhängig addiert er auf alle drei Vertices den Normalenvektor des neuen Dreiecks auf.
Wenn die Geometrieerzeugung fertig ist, normalisiert der Geopuffer alle Vertex-Normalen und gibt den fertigen Vertex- und Indexbuffer aus.

Ja, hmm.. Das klingt so nach vorverarbeitung beim Laden oder im Editor.. ich erzeuge massenweise Kram in Echteit, da wird das schnell lahm wenn man zuviel dazwischen packt.
Ich glaube ich komme nicht drumherum eine Erzeugung zu finden die weiche Normalen gleich miterzeugen kann, notfalls eben pro Dreieck einmal... ist vermutlich immer noch schneller als die passenden Verticies "wiederzufinden".

[Chromanoid]

mmh also ich würde beim generieren einfach jedem vertex ne nummer mitgeben. beim generieren dann auch gleichzeitig nen indexbuffer bauen der mit den nummerierten ggf. redundanten vertices arbeitet. in diesem indexbuffer sind sozusagen einfach nur zahlen von 1-n in richtiger reihenfolge (also indexbuffer=i), da du ja pro vertex ne neue nummer kriegst. dann sortierst du die vertices einfach nach x,y,z. dann gehst du diese sortierte liste durch und ersetzt alle doppelten vertices im indexbuffer mit [anzahl der bisher einzigartigen vertices]. die positionen der nummern der vertices im indexbuffer sind ja die eigenen nummern, da verliert man also kaum performance. das einzige was lange dauert ist das sortieren der vertices.... während dieses prozesses baust du auch gleich nen neuen vertexbuffer (immer nur die einzigartigen vertices)...

ich kenn mich da nicht aus aber so aus dem bauch heraus könnte ich mir vorstellen, dass du beim zusammenfassen der gleichen vertices zu einem neuen noch alle normalen der vertices nehmen kannst und den durchschnitt davon als neue normale für den neuen vertex nimmst...

[dronus]

dann sortierst du die vertices einfach nach x,y,z. dann gehst du diese sortierte liste durch und ersetzt alle doppelten vertices im indexbuffer

Das muss ich mal probieren. Im Moment hab ich leider eine Wegwerfstrategie, sobald daten in der GraKa sind schmeiss ich sie weg. Sonst würde ich den hohen Durchsatz nicht lange hinbekommen. Das Problem ist dass ich nicht weiss ob evtl. später weitere Geometrie hinzukommt.. dann hab ich plötzlich doppelte Verticies, aber gar keine Zugriff mehr auf die alten, solange ich nicht aus der GraKa zurücklese.

ich kenn mich da nicht aus aber so aus dem bauch heraus könnte ich mir vorstellen, dass du beim zusammenfassen der gleichen vertices zu einem neuen noch alle normalen der vertices nehmen kannst und den durchschnitt davon als neue normale für den neuen vertex nimmst...

Warum durchgestrichen? Das ist eine tolle Idee. Das werd ich probieren, wenn ich die Wegschmeissstrategie im Griff hab.

Die optimale Lösung wäre, von allen an die GraKa geschickten Daten genau die Randverticies im Speicher behalten zu können. Dann kann man später weitere Geometrie anpassen. Man müsste aber auch die Normalen der schon in der GraKa befindlichen Randverticies neu berechnen. Vielleicht verwendet man immer zwei Buffer, einen mit x,y,z und allen Textur-Daten, und einen weiteren nur mit den Normalen.

Perfekt wäre, wenn ich eine bestimmte Menge Geometrie zur GraKa schicken kann, und später, wenn ich weitere Stücke nachschicke, auf der GraKa die Normalen verbunden werden können. Dazu fällt mir aber grad kein Shader ein. Vielleicht geht sowas mit CUDA/OpenCL?

Auch witzig aber wild wäre, die Normalen im Screenspace zu berechnen. Vielleicht so:
Die Verticies bekommen Texturkorrdinaten pro Primitive, also über jedem Dreieck ein ganzer Texturdurchlauf. Der Pixelshader schreibt Dreiecksnormalen (Flat-Shading) und diese komischen Texturkoordinaten in den Framebuffer.
Ein zweiter Pass im Screenspace liest jetzt die Texturkoordinaten, und kann damit den Abstand zu den Dreieckskanten bestimmen. So kann der Pixelshader ein paar Pixel an den Kanten der Nachbardreiecke auslesen und kennt damit die Normalen an allen Kanten des Dreieicks. Daraus kann er die Normale im aktuellen Pixel interpolieren. Dann kann das Shading berechnet werden..

[Stefan Zerbst]

Ok.. unmerklich klingt aber gut :-)

Das kommt ganz auf die Größe der Modelle und auf den "Cache-Miss" bei einem unoptimierten Layout drauf an. Das "unmerklich" würde ich aus dem Satz streichen und durch "kann durchaus einen Performancegewinn und wird nie einen Performanceverlust bringen" ersetzen. Google mal nach Tipsify oder falls es DirectX ist benutze auf den ID3DXMeshes das Tipsify welches schon onboard ist. Dort heisst es eventuell nur "ID3DXMesh::Optimize".

Ich hab hier CPU-Code der sehr viel komplizierter und langsamer würde wenn er Indicies erzeugen muss. Ich erzeuge viele Dreiecke rekursiv, und es wäre sehr schwer die gemeinsamen Verticies von verschiedenen Dreiecken im Baum zu finden.
Das einzig blöde ist, dass ich dann auf Soft Shading verzichten muss, da ich zu jedem Vertex dann auch getrennte Normalen habe und die nicht verrechnen kann... gibts da irgendein Rezept für?

Das kommt ganz darauf an was du gerade machst. Aber leider klingt das erstmal so, als ob de rganze Ansatz es so zu machen (was auch immer "es" ist) nicht gerade optimal ist. Klar sind Algorithmen schön die rekursiv irgendwo durcheiern und nur Vertices raushauen wie zum Beispiel beim ROAM oder ähnlichen Terrain-Algorithmen. Mit OpenGL kann man die sogar gleich mit leider ziemlich guter Performance rendern. Aber optimal ist das nicht. Heutzutage sollte man seine Datenstrukturen und deren Generierung mehr auf die Bedürfnisse einer modernen GPU einrichten.

Ciao,
Stefan

[Stefan Zerbst]

Du packst Vertex- und Indexbuffer in eine Geometriepuffer-Klasse. Der hat eine Funktionum ein neues Dreieck einzufügen. Wenn du die mit drei Vertices aufrufst, prüft der Puffer, ob die Vertices schon vorhanden sind und fügt in diesem Fall bloß einen neuen Index hinzu.

Igitt wie lange soll das denn dauern? :mrgreen:

Wenn wir hier über große Datenmengen sprechen, wie zum Beispiel ein paar Hundertausend oder gar Millionen Dreiecke dann willst du Hundertausendmal je drei Vertices prüfen ob diese schon in der Liste vorhanden sind wobei die Liste am Ende auch Hundertausende Einträge hat? Das geht sicherlich besser wenn man weiß was für Daten eigentlich erzeugt werden sollen. Eine derartige Verallgemeinerung mit Prüfen auf identische Vertices ist sicherlich ein Spezialfall den man nie brauchen wird.

Ciao,
Stefan

[Aramis]

Gegen Krishty's Lösung ist nichts einzuwenden, sie setzt nur eine ordentliche Datenstruktur für die Vertices voraus - wie Schrompf in Assimp's Vertexjoiner demonstriert hat, lässt sich die Laufzeitkomplexität für die Suche nach identischen Vertices ohne großen Aufwand von O(n) auf O(logn) senken (Andere, real-life, Performanceaspekte ganz dreist vernachlässigend).

Natürlich ist eine spezialisierte Lösung potentiell schneller, da stimme ich zu. Im Interesse den Entwicklungsaufwand zu senken haben wiederverwendbare, verallgemeinerte Ansätze aber doch einen gewissen Reiz...

EDIT - Übrigens ließe sich die Suche nach identischen Vertices hervorragend parallelisieren :-)

[Krishty]

Wenn wir hier über große Datenmengen sprechen, wie zum Beispiel ein paar Hundertausend oder gar Millionen Dreiecke dann willst du Hundertausendmal je drei Vertices prüfen ob diese schon in der Liste vorhanden sind wobei die Liste am Ende auch Hundertausende Einträge hat? Das geht sicherlich besser wenn man weiß was für Daten eigentlich erzeugt werden sollen. Eine derartige Verallgemeinerung mit Prüfen auf identische Vertices ist sicherlich ein Spezialfall den man nie brauchen wird.

Wie gesagt besitzen rekursiv erzeugte Vertexlisten eine äußert berechenbare Lokalität, die man wunderbar einsetzen kann. Man kann den Geopuffer ja für einzelne Datensätze spezialisieren, indem man die Suchfunktion für jeden Anwendungsfall überschreibt ... aber wenn man die Listen einfach nur von vorn nach hinten vergleicht, ist das natürlich die katastrophale Lösung schlechthin. Wenn man hingegen in den richtigen Abständen sucht wird man schnell Matches finden ... und man kann ja abbrechen, wenn man nach einer gewissen Zahl Vergleiche nichts gefunden hat (obwohl dann die Normalen durcheinander kommen könnten).

Wenn man einen Vertex-Shader hat, der keine normierten Normalenvektoren voraussetzt, kann man sich sogar den finalen Schritt sparen.

EDIT - Übrigens ließe sich die Suche nach identischen Vertices hervorragend parallelisieren :-)

Stimmt ... sogar über den offensichtlichen Anteil hinaus: Limitierend wird bei dem Ansatz nämlich sicher die Speicherbandbreite sein, und während die CPU auf neue Floats zum vergleichen wartet, kann sie mit Hyper-Threading schon die Berechnung des nächsten Dreiecks zwischenschieben.

Natürlich kann man auch einfach seinen Spezialansatz einbauen, indem man z.B. die Rekursion über Bord wirft. Habe mal ein Geodom iterativ ohne doppelte Vertices erzeugt ... es war ein bisschen wie ... habt ihr Apocalypse Now gesehen? Jedenfalls ist der Code dann nach ein paar Monaten wieder rausgeflogen, weil er einfach nicht wartbar war. Muss aber jeder für sich entscheiden.

[dronus]

Natürlich kann man auch einfach seinen Spezialansatz einbauen, indem man z.B. die Rekursion über Bord wirft. Habe mal ein Geodom iterativ ohne doppelte Vertices erzeugt ... es war ein bisschen wie ... habt ihr Apocalypse Now gesehen? Jedenfalls ist der Code dann nach ein paar Monaten wieder rausgeflogen, weil er einfach nicht wartbar war. Muss aber jeder für sich entscheiden.

Ja das ist nicht so einfach, "es" wie es schon umschrieben wurde ist irgendein Subdivisions-Objekt, manchmal Landschaft, manchmal Gebäude usw. letztendlich wird in der Rekursion teilweise wilder Kram berechnet den ich weder lokal/iterativ berechnen kann noch in einen Geometrieshader packen kann.
Auf der untersten Ebene kann vielleicht ein Geometrieshader eckiges rund oder noch etwas rauher machen, aber ich hab keine Lust die ganzen Subdivisions-Routinen nochmal für den Shader zu doppeln. Die müssten ja dann präzise dem CPU-Algortihmus gleichen, sonst wundert man sich... Auf der CPU brauch ich sie auf jedenfall, um Objekteigenschaften zu ermitteln usw.

[Ingrater]

Wenns nur darum geht, dass du die Daten auch auf dem CPU brauchst könntest du Transform feedback nehmen und dann die Daten zurück auf die CPU holen. Das würde dich allerdings im momentanen Zustand auf Nvidia Karten beschränken, denn soweit ich weiß hat ATI immer noch keine geometry shader extension.