Existe uma (família de) funções de ruído monotonicamente não decrescentes?

10

Eu gostaria de uma função para animar um objeto que se move do ponto A para o ponto B ao longo do tempo, de modo que ele atinja B em algum tempo fixo, mas sua posição a qualquer momento seja aleatoriamente perturbada de maneira contínua, mas nunca retrocede. Os objetos se movem ao longo de linhas retas, então eu só preciso de uma dimensão.

Matematicamente, isso significa que estou procurando por alguns f (x), x continuous [0,1] contínuos, tais que:

  • f (0) = 0
  • f (1) = 1
  • x <y → f (x) ≤ f (y)
  • Na "maioria" dos pontos, f (x + d) - f (x) não tem relação óbvia com d. (A função não está aumentando uniformemente ou é previsível; acho que também é equivalente a dizer que nenhum grau de derivada é uma constante.)

Idealmente, eu realmente gostaria de alguma maneira de ter uma família dessas funções, fornecendo algum estado inicial. Eu precisaria de pelo menos 4 bits de semente (16 funções possíveis), para o meu uso atual, mas como isso não é muito, sinta-se à vontade para fornecer ainda mais.

Para evitar vários problemas com erros de acumulação, prefiro que a função não exija nenhum tipo de estado interno. Ou seja, quero que seja uma função real, não uma "função" de programação.


fonte
3
Seu terceiro e quarto requisito podem ser aproximados como f'(x)>0, de modo que a integração normalizada do valor absoluto de qualquer função de ruído cumpra todos os seus requisitos. Infelizmente, não conheço nenhuma maneira fácil de calcular isso, mas talvez alguém o faça. :)
SkimFlux
Será que perturbar a perpendicular da sua função inclinação instantânea funcionaria?
kaoD
Quando você diz "Para evitar vários problemas com erros de acumulação", pensei que estava preocupado com a precisão. Parece que, com base nos seus muitos comentários, você está preocupado com o custo de desempenho de muitas avaliações em excesso. Você deve indicar exatamente a quais restrições de desempenho e memória estamos sujeitos - o requisito é inútil de qualquer maneira, porque aparentemente podemos construir funções com estados que não possuem erros de acumulação (o que isso significa, afinal?). Além disso, seu quarto ponto está errado. Um exemplo trivial: nenhuma derivada de e ^ x é constante; portanto, não é equivalente a dizer isso.
Superbest

Respostas:

4

Para este post, y = f (t) onde t é o parâmetro que você varia (tempo / progresso) e y é a distância do alvo. Então, falarei em termos de pontos em gráficos 2D em que o eixo horizontal é tempo / progresso e a vertical é distância.

Eu acho que você pode fazer uma curva cúbica de Bezier com o primeiro ponto em (0, 1) e o quarto (último) ponto em (1, 0). Os dois pontos médios podem ser colocados aleatoriamente (x = rand, y = rand) dentro desse retângulo 1 por 1. Não consigo verificar isso analiticamente, mas apenas brincando com um applet (sim, vá em frente e ria) parece que a curva de Bezier nunca diminuirá com essa restrição.

Essa será sua função elementar b (p1, p2), que fornece um caminho não decrescente do ponto p1 ao ponto p2.

Agora você pode gerar ab (p (1) = (0, 1), p (n) = (1, 0)) e selecionar um número de p (i) ao longo dessa curva, de modo que 1

Essencialmente, você está gerando um caminho "geral" e, em seguida, dividindo-o em segmentos e regenerando cada segmento.

Como você deseja uma função matemática: Suponha que o procedimento acima seja empacotado em uma função y = f (t, s), que fornece a distância em t para a função de semente s. Você precisará de:

  • 4 números aleatórios para colocar os 2 pontos do meio da spline principal de Bezier (de (0, 1) a (1, 0))
  • números n-1 para os limites de cada segmento se você tiver n segmentos (o primeiro segmento sempre começa em (0, 1) ou seja, t = 0 e o último termina em (1,0) ou seja, = 1)
  • 1 número se você deseja aleatoriamente o número de segmentos
  • Mais 4 números para colocar os pontos médios do spline do segmento em que seu t atinge

