„Index Compression“ – wie effizient?

[Krishty]

Hi,

Hier gibt es ein paar Unklarheiten über ein Paper.


In diesem Paper wird ab Seite 35 eine Methode beschrieben, um Indexdaten von Dreiecksmeshes zu komprimieren. Die Methode selbst entspricht so einer Art RLE-Encoding … ich zitiere einfach mal ein Beispiel. Das hier sind die Indizes:

Code: Alles auswählen

 0  1  2
 0  2  3
 3  2  4

Anstatt die einfach so zu speichern, speichert man eine zwei-Bit-Information darüber, ob der Index bereits im vorherigen Dreieck vorkam oder ob er „frisch“ ist. 00 bedeutet new, 01, 10 und 11 bedeuten, dass der Index aus dem vorherigen Dreieck stammt:

Code: Alles auswählen

new 0  new 1  new 2
prev0  prev2  new 3
prev2  prev1  new 4

Da Vertex-Cache-Optimizer sehr regelmäßige Indizes erzeugen, funktioniert die Methode damit besonders gut.


Soweit, sogut. Jetzt das eigentliche Problem … auch hier zitiere ich wieder das Paper:

85% compression
6.5 : 1

Okay. Wie soll das denn bitte gehen!?


Überschlagen wir das Ganze mal:
– Ein unkomprimierter Index ist 18 Bits groß. Zwei um zu markieren, dass er „frisch“ ist sowie 16 für die Zahl selbst.
– Ein komprimierter Index ist zwei Bits groß.
– In zwei Dreiecken sind immer mindestens zwei der drei Indizes unterschiedlich, denn sonst wäre es dasselbe Dreieck.
Selbst wenn wir nun davon ausgehen, dass immer nur der beste Fall eintritt und die Indizes perfekt regelmäßig wären (toller Optimizer, Rotation usw), würde das bedeuten, dass zwei Drittel aller Indizes zwei Bits groß sind und ein Drittel 18 Bits. Das macht im Schnitt 1 1/3 + 6 = 7 1/3 Bits pro Index – oder eine Kompression von 2,18 : 1.

Wie kommt das Paper nun auf die dreifache Kompression?!?

Selbst in dem Beispiel aus dem Paper lassen sich nur 11 von 24 Indizes komprimieren. Ich habe das selbst mal getestet und bei einem gewöhnlichen Mesh, mit Assimps Locality-Improver geladen, liegen die tatsächlich komprimierbaren Indizes bei rund 50%. Das geht eher auf eine Kompression von 1,7 : 1 zu.


Ich habe die Methode ein wenig erweitert: Bei mir markiert ein einziges Bit, ob der Index komprimiert ist, oder nicht. Bei komprimierten Indizes folgen dann n weitere Bits um 2^n vorherige Indizes wiederzuverwenden. Mal meine Kompressionsraten mit verschiedenen ns:
Zwei Bits: 62% komprimierbar, Kompression 1,78 : 1
Drei Bits: 70% komprimierbar, Kompression 1,87 : 1
Vier Bits: 75% komprimierbar, Kompression 1,81 : 1
Fünf Bits: 76% komprimierbar, Kompression 1,69 : 1


Also, habe ich da etwas fundamental falsch verstanden oder ist 6,5 : 1 einfach aus der Luft gegriffen?

Gruß, Ky

[Zudomon]

Hab mal flüchtig drüber geschaut. Ich glaube aber, die komprimieren nicht einen Index, sondern 3 in diesen 2 Bit.... sah zumindest so aus.

Edit: Also ein unkomprimiertes Dreieck ist somit 16 + 16 + 16 + 2 = 50 Bits und in den anderen drei Fällen 18 Bits. Musst mal ausrechnen, ob das dann eher hinkommt mit dem Verhältnis... ich bin dazu jetzt zu müde. ;)

[Krishty]

Jetzt wo du es sagst: Sie scheinen tatsächlich zwei Indizes in zwei Bits zu komprimieren … erst wird so rotiert, dass der neue Index immer hinten steht und dann wird in den zwei Bits gespeichert, welchen vorherigen Indizes die ersten beiden Indizes entsprechen, oder ob das komplette Dreieck neugeschrieben wird … sehr interessant …

