Quelle est l'origine de ce monocouche GLSL rand ()?

92

J'ai vu ce générateur de nombres pseudo-aléatoires à utiliser dans les shaders mentionnés ici et là sur le Web :

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

Il est appelé diversement "canonique", ou "une seule ligne que j'ai trouvée sur le Web quelque part".

Quelle est l'origine de cette fonction? Les valeurs constantes sont-elles aussi arbitraires qu'elles le paraissent ou y a-t-il de l'art dans leur sélection? Y a-t-il une discussion sur les mérites de cette fonction?

EDIT: La référence la plus ancienne à cette fonction que j'ai rencontrée est cette archive de février 08 , la page d'origine étant maintenant partie du Web. Mais il n'y a pas plus de discussion là-dessus qu'ailleurs.

Grumdrig
la source
C'est une fonction de bruit, utilisée pour créer un terrain généré de manière procédurale. similaire à quelque chose comme ceci en.wikipedia.org/wiki/Perlin_noise
foreyez

Réponses:

42

Question très intéressante!

J'essaie de comprendre cela en tapant la réponse :) Tout d'abord, un moyen facile de jouer avec: 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

Pensons ensuite à ce que nous essayons de faire ici: Pour deux coordonnées d'entrée x, y nous retournons un "nombre aléatoire". Maintenant, ce n'est pas un nombre aléatoire. C'est la même chose chaque fois que nous saisissons le même x, y. C'est une fonction de hachage!

La première chose que fait la fonction est de passer de 2d à 1d. Ce n'est pas intéressant en soi, mais les nombres sont choisis pour ne pas se répéter typiquement. Nous avons également une addition en virgule flottante. Il y aura encore quelques bits de y ou de x, mais les nombres peuvent être choisis correctement pour faire un mélange.

Ensuite, nous échantillonnons une fonction de boîte noire sin (). Cela dépendra beaucoup de la mise en œuvre!

Enfin, il amplifie l'erreur dans l'implémentation de sin () en multipliant et en prenant la fraction.

Je ne pense pas que ce soit une bonne fonction de hachage dans le cas général. Le sin () est une boîte noire, sur le GPU, numériquement. Il devrait être possible d'en construire une bien meilleure en prenant presque toutes les fonctions de hachage et en les convertissant. Le plus dur est de transformer l'opération d'entier typique utilisée dans le hachage du processeur en opérations flottantes (demi ou 32 bits) ou en virgule fixe, mais cela devrait être possible.

Encore une fois, le vrai problème avec cela en tant que fonction de hachage est que sin () est une boîte noire.

starmole
la source
1
Cela ne répond pas à la question sur l'origine, mais je ne pense pas que ce soit vraiment une réponse. J'accepterai cette réponse à cause du graphique illustratif.
Grumdrig
19

L'origine est probablement le papier: "Sur la génération de nombres aléatoires, avec l'aide de y = [(a + x) sin (bx)] mod 1", WJJ Rey, 22e réunion européenne des statisticiens et 7e Conférence de Vilnius sur la théorie des probabilités et Statistiques mathématiques, août 1998

EDIT: Puisque je ne trouve pas de copie de cet article et que la référence "TestU01" peut ne pas être claire, voici le schéma décrit dans TestU01 en pseudo-C:

#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;
} 

où la seule valeur constante recommandée est le B1.

Notez que c'est pour un flux. La conversion en un hachage 1D «n» devient la grille entière. Donc, je suppose que quelqu'un a vu cela et a converti 't' en une simple fonction f (x, y). En utilisant les constantes originales ci-dessus, cela donnerait:

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
la source
3
Très intéressant en effet! J'ai trouvé un article qui y fait référence ainsi que le journal lui-même sur Google Livres, mais il semble que le discours ou l'article lui-même ne soit pas inclus dans le journal.
Grumdrig
1
En outre, il semblerait d'après le titre que la fonction dont je parle devrait revenir fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))pour se conformer à la fonction sur laquelle porte l'article.
Grumdrig
Et encore une chose, si c'est bien l'origine de l'utilisation de la fonction, la question de l'origine des nombres magiques (choix de aet b) utilisés à maintes reprises demeure, mais peut avoir été utilisée dans l'article que vous citez.
Grumdrig
Je ne trouve plus le papier non plus. (modifier: même article que le lien ci-dessus)
MB Reynolds
Mettez à jour la réponse avec plus d'informations.
MB Reynolds
8

les valeurs constantes sont arbitraires, surtout qu'elles sont très grandes et à quelques décimales des nombres premiers.

un module sur 1 d'un sinus de haute amplitude multiplié par 4000 est une fonction périodique. c'est comme un store de fenêtre ou un métal ondulé fait très petit parce qu'il est multiplié par 4000 et tourné à un angle par le produit scalaire.

comme la fonction est 2D, le produit scalaire a pour effet de faire tourner la fonction périodique en oblique par rapport aux axes X et Y. Par rapport 13/79 environ. C'est inefficace, vous pouvez en fait réaliser la même chose en faisant sinus de (13x + 79y) cela permettra également d'obtenir la même chose je pense avec moins de maths ..

