Was ist der Ursprung dieses GLSL rand () Einzeilers?

92

Ich habe diesen Pseudozufallszahlengenerator zur Verwendung in Shadern gesehen, auf die hier und da im Internet Bezug genommen wird :

float rand(vec2 co){
  return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

Es wird verschiedentlich als "kanonisch" oder "ein Einzeiler, den ich irgendwo im Internet gefunden habe" bezeichnet.

Was ist der Ursprung dieser Funktion? Sind die konstanten Werte so willkürlich, wie sie scheinen, oder gibt es Kunst in ihrer Auswahl? Gibt es eine Diskussion über die Vorzüge dieser Funktion?

BEARBEITEN: Der älteste Verweis auf diese Funktion, auf den ich gestoßen bin, ist dieses Archiv vom Februar '08 , wobei die ursprüngliche Seite jetzt aus dem Web entfernt wurde. Aber es gibt dort nicht mehr Diskussionen darüber als anderswo.

Grumdrig
quelle
Es ist eine Geräuschfunktion, mit der prozedural erzeugtes Gelände erstellt wird. ähnlich wie so en.wikipedia.org/wiki/Perlin_noise
foreyez

Antworten:

42

Sehr interessante Frage!

Ich versuche dies herauszufinden, während ich die Antwort eingebe :) Zuerst eine einfache Möglichkeit, damit zu spielen: http://www.wolframalpha.com/input/?i=plot%28+mod%28+sin%28x*12.9898 +% 2B + y * 78,233% 29 + * + 43758,5453% 2C1% 29x% 3D0..2% 2C + y% 3D0..2% 29

Überlegen wir uns dann, was wir hier versuchen: Für zwei Eingabekoordinaten x, y geben wir eine "Zufallszahl" zurück. Dies ist jedoch keine Zufallszahl. Es ist jedes Mal dasselbe, wenn wir dasselbe x, y eingeben. Es ist eine Hash-Funktion!

Das erste, was die Funktion tut, ist, von 2d auf 1d zu gehen. Das ist an sich nicht interessant, aber die Zahlen werden so gewählt, dass sie sich normalerweise nicht wiederholen. Außerdem haben wir dort eine Gleitkommaaddition. Es wird noch ein paar Bits von y oder x geben, aber die Zahlen könnten einfach richtig gewählt werden, damit eine Mischung entsteht.

Dann probieren wir eine Black-Box-Funktion sin () aus. Dies hängt stark von der Implementierung ab!

Zuletzt wird der Fehler in der sin () - Implementierung durch Multiplizieren und Nehmen des Bruchs verstärkt.

Ich denke nicht, dass dies im allgemeinen Fall eine gute Hash-Funktion ist. Die sin () ist numerisch eine Black Box auf der GPU. Es sollte möglich sein, eine viel bessere zu konstruieren, indem fast jede Hash-Funktion übernommen und konvertiert wird. Der schwierige Teil besteht darin, die typische Ganzzahloperation, die beim CPU-Hashing verwendet wird, in Float- (Halb- oder 32-Bit-) oder Festkommaoperationen umzuwandeln, dies sollte jedoch möglich sein.

Das eigentliche Problem bei dieser Hash-Funktion ist wiederum, dass sin () eine Black Box ist.

Starmole
quelle
1
Dies beantwortet nicht die Frage nach dem Ursprung, aber ich denke nicht, dass es wirklich beantwortbar ist. Ich werde diese Antwort aufgrund der veranschaulichenden Grafik akzeptieren.
Grumdrig
19

Der Ursprung ist wahrscheinlich das Papier: "Über die Erzeugung von Zufallszahlen mit Hilfe von y = [(a + x) sin (bx)] mod 1", WJJ Rey, 22. Europäisches Statistiktreffen und 7. Vilnius-Konferenz über Wahrscheinlichkeitstheorie und Mathematische Statistik, August 1998

BEARBEITEN: Da ich keine Kopie dieses Dokuments finden kann und die Referenz "TestU01" möglicherweise nicht klar ist, ist hier das Schema wie in TestU01 in Pseudo-C beschrieben:

#define A1 ???
#define A2 ???
#define B1 pi*(sqrt(5.0)-1)/2
#define B2 ???

uint32_t n;   // position in the stream