… damit wären im Optimalfall 18 Bits pro Dreieck drin (zwei für die ersten beiden Indizes, 16 für den Neuen) – also 2,667 : 1 … besser als vorher, aber immernoch 2,5 Mal zu schlecht :(

Für 6,5 : 1 müssten sie drei 16-Bit-Indizes in durchschnittlich 7,4 Bits quetschen …

[TGGC]

Selbst wenn man durch welchen Trick auch immer nur noch einen statt 3 Indizes per Dreieck speichert, so kann man ja nur 1:3 erreichen. Das ist also auf jeden Fall eine Obergrenze fuer die Kompression, die dieser Algorithmus allein erreicht. f'`8k

[ ] Autocogito


Gruß, TGGC (Video!)

[Krishty]

Also wie befürchtet – es fehlt entweder der Algorithmus mit der stärksten Wirkung oder es sind geschönte Zahlen … da hat sich sicher jemand gedacht, das baue eh niemand nach :roll: …

[Schrompf]

Evtl. sind die Autoren aber auch nur von 32Bit-Indizes ausgegangen, damit die Zahlen schöner aussehen.

[TGGC]

Das aendert aber nichts an meinem Argument. Interessant waere natuerlich, wenn man auch "neuer Vertex" abkuerzt, und dann alles so anordnet, das man die neuen Indizes einfach durchnummeriert, z.b.

neu, neu, neu
alt1, alt2, neu
neu, neu, neu
alt1, alt2, neu

ergaebe dann:

0, 1, 2
0, 2, 3,
4, 5, 6,
4, 5, 7

iq von RGBA hat dazu auch mal einen Vortrag gehalten, danach koennte man mal suchen. Er hat da allerdings nur darauf optimiert, das ein normale Packalgo diese Daten dann gut packen kann. f'`8k


Gruß, TGGC (Video!)

[Julien Koenen]

Man braucht ja keine 16 bit für den neuen Index. Da reichen im Schnitt deutlich weniger (5-7), da man die indices ja delta-komprimieren kann. (Also vorher eine Liste der neuen Indices bauen, jeweils den Indexwert des Vorgängers abziehen, bias auf 0 addieren (und merken) und dann die deltas in möglichst wenig Bits speichern).

Gruß
Julien

[Krishty]

Stimmt. Ich habe hier gerade nur ein Modell mit 1800 Vertices zur Hand, aber dort liegen zwei Drittel aller neuen Indizes nicht weiter als zwei Bits von einem der vorherigen Werte entfernt. Wenn ich gar vier Bits als Offset speichere, decke ich damit 85% aller neuen Indizes zum Preis von neun Bits und die verbliebenen 15% zum Preis von 17 Bits ab, statt wie bisher alle für 16. TGGCs Inkrementelle Methode wäre nochmals effizienter, weil 50% der Indizes nur eins entfernt liegen. Das könnte sich sehr gut rechnen, ich werde es direkt testen.

Man kann die Liste außerdem in einige größere Happen unterteilen, den kleinsten darin vorkommenden Index ermitteln, von allen Indizes abziehen und gesondert speichern. Dadurch werden die Zahlen kleiner und man kann auf ein paar zusätzliche Bits verzichten. (Splitten der Liste habe ich eh vor, damit ordentlich parallelisiert werden kann.)

Sobald mehr als ein Pass ins Spiel kommt, wird die Kompression für mich allerdings uninteressant … soll noch einigermaßen performant bleiben.

[Julien Koenen]

In dem Paper ging es ja vor allem um die PS3 und die SPUs. Da sind mehrere Passes normalerweise kein Problem, da üblicherweise der DMA Transfer vom nächsten Stück sowieso abgewartet werden muss (solange hat man ja eh "Freizeit").

Gruß
Julien

[eXile]

Also die Angabe, dass genau eine Kompression von 6.5 zu 1 erreicht wurde, ist falsch. Schließlich gibt es keinen Komprimierer, welche eine beliebige Eingabe immer in seiner Größe bei gleichbleibenden Informationsgehalt verkleinern kann.

[TGGC]

Doch gibt es, z.b. Texturkompression.

Wie dem auch sei, die Kompression von zwei aus drei Indizes, wie im Paper beschrieben, reicht nicht aus um diese Rate - ob nun genau oder in etwa - zu erreichen. f'`8k


Gruß, TGGC (Video!)

[Krishty]

Doch gibt es, z.b. Texturkompression.

Texturkompression ist lossy, das kann man nicht wirklich vergleichen – von daher hat eXile auch recht. Andererseits bin ich auch nie davon ausgegangen, exakt diesen Wert zu erreichen … aber nur ein Drittel ist schon irgendwie enttäuschend.

Wie auch immer, bei mir hat sich das jetzt bei 2,33 : 1 (43% der Ursprungsgröße) eingependelt … als „nebenbei“ implementiertes Luxusfeature bin ich damit recht zufrieden, zumal der Parser bei höherer Kompression viel zu komplex und unübersichtlich (und damit langsam) wird, daher lasse ich es auch erstmal gut sein …

… vielen Dank für eure Hilfe :)

