„Index Compression“ – wie effizient?

[Seraph]

PS: Schade, dass scheinbar die Diskussionsqualität in diesem Forum in den letzten Jahren nicht besser geworden ist.

Was mich viel mehr stoert als die "inhaltslosen" Aussagen ist die Art und Weise wie hier diskutiert wird. Ironischerweise bist Du eine derjenigen Personen, welche sich diesem Stil eben mal angeschlossen haben. Von TGGC hingegen habe ich ueber kurz oder lang nichts anderes erwartet. Es waere schoen wenn ihr nicht nur euer mathematisches Verstaendnis, sondern auch eure soziale Kompetenz unter Beweis stellen wuerdet!

[Chromanoid]

:P http://www.youtube.com/watch?v=KIVFerZy-Oo
hab ich neulich gefunden, als ich mal wissen wollte was tggc eigentlich bedeutet :D musste ich einfach posten... ist bestimmt schon altbekanntes aber egal :mrgreen: [/size]

[Julien Koenen]

Was mich viel mehr stoert als die "inhaltslosen" Aussagen ist die Art und Weise wie hier diskutiert wird. Ironischerweise bist Du eine derjenigen Personen, welche sich diesem Stil eben mal angeschlossen haben.

Gewisse Sachen kann Ich einfach nicht unwidersprochen stehen lassen.Es tut mir leid, wenn ich das Thema angeheizt haben sollte. Ich kenne ja auch die Leute und die Diskussionskultur in diesem Forum nicht (mehr.. ist schon ein paar Jahre her). Es ging mir bei meiner Aussage zur Diskussionsqualität auch weniger darum, dass alle lieb und nett zueinander sind (Das ist eher unüblich in Internet-Foren), als dass Grundlagen einer sinnvollen Diskussion eingehalten werden (Zum Beispiel beim Thema bleiben und auf Argumente der Gegenseite reagieren).

Gruß
Julien

[Schrompf]

85% sind ja nahezu ein Sechstel. Nicht übel.

Eine Frage zur Motivation: nehmen bei Euch die Indexbuffer so viel Speicher ein, dass sich solche Optimierung überhaupt lohnt? Bei mir sind die VertexBuffer irgendwie immer um den Faktor 10 größer.

[Julien Koenen]

Wie gesagt: Das ist eine Sache die sich vor allem auf der PS3 lohnt, da man die Indexdaten da komprimiert im Speicher halten kann und mit einer SPU on the fly auspackt. Und da lohnt sich das auf jeden Fall (es "kostet" ja nix). Auf dem PC wird sich das vermutlich nicht lohnen.

Gruß
Julien

[TGGC]

http://www.pouet.net/prod.php?which=31520
http://www.pouet.net/prod.php?which=30204 f'`8k


Gruß, TGGC (Video!)

[Helmut]

http://www.pouet.net/prod.php?which=31520
http://www.pouet.net/prod.php?which=30204 f'`8k

Warum berühren die Schuhe nicht den Boden?

Hast übrigens versehentlich im falschen Thread gepostet.

Ciao

[TGGC]

Weils nur 4kb Speicher benoetigen darf.

Nein, ist genau der richtige Thread hier. f'`8k


Gruß, TGGC (Video!)

[Krishty]

Ich hatte eben mal eine halbe Stunde Zeit und den Algorithmus kurz mal implementiert: http://pastebin.com/m36f29534 . Ergebnis für den SEHR kleinen Testfall: 85% Reduktion. Ich hatte leider hier keinen anständigen Ladecode rumliegen den ich veröffentlichen könnte. Aber wenn das jemand mal mit richtigen Modeldaten ausprobieren mag, würde mich das Ergebnis interessieren. Ich werde es wohl nächste Woche auch nochmal in der Firma ausprobieren.

Das wäre toll - wir sollten uns dabei mal auf eine gemeinsame Indexliste einigen, deine besagte Liste bekommt man ja schon auf 1:4 indem man einfach nur die vorderen 12 Bits jedes Indizes abschneidet :)

Deine Implementation werde ich mir auf jeden Fall mal ansehen, weil du ja offenbar nicht solche Veränderungen daran vorgenommen hast wie ich - der Vergleich interessiert mich brennend :)

Edit: Mit den 3072 Dreiecken und 1500 Vertices, die ich immer teste, kommt dein Code auf 46,2% (61% nach dem ersten Pass) oder 1 : 2,16. Sorry dass hier erst was mit 1 : 1,83 stand, das 1 - x in deiner Anzeige war so verwirrend ;)

Eine Frage zur Motivation: nehmen bei Euch die Indexbuffer so viel Speicher ein, dass sich solche Optimierung überhaupt lohnt? Bei mir sind die VertexBuffer irgendwie immer um den Faktor 10 größer.

Meine Vertices werden bereits komprimiert und im Vertex-Shader entpackt, nun sind die Indizes dran (natürlich nur im RAM, nicht auf der GPU), ansonsten: Just for fun :)

[Dirk Schulz]

Hi,

Krishty, kannst du die Indexliste vielleicht irgendwo online stellen und sagen, wie groß die bei dir ist?