Portanto, cada semente deve fornecer um dos seguintes:

  • 7 + n números reais entre 0 e 1 (se você deseja controlar o número de segmentos)
  • 7 números reais e um número inteiro maior que 1 (para um número aleatório de segmentos)

Eu imagino que você pode realizar qualquer um desses simplesmente fornecendo uma matriz de números como a semente s. Como alternativa, você pode fornecer algo como um número s como semente e, em seguida, chamar o gerador de números aleatórios interno com rand (s), rand (s + 1), rand (s + 2) e assim por diante (ou inicializar com se continuar chamando rand.NextNumber).

Observe que, embora toda a função f (t, s) seja composta de muitos segmentos, você está avaliando apenas um segmento para cada t. Você vai precisar para calcular repetidamente os limites de segmentos com este método, porque você vai ter que classificá-los para se certificar que não há dois segmentos se sobrepõem. Você provavelmente pode otimizar e se livrar desse trabalho extra e encontrar apenas os pontos finais de um segmento para cada chamada, mas isso não é óbvio para mim no momento.

Além disso, as curvas de Bezier não são necessárias; qualquer spline com comportamento adequado servirá.

Criei uma implementação de amostra do Matlab.

A função de Bezier (vetorizada):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

A função composta de Bezier descrita acima (deliberadamente deixada sem vetor para esclarecer quanta avaliação é necessária para cada chamada):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

O script que plota a função para uma semente aleatória (observe que este é o único local em que uma função aleatória é chamada, as variáveis ​​aleatórias para todos os outros códigos são propagadas a partir dessa matriz aleatória):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Aqui está um exemplo de saída:

insira a descrição da imagem aqui

Parece atender a maioria dos seus critérios. Contudo:

  • Existem "cantos". Isso pode ser possível usando as curvas de Bezier de maneira mais apropriada.
  • "Obviamente" parece splines, embora você não possa adivinhar o que fará depois de um período não trivial, a menos que conheça a semente.
  • Ele raramente se desvia demais para o canto (pode ser corrigido brincando com a distribuição do gerador de sementes).
  • A função Bezier cúbica não pode alcançar uma área próxima à esquina, dadas essas restrições.
Superbest
fonte
1

Eu acho que, em vez de misturar um monte de cossenos transformados (como os produtos de ponto em ruído perlin dão a você), você pode misturar várias funções monotônicas que começam em f (0) = 0, como f (x) = x ou 2x, ou x ^ 2, etc. De fato, como seu domínio é limitado a 0 => 1, você também pode combinar funções trigonométricas que se ajustam à conta nesse domínio, como cos (90 * x + 270). Para normalizar seus métodos para terminar em 1, você pode simplesmente dividir a soma ponderada desses métodos monotônicos começando em f (0) = 0 por f (1). Algo como isso também deve ser bastante fácil de inverter (o que, a meu ver, você quer um pouco sobre funções reais sem estado versus funções de programação).

Espero que isto ajude.

Gary Dahl
fonte
1

Pode-se analisar essa imagem grosseira insira a descrição da imagem aqui Você pode acabar com uma função que executa sua animação em tempo real, usando uma função de rand uniforme. Eu sei que essa não é a fórmula matemática exata, mas na verdade não existe uma fórmula matemática para uma função aleatória, e mesmo que houvesse uma, você estaria codificando muito para conseguir isso. Considerando que você não especificou nenhuma condição de suavidade, o perfil de velocidade é $ C ^ 0 $ contínuo (mas como você não está lidando com robôs, não precisa se preocupar com perfis de aceleração descontínuos).