P.S.: Es steht noch etwas Refactoring an, danach kann ich euch den Quellcode auf Anfrage bereitstellen.

[TGGC]

Doch gibt es, z.b. Texturkompression.

Texturkompression ist lossy, das kann man nicht wirklich vergleichen – von daher hat eXile auch recht.

Heute werden lossy Verfahren fuer so gut wie alle Daten benutzt - sie sind eher Standard als Ausnahme. Das Verfahren hier ist auch lossy, denn es tauscht ja beliebiebig den Start des Dreiecks. f'`8k

[ ] Autocogito


Gruß, TGGC (Video!)

[eXile]

Heute werden lossy Verfahren fuer so gut wie alle Daten benutzt - sie sind eher Standard als Ausnahme. Das Verfahren hier ist auch lossy, denn es tauscht ja beliebiebig den Start des Dreiecks.

Dass heute solche Verfahren häufig eingesetzt werden, ist völlig wurscht. Es geht hierbei um eine Aussage mathematischer Natur - in dem Paper ist eine Kompressionsrate < 1 für einen Komprimierer gegeben, welche (da dort keine weiteren Einschränkungen an die Eingabe gemacht wurden) allquantifiziert ist.
Da es keine injektive Abbildung gibt, welche eine Menge A auf eine Menge B mit |A| > |B| abbildet, gibt es zwei Urbilder, welche auf dasselbe Bild abgebildet werden. Seien diese zwei Urbilder a != b und das Bild c. Dabei kann Gleichheit gerade im intuitiven Sinne (als Menge von Dreiecken mit denselben Verbindungen) definiert sein, in jedem Falle erhält man so den Widerspruch, dass der Komprimierer unter obiger Annahme nicht korrekt arbeitet. Also: Widerspruch, und die obige Annahme ist falsch, und die Kompressionsrate ist nicht immer < 1.

[TGGC]

Was wird das jetzt, Unwissen mit Hilfe pseudowissenschaftlichen Gebrabbel verstecken? Scheisse in schoenen Tueten? Nicht nur das du Unsinn erzaehlst - es stelt noch nicht mal im geringsten eine "Antwort" auf meine Aussage dar.

Schließlich gibt es keinen Komprimierer, welche eine beliebige Eingabe immer in seiner Größe bei gleichbleibenden Informationsgehalt verkleinern kann.

Dies stellt dann ja wohl auch eine allquantifizierte Aussage dar. Eine falsche Aussage. f'`8k

[ ] Autocogito


Gruß, TGGC (Video!)

[EyDu]

Was heißt hier pseudowissenschaftliches Gebrabbel? eXiles Beweis ist so korrekt und zeigt, dass es keine Kompression geben kann, welche im allgemeinen Fall Daten verlustfrei komprimieren kann.

Wenn ich es richtig in Erinnerung habe, dann werden die Indizes nicht beliebig vertauscht, sonder die Reihenfolge rotiert. Das kann durchaus in diesem Kontext verlustfrei sein, wenn die Reihenfolge nicht weiter benötigt wird, oder alle abhängigen Informationen daran angepasst werden.

[Julien Koenen]

Ähh.. es geht doch um die praktisch (unter realistischen Eingangsdaten) erreichbaren Kompressionsraten und nicht um die garantierte Rate bei Worst-case Eingaben. Also ist dein ganzen "pseudowissenschaftlichen Gebrabbel " etwas inhaltsleer (um es vorsichtig auszudrücken).

Gruß
Julien

[eXile]

