[Mathe] Spirale auf der Einheitskugel

[CodingCat]

Weil sich das Rekonstruieren in meinem Fall am entscheidender Bottleneck herausgestellt hat, bin ich am Ende bei einer wesentlich simpleren Höhe-Winkel-Repräsentation gelandet. Die Hälfte der Bits für Höhe [-1, 1], die andere Hälfte für Winkel [0, 2pi], dann reichen ein sincos, eine Wurzel und ein paar Mads für die Rekonstruktion. Jetzt wo ich eXiles Link zu Octahedron-Normal Vectors sehe, wäre das vielleicht nochmal eine Ecke flotter.

Die Spirale habe ich deshalb leider nicht mehr weiterverfolgt. Da die Oberfläche einer gekappten Kugel der Höhe h \($2\pi \ \int_0^{\cos^{-1} (1 - h)}{sin \theta \ d\theta} = 2 \pi h$\), also linear in der Höhe ist, ist die äquidistante Verteilung von Punkten auf die Höhe wie in diesem Thread eingangs skizziert wohl prinzipiell nicht verkehrt. Auch der lineare Zusammenhang des Kreiswinkels mit dem Arcuscosinus der Höhe erscheint mir nicht ganz verkehrt. Auf die Frage, inwieweit die Punkteverteilung mit den angegebenen Vorfaktoren uniform ist, habe ich leider immer noch keine Antwort. Mit der Einfachheit und damit der Effizienz von Octahedron Normals wird eine spiralbasierte Lösung jedoch ohnehin nicht mithalten können.

[Chromanoid]

Wenn es sich um dreidimensionale Richtungen handelt, wären doch vielleicht auch Quaternionen interessant. Normalisierte Quaternionen bekommst Du recht gut in 32bit (siehe Zarb-Adami, M. (2002). Quaternion Compression. In Treglia, D., Herausgeber, Game Programming Gems 3. Charles River Media. ISBN 978-1584502333.). Aus dem Artikel die "Smallest Three Methode":
Man muss die größte Komponente weglassen.
Welche Komponente weggelassen wurde speichert man in den obersten 2 Bit, dann folgen die Komponenten.
Die kleineren Komponenten liegen bei normalisierten Quaternionen immer zwischen (+/-)1/sqrt(2). So kann man die Komponenten leicht je auf 10 Bit skalieren (also auf 0-1023).
In dem Artikel wird noch eine andere Methode zur Kompression erwähnt ("polar"), die ist etwas komplizierter, erfordert mehr Rechenzeit, ist aber genauer. Die Methode habe ich bisher nicht benutzt, kann also nur durch Nachlesen was dazu sagen...

Edit: Mmh habe gerade gemerkt, dass einen die Zusatzinfos von Quaternionen bei Richtungen ja eigentlich gar nicht interessieren, vergiss meinen Text also...

[eXile]

Was bei meinem letzten Post nicht wirklich herausgekommen ist: Die Sphere-Map Transform ist nicht nur einen Tick genauer in meinen Experimenten; sie ist auch noch um einiges schneller. Nur das interessiert jetzt eher weniger; du willst das ja übers Netzwerk übertragen und nicht im Pixelshader Millionenfach berechnen.

Falls es überhaupt notwendig ist, die Normalen zu enkodieren (ist das wirklich so viel übers Netzwerk?), würde ich einfach mal ONVs vorschlagen, und die als uint16_ts (also UNORM) ins Paket reinschreiben.

Da ich, wie gesagt, das getestet habe, aber hier nur eine Vorgängerversion aus einer Nicht-HLSL-Sprache finde, hier Pseudocode Code gefunden:

Code: Alles auswählen

// Implemented according to the paper: 
// On Floating-Point Normal Vectors
// Quirin Meyer, Jochen Süßmuth, Gerd Sußner, Marc Stamminger and Günther Greiner
// Eurographics Symposium on Rendering 2010

// Expects that the normal vector is approximately uniformly distributed over the sphere, otherwise use a sphere map transform!
// Don't use what you don't understand.
float2 EncodeNormalONV(float3 theNormal)
{
	float3 tmp1 = abs(theNormal);
	float3 tmp2 = theNormal / (tmp1.x + tmp1.y + tmp1.z);
	float2 tmp3 = float2(tmp2.x, tmp2.y);
	float2 tmp4 = tmp2.z < 0 ? tmp3 : sign(tmp3) - tmp3;

	return 0.5f * (tmp4 + float2(1.0f, 1.0f));
}

float3 DecodeNormalONV(float2 theEncodedNormal)
{
	float2 tmp1 = 2 * theEncodedNormal - float2(1.0f, 1.0f);
	float tmp2 = 1 - abs(tmp1.x) - abs(tmp1.y);
	float2 tmp3 = tmp2 > 0 ? tmp1 : sign(tmp1) - tmp1;

	return float3(tmp3.x, tmp3.y, -tmp2);
}

Nachtrag: Ein wenig Disclaimer zum Code geschrieben, weil ja ZFX einen wahnsinnigen Page Rank hat.
Nachtrag: Bitte obigen Code nicht mehr nutzen, sondern den aus dem supplemental Material von hier verwenden.

[CodingCat]

