¿Cuál es el origen de este GLSL rand () de una sola línea?

92

He visto este generador de números pseudoaleatorios para usar en sombreadores a los que se hace referencia aquí y allá en la web :

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

Se le llama "canónico" o "una frase que encontré en la web en alguna parte".

¿Cuál es el origen de esta función? ¿Son los valores constantes tan arbitrarios como parecen o hay algo de arte en su selección? ¿Existe alguna discusión sobre los méritos de esta función?

EDITAR: La referencia más antigua a esta función con la que me he encontrado es este archivo de febrero de 2008 , la página original ya no está en la web. Pero allí no se habla más de eso que en cualquier otro lugar.

Grumdrig
fuente
Es una función de ruido, que se utiliza para crear un terreno generado por procedimientos. similar a algo como esto en.wikipedia.org/wiki/Perlin_noise
foreyez

Respuestas:

42

¡Pregunta muy interesante!

Estoy tratando de resolver esto mientras escribo la respuesta :) Primero, una forma fácil de jugar: 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

Entonces pensemos en lo que estamos tratando de hacer aquí: Para dos coordenadas de entrada x, y devolvemos un "número aleatorio". Ahora bien, este no es un número aleatorio. Es lo mismo cada vez que ingresamos la misma x, y. ¡Es una función hash!

Lo primero que hace la función es pasar de 2d a 1d. Eso no es interesante en sí mismo, pero los números se eligen para que no se repitan normalmente. También tenemos una adición de punto flotante allí. Habrá algunos bits más de yox, pero es posible que los números se elijan correctamente para que se mezclen.

Luego, probamos una función sin () de caja negra. ¡Esto dependerá mucho de la implementación!

Por último, amplifica el error en la implementación sin () multiplicando y tomando la fracción.

No creo que esta sea una buena función hash en el caso general. El sin () es una caja negra, en la GPU, numéricamente. Debería ser posible construir uno mucho mejor tomando casi cualquier función hash y convirtiéndola. La parte difícil es convertir la operación de entero típica utilizada en el hash de la CPU en operaciones flotantes (de medio o 32 bits) o de punto fijo, pero debería ser posible.

Nuevamente, el verdadero problema con esto como función hash es que sin () es una caja negra.

starmole
fuente
1
Esto no responde a la pregunta sobre el origen, pero no creo que sea realmente responsable. Aceptaré esta respuesta por el gráfico ilustrativo.
Grumdrig
19

El origen es probablemente el artículo: "Sobre la generación de números aleatorios, con ayuda de y = [(a + x) sin (bx)] mod 1", WJJ Rey, 22ª Reunión Europea de Estadísticos y 7ª Conferencia de Vilnius sobre Teoría de Probabilidad y Estadística matemática, agosto de 1998

EDITAR: Como no puedo encontrar una copia de este documento y la referencia "TestU01" puede no ser clara, aquí está el esquema como se describe en 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;
} 

donde el único valor constante recomendado es el B1.

Tenga en cuenta que esto es para una secuencia. La conversión a un hash 'n' 1D se convierte en la cuadrícula de enteros. Entonces, supongo que alguien vio esto y convirtió 't' en una función simple f (x, y). Usando las constantes originales anteriores que produciría:

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
fuente
3
¡Muy interesante en verdad! Encontré un artículo que hace referencia a él , así como a la propia revista en Google Books, pero parece que la charla o el artículo en sí no se incluyeron en la revista.
Grumdrig
1
Además, del título parecería que la función por la que estoy preguntando debería volver fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))a ajustarse a la función de la que trata el artículo.
Grumdrig
Y una cosa más, si este es realmente el origen del uso de la función, la cuestión del origen de los números mágicos (elección de ay b) usados ​​una y otra vez permanece, pero puede haber sido usado en el artículo que cita.
Grumdrig
Tampoco puedo encontrar el papel. (editar: mismo documento que el enlace anterior)
MB Reynolds
Actualiza la respuesta con más información.
MB Reynolds
8

los valores constantes son arbitrarios, especialmente porque son muy grandes y están a un par de decimales de los números primos.

un módulo sobre 1 de un seno de amplitud alta multiplicado por 4000 es una función periódica. es como una persiana de ventana o un metal corrugado hecho muy pequeño porque se multiplica por 4000 y gira en ángulo por el producto escalar.

como la función es 2-D, el producto escalar tiene el efecto de convertir la función periódica en un oblicuo con respecto a los ejes X e Y. Por una proporción de 13/79 aproximadamente. Es ineficiente, en realidad puede lograr lo mismo haciendo un seno de (13x + 79y), esto también logrará lo mismo, creo que con menos matemáticas.

Si encuentra el período de la función tanto en X como en Y, puede muestrearlo para que se vea como una onda sinusoidal simple nuevamente.