Was wird das jetzt, Unwissen mit Hilfe pseudowissenschaftlichen Gebrabbel verstecken? Scheisse in schoenen Tueten? Nicht nur das du Unsinn erzaehlst - es stelt noch nicht mal im geringsten eine "Antwort" auf meine Aussage dar.

Schließlich gibt es keinen Komprimierer, welche eine beliebige Eingabe immer in seiner Größe bei gleichbleibenden Informationsgehalt verkleinern kann.

Dies stellt dann ja wohl auch eine allquantifizierte Aussage dar. Eine falsche Aussage.

Ich weiß zwar nicht, was du mit "pseudowissenschaftlichen Gebrabbel" meinst, denn im Grunde steckt hinter meinen Aussagen nur das Schubfachprinzip - sehr pseudowissenschaftlich also. Die paar mathematischen Begriffe, die in meinem Beitrag steckten, lernt man in der Regel schon in der Schule.
Auch war mir nicht im geringsten daran, eine "Antwort auf eine Aussage zu geben". Ich habe deine Aussage widerlegt - und Antworten gibt es wenn überhaupt nur auf Fragen. Leider schaffst du es nicht, in deinem Beitrag selbst dazulegen, warum die zitierte Aussage falsch ist - genau das fällt meiner Meinung nach unter "pseudowissenschaftlich".

Da das eigentliche Kernthema dieses Threads bereits gelöst ist, werde ich wohl nichts weiteres in diesem Thread mehr posten. Nur eines als "Moral von der Geschicht'": Wenn irgendwer behauptet, dass er ein Programm geschrieben hat, was verlustfrei jede Art von Daten komprimieren kann, ist er im Unrecht. ;)

[Zudomon]

Man kann Informationen nicht verlustfrei komprimieren. Versucht mal 4 Zustände in weniger als 2 Bit unterzubringen. :D
Das einzigste, was möglich ist, Redundanz in Datenmengen zu reduzieren. Das bedeutet, in jeder Datenmenge steckt ein gewisser Informationsgehalt und gewisse Redundanz.
Ich kenne da die Huffman- und die Arithmetische Kodierung. Huffman wird soweit ich weiß für die ganzen gängigen Packer eingesetzt, z.B. zip, rar usw. Dabei wird eine Art Wörterbuch erstellt, bei dem versucht wird, große Redudanzen durch relativ wenig Bits zu komprimieren. Bei der Arithmetischen Kodierung, wird berechnet, wie viel Information benötigt wird, um einen bestimmten Wert dazustellen. Erstaunlich ist bei diesem Verfahren, dass z.B. das Optimum einer Information z.B. auch in 2,3 Bits abgebildet werden kann.
http://de.wikipedia.org/wiki/Huffman-Code#Huffman_Code
http://de.wikipedia.org/wiki/Arithmetische_Kodierung

Verlustbehaftete Komprimierung entgegen nimmt gezielt Informationen, die für die menschliche Wahrnehmung am unrelevantesten sind, weg. Also im Gegensatz zu den verlustfreien Komprimierungen wird hier nicht Redundanz gefiltert sondern Informationen ausgelassen.

[Julien Koenen]

Tut mir leid, aber ich muss nochmal auf diesen Dünnschiss reagieren:

" was verlustfrei jede Art von Daten komprimieren kann,". Das ist trivial und nicht Inhalt dieses Threads gewesen. Es ging um sehr spezielle Daten die Redundanzen aufweisen und nicht um "jede Art von Daten". Ich mag auch diese absolut unnötige (und etwas lächerliche) Arroganz in deinem Post nicht (eXile). Evtl. solltest du dir über deine Aussenwirkung genausoviel Gedanken machen wie über das Thema Kompression.

Gruß
Julien

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

[Aramis]

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

Hm .. Genau genommen ist das hier der erste Thread seit langem in dem Leute anfangen sich inhaltslos anzuschimpfen. Lasst es doch einfach an dieser Stelle auf sich beruhen, und gut ist. Schließlich steht da schon lange ein (erledigt) im Threadtitel :-)

[Dirk Schulz]

Hi,

hm ... Entschuldigung, wenn ich mich jetzt doof anstelle, aber die Kompression kann man nur für die Speicherung im Model-Format anwenden, oder?