teodron
fonte
"na verdade, não existe fórmula matemática para uma função aleatória" Quero uma função de ruído, não uma função aleatória. As funções de ruído estão bem documentadas para existir. Definições parciais como essa também tendem a criar ineficiência (avaliar torna-se O (peças), o que se torna um problema quando você tem longas escalas de tempo), funções impuras (avaliar em O (1), mas precisam manter a posição anterior) ou restringir possíveis funções (por exemplo, todos os pontos de inflexão estão em intervalos fixos).
Hmm, desculpe, eu pensei que as funções de ruído também usam um procedimento gerador de números aleatórios e que também dependem de um conjunto discreto de guia / pontos-chave para produzir uma forma (vi o Perlin Noise foi mencionado .. que funciona através de pseudo-aleatório geradores de números que são bastante difíceis de integrar, portanto, não há solução analítica). Alguém pode integrar uma função de ruído analiticamente? Eu estou querendo saber se um deles poderia ser um candidato ligação
teodron
Como exemplo, o ruído Perlin assume um estado inicial de 255 números de 8 bits, mas daí gera ruído aleatório a uma distância infinita em três dimensões; não é realmente preciso descrevê-los como "pontos-guia"; matematicamente, eles se parecem mais com outros 256 parâmetros que você não deseja fornecer. Como você diz, não é essencialmente integrável, mas é uma função pura. A página que você vinculou é uma má explicação do ruído Perlin (na verdade, não é o ruído Perlin, ele explica). Quanto à possibilidade de algum tipo de função de ruído ... bem, essa é a questão, não é?
1

A maneira usual de gerar uma seqüência crescente de N números aleatórios a partir de [0,1] é gerar N números aleatórios em qualquer intervalo, depois dividi-los pela soma total e depois somar um de cada vez para obter a seqüência.

Gere a sequência 2, 2, 5, 8, 6.
Como a soma é 23, nossos números são 2/23, 2/23, 5/23, 8/23 e 6/23.
Nossa sequência final é 2/23, 4/23, 9/23, 17/23, 23/23

Isso pode ser estendido para 2D, gerando esses valores para X e Y. Você pode aumentar N para obter a granularidade desejada.


Na resposta semelhante da @ teodron, você citou preocupações de eficiência com grandes escalas de tempo. Sem saber o problema real que você está enfrentando, não sei dizer se essa preocupação é válida; mas outra opção seria gerar para N pequeno e simplesmente suavizar o resultado. Dependendo da aplicação, isso pode realmente dar melhores resultados.

insira a descrição da imagem aqui
N = 100, sem suavização

insira a descrição da imagem aqui
N = 15, com suavização

BlueRaja - Danny Pflughoeft
fonte
Tudo o que você está fazendo para suavizar, parece que o resultado nem sequer foi uma função (em torno de x = 0,95); Não tenho certeza se isso é um artefato do seu programa de gráficos ou um erro. A monotonicidade também parece ser violada em torno de 0,7. De qualquer forma, estou familiarizado com "a maneira usual" - estou fazendo esta pergunta porque suspeito que a maneira usual é ruim. Afinal, o ruído pré-Perlin não tinha problemas com LUTs gigantes de ruído de valor, era apenas "o caminho usual". Hoje, temos uma maneira consideravelmente mais flexível e eficiente.
3
Concordo com o BlueRaja: existem maneiras conhecidas e fáceis de implementar de suavizar sem violar a monotonicidade, independentemente do exemplo. Por exemplo, média móvel ou desenho splines. No entanto, a preocupação @JoeWreschnig não é irrelevante. As regras e a mecânica do jogo podem depender de objetos que nunca recuam para funcionar - raramente é uma boa idéia supor que coisas que o solicitante não precisa realmente do que ele diz que precisa.
Superbest
1
@BlueRaja: Minhas queixas básicas sobre abordagens fragmentadas como essa são descritas em minha resposta ao teodrone. Não se trata de encontrar "o resultado mais rígido e matematicamente preciso" - é de abrir novas possibilidades com uma ferramenta matemática anteriormente desconhecida para nós. Mais uma vez, considere a analogia entre LUTs de ruído de valor gigante e ruído de Perlin. Nem todas as perguntas no site precisam de uma resposta "boa o suficiente" que qualquer graduado inteligente em CS possa dar entre aulas - às vezes, vamos filmar por fazer algo original e profissional, ok?
1
Ou poderíamos continuar deixando esse site mergulhar em 90% de confusão elementar sobre matrizes de transformação, 10% "me ajudem a parar de jogar!" Isso criará um site incrível de perguntas e respostas para todos os profissionais que adoram participar.
2
@ Joe: Isso é, erm, desnecessário. Você pediu uma solução para atender aos seus critérios, eu lhe dei uma. Só porque é simples, não faz mal.
BlueRaja - Danny Pflughoeft 29/03
1

