¿Qué hace una buena tabla de permutación?

8

Estoy implementando un ruido Perlin mejorado . Su característica clave para la aleatorización es la tabla de permutación codificada, que proporciona gradientes esencialmente aleatorios pero reproducibles en las celdas de la cuadrícula. La tabla de permutación es solo una permutación de los enteros 0..255, y generalmente es la siguiente tabla (copiada directamente de la implementación original de Perlin):

{151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7,
225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247,
120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33,
88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134,
139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220,
105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80,
73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86,
164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38,
147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101,
155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232,
178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12,
191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181,
199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236,
205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180};

Como referencia, un pequeño parche extraído del ruido generado por esta tabla se ve así:

ingrese la descripción de la imagen aquí

Sin embargo, me gustaría que el código sea un poco más flexible y permita reorganizar esta tabla para poder crear un campo de ruido completamente nuevo (en lugar de simplemente muestrearlo en un desplazamiento diferente). Pero no todas las permutaciones se mezclan igualmente bien. En el improbable caso de que la permutación aleatoria sea solo la matriz ordenada de 0a 255, el ruido se vería así en su lugar:

ingrese la descripción de la imagen aquí

Eso es un poco malo. ¡Por supuesto, con una posibilidad de en, este no es un caso del que deba preocuparme. Pero seguramente, esta no es la única permutación que produce artefactos muy notables. Las permutaciones inversas y casi ordenadas probablemente tendrían los mismos problemas. Entonces, ¿cuántas otras permutaciones no son adecuadas? Digamos que el código se usaría en un juego popular para generar un mundo aleatorio por adelantado, aún sería molesto si cada mundo generado número 100,000 se viera remotamente regular.1256!

Entonces, la pregunta es, ¿qué es exactamente lo que hace que una tabla de permutación sea buena (o mala) y cómo evalúo la calidad de una tabla de permutación mediante programación, de modo que pueda reorganizar la tabla una vez más en el improbable caso de que saque una "mala" " ¿mesa?

Martin Ender
fuente
Las pruebas estadísticas para generadores de números aleatorios deberían ser útiles. Calcular el número esperado de pares en orden (orden inverso) podría ser un buen lugar para comenzar con una prueba. Este documento tiene muchas referencias: csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf .
Daniel M Gessel

Respuestas:

4

En primer lugar , un número no debe aparecer dos veces, eso está implícito ya que estamos hablando de permutaciones. Por lo tanto, llenar la tabla con una función aleatoria simple (255) no funcionará.

En segundo lugar , debe asegurarse de que no haya patrones de recurrencia prematuros:

Considere los valores 1,2,3,4: la tabla de permutación 4,3,2,1 no es muy buena debido a sus propiedades cíclicas cortas, es decir, 1 -> 4, 4 -> 1. Del mismo modo con 4,2 , 3,1 o ​​1,2,3,4. Las tablas óptimas lo llevan a través de todas las posiciones: 3,1,4,2 o 2,4,1,3.

Esta propiedad se vuelve cada vez más importante a medida que aumenta el número de dimensiones y realiza búsquedas recursivas.

Sin embargo, este enfoque solo puede crear grupos de valores demasiado similares, que pueden o no ser deseados, lo que me lleva al siguiente punto.

En tercer lugar , cuando genera una tabla con propiedades no cíclicas, debe recorrer los índices restantes sin asignar de manera aleatoria. Cuando sea posible, limite la distancia de paso aleatorio aquí a un cierto rango mínimo y máximo, por ejemplo, 5..120 para evitar grupos agrupados de valores similares. Vale la pena experimentar con estos números.

mhbuur
fuente
¡Bienvenido a Computer Graphics SE! Con respecto a su segundo punto, miré la descomposición cíclica de la tabla de permutación utilizada por Perlin. Consiste en múltiples ciclos de longitudes {4, 121, 89, 12, 4, 15, 4, 6}, ¿entonces aparentemente es lo suficientemente bueno? (¿O tal vez no lo es y una tabla de permutación diferente sería incluso "mejor"? Aunque no estoy seguro de que un humano pueda percibir la diferencia. ¿O es realmente mejor tener ciclos múltiples?) No estoy siguiendo tu tercer punto . ¿Una distribución aleatoria uniforme de qué? ¿Y a qué distancia de paso te refieres?
Martin Ender
¡Gracias! Sí, eso fue bastante críptico, supongo. Hace años experimenté con esto, así que no recuerdo la implementación exacta, pero cuando tienes la implementación para la generación de ruta óptima, debería ser evidente que eliges posiciones aleatorias de lo que queda de los índices no utilizados: es esa longitud de paso aleatoria a la que me refiero.
Actualicé
1

Una posibilidad podría ser tomar prestado de la comunidad criptográfica y, en particular, la sustitución de 8 bits a 8 bits utilizada en el cifrado AES / Rijndael. La tabla y el código para generarla se pueden encontrar en wikipedia.

Supongo que, para generar hasta 256 tablas adicionales, podría hacer algo como:

Func(U8 input, U8 TableNum) = SBox( (TableNum + Sbox(input)) Mod256 )

(ya que la función SBox es bastante no lineal)

Dicho esto, (y perdónenme si me equivoco con algunos de los detalles) en una vida pasada implementé el ruido Perlin usando una función RNG / Hash relativamente simple pero encontré la correlación en X / Y / Z debido a mi simple El mapeo de 2 o 3 dimensiones a un valor escalar fue problemático. Descubrí que una solución muy simple era usar un CRC, por ejemplo. algo como

InputToRNGHash = CRC(Z xor CRC( Y xor CRC(X))). 

Dado que los intrínsecos CRC pueden estar integrados en la CPU HW, este puede ser un enfoque rápido.

Simon F
fuente