Wäre ja toll, wenn man IndexBuffer so komprimieren könnte, aber das geht wohl (noch) nicht, oder? (unter Direct3D9)

Code würde ich persönlich gerne sehen!

Dirk Schulz

[eXile]

Es tut mir leid, aber finde ein paar Worte sind noch angebracht.

Ähh.. es geht doch um die praktisch (unter realistischen Eingangsdaten) erreichbaren Kompressionsraten und nicht um die garantierte Rate bei Worst-case Eingaben. Also ist dein ganzen "pseudowissenschaftlichen Gebrabbel " etwas inhaltsleer (um es vorsichtig auszudrücken).

Mein "Gebrabbel" ist genauso inhaltsleer, wie jeder andere mathematische Beweis auch. Eine Aussage ist gegeben, der Beweis über die Korrektheit der Aussage ist geführt worden. Ich habe nicht von "realistischen" Daten gesprochen. Web-Programmierer können ja auch nicht nur "realistische" Daten vorraussetzen, um dann im Nu von SQL-Injections überrascht zu werden. Auf der Folie steht einfach nur "85% compression". In den presenter's notes steht dann genauer "We’re typically removing about 85% of the index data in this fashion.". Das ist eine meiner Meinung nach vollkommen legitime Aussage. Lediglich einfach nur auf die Folie "85% compression" zu setzen, halte ich für irreführend.

Tut mir leid, aber ich muss nochmal auf diesen Dünnschiss reagieren:

" was verlustfrei jede Art von Daten komprimieren kann,". Das ist trivial und nicht Inhalt dieses Threads gewesen. Es ging um sehr spezielle Daten die Redundanzen aufweisen und nicht um "jede Art von Daten". Ich mag auch diese absolut unnötige (und etwas lächerliche) Arroganz in deinem Post nicht (eXile). Evtl. solltest du dir über deine Aussenwirkung genausoviel Gedanken machen wie über das Thema Kompression.

Anscheinend ist es wohl doch nicht so trivial - denn du hast es leider immer noch nicht verstanden. Du kannst einen wunderschönen, tollen Komprimierer basteln, welcher die Daten aus dem Paper komprimieren kann. Im Regelfall wird der auch gut etwas komprimieren können. Doch darum geht es bei dem obigen Beweis nicht, wie du festgestellt haben wirst. Ich kann deinen tollen Komprimierer immer Daten geben, bei welchem keine Kompression möglich ist - egal, was du auch machst. Dies ist zumindest bezüglich dieses Threadthemas meiner Meinung nach einen Gedankengang wert.
Diese "unnötige" und "lächerliche Arroganz" kann ich nicht feststellen. Gegenfrage: Hast du Erfahrung im mathematischem Beweisen? Meiner Meinung nach ist das ein völlig normaler, ja alltäglicher Beweisstil gewesen. Aber insofern genüge ich ja deinem letzten Satz: Ich habe nur eine ganz grundlegende Eigenschaft von Komprimierer aufgegriffen, die ohne viele Gedanken leicht zu durchschauen ist. Genauso wenige Gedanken muss ich beim Beweis darauf verschwenden, wie ich danach in den Augen anderer dastehe.

Wäre ja toll, wenn man IndexBuffer so komprimieren könnte, aber das geht wohl (noch) nicht, oder? (unter Direct3D9)

Ich glaube, das geht nicht. Schließlich kann die Grafikkarte nicht einfach den neuen Algorithmus "lernen". Von daher denke, dass dies vorallem bei der Speicherung eine Rolle spielt, bzw. falls das Modell geladen wurde, aber zunächst feststeht, dass es noch nicht "renderfertig" sein muss.

[TGGC]

@Dirk: Ich persoenlich mache mir Gedanken um die Speicherung bzw. Modelformat "hobbybedingt" quasi. ;-)

Verlustbehaftete Komprimierung entgegen nimmt gezielt Informationen, die für die menschliche Wahrnehmung am unrelevantesten sind, weg. Also im Gegensatz zu den verlustfreien Komprimierungen wird hier nicht Redundanz gefiltert sondern Informationen ausgelassen.