Eu sugiro esta implementação inspirada no somatório de oitavas encontradas no ruído fractal, com um pouco de baralhamento barato aqui e ali. Acredito que seja razoavelmente rápido e possa ser ajustado solicitando menos oitavas do que armazenadas nos parâmetros com uma perda de precisão de aproximadamente 1/2^octave.

Você poderia vê-lo como uma implementação por partes que requer apenas tempo O (log (partes)) . A matriz de parâmetros é usada tanto para a posição do pivô de dividir e conquistar quanto para a distância percorrida ao atingir o pivô.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

Isso poderia ser feito mais rápido pré-computando as divisões de ponto flutuante, com o custo de armazenar três vezes mais informações.

Este é um exemplo rápido:

cinco trajetórias diferentes

O exemplo foi obtido com o seguinte código:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}
sam hocevar
fonte
0

Pensar em voz alta e admitir cálculo não é o meu ponto forte ... isso talvez não seja possível? Para evitar qualquer padrão óbvio, a média da função de ruído sobre qualquer alteração em x deve ser próxima de zero e para garantir a monotonicidade, a amplitude de ruído sobre essa alteração em x deve ser menor que a alteração em x, como qualquer amplitude maior poderia resulta em um valor menor em x 'em relação a x. Mas isso significaria que, à medida que você reduz dx para 0, essa função também deve reduzir dA (onde A é amplitude) para zero, o que significa que você não recebe contribuição de nenhuma função de ruído compatível.

Eu posso imaginar que seja possível formular uma função que diminua gradualmente a contribuição do ruído quando x se aproxima de 1, mas isso lhe dará uma função curva que desacelera quando x se aproxima de 1, que não é o que eu acho que você deseja.

Kylotan
fonte
1
Posso desenhar milhões de gráficos dessas funções e, como o SkimFlux diz, a integração de uma função de ruído fornece uma função praticamente equivalente se você a normalizar. Portanto, as funções existem , é apenas uma questão de saber se elas podem ser viáveis codificadas . Daí perguntar aqui em vez de math.se.
Por exemplo, qualquer função que desacelera que x se aproxima de 1 tem um equivalente "invertida" função g(x) = 1 - f(1 - x), que, em vez acelera quando x 0. afasta
Claro, as funções existem - você pode desenhar uma como o teodron - mas são funções de 'ruído'? O ruído implica uma função contínua baseada em entrada pseudo-aleatória com uma amplitude implícita em relação a uma linha de base. E se essa amplitude for muito alta, não será possível garantir que a diferença entre as etapas seja baixa o suficiente para manter a saída monotônica. Mas me ocorre que a densidade do ruído e a etapa de interpolação podem ser criadas para atender às suas especificações, sobre as quais vou pensar um pouco mais.
Kylotan
O ruído significa apenas que é "imprevisível", não diz nada sobre os métodos de geração (ou mesmo tecnicamente, continuidade, embora para animação você quase sempre queira ruído coerente). É verdade que os pontos finais fixos restringem um pouco a possível amplitude dessa função, mas não inteiramente. Outras funções de ruído têm propriedades semelhantes, por exemplo, Perlin (x) = 0 para qualquer número inteiro x. A monotonicidade é uma garantia mais forte do que isso, mas não acho que seja tão mais forte que impossibilite.
@JoeWreschnig Tenho certeza que você sabe que a função de ruído Perlin viola descaradamente vários de seus critérios. Primeiramente, passa por 0 nos nós da grade, de modo que f (x + d) -f (x) é um múltiplo constante de d para alguns x (espaçados regularmente) x. Além disso, devido a esse truque inteligente de armazenamento em cache, ele será repetido para grades grandes. Para ruído clássico, acho que a implementação de referência deve ter o bloco da grade (x, y) idêntico ao bloco (x + 256, y + 256). Você deve declarar se isso é aceitável e até que ponto.
Superbest