Man könnte daraus ja nen kleinen Wettbewerb machen ;)

@ TGGC: meinst du damit, dass die Demoszene sowas auch benutzt, um ihre Programme klein zu halten, oder was? Manchmal wären Erklärungen zu den Links schon sinnvoll!

Dirk Schulz

[Krishty]

Ich nehme mal das (erledigt) aus dem Thread-Titel ...

Krishty, kannst du die Indexliste vielleicht irgendwo online stellen und sagen, wie groß die bei dir ist?

Wie meinen? Die rohe, die Komprimierte, ...?

Ich bin dafür, dass wir uns ein Modell mit rund 10k Flächen und 5-10k Vertices suchen, es mit einem professionellen Vertex-Cache-Optimizer optimieren (wie sieht es da in Assimp aus? Wer ist dort dafür zuständig?) und seine Indexliste dann als Referenz nutzen.

Man könnte daraus ja nen kleinen Wettbewerb machen ;)

Hehe, ganz genau :P


Mir kamen da übrigens noch ein paar Ideen: Vertex-Cache-Optimizer erzeugen meist Triangle-Strips. Wenn man das berücksichtigt, also auf eine Kante der vorausgehenden Vertices zugreift, kann man sicher ordentlich was rausholen.

Weiterhin schreibe ich gerade eine Anwendung, die eine Indexliste auf Lokalität überprüft: "Wieviele Indizes der vorausgegangenen Dreiecke liegen nicht weiter als 4 entfernt", "wie oft liegen geteilte Kanten direkt hintereinander" usw. Man muss seinen Feind ja kennen ...

[Dirk Schulz]

Hi,

MistVerdammIch, mit der Idee wollte ich eigentlich ganz groß rauskommen (Lokalität). Da die meisten Indices ja relativ nah aneinander liegen, habe ich nur den offset gespeichert (3 Bit -> 1 Vorzeichen, 2Bit Abstand). Die Liste von Julien hat damit dann ne Kompression von 1:4.

Mit der Indexliste meinte ich schon die rohe, als Array. Werde mal Assimp einbinden und mal an ein paar Modellen herumprobieren.

Dirk Schulz

[Krishty]

Bei mir liegen 50% der Indizes -1 bis +1 von den vorherigen entfernt, 80% -16 bis +16. Hatte mal angefangen, das umzusetzen - dann wurde es mir aber zu komplex (stand alles schonmal in einem früheren Post).
Wo kann ich die Datei denn hochladen? ZFX erlaubt nur-Daten-Dateien wohl nicht ...

[Julien Koenen]

Edit: Mit den 3072 Dreiecken und 1500 Vertices, die ich immer teste, kommt dein Code auf 46,2% (61% nach dem ersten Pass) oder 1 : 2,16. Sorry dass hier erst was mit 1 : 1,83 stand, das 1 - x in deiner Anzeige war so verwirrend ;)

Hmm.. das klingt nach einem schlechten Vertex-cache optimierer ;) Oder es ist ein merkwürdiges Mesh. Evtl. finde ich ja nochmal ein bisschen Zeit das weiter zu verfolgen. Heute leider nicht. Kannst du mir evtl. noch sagen, wieviele bits er pro index am Ende brauchte? (Die "numberOfBitsRequired" variable)?

Gruß
Julien

[Krishty]

Hmm.. das klingt nach einem schlechten Vertex-cache optimierer ;)

Darum schlage ich vor, dass wir für ein Referenzmesh einen professionellen benutzen … Assimp scheint in der Hinsicht nicht so doll zu sein … :/

Kannst du mir evtl. noch sagen, wieviele bits er pro index am Ende brauchte? (Die "numberOfBitsRequired" variable)?

Zwölf. Was komisch ist – der größte Index ist irgendwo bei 1400 oder so (bei mir sind es jedenfalls elf). Das Maxdelta liegt auch bei 2049 …

[Julien Koenen]

ähh.. ok. das ist viel zuviel. So 5-7 bit pro delta index sollten reichen ;)

Algorithmus für einen guten vertex cache optimizer:
http://www.ecse.rpi.edu/~lin/K-Cache-Reorder/

Könntest du evtl. deine Indexliste mal irgendwo hochladen?

Gruß
Julien

[Krishty]

Fragte Dirk ja auch schon. Nur, wo? ZFX akzeptiert nur Bilder -.-

[Julien Koenen]

Konvertier sie in ein .hpp file? ;) Dann muss man auch keine Dateien laden zum testen ;)

Gruß
Julien

[Krishty]

Igitt, ASCII-Daten?!? :P

[Seraph]

Wo kann ich die Datei denn hochladen? ZFX erlaubt nur-Daten-Dateien wohl nicht ...

Versuch es mal zu archivieren und dann hochzuladen.

[Krishty]

Yes, Sir. Heute ist mein einfallsloser Tag.

[Aramis]

Assimp scheint in der Hinsicht nicht so doll zu sein … :/

Algorithmen, die etwas ganz anderes optimieren als man optimieren möchte, sind generell nicht so doll :!:

Assimp's VCache-Optimizer verwendet Tipsify, und funktioniert an sich ganz gut. Im Prinzip generiert er - wie bereits von Dir genannt - möglichst lange TriStrips, das ganze in O(n). Dabei ändert er die Reihenfolge der Indizes ... was deren Eignung für eure Deltakompression naturgemäß eher verschlechtert. aiProcess_JoinIdenticalVertices ohne aiProcess_ImproveCacheLocality hingegen sollte ganz brauchbare Indizes ergeben.

Dieses Manko könnte man natürlich beheben. Nur wäre ich damals nie auf die Idee gekommen dass daraus jemals ein Problem entstehen könnte :-)

Bei mir liegen 50% der Indizes -1 bis +1 von den vorherigen entfernt, 80% -16 bis +16

Jupp, das wäre ziemlich genau das was ich erwartet hätte. Höchstwahrscheinlich sogar ein Eingabemesh das sich verhältnismäßig gut für die Kompression eignet(e).

[TGGC]

@Dirk: Das heisst, das die verlinkten Programme ohne eine solche Art von Kompression nicht moeglich waeren. f'`8k

[ ] Autocogito


Gruß, TGGC (Video!)

[Krishty]

Assimp's VCache-Optimizer verwendet Tipsify, und funktioniert an sich ganz gut. Im Prinzip generiert er - wie bereits von Dir genannt - möglichst lange TriStrips, das ganze in O(n). Dabei ändert er die Reihenfolge der Indizes ... was deren Eignung für eure Deltakompression naturgemäß eher verschlechtert.

Sehr gut zu wissen, danke :)

aiProcess_JoinIdenticalVertices ohne aiProcess_ImproveCacheLocality hingegen sollte ganz brauchbare Indizes ergeben.

Mit Optimierung erreiche ich 1 : 2,32 oder 43%, ohne nur 1 : 2,23 oder 44,7%. Es macht also eher einen Unterschied zum Negativen als zum Positiven, wobei Juliens Algorithmus aber vielleicht wieder anders reagieren würde – sagen kann ich es aber nicht, ich werde mich mal aufmachen, die neue Indexliste zu extrahieren. Oder wir sehen uns direkt nach einem interessanten Model um …

[Julien Koenen]

Hmm. ok. die index liste hat ein acmr (average cache miss rate) von 0.7070 für eine cache size von 20 Einträgen (FIFO). Das ist eigentlich wirklich nicht soo schlecht. Ich habe noch eine Idee wie man die Kompression verbessern könnte, aber ich komme wahrscheinlich erst am Wochenende dazu.

Gruß
Julien

[Krishty]

Mal eine andere Frage: Wenn Assimp schon so schöne Triangle-Strips erzeugt, was hindert mich eigentlich daran, die Meshes auch wirklich als Triangle-Strips zu rendern? So wie ich das sehe, spare ich dabei auch im fertigen Index-Buffer noch Platz (bestenfalls braucht jedes Dreieck nurnoch einen Index), es ist mindestens genauso schnell wie "normale" Indizes und der einzige Nachteil wäre, dass ich degenerierte Dreiecke einfügen müsste, um die Lücken zwischen den Strips zu überbrücken.

Oder übersehe ich da etwas?

[Julien Koenen]

Natürlich kannst du einfach direkt Trianglestrips rendern. Dann kommst du halt nicht unter 16 bit / dreieck, aber du hast den Vorteil, dass du es auch auf dem PC direkt rendern kannst. Aber wo bleibt der sportliche Ehrgeiz? ;) Ich denke mehr als 7 bit / dreieck sollte man nicht brauchen. (Wie war das mit dem Wettbewerb?)

Gruß
Julien

[Krishty]

Hehe, ich würde meine Kompressionsversuche deshalb natürlich noch nicht aufgeben :)

Aber wie ich hier gelesen habe, bedeuten Triangle-Strips nicht unbedingt hohe Lokalität oder höhere Geschwindigkeit ... und bei "schlimmen" Meshes hat man am Ende trotzdem mehr Daten als bei normalen Indizes ...

Ich werde mir wahrscheinlich einen Hybridansatz überlegen, um vorausgehende Kanten und Indizes gleich referenzieren zu können ... aber erstmal muss ich Vorarbeit leisten ...

[Aramis]

Hmm. ok. die index liste hat ein acmr (average cache miss rate) von 0.7070 für eine cache size von 20 Einträgen (FIFO). Das ist eigentlich wirklich nicht soo schlecht

Ihr könnt die Cachegröße auf die Assimp hin optimiert auch manuell setzen. Defaultwert ist 16.

[Schrompf]

Was die Anzahl der Indizes angeht, kann ich keine Aussagen machen. Was aber die Renderperformance angeht, ist der Fall klar: Triangle Strips sind durch die degenerierten Zwischendreiecke *immer* langsamer als freie Dreieckshäufchen, die genauso sortiert sind. Die Sortierung ist das Entscheidende. Den Rest macht der Post-Vertex-Cache der Grafikkarte.