Was macht eine gute Permutationstabelle aus?

8

Ich implementiere verbessertes Perlin-Rauschen . Das Hauptmerkmal für die Randomisierung ist die fest codierte Permutationstabelle, die im Wesentlichen zufällige, aber reproduzierbare Gradienten an den Zellen des Gitters liefert. Die Permutationstabelle ist nur eine Permutation der ganzen Zahlen 0..255und normalerweise die folgende Tabelle (direkt aus Perlins ursprünglicher Implementierung kopiert):

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

Als Referenz sieht ein kleiner Fleck aus dem von dieser Tabelle erzeugten Rauschen folgendermaßen aus:

Geben Sie hier die Bildbeschreibung ein

Ich möchte jedoch, dass der Code etwas flexibler ist und dass diese Tabelle neu gemischt wird, damit ich ein völlig neues Rauschfeld erstellen kann (anstatt es nur mit einem anderen Versatz abzutasten). Aber nicht alle Permutationen werden gleich gut gemischt. In dem unwahrscheinlichen Fall, dass die zufällige Permutation nur das sortierte Array von 0bis ist 255, würde das Rauschen stattdessen so aussehen:

Geben Sie hier die Bildbeschreibung ein

Das ist irgendwie schlecht. Natürlich mit einer Chance von zuDies ist kein Fall, über den ich mir Sorgen machen muss. Dies ist jedoch sicherlich nicht die einzige Permutation, die sehr auffällige Artefakte liefert. Umgekehrt sortierte und fast sortierte Permutationen hätten wahrscheinlich die gleichen Probleme. Wie viele andere Permutationen sind also ungeeignet? Angenommen, der Code würde in einem beliebten Spiel verwendet, um eine zufällige Welt im Voraus zu generieren. Es wäre immer noch ärgerlich, wenn jede 100.000ste generierte Welt aus der Ferne regelmäßig aussehen würde.1256!

Die Frage ist also, was genau eine gute (oder eine schlechte) Permutationstabelle ausmacht und wie ich die Qualität einer Permutationstabelle programmgesteuert einschätze, damit ich die Tabelle in dem unwahrscheinlichen Fall, dass ich eine "schlechte" würfle, erneut neu mischen kann " Tabelle?

Martin Ender
quelle
Statistische Tests für Zufallszahlengeneratoren sollten nützlich sein. Die Berechnung der erwarteten Anzahl von Paaren in geordneter Reihenfolge (umgekehrter Reihenfolge) ist möglicherweise ein guter Ausgangspunkt für einen Test. Dieses Dokument enthält viele Referenzen: csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf .
Daniel M Gessel

Antworten:

4

Zuallererst - eine Zahl darf nicht zweimal vorkommen, das ist impliziert, da es sich um Permutationen handelt. Das Füllen der Tabelle mit einer einfachen Zufallsfunktion (255) funktioniert also nicht.

Zweitens müssen Sie sicherstellen, dass keine vorzeitigen Wiederholungsmuster auftreten:

Betrachten Sie die Werte 1,2,3,4 - die Permutationstabelle 4,3,2,1 ist aufgrund ihrer kurzen zyklischen Eigenschaften, dh 1 -> 4, 4 -> 1, nicht sehr gut. Ebenso mit 4,2 3,1 oder 1,2,3,4. Die optimalen Tische führen Sie durch alle Positionen: 3,1,4,2 oder 2,4,1,3.

Diese Eigenschaft wird immer wichtiger, wenn Sie die Anzahl der Dimensionen erhöhen und rekursive Suchvorgänge durchführen.

Dieser Ansatz allein kann jedoch zu Clustern zu ähnlicher Werte führen, die möglicherweise erwünscht sind oder nicht, was mich zum nächsten Punkt führt.

Drittens , wenn Sie eine Tabelle mit den nicht zyklischen Eigenschaften generieren, müssen Sie die verbleibenden nicht zugewiesenen Indizes auf zufällige Weise durchlaufen. Wenn möglich, beschränken Sie den zufälligen Schrittabstand hier auf einen bestimmten Min- und Max-Bereich, z. B. 5..120, um Clustergruppen mit ähnlichen Werten zu vermeiden. Es lohnt sich, mit diesen Zahlen zu experimentieren.

mhbuur
quelle
Willkommen bei Computer Graphics SE! Zu Ihrem zweiten Punkt habe ich mir die zyklische Zerlegung der von Perlin verwendeten Permutationstabelle angesehen. Es besteht aus mehreren Längenzyklen {4, 121, 89, 12, 4, 15, 4, 6}, also ist das anscheinend gut genug? (Oder vielleicht auch nicht und eine andere Permutationstabelle wäre sogar "besser"? Obwohl ich nicht sicher bin, ob ein Mensch den Unterschied wahrnehmen kann. Oder ist es tatsächlich besser, mehrere Zyklen zu haben?) Ich folge Ihrem dritten Punkt nicht . Eine gleichmäßige zufällige Verteilung von was? Und welche Schrittweite meinst du?
Martin Ender
Vielen Dank! Ja, das war ziemlich kryptisch, denke ich. Es war Jahre her, dass ich damit experimentiert habe, daher erinnere ich mich nicht an die genaue Implementierung, aber wenn Sie die Implementierung für die optimale Pfadgenerierung haben, sollte klar werden, dass Sie zufällige Positionen von dem auswählen, was von nicht verwendeten Indizes übrig bleibt - es ist diese zufällige Schrittlänge beziehe ich mich. Ich habe die Antwort aktualisiert
mhbuur
1

Eine Möglichkeit könnte darin bestehen, Kredite von der kryptografischen Gemeinschaft aufzunehmen, insbesondere die 8-Bit- bis 8-Bit-Substitution, die in der AES / Rijndael-Chiffre verwendet wird. Die Tabelle und der Code zum Generieren finden Sie auf Wikipedia.

Ich würde vermuten, dass Sie, um bis zu 256 zusätzliche Tabellen zu generieren, einfach Folgendes tun könnten:

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

(da die SBox-Funktion ziemlich nichtlinear ist)

Nachdem ich das gesagt habe (und bitte verzeihen Sie mir, wenn ich einige Details falsch verstanden habe), habe ich in einem früheren Leben Perlin-Rauschen mit einer relativ einfachen RNG / Hash-Funktion implementiert, aber die Korrelation in X / Y / Z aufgrund meiner einfachen gefunden Die Zuordnung von 2 oder 3 Dimensionen zu einem Skalarwert war problematisch. Ich fand, dass eine sehr einfache Lösung darin bestand, nur einen CRC zu verwenden, z. etwas wie

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

Angesichts der Tatsache, dass CRCs in CPU HW integriert sein können, kann dies ein schneller Ansatz sein.

Simon F.
quelle