Apa asal mula GLSL rand () one-liner ini?

94

Saya telah melihat generator nomor pseudo-acak ini untuk digunakan dalam shader yang dirujuk di sana-sini di seluruh web :

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

Ini berbagai disebut "kanonik", atau "satu baris yang saya temukan di web di suatu tempat".

Apa asal mula fungsi ini? Apakah nilai-nilai konstan sewenang-wenang seperti yang terlihat atau adakah seni dalam pemilihannya? Apakah ada diskusi tentang manfaat fungsi ini?

EDIT: Referensi terlama untuk fungsi ini yang saya temukan adalah arsip ini dari Feb '08 , halaman asli sekarang telah hilang dari web. Tapi tidak ada lagi diskusi tentang itu di sana daripada di tempat lain.

Grumdrig
sumber
Ini adalah fungsi kebisingan, digunakan untuk membuat medan yang dibuat secara prosedural. mirip dengan sesuatu seperti ini en.wikipedia.org/wiki/Perlin_noise
Shai UI

Jawaban:

42

Pertanyaan yang sangat menarik!

Saya mencoba mencari tahu sambil mengetik jawabannya :) Pertama, cara mudah untuk bermain dengannya: 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

Kemudian mari kita pikirkan tentang apa yang kita coba lakukan di sini: Untuk dua koordinat masukan x, y kita mengembalikan sebuah "bilangan acak". Sekarang ini bukan nomor acak. Itu sama setiap kali kita memasukkan x, y yang sama. Ini adalah fungsi hash!

Hal pertama yang dilakukan fungsi ini adalah beralih dari 2d ke 1d. Itu sendiri tidak menarik, tetapi nomornya dipilih sehingga tidak berulang secara khas. Juga kami memiliki tambahan floating point di sana. Akan ada beberapa bit lagi dari y atau x, tetapi angkanya mungkin saja dipilih dengan benar sehingga tercampur.

Kemudian kami mengambil contoh fungsi kotak hitam sin (). Ini akan sangat bergantung pada implementasinya!

Terakhir, ini memperkuat kesalahan dalam implementasi sin () dengan mengalikan dan mengambil pecahan.

Saya tidak berpikir ini adalah fungsi hash yang baik dalam kasus umum. Sin () adalah kotak hitam, di GPU, secara numerik. Seharusnya mungkin untuk membangun yang jauh lebih baik dengan mengambil hampir semua fungsi hash dan mengubahnya. Bagian yang sulit adalah mengubah operasi integer tipikal yang digunakan dalam cpu hashing menjadi operasi float (setengah atau 32bit) atau titik tetap, tetapi itu harus memungkinkan.

Sekali lagi, masalah sebenarnya dengan ini sebagai fungsi hash adalah bahwa sin () adalah kotak hitam.

starmole
sumber
1
Ini tidak menjawab pertanyaan tentang asal usulnya, tapi menurut saya ini tidak benar-benar dapat dijawab. Saya akan menerima jawaban ini karena grafik ilustrasi.
Grumdrig
19

Asalnya mungkin adalah makalah: "Saat menghasilkan bilangan acak, dengan bantuan y = [(a + x) sin (bx)] mod 1", WJJ Rey, Pertemuan Ahli Statistik Eropa ke-22 dan Konferensi Vilnius ke-7 tentang Teori Probabilitas dan Statistik Matematika, Agustus 1998

EDIT: Karena saya tidak dapat menemukan salinan makalah ini dan referensi "TestU01" mungkin tidak jelas, berikut skema yang dijelaskan di TestU01 dalam 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;
} 

dimana satu-satunya nilai konstanta yang direkomendasikan adalah B1.

Perhatikan bahwa ini untuk aliran. Mengonversi ke 1D hash 'n' menjadi grid integer. Jadi tebakan saya adalah seseorang melihat ini dan mengubah 't' menjadi fungsi sederhana f (x, y). Menggunakan konstanta asli di atas yang akan menghasilkan:

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
sumber
3
Sangat menarik! Saya menemukan makalah yang mereferensikannya serta jurnal itu sendiri di Google Books tetapi tampaknya ceramah atau makalah itu sendiri tidak termasuk dalam jurnal.
Grumdrig
1
Juga, akan muncul dari judul bahwa fungsi yang saya tanyakan harus kembali fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))agar sesuai dengan fungsi yang dibahas makalah ini.
Grumdrig
Dan satu hal lagi, jika ini memang asal penggunaan fungsi, pertanyaan tentang asal mula angka ajaib (pilihan adan b) digunakan berulang-ulang tetap ada, tetapi mungkin telah digunakan dalam makalah yang Anda kutip.
Grumdrig
Saya tidak dapat menemukan kertas itu lagi. (edit: makalah yang sama seperti yang ditautkan di atas)
MB Reynolds
Perbarui jawaban dengan info lebih lanjut.
MB Reynolds
8

nilai konstanta berubah-ubah, terutama yang sangat besar, dan beberapa desimal jauh dari bilangan prima.

modulus di atas 1 dari sinus amplitudo hi dikalikan dengan 4000 adalah fungsi periodik. ini seperti tirai jendela atau logam bergelombang yang dibuat sangat kecil karena dikalikan dengan 4000, dan diputar pada suatu sudut oleh perkalian titik.

karena fungsinya adalah 2-D, hasil perkalian titik memiliki efek memutar fungsi periodik pada sumbu X dan Y secara relatif miring. Dengan rasio sekitar 13/79. Ini tidak efisien, Anda benar-benar dapat mencapai hal yang sama dengan melakukan sinus (13x + 79y) ini juga akan mencapai hal yang sama yang saya pikir dengan lebih sedikit matematika ..