Aquí hay una imagen ampliada en el gráfico.

No sé el origen, pero es similar a muchos otros, si lo usa en gráficos a intervalos regulares, tenderá a producir patrones de muaré y podría ver que eventualmente vuelve a funcionar.

aliential
fuente
Pero en las GPU, X e Y van de 0 ... 1 y eso parece mucho más aleatorio si cambia su gráfico. Sé que esto suena como una afirmación, pero en realidad es una pregunta, porque mi educación matemática terminó a los 18 años.
Cuerdas
Lo sé, acabo de acercarme para que puedas ver que la función aleatoria es de esa forma, excepto que las crestas cambian muy rápido, excepto que tienes que hacer zoom pequeño para ver los cambios ... puedes imaginar que tomando puntos en las crestas dará números bastante aleatorios de 0 a 1 altura para valores de 1 a 1 xey.
aliential
Oh, lo entiendo, y eso parece muy lógico para cualquier generación de números aleatorios que en su núcleo use una función sin
Strings
2
Es un zigzag lineal esencialmente, y se supone que el pecado agrega un poco de variación, es lo mismo que si alguien estuviera moviendo un mazo de cartas de una a diez vueltas y vueltas muy rápidas frente a ti y se supone que debes intentar Si acaso recogiera un patrón de números de las tarjetas, serían números aleatorios porque se movería muy rápido y solo podría obtener un patrón eligiendo tarjetas en una sincronización exacta en relación con la rapidez con que giraban las tarjetas.
aliential
Solo una nota, no sería más rápido de hacer, (13x + 79y)ya dot(XY, AB)que hará exactamente lo que usted describe, ya que es el producto x,y dot 13, 79 = (13x + 79y)
escalar
1

Tal vez sea un mapeo caótico no recurrente, entonces podría explicar muchas cosas, pero también puede ser solo una manipulación arbitraria con grandes números.

EDITAR: Básicamente, la función fract (sin (x) * 43758.5453) es una función simple tipo hash, sin (x) proporciona una interpolación sin problemas entre -1 a 1, por lo que sin (x) * 43758.5453 será una interpolación de - 43758.5453 a 43758.5453. Este es un rango bastante amplio, por lo que incluso un pequeño paso en x proporcionará un gran paso en el resultado y una gran variación en la parte fraccionaria. El "fract" es necesario para obtener valores en el rango de -0,99 ... a 0,999 .... Ahora, cuando tenemos algo como la función hash, deberíamos crear una función para el hash de producción a partir del vector. La forma más sencilla es llamar "hash" por separado para x cualquier componente y del vector de entrada. Pero luego, tendremos algunos valores simétricos. Entonces, deberíamos obtener algún valor del vector, el enfoque es encontrar un vector aleatorio y encontrar el producto "punto" para ese vector, aquí vamos: fract (sin (dot (co.xy, vec2 (12.9898,78.233))) * 43758.5453); Además, según el vector seleccionado, su longitud debe ser lo suficientemente larga para tener varios peroides de la función "sin" después de que se calcule el producto "punto".

romano
fuente
pero luego 4e5 debería funcionar también, no entiendo por qué el número mágico 43758.5453. (también, compensaría x por algún número fraccionario para evitar rand (0) = 0.
Fabrice NEYRET
1
Creo que con 4e5 no obtendrás tanta variación de los bits fraccionarios, siempre te dará el mismo valor. Por lo tanto, se deben cumplir dos condiciones, lo suficientemente grandes y tener una variación suficientemente buena de las partes fraccionarias.
Roman
¿Qué quieres decir con "siempre te dará el mismo valor"? (si quiere decir que siempre tomará los mismos dígitos, primero, todavía son caóticos, segundo, los flotantes se almacenan como m * 2 ^ p, no como 10 ^ p, por lo que * 4e5 aún codifica bits).
Fabrice NEYRET
Pensé que escribiste una representación exponencial del número, 4 * 10 ^ 5, por lo que sin (x) * 4e5 te dará un número no tan caótico. Estoy de acuerdo en que los bits fraccionarios de la onda sinusoidal también te darán un buen chatoico.
Roman
Pero, entonces depende del rango de x, quiero decir si la función debe ser robusta para valores pequeños (-0.001, 0.001) y grandes (-1, 1). Puede intentar ver la diferencia con fract (sin (x /1000.0) * 43758.5453); y fract (sin (x /1000.0) * 4e5);, donde x en el rango [-1., 1.]. En la segunda variante la imagen será más monótona (al menos veo la diferencia en el sombreador). Pero, en general, estoy de acuerdo en que aún puede usar 4e5 y obtener un resultado suficientemente bueno.
Roman