double next() {
  double t = fract(A1     * sin(B1*n));
  double u = fract((A2+t) * sin(B2*t));
  n++;
  return u;
} 

wobei der einzige empfohlene konstante Wert der B1 ist.

Beachten Sie, dass dies für einen Stream ist. Die Konvertierung in einen 1D-Hash 'n' wird zum ganzzahligen Raster. Ich vermute also, dass jemand dies gesehen und 't' in eine einfache Funktion f (x, y) umgewandelt hat. Die Verwendung der obigen Originalkonstanten würde ergeben:

float hash(vec2 co){
  float t = 12.9898*co.x + 78.233*co.y; 
  return fract((A2+t) * sin(t));  // any B2 is folded into 't' computation
}
MB Reynolds
quelle
3
Sehr interessant! Ich habe in Google Books ein Papier gefunden, das darauf sowie auf das Journal selbst verweist, aber es scheint, dass der Vortrag oder das Papier selbst nicht im Journal enthalten war.
Grumdrig
1
Aus dem Titel geht auch hervor, dass die Funktion, nach der ich frage, zurückkehren sollte fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER)), um der Funktion zu entsprechen, um die es in dem Papier geht.
Grumdrig
Und noch etwas: Wenn dies tatsächlich der Ursprung der Verwendung der Funktion ist, bleibt die Frage nach dem Ursprung der immer wieder verwendeten magischen Zahlen (Auswahl von aund b) offen, wurde aber möglicherweise in dem von Ihnen zitierten Papier verwendet.
Grumdrig
Ich kann das Papier auch nicht mehr finden. (bearbeiten: gleiches Papier wie oben verlinkt)
MB Reynolds
Aktualisieren Sie die Antwort mit weiteren Informationen.
MB Reynolds
8

Die konstanten Werte sind willkürlich, insbesondere weil sie sehr groß sind und ein paar Dezimalstellen von den Primzahlen entfernt sind.

Ein Modul über 1 eines Sinus mit hoher Amplitude multipliziert mit 4000 ist eine periodische Funktion. Es ist wie eine Jalousie oder ein Wellblech, das sehr klein gemacht wird, weil es mit 4000 multipliziert und vom Punktprodukt in einem Winkel gedreht wird.

Da die Funktion 2-D ist, bewirkt das Punktprodukt, dass die periodische Funktion relativ zur X- und Y-Achse schräg gedreht wird. Im Verhältnis 13/79 ungefähr. Es ist ineffizient, Sie können das gleiche erreichen, indem Sie Sinus von (13x + 79y) machen. Dies wird auch das gleiche erreichen, was ich denke, mit weniger Mathematik.

Wenn Sie die Periode der Funktion sowohl in X als auch in Y finden, können Sie sie abtasten, sodass sie wieder wie eine einfache Sinuswelle aussieht.

Hier ist ein Bild davon in der Grafik gezoomt

Ich kenne den Ursprung nicht, aber er ähnelt vielen anderen. Wenn Sie ihn in regelmäßigen Abständen in Grafiken verwenden, erzeugt er tendenziell Moiré-Muster und Sie können sehen, dass er irgendwann wieder auftritt.

aliential
quelle
Aber auf GPUs reichen X und Y von 0..1 und das sieht viel zufälliger aus, wenn Sie Ihr Diagramm ändern. Ich weiß, das klingt nach einer Aussage, aber es ist eigentlich eine Frage, weil meine Mathematikausbildung mit 18 Jahren endete.
Strings
Ich weiß, ich habe nur hineingezoomt, damit Sie sehen können, dass die Zufallsfunktion diese Form hat, außer dass sich die Grate sehr schnell ändern, außer dass Sie klein zoomen müssen, um die Änderungen überhaupt zu sehen ... Sie können sich vorstellen, dass Sie Punkte nehmen Auf den Graten ergeben sich ziemlich zufällige Zahlen von 0 bis 1 Höhe für 1 bis 1 x- und y-Werte.
Aliential
Oh, ich verstehe, und das scheint sehr logisch für jede Zufallszahlengenerierung, die im Kern eine Sündenfunktion verwendet
Strings
2
Es ist im Wesentlichen ein linearer Zickzack, und die Sünde soll ein kleines bisschen Abwechslung hinzufügen. Es ist das gleiche, als würde jemand ein Kartenspiel von eins bis zehn sehr schnell vor Ihnen drehen und Sie sollten es versuchen Nehmen Sie am Ende ein Muster von Zahlen von den Karten auf, es wären Zufallszahlen, da es sehr schnell gehen würde, dass er nur dann ein Muster erhalten könnte, wenn er Karten in einer exakten Synchronisation relativ zu der Geschwindigkeit, mit der sich die Karten drehten, auswählte.
Aliential
Nur eine Anmerkung, es wäre nicht schneller zu tun, (13x + 79y)da dot(XY, AB)genau das tun wird, was Sie beschreiben, da es das Punktprodukt ist, dasx,y dot 13, 79 = (13x + 79y)
Uhr
1

