Normalenvektoren für die Quantisierung optimieren

[Krishty]

Hi,

Ich quantisiere momentan Normalenvektoren (eigentlich auch Tangente und Bitangente, wollte nur niemanden mit Tangent-Space abschrecken ;) ) in signed chars (DirectXlern als signed normalized oder SNorm bekannt).

Da ich die Vektoren nach ihrer Rückkonvertierung eh erneut normalisiere, wollte ich die Speicherung optimieren, indem ich die Vektoren bei Bedarf verkürze oder verlängere um eine passendere Quantisierung zu finden. Ich hoffe, ihr wisst was ich meine, sonst zeichne ich euch auch gerne noch ein Bild.

Meine Frage ist nun, wie ich – abgesehen von Brute-Force – die optimale Vektorlänge herausfinden kann?

Gruß, Ky

Edit: Okay, hier mal eine Skizze. Ich demonstriere einfach mal an einem 2D-Vektor, den ich auf 2×2 Bits quantisiere, was ich will:

Wenn ich nur Vektoren der Einheitslänge quantisiere, kann ich nur fünf unterschiedliche Vektoren (Bild oben, Nr. 1, 2, 3, 4, 5) speichern. Wenn ich die Einheitslänge aufgebe, werden es fast doppelt soviele (Bild unten, Nr. 6, 7, 8, 9 kommen dazu). Also, wie komme ich für einen beliebigen Vektor an die optimale Länge?

[Zudomon]

Hi! :D

Wenn du 4 Bits zur Verfügung hast, dann kannst du ja damit 16 Vektoren darstellen. Vielleicht könntest du dich also über eine Art Indextable dahin hangeln.

Ansonsten könntest du eventuell auch mal folgendes probieren:
Du gehst von einer Einheitsmatrix aus, die wird zuerst um die X-Achse und dann um die Y-Achse rotiert. Ich bin mir nicht sicher, aber meiner Meinung nach könntest du damit alle Vektoren erreichen. Da ich mir vorstelle, dass man da dann mit 2 Werte ( die die Rotationen angeben ) komprimiert, könnte man daraus ja dann das komplette Achsensystem ermitteln und hätte so Normale, Tangente und Binormale gespeichert.

Gruß
Zudo

[Krishty]

Naja, die 4 Bits waren nur ein Beispiel, weil eine Zeichnung in 3D mit 8 Bits pro Dimension unübersichtlich geworden wäre :D

An eine Tabelle habe ich auch schon gedacht, das erscheint mir aber ziemlich schwierig – ich habe am Ende zwar „nur“ 16,7 mio mögliche Ergebnisse (bei einem 3D-Vektor in 3×8 Bits), die Indizierung selbst müsste aber durch den rohen Float-Vektor geschehen – und der hat bei drei Floats à 32 Bits eine ganze Menge mehr Zustände … nicht zu vergessen dass ich auch die Lookup-Tabelle irgendwie ausrechnen müsste.

Ja, durch Speicherung der Rotationen (oder direkt Polarkoordinaten) lassen sich Normalen noch besser komprimieren. Es geht hier aber um Normal-Maps, die ich direkt in die Shader lade, und deren Daten in 3×8 Bits zu speichern hat den Vorteil, dass im Shader nur ein normalize() anfällt – nicht je zwei Sinus- und Kosinusoperationen.

[Jörg]

Die naive Loesung ist nicht die schnellste. Eine Verbesserung waere, nur den Sektor abzusuchen, welcher den normierten Vektor einschliesst. Einen Scan-Line Algorithmus ueber das moeglichst minimal-einschliessende Dreieck.
Oder Du nimmst was aus der Vektorquantisierungsecke...da die ja nichts anderes betreiben (nur m.E. mit weniger Constraints auf den Ausgangsvektoren).

[Krishty]

Über die begrenzte Suche denke ich auch nach. Wird ein Vektor ganz ohne Optimierung auf 8 Bits auf jeder Achse quantisiert, streift er dabei (grob geschätzt) höchstens 14 ((8×8×8)^0.5) nähere Zustände … wenn ich den Vektor also in Vierzehnteln quantisiere bekomme ich die vierzehn näheren Zustände, dann bewege ich mich bei jedem einen Zustand positiv und negativ in jede Raumrichtung und habe damit alle 7×14 = 98 Zustände, die dem Originalvektor am nächsten sein könnten. Die 98 Zustände zu überprüfen und dann den treffendsten rauszusuchen wäre als erste Lösung möglich …