Danke, gleich mal eingebaut. Brachte leider "nur" 1-2 ms, im Moment hänge ich mehr bei den Atomics. Dennoch, wo wir schon bei Shader Code sind, gibt es noch einen intelligenteren (effizienteren) Weg als Multiplikation, Int-Casts und Bit-Shifts, um die Daten in uint-UAVs abzulegen?

[CodingCat]

Da ich, wie gesagt, das getestet habe, aber hier nur eine Vorgängerversion aus einer Nicht-HLSL-Sprache finde, hier Pseudocode Code gefunden: [...]

Kurze Ergänzung: Wenn man das von der Enkodierung berechnete 2-Tupel in einen 32-Bit-Integer presst (16 Bits pro Komponente), erleidet man mit der Fallunterscheidung nach tmp2 bei der Dekodierung leider desöfteren Schiffbruch, weil bisweilen Normalenprojektionen von außerhalb der Pyramidengrundfläche durch die Kompression die Seite wechseln. Getreu dem Motto "There can never be enough epsilons!" habe ich also faul ein Epsilon in eXiles Code geschmuggelt.

Encode:
float2 tmp3 = oneMinusUlgyZSignEps * float2(tmp2.x, tmp2.y);

Decode:
float2 tmp3 = tmp2 > 0.0f ? tmp1 : sign(tmp1) - tmp1;
tmp2 -= sign(tmp2) * ulgyZSignEps;

Besser wäre es wohl, die richtige Seite direkt auf Integer-Ebene zu enkodieren und zu dekodieren. Dies wird dem aufmerksamen Leser als Übung überlassen. ;)

[CodingCat]

Da ich, wie gesagt, das getestet habe, aber hier nur eine Vorgängerversion aus einer Nicht-HLSL-Sprache finde, hier Pseudocode Code gefunden: [...]

Kurze Ergänzung: Wenn man das von der Enkodierung berechnete 2-Tupel in einen 32-Bit-Integer presst (16 Bits pro Komponente), erleidet man mit der Fallunterscheidung nach tmp2 bei der Dekodierung leider desöfteren Schiffbruch, weil bisweilen Normalenprojektionen von außerhalb der Pyramidengrundfläche durch die Kompression die Seite wechseln.

Da Octahedron Normals gerade an mehreren Stellen "wiederentdeckt" werden (Wow, manchmal dauert es echt lange, bis sowas ankommt!), ein Nachtrag zum Nachtrag: Man braucht keine Epsilons, wenn man die Negierung mit einer Vertauschung der ersten beiden Komponenten UND DEREN VORZEICHEN kombiniert, weil dann auf beiden Seiten der inneren Raute / Pyramidengrundfläche benachbarte Richtungen nebeneinander landen. Damit ist der Ausgang der Fallunterscheidung bei der Dekodierung für die Richtungen auf der Unterscheidungsgrenze irrelevant: Sollte ein kodierter Vektor durch Präzisionsverlust die Seite wechseln, stellt er trotzdem noch eine im Rahmen der Diskretisierungsgenauigkeit korrekte Richtung da.

Encode:
float2 tmp4 = tmp2.z < 0 ? tmp3 : (1.0f - abs(tmp3.yx)) * signNotZero(tmp3.xy); // Beachte Vertauschung der Komponenten UND Vertauschung der Vorzeichen

Decode:
float2 tmp3 = tmp2 > 0 ? tmp1 : (1.0f - abs(tmp1.yx)) * signNotZero(tmp1.xy);

(Warum ist das so? Die Grenze liegt gerade bei z = 0, somit gilt dort |y| = 1 - |z| - |x| = 1 - |x|. Oberhalb der Grenze x' = x, unterhalb mit Vertauschung x' = s(x) * (1 - |y|) = s(x) * (1 - 1 + |x|) = s(x) * |x| = x.)

Ich möchte noch anmerken, dass im Netz noch mehr Implementierungen rumfliegen, die das Problem des hier eingangs geposteten Codes teilen. Insbesondere ist schon die Projektion im oben verlinkten Ursprungspaper problematisch - denn dort wird zwar die Komponentenvertauschung angegeben, nicht jedoch die anschließende Vertauschung der Vorzeichen, was wieder in 2 von 8 Fällen den falschen Quadrant wählt. Selbes gilt für die daraus abgeleitete Implementierung im gerade aufgetauchten Blog-Post hier. Es ist zu befürchten, dass uns derlei Implementierungen noch lange erhalten bleiben.

Das neue eingangs in diesem Post verlinkte JCGT-Paper macht es glücklicherweise richtig und kommt mit allerlei getestetem und optimiertem Shader-Code, also am besten darauf bauen.

[eXile]

Ja, das habe ich auch gesehen. Ich habe meinen obigen Post nun auch editiert.

Eigentlich hätte ich mir das schon damals denken können, aber ich hatte in meinem Mathematica-Skript einen Fehler drin, den ich gerade gefunden habe (ansonsten hätte ich diese Unstetigkeit wohl hoffentlich unter Umständen vielleicht entdeckt).

Im supplemental material vom JCGT-Paper fehlen leider die qualitativen Bildvergleiche, die im Paper (z.B. bei Figure 8) versprochen wurden. Das wäre eigentlich sehr wichtig zu sehen. Ich habe Morgan McGuire mal eine Twitter-Nachricht deswegen geschrieben; wenn das nach Ostern nichts wird, kommt noch eine Mail hinterher.