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

8

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:

entrez la description de l'image ici

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:

entrez la description de l'image ici

C'est plutôt mauvais. Bien sûr, à une chance de1 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?

Martin Ender
la source
Des tests statistiques pour les générateurs de nombres aléatoires devraient être utiles. Le calcul du nombre attendu de paires dans l'ordre (ordre inverse) peut être un bon point de départ pour un test. Ce document contient de nombreuses références: csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf .
Daniel M Gessel du

Réponses:

4

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.

mhbuur
la source
Bienvenue dans Computer Graphics SE! Concernant votre deuxième point, j'ai examiné la décomposition cyclique de la table de permutation utilisée par Perlin. Il se compose de plusieurs cycles de longueurs {4, 121, 89, 12, 4, 15, 4, 6}, donc apparemment, c'est assez bon? (Ou peut-être que ce n'est pas le cas et qu'une table de permutation différente serait encore "meilleure"? Bien que je ne sois pas sûr qu'un humain puisse percevoir la différence. Ou est-il préférable d'avoir plusieurs cycles?) Je ne suis pas en train de suivre votre troisième point . Une distribution aléatoire uniforme de quoi? Et quelle distance de pas voulez-vous dire?
Martin Ender
Merci! Ouais, c'était assez énigmatique je suppose. Il y a des années, j'ai expérimenté cela, donc je ne me souviens pas de l'implémentation exacte, mais lorsque vous avez l'implémentation pour la génération de chemin optimale, il devrait devenir évident que vous choisissez des positions aléatoires de ce qui reste des indices inutilisés - c'est cette longueur de pas aléatoire dont je parle. J'ai mis à jour la réponse
mhbuur
1

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.

Simon F
la source