Jakie jest pochodzenie tego jednowierszowego GLSL rand ()?

93

Widziałem ten generator liczb pseudolosowych do użytku w modułach cieniujących, o których mowa tu i tam w sieci :

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

Jest różnie nazywany „kanonicznym” lub „jednym wierszem, który znalazłem gdzieś w sieci”.

Jakie jest pochodzenie tej funkcji? Czy wartości stałe są tak arbitralne, jak się wydają, czy też jest jakaś sztuka w ich wyborze? Czy jest dyskusja na temat zalet tej funkcji?

EDYCJA: Najstarszym odniesieniem do tej funkcji, z jakim się spotkałem, jest archiwum z lutego 2008 roku , oryginalna strona została usunięta z sieci. Ale nie ma tam więcej dyskusji na ten temat niż gdziekolwiek indziej.

Grumdrig
źródło
Jest to funkcja szumowa, używana do tworzenia terenu generowanego proceduralnie. podobne do czegoś takiego en.wikipedia.org/wiki/Perlin_noise
foreyez

Odpowiedzi:

42

Bardzo ciekawe pytanie!

Próbuję to rozgryźć podczas wpisywania odpowiedzi :) Najpierw łatwy sposób na zabawę: 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

Następnie zastanówmy się, co próbujemy tutaj zrobić: Dla dwóch współrzędnych wejściowych x, y zwracamy „liczbę losową”. Teraz nie jest to jednak liczba losowa. Jest tak samo za każdym razem, gdy wprowadzamy te same x, y. To funkcja skrótu!

Pierwszą rzeczą, jaką robi funkcja, jest przejście z 2d do 1d. To nie jest interesujące samo w sobie, ale liczby są tak dobrane, aby się nie powtarzały. Mamy tam również dodatek zmiennoprzecinkowy. Będzie jeszcze kilka bitów od y lub x, ale liczby mogą być po prostu wybrane dobrze, więc robi się mieszanie.

Następnie próbkujemy funkcję sin () z czarnej skrzynki. Będzie to dużo zależeć od wdrożenia!

Wreszcie wzmacnia błąd w implementacji sin () poprzez pomnożenie i pobranie ułamka.

Nie sądzę, żeby to była dobra funkcja skrótu w ogólnym przypadku. Sin () to numerycznie czarna skrzynka na GPU. Powinno być możliwe skonstruowanie znacznie lepszego, biorąc prawie każdą funkcję skrótu i ​​konwertując ją. Najtrudniejsze jest przekształcenie typowej operacji na liczbach całkowitych używanej w haszowaniu procesora w operacje zmiennoprzecinkowe (pół- lub 32-bitowe) lub operacje stałoprzecinkowe, ale powinno być możliwe.

Ponownie, prawdziwym problemem związanym z tym jako funkcją skrótu jest to, że sin () jest czarną skrzynką.

starmole
źródło
1
To nie odpowiada na pytanie o pochodzenie, ale nie sądzę, że tak naprawdę można na to odpowiedzieć. Przyjmę tę odpowiedź ze względu na ilustracyjny wykres.
Grumdrig
19

Źródłem jest prawdopodobnie artykuł: "O generowaniu liczb losowych za pomocą y = [(a + x) sin (bx)] mod 1", WJJ Rey, 22. European Meeting of Statisticians and the 7th Vilnius Conference on Probability Theory and Statystyka matematyczna, sierpień 1998

EDYCJA: Ponieważ nie mogę znaleźć kopii tego dokumentu, a odniesienie do „TestU01” może nie być jasne, oto schemat opisany w TestU01 w 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;
} 

gdzie jedyną zalecaną wartością stałą jest B1.

Zwróć uwagę, że dotyczy to strumienia. Konwersja do 1-wymiarowego skrótu „n” staje się siatką liczb całkowitych. Domyślam się, że ktoś to zobaczył i przekształcił „t” w prostą funkcję f (x, y). Użycie oryginalnych stałych powyżej dałoby:

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
źródło
3
Rzeczywiście bardzo interesujące! Znalazłem artykuł, który odnosi się do niego, a także do samego dziennika w Google Books, ale wydaje się, że sam referat lub artykuł nie zostały uwzględnione w czasopiśmie.
Grumdrig
1
Ponadto z tytułu wynikałoby, że funkcja, o którą pytam, powinna powrócić fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))do funkcji, o której mowa w artykule.
Grumdrig
I jeszcze jedno, jeśli to rzeczywiście jest pochodzenie użycia funkcji, pozostaje kwestia pochodzenia magicznych liczb (wybór ai b) używanych wielokrotnie, ale mogła zostać użyta w cytowanej pracy.
Grumdrig
Nie mogę już znaleźć papieru. (edytuj: ten sam artykuł, co link powyżej)
MB Reynolds
Zaktualizuj odpowiedź, podając więcej informacji.
MB Reynolds
8

wartości stałe są dowolne, zwłaszcza że są bardzo duże i oddalone o kilka miejsc po przecinku od liczb pierwszych.

moduł powyżej 1 sinusa o wysokiej amplitudzie pomnożony przez 4000 jest funkcją okresową. jest jak roleta okienna lub blacha falista, która jest bardzo mała, ponieważ jest pomnożona przez 4000 i obrócona pod kątem przez iloczyn skalarny.

ponieważ funkcja jest 2-D, iloczyn skalarny powoduje obrócenie funkcji okresowej ukośnie względem osi X i Y. W przybliżeniu o stosunku 13/79. Jest to nieefektywne, możesz osiągnąć to samo, wykonując sinus (13x + 79y), to również da to samo, co myślę, przy mniejszej liczbie matematyki.

