[Mathe] Spirale auf der Einheitskugel

[CodingCat]

Ich bin gerade auf der Suche nach einer einigermaßen gleichverteilten Diskretisierung der Oberfläche der Einheitskugel. Naheliegend ist der Weg über eine Spirale, wobei ich folgendes auftreiben konnte: Analytically exact spiral scheme for generating uniformly distributed points on the unit sphere. Ich verstehe nicht viel von dem, was dort gezeigt wird, aber das iterative Lösen nichtlinearer Gleichungen ist für die GPU wohl eher ungeeignet. Also habe ich mir einfach mal deren Anfangslösungen geschnappt, was zu folgender Spirale führt:

\($$\theta = \cos^{-1} (1 - 2t), \ t \in [0, 1] \\
\phi = \sqrt{\pi n} \theta, \ n = \text{Anzahl der Schritte} \\
p(x) = \begin{pmatrix} \sin \theta &\times& \cos \phi \\ \cos \theta & & \\ \sin \theta &\times& \sin \phi \end{pmatrix}$$\)

Von t zum Punkt kommt man somit mit 3 trigonometrischen Funktionen und einer Wurzel:

\($$\cos \theta = 1 - 2t \\
\sin \theta = \sqrt{1 - \cos^2 \theta} = \sqrt{1 - (1 - 2t)^2} \\
\theta = \cos^{-1} (1 - 2t) \\
\sin \phi = \sin (\sqrt{\pi n} \theta) \\
\cos \phi = \cos (\sqrt{\pi n} \theta)$$\)

In die andere Richtung sieht es ähnlich aus, drei trigonometrische Funktionen:

\($$\phi = \phi_r + 2\pi k, \ \phi_r = \text{Winkel im aktuellen "Ring"}, \ k \in \mathbb{N} \\
\phi_r = \operatorname{atan2}(p_z, p_x) \\
\theta = \frac{\phi}{\sqrt{\pi n}} = \frac{\phi_r + 2\pi k}{\sqrt{\pi n}} \\
k = \left\lfloor \frac{\sqrt{\pi n} \theta - \phi_r}{2 \pi} \right\rfloor = \left\lfloor \frac{\sqrt{\pi n}\ \cos^{-1} p_y - \phi_r}{2 \pi} \right\rfloor \\
t = \frac{1 - \cos \theta}{2} = \frac{1 - \cos \frac{\phi_r + 2\pi k}{\sqrt{\pi n}}}{2}$$\)

Ich sehe momentan keine Möglichkeit, das stark zu vereinfachen. Drei trigonometrische Funktionen sind nicht wirklich optimal, zur Verteilung kann ich auch noch nichts sagen. Alle Angaben ohne Gewähr, Fortsetzung folgt (hoffentlich).

[eXile]

Ich bin gerade auf der Suche nach einer einigermaßen gleichverteilten Diskretisierung der Oberfläche der Einheitskugel. Naheliegend ist der Weg über eine Spirale

Also eigentlich wäre mir eine Spirale als so ziemlich letztes eingefallen. Das Problem, eine Kugel möglichst „gleichmäßig“ (was auch immer das sein mag) zu approximieren, ist ja äquivalent dazu, möglichst „gleichmäßig“ (dito) \($n$\) Punkte auf der Kugeloberfläche zu verteilen, und dann eine konvexe Hülle zu bilden.

(Wie sich durch genaue algebraische Analyse herausstellt, kann man extrem harte Anforderungen an Gleichmäßigkeit nur bis 120 Punkte garantieren (siehe das grandiose Kugel-FAQ). Aber das ist in den meisten Fällen ja nicht der Fall.)

Daher von mir erstmal die Frage: Hast du dir schon einmal Halton- bzw. Hammersley-Sampling auf der Halbkugel angeschaut? Das sind low-discrepancy Folgen, die auch bei Quasi-Monte-Carlo-Methoden zum Einsatz kommen.

Durch Einsatz solcher Folgen kriegt man die Varianz von Monte-Carlo-Methoden (die ist \($O(\frac{1}{\sqrt{n}})$\), falls die Varianz überhaupt existiert) auf Quasi-Monte-Carlo-Niveau (das ist unter bestimmten Umständen nahe \($O(\frac{1}{n})$\)) gedrückt; kurz gesagt, du hast viel weniger Rauschen, und das ist in der Raytracing-Community auch wohlbekannt. Du kannst dir hier, via hier, mal eine lauffähige Demo reinziehen (drück mal die Ziffer 4 auf der Tastatur).

Oder vielleicht ist das auch alles Mist. :)