… die Vektorquantisierung sah mir auf den ersten Blick zu abstrakt und zu vielseitig aus, um sie auf dieses spezielle Problem anzuwenden, aber da könnte ich mich ja auch nochmal einarbeiten … hatte aber eigentlich vor, nicht zuviel Zeit zu investieren :D

[Jörg]

Ja, das mit dem Sektor war anders gemeint, aber es geht freilich einfacher: Eine sehr simple Lösung ist es, einfach den Strahl als Linie vom Nullpunkt aus abzutasten (in 3D), dabei erhaeltst du jeweils einen Punkt und die Nachbarn (pro Koordinaten auf und abrunden). Unter all diesen moeglichen Loesungen und kannst Dir dann die guenstigste raussuchen. Da das Linienzeichnen immer ein periodisches Muster aufweist, musst Du m.E. nichtmal bis zum Ende gehen.

[Krishty]

Ich glaube, wir meinen das gleiche -- nur, dass ich direkt kalkuliert habe, in welchen Schritten ich abtasten muss und vergessen habe, dass auf- und abrunden einfacher ist als die Komponenten hinterher erst zu korrigieren :)

[Krishty]

Leute, seht zu wie ihr eure Normalen quantisiert …

Alleine wenn ihr die Zahlen korrekt auf- und abrundet, statt (wie beim C-Cast) immer nur abzurunden, reduziert ihr die Fehlerrate auf 70%.
Mit meiner Optimierung kann diese Fehlerrate dann nochmal auf atemberaubende 16% (11,5% des C-Casts) reduziert werden … also die sechsfache Qualität bei gleichem Speicherverbrauch … die Normalen müssen dann beim Laden erneut normalisiert werden, aber das macht man ja meist sowieso.

… falls ihr genaue Zahlen und Code wollt, schreibt es hier.

[eXile]

Ich will eigentlich nur ein einfaches Vorher-/Nachher-Bild ;)

[Krishty]

:D Guter Punkt.

Wenn ich ein Modell ausreichend hoch tesseliere, könnte ich eine Object-Space-Normal-Map anfertigen, auf der man Banding erkennt … und wenn ich damit rendere, kann man die Rundungsfehler wahrscheinlich auch auf dem Modell wiederfinden …

Wenn ich den Algorithmus dann auf die GPU portiere, müsste ich eine schön vergrieselte Normal-Map zeigen können, und dass das Modell damit gerendert stufenfrei aussieht …

… mal sehen ob ich das hinbekomme, das dauert dann aber wahrscheinlich eine ganze Weile.

Edit: Bin jetzt bei genau 800%iger Qualitätsverbesserung bei 24-Bit-Normalen angekommen … wenn ich die Berechnung jetzt noch irgendwie effizient gestalten könnte und nicht nur durch Brute-Force, wäre das doch schon was.

[Krishty]

So, hier mal ein Beispiel.

Ich habe eine Situation konstruiert, die Normalmaps regelmäßig an die Grenze treibt – sehr, sehr sanfte Wölbungen, wie sie z.B. bei Autos vorkommen (ATI hatte mal eine D3D9-Demo für deren eigens entwickeltes Normal-Map-Format, wo die Kurven eines Sportwagens mit 24-Bit-Normalen katastrophal aussahen) oder bei Fensterscheiben.

Das gezeigte Mesh ist 10×10m groß und hat in der Mitte eine sanfte Wölbung von 10cm. Entschuldigt, dass die Perspektive nicht genau gleich ist – ich musste jedes Mal von Hand dahinnavigieren :/ Es sollte aber deutlich werden, was ich meine.

Hier die „gewöhnliche“ Normal-Map – einmal im Object-Space und einmal bei flacher Beleuchtung auf dem Modell:

Und hier meine optimierte Normal-Map:

Es sieht beide Male besch***en aus, aber so ist es bei konstruierten Tests ja immer ;) Wahrscheinlich vor allem, weil ich den Kontrast ultimativ aufdrehen musste, damit man überhaupt Schattierungen sieht … übrigens wurden beide Normal-Maps direkt aus Geometrie auf der GPU erzeugt.

Bei der Konvertierung zu 16-Bit-SNorms konnte ich übrigens den Tangent-Space meines Testmodells ohne Fehlerrate übernehmen – also den kompletten Tangentspace verlustfrei von 12 auf 6 Bytes pro Achse. Da dürfte die Hauptanwendungsmöglichkeit liegen.

[Jörg]

Wie filterst Du die Normalen?

[Krishty]

16× anisotrop, allerdings ohne Mip-Levels. Warum?

[Jörg]

Und danach normalisierst Du?

[Krishty]

Japp.

Ich verstehe langsam, worauf du hinaus willst – wenn mehrere Texel interpoliert werden und man das Ergebnis normalisiert, kann Müll rauskommen, oder?