Welche Information weggelassen wird bzw. welche gerade "unrelevant" sein soll, ist natuerlich relativ. Und genau so macht es auch diese Index Kompression, wenn man sich diese mal kurz vor Augen fuehrt. Zunaechst werden alle Dreiecke geordnet, das die folgenden Dreiecke moeglichst viele Indizes mit den vorhergehenden gemein haben. Danach wird noch der jeweils neue Index nach hinten gesetzt. Wenn man das Mesh nur normal rendern will, brauch man die Informationen ueber die Reihenfolge ja auch nicht. Aber natuerlich gibts auch Faelle (Alphablending, Editieren, Optimierung auf FrontToBack Rendering) wo diese Information nuetzlich sein kann - dann ist diese Kompression nicht so toll.

Ich nehme an, da fuer die Mehrzahl der Nutzer hier eine Antwort auf eXiles Ausfuehrungen nutzlos und da diese ohnehin nichts bewirkt, sollte ich diese wohl unterlassen. f'`8k

[ ] Autocogito


Gruß, TGGC (Video!)

[Krishty]

Hm .. Genau genommen ist das hier der erste Thread seit langem in dem Leute anfangen sich inhaltslos anzuschimpfen.

Da stoßen Programmierer, Informatiker und Mathematiker auf eine Aussage, die sie alle drei komplett unterschiedlich deuten …

… ich als Programmierer sehe hier einen Fall, der bei Bild-, Ton- und Textkompression eher unüblich ist: Dass dieselben Daten drei unterschiedliche binäre Repräsentationen haben. In der Rotation der Indizes ist keine Information enthalten, die ich je auswerten würde. Darum geht bei der Kompression keine Information verloren und sie ist verlustfrei.

Dann schreit der Informatiker natürlich, das Bitmuster sei unterschiedlich, ergo die Kompression verlustbehaftet. Der Mathematiker kommt mit irgenwelchen Abbildungen usw usf … und schon ist der Flamewar perfekt.

Also, ich meinte das in der Hinsicht, dass man bei Texturkompression Artefakte sieht, wenn man nah ranzoomt. Bei MP3 hört man Artefakte, wenn man langsamer abspielt. Aber bei Indexkompression kann man ranzoomen, das Modell drehen und wenden wie man will: Es sieht genauso aus wie vorher. Die binäre Repräsentation mag unterschiedlich sein, aber sie ist in jedem Fall richtig.

hm ... Entschuldigung, wenn ich mich jetzt doof anstelle, aber die Kompression kann man nur für die Speicherung im Model-Format anwenden, oder?

Wäre ja toll, wenn man IndexBuffer so komprimieren könnte, aber das geht wohl (noch) nicht, oder? (unter Direct3D9)

Ja, Index-Buffer bleiben leider (auch unter D3D10/11) unkomprimiert. Da ich aber jedes Modell designbedingt nochmal im Speicher haben muss und die Kompression in einem einzelnen Pass ausreichend schnell scheint, kann ich hier und da ein paar KiB Arbeitsspeicher sparen. Es hat nicht wirklich den großen Nutzen, aber es macht mir Spaß, mit sowas zu spielen.

Code würde ich persönlich gerne sehen!

Ich hoffe, ihn bis morgen fertig zu haben – dann poste ich ihn hier :)

Wenn man das Mesh nur normal rendern will, brauch man die Informationen ueber die Reihenfolge ja auch nicht. Aber natuerlich gibts auch Faelle (Alphablending, Editieren, Optimierung auf FrontToBack Rendering) wo diese Information nuetzlich sein kann - dann ist diese Kompression nicht so toll.

Wobei man dazusagen muss, dass die Cache-Optimierung nicht zwingend erforderlich ist (ich habe sie ja auch nicht als Teil der Kompression implementiert, sondern nutze die von Assimp). Theoretisch lassen sich alle Indizes komprimieren, nur wahrscheinlich bedeutend schlechter, wenn die Reihenfolge der Dreiecke für einen deiner o.g. Fälle wichtig ist.

[Zudomon]

Wenn das ganze nur zum speichern relevant ist, hat jemand mal probiert, wie viel es denn bringt, einfach eine Indexliste normal zu komprimieren? (zip etc.)

[Julien Koenen]

Es tut mir leid, aber finde ein paar Worte sind noch angebracht.

Ok, dann muss ich wohl auch noch mal ein paar Dinge klarstellen.

Ich habe nicht von "realistischen" Daten gesprochen. Web-Programmierer können ja auch nicht nur "realistische" Daten vorraussetzen, um dann im Nu von SQL-Injections überrascht zu werden.