Si vous trouvez la période de la fonction à la fois en X et en Y, vous pouvez l'échantillonner pour qu'elle ressemble à nouveau à une simple onde sinusoïdale.

Voici une image agrandie du graphique

Je ne connais pas l'origine mais c'est similaire à beaucoup d'autres, si vous l'utilisiez dans des graphiques à intervalles réguliers, cela aurait tendance à produire des motifs de moiré et vous pourriez voir qu'il finit par recommencer.

alientiel
la source
Mais sur les GPU, X et Y vont de 0..1 et cela semble beaucoup plus aléatoire si vous changez votre graphique. Je sais que cela ressemble à une affirmation, mais c'est en fait une question, car mes études de mathématiques ont pris fin à 18 ans.
Strings
je sais, je viens de zoomer pour que vous puissiez voir que la fonction aléatoire est de cette forme sauf que les crêtes changent très rapidement, sauf que vous devez zoomer petit pour voir les changements du tout ... vous pouvez imaginer que prendre des points sur les crêtes donnera des nombres assez aléatoires de 0 à 1 hauteur pour 1 à 1 valeurs x et y.
aliential le
Oh, je comprends, et cela semble très logique pour toute génération de nombres aléatoires qui à la base utilise une fonction sin
Strings
2
c'est essentiellement un zigzag linéaire, et le péché est censé ajouter un tout petit peu de variation, c'est la même chose que si quelqu'un faisait défiler un paquet de cartes de une à 10 très rapidement en rond et en rond devant vous et vous êtes censé essayer finissez par prendre un modèle de nombres sur les cartes, ce seraient des nombres aléatoires car il serait très rapide qu'il ne puisse obtenir un modèle qu'en choisissant les cartes dans une synchronisation exacte par rapport à la vitesse à laquelle les cartes tournaient.
aliential
Juste une note, ce ne serait pas plus rapide à faire (13x + 79y)car dot(XY, AB)fera exactement ce que vous décrivez, comme c'est le produit scalaire, quix,y dot 13, 79 = (13x + 79y)
quand le
1

C'est peut-être une cartographie chaotique non récurrente, alors cela pourrait expliquer beaucoup de choses, mais cela peut aussi être juste une manipulation arbitraire avec de grands nombres.

EDIT: Fondamentalement, la fonction fract (sin (x) * 43758.5453) est une simple fonction de hachage, le sin (x) fournit une interpolation lisse du sin entre -1 à 1, donc sin (x) * 43758.5453 sera une interpolation de - 43758.5453 à 43758.5453. C'est une plage assez énorme, donc même un petit pas dans x fournira un grand pas dans le résultat et une très grande variation dans la partie fractionnaire. Le "fract" est nécessaire pour obtenir des valeurs comprises entre -0,99 ... et 0,999 .... Maintenant, lorsque nous avons quelque chose comme une fonction de hachage, nous devons créer une fonction de hachage de production à partir du vecteur. Le moyen le plus simple est d'appeler "hash" séparément pour x n'importe quelle composante y du vecteur d'entrée. Mais alors, nous aurons des valeurs symétriques. Donc, nous devrions obtenir une valeur du vecteur, l'approche est de trouver un vecteur aléatoire et de trouver le produit "point" de ce vecteur, nous y voilà: fract (sin (dot (co.xy, vec2 (12,9898,78,233))) * 43758,5453); De plus, selon le vecteur sélectionné, sa longueur doit être suffisamment longue pour avoir plusieurs péroïdes de la fonction "sin" après que le produit "point" soit calculé.

romain
la source
mais alors 4e5 devrait fonctionner aussi, je ne comprends pas pourquoi le nombre magique 43758.5453. (aussi, je compenserais x par un nombre fractionnaire pour éviter rand (0) = 0.
Fabrice NEYRET
1
Je pense qu'avec 4e5, vous n'obtiendrez pas autant de variation des bits fractionnaires, cela vous donnera toujours la même valeur. Donc, deux conditions doivent être remplies, suffisamment grandes et avoir une assez bonne variation des parties fractionnaires.
Roman
que voulez-vous dire, "vous donnera toujours la même valeur"? (si vous voulez dire qu'il prendra toujours les mêmes chiffres, premièrement, ils sont toujours chaotiques, deuxièmement, les flottants sont stockés sous la forme m * 2 ^ p, pas 10 ^ p, donc * 4e5 brouille toujours les bits).
Fabrice NEYRET
Je pensais que vous aviez écrit une représentation exponentielle du nombre, 4 * 10 ^ 5, donc sin (x) * 4e5 vous donnera un nombre pas si chaotique. Je suis d'accord que les bits fractionnaires de sin wave vous donneront également un bon chatoïque.
Roman
Mais cela dépend de la plage de x, je veux dire si la fonction doit être robuste pour les petites (-0,001, 0,001) et les grandes valeurs (-1, 1). Vous pouvez essayer de voir la différence avec fract (sin (x /1000.0) * 43758.5453); et fract (sin (x /1000.0) * 4e5) ;, où x dans l'intervalle [-1., 1.]. Dans la deuxième variante, l'image sera plus monotone (au moins je vois la différence dans le shader). Mais, en général, je suis d'accord que vous pouvez toujours utiliser 4e5 et avoir un résultat assez bon.
Roman