[Jörg]

Wobei mehrere auch schon 2 bedeuten kann, wenn sie in extremeren Lagen im Grid liegen.

[Krishty]

Genau … wirklich interessanter Punkt und damit hast du auch vollkommen Recht … hier mal ein paar Nahaufnahmen:

Sobald Mip-Maps dazukommen wird das so richtig übel werden, dann liegen die Samples ja fast immer zwischen zwei Levels … damit dürfte sich das Thema für gefilterte Texturen erledigt haben.

[eXile]

Bezüglich des Algorithmus:
Wie schon in nem anderen Thread zu komischen Vektoren gesagt, handelt es sich dabei um ein Nearest-Neighbor-Problem, das mit geeigneten Algorithmen in O(log(n))-Zeit zu handeln ist.

http://en.wikipedia.org/wiki/Nearest_neighbor_search

Dabei ist S dann die Menge aller quantisierbaren Vektoren, d.h. (2^8)^3 viele Elemente sind in S. q ist der zu quantisierende Vektor, und die Metrik ist der ganz normale euklidische Abstand (man könnte auch die 1-Norm nehmen). Der Algorithmus müsste dann in ca. 8^3 Schritten fertig werden, d.h. nach 512 Schritten pro Vektor.

[Krishty]

Thx, dann habe ich ja jetzt was Greifbares zum Durcharbeiten … momentan bin ich bei ceil(sqrt(3)*8)*2 = 28 Samples, weil ich eh nur die direkt nächsten Punkte in Betracht ziehe … mal schauen, was ich noch rausholen kann. Am liebsten wäre mir ja was komplett Schritt- und schleifenloses, aber das Leben ist halt manchmal grausam :D

[eXile]

Mhh ich hab noch was nachgedacht.
1. Der NN-Algorithmus ist nur recht schlecht anwendbar, da um eine Metrik zu erhalten, man alle Punkte auf die Einheitskugel projezieren müsste, um dann zu dem zu quantisierenden Vektor den nächsten Punkt zu bestimmen. Das ist nicht sinnvoll.
2. Da die Punkte eigentlich alle regelmäßig verteilt sind, ist ein NN-Algorithmus Overkill. Grundidee für neuen Algorithmus: Man stellt sich die (2^8)^3 Punkte als aneinandergeklatschte Würfel vor (wie eine 3D-Textur). Man hat den Normalenvektor q gegeben, also eine Richtung. Nun muss man nur vom Nullpunkt aus in diese Richtung die Würfel durchgehen (muss noch mal nachdenken, wie viele äquidistante Samples ausreichend sind). Für einen Samplepunkt kann man direkt den betroffenen Würfel ermitteln, also auch direkt die Entfernung zum Würfelmittelpunkt. Bei dieser Schleife als das minimale Element merken, und das isser dann auch ;)

Edit: Wenn du dich jetzt fragst, "Warum Würfel?! Das müssen bei einen Abstand doch Kugeln sein!" - keine Panik. Aus der Mathematik weiß man: Alle p-Normen sind äquivalent, also macht es keinen Unterschied, ob man für eine Berechnung eines minimalen Abstandes Würfel oder Kugeln nimmt.

[Jörg]

Mhh ich hab noch was nachgedacht.
...
2. Da die Punkte eigentlich alle regelmäßig verteilt sind, ist ein NN-Algorithmus Overkill. Grundidee für neuen Algorithmus: Man stellt sich die (2^8)^3 Punkte als aneinandergeklatschte Würfel vor (wie eine 3D-Textur). Man hat den Normalenvektor q gegeben, also eine Richtung. Nun muss man nur vom Nullpunkt aus in diese Richtung die Würfel durchgehen (muss noch mal nachdenken, wie viele äquidistante Samples ausreichend sind).

Genau das wurde doch schon beschrieben, aber schad' ja nix, es nochmal zu wiederholen. ;)

[Krishty]

So, nicht dass ihr denkt, das Thema wäre inzwischen in den technischen Schwierigkeiten versickert:

Ich habe mir in den letzten Tagen mal ein paar weiterführende Gedanken über die Quantisierung gemacht und muss deshalb zu allererst meine vorherige Aussage mit den 32 Samples für einen dreidimensionalen 8-Bit Vektor revidieren. Ich brauche dafür momentan bedeutend mehr Samples, eher im Bereich von fünf- oder sechstausend … dann verdoppelt sich die Präzision auch nochmal. Hatte die Bits mit dem Wertebereich verwechselt -.-