Das ist absoluter Quatsch. Was haben SQL-Injections denn mit dem Thema zu tun? Es geht hier um einen völlig normalen Vorgang in der Informatiker-Praxis. Man guckt sich typische Datenmuster an, um darin Redundanzen zu erkennen und damit Kompressionsmöglichkeiten zu haben. Natürlich kann man eine Worst-case Mesh erzeugen, dass einfach nicht gut mit dieser Methode komprimierbar ist, aber "normale" Meshes sind nunmal zusammenhängend und haben viele Redundanzen in der Indexliste. Das kann man jetzt einfach ignorieren, weil es nicht "immer" auftritt, oder man macht das beste draus. Das ist evtl. ein Problem der Unterschiedlichen Sichtweise (Theorie<->Praxis)

Lediglich einfach nur auf die Folie "85% compression" zu setzen, halte ich für irreführend.

Das sind (verkürzte) Folien eines Vortrages. Es ist durchaus üblich, dass man nicht komplette Beweise auf Vortragsfolien packt und einige der (evtl. wichtigen) Informationen nur im Audio-Teil des Vortrages vorhanden sind.

Anscheinend ist es wohl doch nicht so trivial - denn du hast es leider immer noch nicht verstanden.

Doch, es ist trivial. Und ich habe es auch verstanden.

Ich kann deinen tollen Komprimierer immer Daten geben, bei welchem keine Kompression möglich ist - egal, was du auch machst.

Und? Das ist ja aber kein Problem, weil einfach in der Praxis ALLE Indexlisten diese Redundanzen aufweisen (Und wenn nicht, speichert man das Mesh halt unkomprimiert (oder gleich komplett ohne Indizierung))

Dies ist zumindest bezüglich dieses Threadthemas meiner Meinung nach einen Gedankengang wert. Diese "unnötige" und "lächerliche Arroganz" kann ich nicht feststellen.

Wenn du das meinst, dann kann man das anders formulieren. Ein Hinweis darauf, dass es theoretische Grenzen für die Kompression von allgemeinen Daten gibt ist sicher wertvoll. Aber der Ton macht die Musik.

Gegenfrage: Hast du Erfahrung im mathematischem Beweisen?

Ja, habe ich.

Genauso wenige Gedanken muss ich beim Beweis darauf verschwenden, wie ich danach in den Augen anderer dastehe.

Das solltest du aber evtl. Bei der Interaktion mit anderen (durchaus intelligenten Menschen) ist es durchaus üblich sich Gedanken über die Wirkung seiner Aussagen zu machen.

Gruß
Julien

[Krishty]

Wenn das ganze nur zum speichern relevant ist, hat jemand mal probiert, wie viel es denn bringt, einfach eine Indexliste normal zu komprimieren? (zip etc.)

Habe nur ein Model getestet, aber …:

2,75 : 1 mit 7-Zip auf höchster Kompressionsstufe.
1,96 : 1 mit 7-Zip im ZIP-Modus.
2,32 : 1 mit meiner Kompression.

Wenn man TGGCs Vorschlag iterativer Indizes und eine ganze Menge weiterer Tricks einsetzt, sind vielleicht auch die 6,5 : 1 aus dem Paper möglich. Letztendlich beweist es aber wieder einmal: Wenn man weiß, was die Daten bedeuten, fällt die Kompression wesentlich leichter …

Der Code ist nach größerem Bug-Hunt in den letzten Tagen quasi fertig und wird heute abend noch gepostet.


Edit: Voilà …
Es wird natürlich die Bit-Stream-Klasse aus dem anderen Thread benötigt. Die Klasse CTriangle ist prototypisch für eure Dreiecksklasse. Die beiden wichtigen Funktionen, CompressTrianglesToBitStream(…) und ExtractTrianglesFromBitStream(…) findet ihr ganz unten … oben ist eine Einführung in den Algorithmus – aber bitte nicht mein Englisch schlecht machen … mit aller anderen Kritik immerzu drauf, ich halt’s aus :)

[Julien Koenen]

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.

Gruß
Julien

PS: Das ist kein Produktionscode und einfach so runtergehackt .. Also nicht Beschweren, wenn es die Festplatte formatiert ;)