Qual é a origem deste GLSL rand () one-liner?

92

Já vi este gerador de números pseudo-aleatórios para uso em shaders mencionados aqui e ali na web :

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

É também chamado de "canônico" ou "uma linha que encontrei em algum lugar na web".

Qual é a origem desta função? Os valores constantes são tão arbitrários quanto parecem ou existe alguma arte para sua seleção? Existe alguma discussão sobre os méritos desta função?

EDIT: A referência mais antiga a esta função que encontrei é este arquivo de fevereiro de 2008 , a página original agora sendo retirado da web. Mas não há mais discussão sobre isso do que em qualquer outro lugar.

Grumdrig
fonte
É uma função de ruído, usada para criar terreno gerado por procedimentos. semelhante a algo assim en.wikipedia.org/wiki/Perlin_noise
foreyez

Respostas:

42

Pergunta muito interessante!

Estou tentando descobrir isso enquanto digito a resposta :) Primeiro, uma maneira fácil de brincar com isso: 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

Então, vamos pensar sobre o que estamos tentando fazer aqui: para duas coordenadas de entrada x, y, retornamos um "número aleatório". Agora, este não é um número aleatório. É o mesmo sempre que inserimos o mesmo x, y. É uma função hash!

A primeira coisa que a função faz é ir de 2d para 1d. Isso não é interessante em si, mas os números são escolhidos de forma que não se repitam normalmente. Também temos uma adição de ponto flutuante lá. Haverá mais alguns bits de y ou x, mas os números podem ser escolhidos da maneira certa para que haja uma mistura.

Em seguida, experimentamos uma função sin () de caixa preta. Isso vai depender muito da implementação!

Por último, ele amplifica o erro na implementação de sin () multiplicando e obtendo a fração.

Não acho que seja uma boa função hash no caso geral. O sin () é uma caixa preta, na GPU, numericamente. Deve ser possível construir um muito melhor pegando quase qualquer função hash e convertendo-a. A parte difícil é transformar a operação típica de inteiro usada no hash da CPU em float (metade ou 32 bits) ou operações de ponto fixo, mas deve ser possível.

Novamente, o verdadeiro problema com isso como uma função hash é que sin () é uma caixa preta.

toupeira
fonte
1
Isso não responde à pergunta sobre a origem, mas não acho que seja realmente respondível. Aceito essa resposta por causa do gráfico ilustrativo.
Grumdrig
19

A origem é provavelmente o papel: "Sobre a geração de números aleatórios, com a ajuda de y = [(a + x) sin (bx)] mod 1", WJJ Rey, 22º Encontro Europeu de Estatísticos e a 7ª Conferência de Vilnius sobre Teoria de Probabilidade e Estatística Matemática, agosto de 1998

EDITAR: Como não consigo encontrar uma cópia deste artigo e a referência "TestU01" pode não estar clara, aqui está o esquema descrito em TestU01 em 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;
} 

onde o único valor constante recomendado é o B1.

Observe que isso é para um riacho. A conversão para um hash 'n' 1D torna-se a grade inteira. Então, meu palpite é que alguém viu isso e converteu 't' em uma função simples f (x, y). Usar as constantes originais acima resultaria em:

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
fonte
3
Muito interessante mesmo! Encontrei um artigo que faz referência a ele , bem como ao próprio jornal no Google Books, mas parece que a palestra ou o próprio artigo não foram incluídos no jornal.
Grumdrig
1
Além disso, o título parece que a função sobre a qual estou perguntando deve retornar fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))para se adequar à função a que se refere o artigo.
Grumdrig
E mais uma coisa, se esta é realmente a origem do uso da função, a questão da origem dos números mágicos (escolha de ae b) usados ​​continuamente permanece, mas pode ter sido usada no artigo que você cita.
Grumdrig
Também não consigo encontrar o jornal. (editar: mesmo papel do link acima)
MB Reynolds
Atualize a resposta com mais informações.
MB Reynolds
8

os valores constantes são arbitrários, especialmente porque eles são muito grandes, e alguns decimais de distância dos números primos.

um módulo acima de 1 de um sinus de amplitude alta multiplicado por 4000 é uma função periódica. é como uma cortina de janela ou um metal corrugado muito pequeno porque é multiplicado por 4000 e virado em um ângulo pelo produto escalar.

como a função é 2-D, o produto escalar tem o efeito de girar a função periódica oblíqua em relação aos eixos X e Y. Na proporção de 13/79 aproximadamente. É ineficiente, você pode realmente conseguir o mesmo fazendo sinus de (13x + 79y) isso também vai conseguir a mesma coisa que eu acho com menos matemática.

Se você encontrar o período da função em X e Y, poderá fazer uma amostragem para que pareça uma onda senoidal simples novamente.