Nun aber weiter zu meinen neuen Erkentnissen der letzten Tage. Mein neues Vorgehen beschreibe ich hier einfach mal anhand von ein paar Skizzen (zu Anschauungszwecken wieder durch einen zweidimensionalen positiven Vektor, den ich in 2×2 Bits quantisiere).

Wir beginnen mit dem normalisierten Vektor und bringen ihn auf eine „kubische” Länge, d.h. machen ihn so lang, dass er die Oberfläche eines Kubus (oder im 2D-Beispiel: eines Quadrats) berührt. Dazu wird die längste Komponente gewählt und auf Eins skaliert. Alle anderen Komponenten werden mit demselben Faktor skaliert.
Das hat mehrere Gründe: Zum einen kann eine optimale Quantisierung nicht nur durch einen kürzeren Vektor gegeben sein, sondern auch durch einen längeren (insbesondere bei Vektoren, die sich den Achsen annähern). Durch die kubische Normalisierung stellen wir sicher, dass auch der gesamte zur Verfügung stehende Zustandsraum genutzt werden kann.
Weiterhin erlaubt es uns, die Schrittweite, in der wir die Vektoren durchlaufen, konstant zu wählen. Sie (oder besser, ihr Nenner) ist dann nämlich genauso groß wie die Menge der möglichen Zustände pro Achse minus Eins (in der Skizze also ein Drittel).

Dann wird der Vektor in dieser Schrittlänge durchlaufen. Um möglichst viele Variationen zu erzwingen, verschieben wir den Vektor dabei um einen halben Schritt, so dass alle Samples genau zwischen den Quantisierungen liegen. An den Punkten A, B und C werden wir den Vektor testen.

Bei jedem Test werden die Koordinaten einzeln auf- oder abgerundet, danach wird der Fehler zum ursprünglichen Vektor getestet. In zwei Dimensionen ergeben sich pro Sample vier nächstmögliche Quantisierungen (s0, s1, s2, s3), in drei Dimensionen wären es acht.
Die Fehlermessung erfolgt bei mir momentan noch über den Winkel zwischen Quell- und quantisiertem Vektor, wahrscheinlich wäre die vorgeschlagene Messung des Abstandes zwischen Punkt und Linie schneller. Momentan ist das aber noch ein Detail, obwohl die das größte Optimierungspotenzial bietet.
Der Punkt mit der niedrigsten Abweichung (in diesem Beispiel s1) wird gespeichert und erst ersetzt, wenn ein Punkt mit besserer Quantisierung gefunden wird. Hier kann man eine ganze Menge rausholen, indem man abbricht, wenn man einen Punkt mit Nullabweichung gefunden hat.
So wird für alle Samples verfahren:

Letztendlich erweist sich s9 als optimales Sample.


Damit liegt die maximale Anzahl an Samples bei (Zustände pro Achse - 1) × 2^Dimension, für einen dreidimensionalen Vektor in acht Bits wären das also 2048 zu vergleichende Punkte. Wirklich gut ist das nicht.
Euch ist vielleicht schon aufgefallen, dass die Punkte der Samples sich überlagern (s1 und s7, s5 und s8, s6 und s11). Ich habe bemerkt, dass man mit nur der Hälfte der Samples auskommen kann. Wie man den Ausgangsvektor in diesem Fall unterteilen muss weiß ich noch nicht genau, aber die Anzahl der zu prüfenden Punkte würde sich halbieren (Nurnoch 1024 Samples für einen 3×8-Bit-Vektor, in meinen Augen eine recht verlockende Optimierung).

Eine andere Idee wäre, nicht immer auf- und abzurunden sondern einfach „echt“ zu runden. Dann wären es nur 256 Samples für einen 3×8-Bit-Vektor. Ich habe allerdings noch nicht genauer geprüft, ob damit auch wirklich alle guten Samples erfasst werden.

Die Implementierung beider Versionen wird sicher noch ein paar Tage dauern, aber ich wollte mich halt gerne nochmal zurückmelden.

[Lord Delvin]

(Das folgende ohne, dass ich den ganzen Thread gelesen hätte, weil ichs eigentlich für keine gute Idee halte:)

Kannst du nicht einfach deinen Vector auf einen Würfel hochskalieren(mit max, so wie schon von dir beschrieben). Dann merkst du dir in den ersten 2-3 bits, welche achse du dafür gewählt hast und verwendest den rest ganz normal für die beschreibung deines Vektors? Dann sparst du dir eine Komponente, den Zustandsraum kannst du (fast; es fehlt evnetuell bei der codierung ein halbes bit) ganz ausnutzen und das ganze ist in O(1) und wenigen instruktionen weil die rekonstruktion aus einem switch und ein paar bitschiftoperationen und einer normierung am ende besteht.
Wenn ich so drüber nachdenke könnnte sich das sogar wirklich lohnen, weil man sich die Bandbreite dadurch echt verkleinert. Ich würd aber kein short sondern gleich ein int nehmen, weil ich mal davon ausgehe, dass das auch bei gpus die gängige busbreite ist und der short dann genausoschnell sein müsste. Kann man aber bestimmt schnell ausprobieren.