Vielleicht ist es eine nicht wiederkehrende chaotische Abbildung, dann könnte sie viele Dinge erklären, kann aber auch nur eine willkürliche Manipulation mit großen Zahlen sein.

BEARBEITEN: Grundsätzlich ist die Funktion Bruch (sin (x) * 43758.5453) eine einfache Hash-ähnliche Funktion, die sin (x) liefert eine glatte Sin-Interpolation zwischen -1 bis 1, also ist sin (x) * 43758.5453 eine Interpolation von - 43758.5453 bis 43758.5453. Dies ist ein ziemlich großer Bereich, so dass selbst kleine Schritte in x einen großen Ergebnisschritt und eine wirklich große Variation des Bruchteils liefern. Der "Bruch" wird benötigt, um Werte im Bereich von -0,99 ... bis 0,999 ... zu erhalten. Wenn wir nun so etwas wie eine Hash-Funktion haben, sollten wir aus dem Vektor eine Funktion für den Produktions-Hash erstellen. Der einfachste Weg ist, "Hash" separat für x jede y-Komponente des Eingabevektors aufzurufen. Aber dann werden wir einige symmetrische Werte haben. Wir sollten also einen Wert aus dem Vektor erhalten. Der Ansatz besteht darin, einen zufälligen Vektor zu finden und ein "Punkt" -Produkt für diesen Vektor zu finden. Los geht's: Bruch (sin (Punkt (co.xy, vec2 (12,9898,78,233)) * 43758,5453); Entsprechend dem ausgewählten Vektor sollte seine Länge lang genug sein, um mehrere Peroide der "sin" -Funktion zu haben, nachdem das "dot" -Produkt berechnet wurde.

römisch
quelle
aber dann sollte 4e5 auch funktionieren, ich verstehe nicht warum die magische nummer 43758.5453. (Außerdem würde ich x um eine Bruchzahl versetzen, um Rand (0) = 0 zu vermeiden.
Fabrice NEYRET
1
Ich denke, mit 4e5 werden Sie nicht so viele Variationen der Bruchbits erhalten, es wird Ihnen immer den gleichen Wert geben. Es müssen also zwei Bedingungen erfüllt sein, die groß genug sind und eine gute Variation der Bruchteile aufweisen.
Roman
Was meinst du mit "wird dir immer den gleichen Wert geben"? (Wenn Sie meinen, es werden immer die gleichen Ziffern benötigt, erstens sind sie immer noch chaotisch, zweitens werden Float als m * 2 ^ p und nicht als 10 ^ p gespeichert, also verschlüsselt * 4e5 immer noch Bits).
Fabrice NEYRET
Ich dachte, Sie haben eine exponentielle Darstellung der Zahl 4 * 10 ^ 5 geschrieben, also gibt Ihnen sin (x) * 4e5 keine so chaotische Zahl. Ich bin damit einverstanden, dass gebrochene Bits aus der Sinuswelle Ihnen auch eine gute Chatoik geben.
Roman
Aber dann kommt es auf den Bereich von x an, ich meine, ob die Funktion für kleine (-0,001, 0,001) und große Werte (-1, 1) robust sein sollte. Sie können versuchen, einen Unterschied mit Bruch zu erkennen (sin (x / 1000.0) * 43758.5453); und Bruch (sin (x / 1000,0) * 4e5); wobei x im Bereich [-1., 1.] liegt. In der zweiten Variante wird das Bild monotoner sein (zumindest sehe ich den Unterschied im Shader). Im Allgemeinen stimme ich jedoch zu, dass Sie 4e5 weiterhin verwenden können und ein ausreichend gutes Ergebnis erzielen.
Roman