[CodingCat]

Hm, interessant. Die Kugel-FAQ muss ich auf alle Fälle mal lesen. Und nein, ich habe von Sampling bis jetzt praktisch keine Ahnung. Und sorry, ich hatte überhaupt nicht erwähnt, wie ich auf die Spirale komme. Ich suche nach einer 16-Bit-Repräsentation für Strahlrichtungen, d.h. eine möglichst gleichmäßige Punkteverteilung für \($n = 2^{16}$\) Punkte/Richtungen/Werte, mit effizienter Konvertierung in beide Richtungen.

[eXile]

Ich suche nach einer 16-Bit-Repräsentation für Strahlrichtungen, d.h. eine möglichst gleichmäßige Punkteverteilung für \($n = 2^{16}$\) Punkte/Richtungen/Werte, mit effizienter Konvertierung in beide Richtungen.

Aha, darin versteckt sich eine Bedingung, warum meine Vorschläge doch Mist waren: Mir sind bisher nur iterative Generatoren solcher Sequenzen untergekommen, und keine „random access“ Varianten. Damit sind die Sequenzen wohl für deine Konvertierungszwecke ungeeignet. Vor allen Dingen gibt es keine Zurückkonvertierung bei solchen Sequenzen. So langsam ergibt eine Spirale richtig SInn.

Und ja, irgendwo habe ich das mit den Normalen und der Spirale schon einmal gehört; das war doch mal in irgendeiner Präsentation, oder? Ich zumindest finde nichts mehr hier.

[CodingCat]

Und ja, irgendwo habe ich das mit den Normalen und der Spirale schon einmal gehört; das war doch mal in irgendeiner Präsentation, oder? Ich zumindest finde nichts mehr hier.

Ich habe es bis jetzt nur zufällig auf Twitter aufgeschnappt (siehe meine Favoriten dort). Ich habe denjenigen vorhin mal angeschrieben, eventuell hat er ja eine passende Spirale parat.

[MadMax]

Ich weiß, dass mein Prof. (Dachsbacher) in seiner ursprünglichen Arbeit über Antiradiance eine Spriale verwendet hat um eine Kugel/Halbkugel zu diskretisieren. Mal schauen ob ich den Code noch finde.

[[none]]

MINIMAL DISCRETE ENERGY ON THE SPHERE
E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou
Kapitel 5, allerdings nur in eine Richtung
http://www.intlpress.com/_newsite/site/ ... -A-003.pdf

[CodingCat]

MINIMAL DISCRETE ENERGY ON THE SPHERE
E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou
Kapitel 5, allerdings nur in eine Richtung
http://www.intlpress.com/_newsite/site/ ... -A-003.pdf