Jeśli znajdziesz okres funkcji zarówno w X, jak i Y, możesz próbkować go, aby ponownie wyglądał jak prosta fala sinusoidalna.

Oto jego zdjęcie powiększone na wykresie

Nie znam pochodzenia, ale jest podobny do wielu innych, jeśli użyjesz go w grafice w regularnych odstępach czasu, będzie miał tendencję do tworzenia wzorów mory i możesz zobaczyć, że w końcu znowu się kręci.

aliential
źródło
Ale na GPU X i Y mieszczą się w zakresie od 0..1 i wygląda to znacznie bardziej losowo, jeśli zmienisz wykres. Wiem, że to brzmi jak stwierdzenie, ale w rzeczywistości jest to pytanie, ponieważ moja edukacja matematyczna skończyła się w wieku 18 lat.
Strings
Wiem, po prostu powiększyłem, aby zobaczyć, że losowa funkcja ma taką formę, z wyjątkiem tego, że grzbiety zmieniają się bardzo szybko, z wyjątkiem tego, że musisz powiększyć małe powiększenie, aby w ogóle zobaczyć zmiany ... możesz sobie wyobrazić, że biorąc punkty na grzbietach da całkiem losowe liczby od 0 do 1 wysokości dla 1 do 1 wartości xiy.
aliential
Och, rozumiem, i wydaje się to bardzo logiczne dla każdego generowania liczb losowych, które w swej istocie używa funkcji grzechu
Strings
2
to w zasadzie liniowy zygzak, a grzech ma dodać odrobinę urozmaicenia, to tak samo, jakby ktoś rzucał przed tobą talią kart od jednego do 10 bardzo szybko w kółko i powinieneś spróbować na koniec podnieś wzór liczb z kart, byłyby to liczby losowe, ponieważ bardzo szybko poruszałby się, gdyby mógł uzyskać wzór tylko poprzez wybranie kart w dokładnej synchronizacji w stosunku do szybkości obracania się kart.
aliential
Tylko uwaga, nie byłoby to szybsze, (13x + 79y)ponieważ dot(XY, AB)zrobi dokładnie to, co x,y dot 13, 79 = (13x + 79y)
opisujesz
1

Może jest to jednorazowe chaotyczne mapowanie, które mogłoby wyjaśnić wiele rzeczy, ale może też być po prostu dowolną manipulacją dużymi liczbami.

EDYCJA: Zasadniczo funkcja ułamek (sin (x) * 43758.5453) jest prostą funkcją podobną do skrótu, sin (x) zapewnia płynną interpolację grzechu między -1 do 1, więc sin (x) * 43758.5453 będzie interpolacją od - Od 43758,5453 do 43758,5453. Jest to dość duży zakres, więc nawet mały krok w x zapewni duży skok w wyniku i naprawdę duże zróżnicowanie w części ułamkowej. „Ułamek” jest potrzebny do uzyskania wartości z zakresu od -0,99 ... do 0,999 .... Teraz, gdy mamy coś w rodzaju funkcji skrótu, powinniśmy utworzyć funkcję do produkcji hash z wektora. Najprostszym sposobem jest oddzielne wywołanie „hasha” dla x dowolnego składnika y wektora wejściowego. Ale wtedy będziemy mieli pewne symetryczne wartości. Więc powinniśmy pobrać jakąś wartość z wektora, podejście polega na znalezieniu jakiegoś losowego wektora i znalezieniu iloczynu "kropkowego" do tego wektora, zaczynamy: fract (sin (dot (co.xy, vec2 (12,9898,78,233))) * 43758,5453); Ponadto, zgodnie z wybranym wektorem, jego długość powinna być na tyle duża, aby mieć kilka peroidów funkcji „sin” po obliczeniu iloczynu „kropkowego”.

rzymski
źródło
ale wtedy 4e5 też powinno działać, nie rozumiem, dlaczego magiczna liczba 43758,5453. (również przesunąłbym x o jakąś liczbę ułamkową, aby uniknąć rand (0) = 0.
Fabrice NEYRET
1
Myślę, że przy 4e5 nie dostaniesz tak dużej zmienności bitów ułamkowych, zawsze da ci to tę samą wartość. Tak więc muszą być spełnione dwa warunki, wystarczająco duże i mieć wystarczająco dobrą zmienność części ułamkowych.
Roman
co masz na myśli, mówiąc „zawsze będzie dawać tę samą wartość”? (jeśli masz na myśli te same cyfry, po pierwsze, nadal są chaotyczne, po drugie, zmiennoprzecinkowe są przechowywane jako m * 2 ^ p, a nie 10 ^ p, więc * 4e5 nadal szyfruje bity).
Fabrice NEYRET
Myślałem, że napisałeś wykładniczą reprezentację liczby, 4 * 10 ^ 5, więc sin (x) * 4e5 da ci mniej chaotyczną liczbę. Zgadzam się, że ułamkowe bity z fali grzechu również dadzą ci dobrą chatoic.
Roman
Ale wtedy zależy to od zakresu x, mam na myśli, czy funkcja powinna być odporna dla małych (-0,001, 0,001) i dużych wartości (-1, 1). Możesz spróbować zobaczyć różnicę z ułamkiem (sin (x /1000.0) * 43758.5453); and fract (sin (x /1000.0) * 4e5) ;, gdzie x in range [-1., 1]. W drugim wariancie obraz będzie bardziej monotoniczny (przynajmniej widzę różnicę w shaderze). Ale ogólnie zgadzam się, że nadal możesz używać 4e5 i mieć wystarczająco dobry wynik.
Roman