Qu'est-ce qui fait une bonne table de permutation?

Je suis mise en œuvre de l' amélioration de bruit de Perlin . Sa caractéristique clé pour la randomisation est la table de permutation codée en dur, qui donne des gradients essentiellement aléatoires mais reproductibles aux cellules de la grille. La table de permutation n'est qu'une permutation des entiers 0..255, et est généralement la table suivante (copiée directement de l'implémentation originale 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};

Pour référence, un petit patch tiré du bruit généré par ce tableau ressemble à ceci:

Cependant, je voudrais que le code soit un peu plus flexible et permette à ce tableau d'être remanié afin que je puisse créer un champ de bruit complètement nouveau (au lieu de simplement l'échantillonner à un décalage différent). Mais toutes les permutations ne sont pas également bien mélangées. Dans le cas peu probable où la permutation aléatoire ne serait que le tableau trié de 0à 255, le bruit ressemblerait plutôt à ceci:

C'est plutôt mauvais. Bien sûr, à une chance de$1$ dans $256!$, ce n'est pas un cas dont je dois m'inquiéter. Mais ce n'est sûrement pas la seule permutation qui donne des artefacts très visibles. Les permutations triées et presque triées en sens inverse auraient probablement les mêmes problèmes. Alors, combien d'autres permutations ne conviennent pas? Supposons que le code soit utilisé dans un jeu populaire pour générer un monde aléatoire à l'avance, il serait toujours ennuyeux que chaque 100 000e monde généré semble à distance régulier.

La question est donc de savoir ce qui fait exactement une bonne (ou une mauvaise) table de permutation, et comment puis-je évaluer la qualité d'une table de permutation par programme, de sorte que je puisse remanier la table une fois de plus dans le cas peu probable où je lancerais une "mauvaise" " table?

Tout d'abord - un nombre ne doit pas apparaître deux fois, c'est sous-entendu puisque nous parlons de permutations. Donc, remplir la table avec une simple fonction aléatoire (255) ne fonctionnera pas.

Deuxièmement , vous devez vous assurer qu'il n'y a pas de modèles de récurrence prématurée:

Considérez les valeurs 1,2,3,4 - la table de permutation 4,3,2,1 n'est pas très bonne en raison de ses propriétés cycliques courtes, c'est-à-dire 1 -> 4, 4 -> 1. De même avec 4,2 , 3,1 ou 1,2,3,4. Les tables optimales vous guident à travers toutes les positions: 3,1,4,2 ou 2,4,1,3.

Cette propriété devient de plus en plus importante à mesure que vous augmentez le nombre de dimensions et effectuez des recherches récursives.

Cependant, cette approche seule peut créer des grappes de valeurs trop similaires, qui peuvent ou non être souhaitées, ce qui m'amène au point suivant.

Troisièmement , lorsque vous générez une table avec les propriétés non cycliques, vous devez parcourir les indices non attribués restants de manière aléatoire. Lorsque cela est possible, contraignez ici la distance de pas aléatoire à une certaine plage min et max, par exemple 5..120 pour éviter des groupes groupés de valeurs similaires. Ces chiffres méritent d'être expérimentés.

Une possibilité pourrait être d'emprunter à la communauté cryptographique et, en particulier, à la substitution de 8 bits à 8 bits utilisée dans le chiffrement AES / Rijndael. Le tableau et le code pour le générer peuvent être trouvés sur wikipedia.

Je suppose que, pour générer jusqu'à 256 tables supplémentaires, vous pouvez simplement faire quelque chose comme:

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

(puisque la fonction SBox est assez non linéaire)

Cela dit, (et s'il vous plaît pardonnez-moi si j'ai certains détails erronés) dans une vie passée, j'ai implémenté du bruit Perlin en utilisant une fonction RNG / Hash relativement simple mais j'ai trouvé la corrélation en X / Y / Z en raison de ma simplicité la mise en correspondance de 2 ou 3 dimensions avec une valeur scalaire était problématique. J'ai trouvé qu'une solution très simple consistait simplement à utiliser un CRC, par exemple. quelque chose comme

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

Étant donné que les CRC intrinsèques peuvent être intégrés au CPU HW, cela peut être une approche rapide.