Aqui está uma foto ampliada no gráfico

Não sei a origem, mas é semelhante a muitos outros, se você usá-lo em gráficos em intervalos regulares, ele tenderia a produzir padrões moiré e você poderia ver que eventualmente ele volta ao normal.

aliential
fonte
Mas nas GPUs X e Y variam de 0 a 1 e isso parece muito mais aleatório se você alterar seu gráfico. Eu sei que isso soa como uma afirmação, mas na verdade é uma pergunta, porque minha educação matemática terminou aos 18 anos.
Strings de
Eu sei, eu apenas ampliei para que você possa ver que a função aleatória é dessa forma, exceto que as cristas mudam muito rapidamente, exceto que você precisa aumentar o zoom para ver as mudanças ... você pode imaginar que tirando pontos nas cristas darão números bastante aleatórios de 0 a 1 altura para 1 a 1 valores xey.
aliential de
Oh, eu entendo, e isso parece muito lógico para qualquer geração de número aleatório que em seu núcleo usa uma função sin
Strings de
2
é um zigue-zague linear essencialmente, e o pecado supostamente adiciona um pouquinho de variação, é o mesmo como se alguém estivesse sacudindo um baralho de um para 10 muito rápido rodando e rodando na sua frente e você deveria tentar Se pegasse um padrão de números das cartas, eles seriam números aleatórios porque seria um movimento muito rápido que ele só poderia obter um padrão escolhendo cartas em uma sincronização exata em relação à velocidade de rotação das cartas.
aliential de
Apenas uma nota, não seria mais rápido para fazer (13x + 79y)uma vez dot(XY, AB)vai fazer exatamente o que você descreve, como o produto escalar, o quex,y dot 13, 79 = (13x + 79y)
whn
1

Talvez seja algum mapeamento caótico não recorrente, então poderia explicar muitas coisas, mas também pode ser apenas alguma manipulação arbitrária com grandes números.

EDITAR: Basicamente, a função fract (sin (x) * 43758.5453) é uma função simples do tipo hash, o sin (x) fornece uma interpolação de sin (x) suave entre -1 e 1, então sin (x) * 43758.5453 será interpolação de - 43758,5453 a 43758,5453. Este é um intervalo bastante grande, então mesmo um pequeno passo em x fornecerá um grande passo no resultado e uma variação realmente grande na parte fracionária. A "fratura" é necessária para obter valores na faixa de -0,99 ... a 0,999 .... Agora, quando temos algo como uma função hash, devemos criar uma função para o hash de produção a partir do vetor. A maneira mais simples é chamar "hash" separadamente para x qualquer componente y do vetor de entrada. Mas então, teremos alguns valores simétricos. Portanto, devemos obter algum valor do vetor, a abordagem é encontrar algum vetor aleatório e encontrar o produto "ponto" para esse vetor, vamos lá: fract (sin (ponto (co.xy, vec2 (12.9898,78.233))) * 43758.5453); Além disso, de acordo com o vetor selecionado, seu comprimento deve ser longo o suficiente para ter várias peróides da função "sin" após o produto "ponto" ser calculado.

romano
fonte
mas o 4e5 também deve funcionar, não entendo por que o número mágico 43758.5453. (também, eu compensaria x por algum número fracionário para evitar rand (0) = 0.
Fabrice NEYRET
1
Acho que com 4e5 você não obterá tanta variação dos bits fracionários, ele sempre fornecerá o mesmo valor. Portanto, duas condições devem ser atendidas, grande o suficiente e com variação boa o suficiente das partes fracionárias.
Romano
o que você quer dizer com "sempre dará a você o mesmo valor"? (se você quer dizer que sempre terá os mesmos dígitos, primeiro, eles ainda são caóticos, segundo, float são armazenados como m * 2 ^ p, não 10 ^ p, então * 4e5 ainda embaralha bits).
Fabrice NEYRET
Achei que você escreveu uma representação exponencial do número, 4 * 10 ^ 5, então sin (x) * 4e5 lhe dará um número não tão caótico. Eu concordo que bits fracionários da onda de pecado também lhe darão um bom chatoico.
Romano
Mas, então, depende do intervalo de x, quero dizer, se a função deve ser robusta para valores pequenos (-0,001, 0,001) e grandes (-1, 1). Você pode tentar ver a diferença com fratura (sin (x /1000.0) * 43758.5453); e fract (sin (x /1000,0) * 4e5) ;, onde x no intervalo [-1., 1.]. Na segunda variante, a imagem será mais monotônica (pelo menos vejo a diferença no shader). Mas, em geral, concordo que você ainda pode usar 4e5 e ter um resultado bom o suficiente.
Romano