Gruß
Lord D

[Krishty]

Könnte ich machen, nur wäre mir das Entpacken zu kompliziert. Die effektivste Methode wäre wahrscheinlich, den Vektor in Polarkoordinaten zu speichern (2 x 2 Bytes) ... aber ich bevorzuge den für den Shader bequemsten Weg, nämlich einfach drei Koordinaten entgegenzunehmen und erneut zu normalisieren, ohne komplizierte Dekompression.

Ich würd aber kein short sondern gleich ein int nehmen, weil ich mal davon ausgehe, dass das auch bei gpus die gängige busbreite ist und der short dann genausoschnell sein müsste.

Verstehe ich nicht :/

[Lord Delvin]

Ich würd aber kein short sondern gleich ein int nehmen, weil ich mal davon ausgehe, dass das auch bei gpus die gängige busbreite ist und der short dann genausoschnell sein müsste.

Verstehe ich nicht :/

Naja wenn du in der Zeit in der du das teil entpackst genau ein int bekommst, dann kannst du auch einen int entpacken, weil du die 2 shorts die du in der Zeit bekommen würdest, sowieso nicht schnell genug entpacken kannst.

Ich hab aber zugegebener Maßen nie nen Shader für DX/OGL geschrieben, deswegen hab ich mich auch so lange zurück gehalten, aber kann man nicht sowas machen wie:

Code: Alles auswählen

unpack(int n)
int x,y
switch(n>>30)
{
case 0:
  x = max,
  y = n&0xc000 0000;
  break;
case 1:
  y = max;
  x = n&0xc000 0000;

...
}
return normalize(x,y);

wobei man das noch optimieren kann, indem man das erste bit als vorzeichen von max nimmt. Das mit dem vorzeichen führt halt leider dazu, dass du im 3 dimensionalen 1 bit verlierst oder eine dimension bevorzugen musst und einen zustand in dem entscheidungsteil frei hast, weil 2^2 halt 4 ist und nicht 3.

Hielt das eigentlich für ne gute Kompressionsmethode, weil man eventuell ne chance hat so schnell zu sein, dass der bus nicht plötzlich z.T. ungenutzt ist. Aber vielleicht hab ich auch falsche vorstellungen von den Fähigkeiten der verwendeten Sprache bzw dem Verhältniss Rechenzeit/Übertragungsrate

Gruß
LordD

[Krishty]

Okay, jetzt verstehe ich, was du meinst :) Ohne Programmiererfahrung konntest du das nicht wissen: Es ist möglich, die Daten im Shader anders zu empfangen als sie im Vertex-Format deklariert sind.

Speziell bedeutet das, dass du in deinen Vertices z.B. ein 2-Byte-SNorm deklarierst (also ein signed int, das einen Bereich von -1 bis 1 darstellt). Der im Shader verwendete Datentyp ist davon entkoppelt, d.h., dass du die Komponente dort z.B. als float deklarieren kannst. Die Konvertierung wird dann von der Hardware durchgeführt (wie genau weiß ich nicht, aber da Vertex- und Texturformate ab D3D10 vereint sind kann ich mir vorstellen, dass dieselbe Logik verwendet wird wie beim Laden von Texturen - zumal die Vertex-Daten genau gleich ausgerichtet sein müssen. Die Hardware wird sie also schneller entpacken können, als ich das explizit per Shader-Code je könnte, aber wer es besser weiß, soll mich bitte aufklären).

Da liegt dann auch der Vorteil meiner Methode: Sie ist für den Shader transparent, er nimmt also keine chars, shorts oder ints entgegen und entpackt die dann, sondern immer nur einen Vektor von drei floats. Ob in meinem Vertex-Format chars, shorts, ints oder floats genutzt werden um die Daten zu speichern ist egal, sie kommen immer fertig konvertiert im Shader an, wo ich den Vektor dann nurnoch schnell normalisiere.


Noch ein Kommentar zur Methode allgemein: Sie ist natürlich nur anwendbar, wenn der Tangent-Space auch wirklich normalisiert ist, also keine Texturverzerrungen vorkommen. Das ist bei mir auch zum Glück der Fall.