Danke, das kommt schonmal verblüffend gut hin. Dass die dort den Azimutalwinkel als rekursive Folge definieren, hilft zwar nicht wirklich, aber man kann von deren Folge tatsächlich auf die Formeln von oben kommen:
\($$\begin{align*}
\phi_k &= \phi_{k - 1} + \frac{C}{\sqrt{N}} \frac{1}{\sqrt{1 - h_k^2}} & \text{// rückwärts} \\
\phi_k &= \phi_{k - 1} - \frac{C}{\sqrt{N}} \frac{1}{\sqrt{1 - h_k^2}} \hat{=} - \frac{C}{\sqrt{N}} \sum_{j=1}^{k} {\frac{1}{\sqrt{1 - h_k^2}}} = \frac{C}{\sqrt{N}} \sum_{j=1}^{k} {\arccos' h_k} & \text{// in etwa Integral über die Ableitung von acos} \\
&\approx \frac{C}{\sqrt{N}} \frac{N}{2} \int_{-1}^{h_k} {\arccos' x dx}\ \hat{\approx}\ \sqrt{N \pi}\ \cos^{-1} h_k & \text{// mit deren } C \approx 3.6 = 2 \times 1.8 \approx 2 \sqrt{\pi}
\end{align*} $$\)
Das Konvertierungsproblem mit den drei trigonometrischen Funktionen bleibt allerdings bestehen.

Ich weiß, dass mein Prof. (Dachsbacher) in seiner ursprünglichen Arbeit über Antiradiance eine Spriale verwendet hat um eine Kugel/Halbkugel zu diskretisieren. Mal schauen ob ich den Code noch finde.

Das wäre auf jeden Fall interessant, insbesondere weil die Diskretisierung dort ja vermutlich auch in einem Echtzeitkontext stattfand. (Nebenbei: Du bist auch am KIT? Sind wir uns schonmal begegnet? ;))

[eXile]

Naja, wenn die Punkte halbwegs gleichverteilt sein sollen, kommst du wohl niemals ohne trigonometrischen Term aus (ein \($\sin(\vartheta)$\) taucht ja schon in der Funktionaldeterminante auf; ohne irgendeine Betrachtung dieser kriegt man keine gleichmäßige Verteilung hin). Außerdem habe ich noch eine Frage an deine Anforderungen: Ist es wichtig, dass konsekutive Werte nahe beisammen sind; oder ist die Reihenfolge komplett egal, und nur die Menge aller Punkte sollte gleichmäßig verteilt sein?

[CodingCat]

Ja, mir ist durchaus bewusst, dass ich nicht ohne Trigonometrie auskommen werde. Die Frage ist, geht es eventuell mit weniger? Die Reihenfolge ist egal, solange ich gut in beide Richtungen konvertieren kann.

[MadMax]

MINIMAL DISCRETE ENERGY ON THE SPHERE
E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou
Kapitel 5, allerdings nur in eine Richtung
http://www.intlpress.com/_newsite/site/ ... -A-003.pdf

Danke, das kommt schonmal verblüffend gut hin. Dass die dort den Azimutalwinkel als rekursive Folge definieren, hilft zwar nicht wirklich, aber man kann von deren Folge tatsächlich auf die Formeln von oben kommen:
\($$\begin{align*}
\phi_k &= \phi_{k - 1} + \frac{C}{\sqrt{N}} \frac{1}{\sqrt{1 - h_k^2}} & \text{// rückwärts} \\
\phi_k &= \phi_{k - 1} - \frac{C}{\sqrt{N}} \frac{1}{\sqrt{1 - h_k^2}} \hat{=} - \frac{C}{\sqrt{N}} \sum_{j=1}^{k} {\frac{1}{\sqrt{1 - h_k^2}}} = \frac{C}{\sqrt{N}} \sum_{j=1}^{k} {\arccos' h_k} & \text{// in etwa Integral über die Ableitung von acos} \\
&\approx \frac{C}{\sqrt{N}} \frac{N}{2} \int_{-1}^{h_k} {\arccos' x dx}\ \hat{\approx}\ \sqrt{N \pi}\ \cos^{-1} h_k & \text{// mit deren } C \approx 3.6 = 2 \times 1.8 \approx 2 \sqrt{\pi}
\end{align*} $$\)
Das Konvertierungsproblem mit den drei trigonometrischen Funktionen bleibt allerdings bestehen.

Ich weiß, dass mein Prof. (Dachsbacher) in seiner ursprünglichen Arbeit über Antiradiance eine Spriale verwendet hat um eine Kugel/Halbkugel zu diskretisieren. Mal schauen ob ich den Code noch finde.

Das wäre auf jeden Fall interessant, insbesondere weil die Diskretisierung dort ja vermutlich auch in einem Echtzeitkontext stattfand. (Nebenbei: Du bist auch am KIT? Sind wir uns schonmal begegnet? ;))

Nein ich habe bei ihm meine Diplomarbeit (über Antiradiance) geschrieben als er noch Prof. in Stuttgart war. Mit CG beschäftige ich mich nur noch privat :-(. Ich habe zwar den Code gefunden aber der ist leider nirgends veröffentlicht deswegen möchte ich ihn lieber nicht posten. Wenn du aber so oder so am KIT bist kannst ihn ja einfach mal fragen. Die Datei ist ein Header(NORMALCLUSTER.h) aus seiner Diplomarbeit von 2002 (Point Based Rendering).

[CodingCat]

OK, danke fürs Raussuchen!

[Schrompf]

Sorry für das Thread-Ausbuddeln, aber ich habe gerade das gleiche Problem. Ich will eine Blickrichtung - einen normierten Vektor - mit möglichst wenig Bits über das Netzwerk übertragen. Ich könnte auch einfach in zwei Winkel auflösen und mit ~24 Bits hinkommen, aber irgendwie wäre das Verschwendung für Richtungen nahe der Pole. Bei welcher Lösung bist Du am Ende gelandet?

[eXile]

Wie immer: Ich brauche mehr Details! ;)

1. Bedeutet Blickrichtung, dass der zu enkodierende Vektor auf der ganzen Kugeloberfläche gleichverteilt ist?
   (Wie es beispielsweise bei View-Vektoren im Welt-Raum der Fall ist.)
2. Oder ist es beispielsweise so, dass der zu enkodierende Vektor meist in entweder positive oder negative z-Hemisphäre zeigt?
   (Wie es beispielsweise bei View-Vektoren im Tangentenraum der Fall ist.)

Wenn ersteres der Fall ist, würde ich zu Octahedron-Normal Vectors greifen. Die vergeben 50 % fürs Bild der Abbildung auf Vektoren mit positiver z-Richtung und auch 50 % auf Vektoren mit negativer z-Richtung. Dabei haben beide Teilbilder identische Verteilungsfunktionen; es ist also für uniform verteilte Vektoren ganz gut geeignet. Eignet sich für Enkodierung auf DXGI_FORMAT_R16G16_UNORM; macht 32 Bits.

Wenn letzteres der Fall ist, gibt es zwei Möglichkeiten:

1. Du benutzt eine Sphere-Map Transform, um die Vektoren in zwei Dimensionen abzubilden. Zwar hast du auch hier 50 % des Bildes für Vektoren mit positiver z-Richtung und 50 % des Bildes für solche mit negativer z-Richtung; die jeweilige Verteilungsfunktion ist aber unterschiedlich. Eignet sich für Enkodierung auf DXGI_FORMAT_R16G16_UNORM; macht 32 Bits.
   Bei der Implementierung muss man beachten, die z-Richtung mit \($-1$\) vorzumultiplizieren, weil ansonsten die unvorteilhaftere Dichtefunktion für die häufiger auftretenden Vektoren genommen wird.
2. Du benutzt Best-Fit Normals; im Blogeintrag sind alle relevanten Artikel verlinkt. Braucht eine Lookup-Textur (in praktischen Fällen \($1024 \times 1024$\) groß); eignet sich für Enkodierung auf DXGI_FORMAT_R8G8B8A8_UNORM (wobei Alpha nicht benutzt wird); macht 24 Bits.
   
   (Für diese Auflistung habe ich bereits dies durchgearbeitet; dieser Post hat bereits alle dort enthaltenen Informationen verwurschtet und verarbeitet, nur damit das nicht gleich jemand hinterher postet. ;))

Wie man sieht, habe ich in der letzten Aufzählung (also für sich in einer Hemisphäre häufende Vektoren) die Octahedron-Normal Vectors nicht aufgenommen:

• Weil diese meiner Erfahrung nach nicht für solche Vektoren eignet.
• Die Sphere-Map Transform durch andere Dichtefunktionen einen Vorteil hat; erstaunlicherweise, da gilt:
  • Die Sphere-Map Transform deckt nur \($\frac{1}{\sqrt{2}}\approx 70.71\,\%$\) des Zielraumes mit ihrem Bild ab.
  • Die Octahedron-Normal Vectors deckt logischerweise 100 % des Zielsraums ab.

Dass es keine verzerrungsfreie Abbildung von der Kugel in die Ebene gibt (formal: keine isometrische Abbildung), und damit man bei jeder solchen Abbildung über ihre Dichteverteilung rumdiskutieren kann, habe ich glaube ich schon oft genug gesagt; eine perfekte Lösung gibt es also nicht.

[Schrompf]

Danke für den ganzen Lesestoff! Ich werde mal Deinen Links folgen und nachlesen. Zu dem "Mehr Details"-Wunsch: es geht hier nicht um 3D-Grafik, sondern um Spiellogik über's Netzwerk. Wenn ich die Blickrichtung des Spielers an den Server übertragen will, ist der zu übertragende Vektor meist nahe der Bodenebene. Dort sollte er allerdings auf vielleicht ein Hunderstel Grad genau sein - wenn ich mit der Sniper auf einen 500m entfernten Feind anlege, sind das immernoch ~9cm Schrittweite. Das ist der extremste Fall, der mir einfällt.

Wenn ich damit den Bewegungsvektor eines Objekts übertragen will, würde ich eine Richtung und ein Tempo kodieren. Die Richtung dürfte in dem Fall deutlich weniger präzise sein, und die Geschwindigkeit würde ich als schmalen handgebauten Float übertragen, also Mantisse und Exponent. Vorzeichen kann ich mir ja sparen. Und da die Position auch in regelmäßigen Abständen übertragen werden soll, dürfen sich auch gern durch die Kompressionsverluste kleine Fehler aufsummieren... die Position muss nur optisch grob für alle Spieler gleich aussehen.

Hm... während ich das so tippe, fällt mir auf, dass ich durch Ausgleich der Werteverteilung auf der Kugel ja bestenfalls ein Bit an Genauigkeit im Speckgürtel gewinne. Ich glaube, ich mache mir grad viel zu viele Gedanken.

[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.