Jika Anda menemukan periode fungsi di X dan Y, Anda dapat mengambil sampelnya sehingga akan terlihat seperti gelombang sinus sederhana lagi.

Berikut adalah gambar grafik yang diperbesar

Saya tidak tahu asalnya tetapi ini mirip dengan banyak lainnya, jika Anda menggunakannya dalam grafik secara berkala, itu akan cenderung menghasilkan pola moire dan Anda bisa melihatnya akhirnya berputar lagi.

aliential
sumber
Tetapi pada GPU X dan Y berkisar dari 0..1 dan itu terlihat jauh lebih acak jika Anda mengubah grafik Anda. Saya tahu ini terdengar seperti pernyataan tetapi sebenarnya ini adalah pertanyaan, karena pendidikan matematika saya berakhir pada usia 18 tahun.
String
saya tahu, saya baru saja memperbesar sehingga Anda dapat melihat bahwa fungsi acak adalah dari bentuk itu kecuali bahwa punggungnya sangat cepat berubah, kecuali Anda harus memperbesar kecil untuk melihat perubahan sama sekali ... Anda dapat membayangkan bahwa mengambil poin di punggung bukit akan memberikan angka acak yang cukup dari 0 hingga 1 tinggi untuk 1 hingga 1 x dan nilai y.
aliential
Oh, saya mengerti, dan itu tampaknya sangat logis untuk setiap pembuatan bilangan acak yang pada intinya menggunakan fungsi sin
Strings
2
Ini adalah zigzag linier pada dasarnya, dan dosa seharusnya menambahkan sedikit variasi, itu sama seperti jika seseorang menjentikkan satu pak kartu dari satu menjadi 10 dengan sangat cepat berputar-putar di depan Anda dan Anda seharusnya mencoba akhirnya mengambil pola angka dari kartu, itu akan menjadi angka acak karena akan menjentikkan sangat cepat sehingga dia hanya bisa mendapatkan pola dengan memilih kartu dalam sinkronisasi yang tepat relatif terhadap seberapa cepat kartu itu berputar.
aliential
Sekadar catatan, itu tidak akan lebih cepat untuk dilakukan (13x + 79y)karena dot(XY, AB)akan melakukan persis seperti yang Anda gambarkan, sebagai produk titik, yangx,y dot 13, 79 = (13x + 79y)
whn
1

Mungkin itu beberapa pemetaan kacau yang tidak berulang, kemudian bisa menjelaskan banyak hal, tetapi juga bisa hanya beberapa manipulasi sewenang-wenang dengan jumlah besar.

EDIT: Pada dasarnya, fungsi frakt (sin (x) * 43758.5453) adalah fungsi seperti hash sederhana, sin (x) memberikan interpolasi sin halus antara -1 hingga 1, jadi sin (x) * 43758.5453 akan menjadi interpolasi dari - 43758.5453 hingga 43758.5453. Ini adalah rentang yang cukup besar, sehingga langkah kecil dalam x akan memberikan hasil langkah yang besar dan variasi yang sangat besar pada bagian pecahan. "Fraktur" diperlukan untuk mendapatkan nilai dalam kisaran -0,99 ... hingga 0,999 .... Sekarang, ketika kita memiliki sesuatu seperti fungsi hash, kita harus membuat fungsi untuk produksi hash dari vektor. Cara termudah adalah memanggil "hash" secara terpisah untuk x sembarang komponen y dari vektor masukan. Tetapi kemudian, kita akan memiliki beberapa nilai simetris. Jadi, kita harus mendapatkan beberapa nilai dari vektor tersebut, pendekatannya adalah mencari beberapa vektor acak dan menemukan perkalian "titik" ke vektor itu, ini dia: fract (sin (dot (co.xy, vec2 (12.9898,78.233))) * 43758.5453); Juga, menurut vektor yang dipilih, panjangnya harus cukup panjang untuk memiliki beberapa peroid dari fungsi "sin" setelah perkalian "titik" akan dihitung.

Roma
sumber
tapi 4e5 juga akan bekerja, saya tidak mengerti mengapa angka ajaib 43758.5453. (juga, saya akan mengimbangi x dengan beberapa angka pecahan untuk menghindari rand (0) = 0.
Fabrice NEYRET
1
Saya pikir dengan 4e5 Anda tidak akan mendapatkan begitu banyak variasi dari bit pecahan, itu akan selalu memberi Anda nilai yang sama. Jadi, dua syarat harus dipenuhi, cukup besar dan memiliki variasi pecahan yang cukup baik.
Roman
apa maksudmu, "akan selalu memberimu nilai yang sama"? (jika maksud Anda itu akan selalu mengambil digit yang sama, pertama, mereka masih kacau, kedua, float disimpan sebagai m * 2 ^ p, bukan 10 ^ p, jadi * 4e5 masih mengacak bit).
Fabrice NEYRET
Saya pikir Anda menulis representasi eksponensial dari bilangan tersebut, 4 * 10 ^ 5, jadi sin (x) * 4e5 akan memberi Anda bilangan yang tidak terlalu kacau. Saya setuju bahwa bit pecahan dari gelombang dosa akan memberi Anda chatoic yang bagus juga.
Roman
Tapi, itu tergantung pada kisaran x, maksud saya jika fungsi harus kuat untuk nilai kecil (-0.001, 0.001) dan besar (-1, 1). Anda dapat mencoba melihat perbedaan dengan fract (sin (x /1000.0) * 43758.5453); dan fract (sin (x /1000.0) * 4e5) ;, dimana x dalam range [-1., 1.]. Pada varian kedua gambar akan lebih monotonik (setidaknya saya melihat perbedaan pada shadernya). Tapi, secara umum, saya setuju bahwa Anda masih bisa menggunakan 4e5 dan mendapatkan hasil yang cukup baik.
Roman