Algoritmo de deslocamento do ponto médio

14

MDPMDP

Esta questão surgiu principalmente do puro desespero , depois de passar várias horas tentando descobrir o problema.

Se você olhar para a figura acima, verá que meu algoritmo de algoritmo de deslocamento do ponto médio está funcionando (um pouco) com sucesso; na produção de um padrão de ruído um tanto coerente.

No entanto, está deixando para trás uma grade pontilhada preta na imagem, e não faço ideia do porquê. Eu posso prever que isso seja um problema na matemática, mas simplesmente não consigo vê-lo; nem isso foi apontado em nenhum recurso on-line como um possível problema; portanto, qualquer ajuda será apreciada para caçar esse bug.

unsigned char** mdp(unsigned char** base, unsigned base_n, unsigned char r) {
    size_t n = (2 * base_n) - 1;

    unsigned char** map = new unsigned char*[n];
    for (unsigned i = 0; i < n; ++i) map[i] = new unsigned char[n];

    // Resize
    // 1 0 1
    // 0 0 0
    // 1 0 1
    for (size_t i = 0; i < n; i += 2) {
        for (size_t j = !(i % 2 == 0); j < n; j += 2) {
            map[i][j] = base[i / 2][j / 2];
        }
    }

    // Diamond algorithm
    // 0 0 0
    // 0 X 0
    // 0 0 0
    for (size_t i = 1; i < n; i += 2) {
        for (size_t j = 1; j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            unsigned char a = map[i - 1][j - 1];
            unsigned char b = map[i - 1][j + 1];
            unsigned char c = map[i + 1][j - 1];
            unsigned char d = map[i + 1][j + 1];
            map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv; // EDIT: <-- thanks! the bug! `map_ij + rv`, not `r`
            else map_ij = 255;
        }
    }

    // Square algorithm
    // 0 1 0
    // 1 0 1
    // 0 1 0
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = (i % 2 == 0); j < n; j += 2) {
            unsigned char& map_ij = map[i][j];

            // get surrounding values
            unsigned char a = 0, b = a, c = a, d = a;
            if (i != 0) a = map[i - 1][j];
            if (j != 0) b = map[i][j - 1];
            if (j + 1 != n) c = map[i][j + 1];
            if (i + 1 != n) d = map[i + 1][j];

            // average calculation
            if (i == 0) map_ij = (b + c + d) / 3;
            else if (j == 0) map_ij = (a + c + d) / 3;
            else if (j + 1 == n) map_ij = (a + b + d) / 3;
            else if (i + 1 == n) map_ij = (a + b + c) / 3;
            else map_ij = (a + b + c + d) / 4;

            unsigned char rv = std::rand() % r;
            if (map_ij + r < 255) map_ij += rv;
            else map_ij = 255;
        }

    }

    return map;
}

Se você tiver outras dicas ou recursos além de http://www.gameprogrammer.com/fractal.html e http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2 para geração de terreno com base em fractal, eu recomendaria aprecie-os como comentários também.

Editar:

MDP

Esta é a nova imagem, conforme sugestão de Fabians (ty), no entanto, ainda possui algumas peculiaridades estranhas, que você poderá ver imediatamente (pequenas 'covinhas' em todos os lugares).

O que poderia estar causando esse comportamento estranho? Código fonte atualizado: http://www.pastie.org/1924223

Editar:

Muito obrigado a Fabian em encontrar o erro de verificação de limites, para os interessados, aqui está a solução atual como 512x512 png. E código fonte atual (modificado por Fabian) . MDP

Editar (anos depois): versão do Python https://gist.github.com/dcousens/5573724#file-mdp-py

deceleratedcaviar
fonte
Nas fotos, parece que cada um dos pontos está na mesma altura. Os cantos estão na mesma altura também?
Deft_code 18/05/11
1
Pelo que vale, suas imagens parecem muito bonitas. :)
ChrisE
scrand (): não tenho certeza absoluta de que entendi - isso deve retornar um caractere assinado no intervalo (-r / 2, r / 2]? As covinhas, para mim, de qualquer maneira, parecem como o resultado As áreas adjacentes parecem repentinamente disparar em preto e voltar ao branco. No geral, também parece haver faixas afiadas, sugerindo novamente que você está transbordando, talvez. precisão mais alta (digamos, número inteiro) e, em seguida, fixando os valores no intervalo [0,256] ou [-128,127]?
ChrisE
O problema foi resolvido abaixo, porque eu estava checando os limites contra o intervalo do valor aleatório, e não seu valor real. O scrand () era uma função temporária de 'ruído' retornando idealmente [-128, 127]
deceleratedcaviar
Ah legal! Fico feliz em saber que está funcionando agora.
19411 ChrisE

Respostas:

12

O algoritmo adiciona recursivamente um valor, mas o valor pode ser positivo ou negativo (normalmente + -1 / (2 ^ oitava))

Se você começar do zero e adicionar apenas valores positivos, poderá subir e é por isso que está vendo os vértices serem abaixados.

tente começar em 127, em vez de zero, para os quatro cantos e também tente caracteres assinados (em seguida, verifique os limites superior e inferior)

EDITAR

então, mais duas coisas precisam mudar no principal (64 >> i) para obter o meio efeito a cada oitava e também a sua função de saída (aquela que mapeia o final [] [] tp o imgdta [], você apenas precisa colocar

imgdta [(i * n) + j] = 128 + final [i] [j];

em vez do bloco if else.

Outra coisa, não sei por que, mas sua verificação de limites está falhando (que são as linhas 38 e 65) se você remover a verificação totalmente, também notará algumas novas bolhas escuras, então eu acho que talvez você precise promover para um tipo maior antes de fazer os limites, verifique se deseja uma imagem mais barulhenta que a imagem "64 / i".

OUTRA EDIÇÃO

acabei de descobrir o que era, você está comparando com 'r', e não 'rv', na verificação de limites. Aqui está o código fixo: http://pastie.org/1927076

Richard Fabian
fonte
Esta foi definitivamente a melhor maneira de fazer isso, mas ainda não há charuto, parece que minha imagem ainda tem algumas 'peculiaridades', atualizei o post original.
Deceleratedcaviar
Não tenho certeza mas a linha 93 looks errado, 64 / i talvez precise ser 64 >> i (como você metade do efeito cada oitava)
Richard Fabian
Ahhh!! Muito obrigado, não acredito nisso, sabia que seria algo estúpido para esse segundo problema. Adorei seu código TGA improvisado, desculpe, eu deveria ter poupado o problema e colocado o cabeçalho.
Deceleratedcaviar
3

Duas coisas que saltam para fora:

  1. Você tem um motivo convincente para fazer isso em ponto fixo? Não há nada errado com isso por si só, e há muitas razões para usá-lo (principalmente os requisitos de memória, se você planeja subir em direção a um mapa ENORME), mas eu definitivamente começaria com uma versão em ponto flutuante do algoritmo e converta-o em ponto fixo depois de ter funcionado; isso deve, se nada mais, eliminar uma fonte plausível de erros (em particular, suspeito que seu grampo possa estar causando problemas e as condições para quando adicionar / subtrair rv).
  2. Embora seja difícil dizer pelo código que vejo, não parece que seu deslocamento aleatório de altura esteja escalando com o nível e que combinado com o problema em (1) pode estar causando alguns dos problemas - você não deve estar deslocando pela mesma quantidade em cada nível.

Ah, e uma coisa não algorítmica: eu recomendo fortemente não fazer alocações na sua função mdp (); passe em duas matrizes diferentes já alocadas e faça a iteração 'in-loco', passando de uma para a outra. Se nada mais, isso permitirá que você faça ping-pong para frente e para trás enquanto faz as camadas, em vez de precisar alocar uma nova matriz a cada intervalo de tempo.

Steven Stadnicki
fonte
Alguns pontos positivos, obviamente, estou apenas tentando corrigir o algoritmo, a implementação está longe do ideal, e nem limpo a memória neste momento: P.
Deceleratedcaviar
Neste ponto, o escalonamento dos passes é de 64 / i, obviamente vou mudar isso mais tarde, mas isso não explica o efeito das covinhas atualmente. : S
deceleratedcaviar
0

Além do acima, no momento você não está excluindo a memória que está alocando. Para remediar isso, altere a linha 104 de:

for (unsigned i = 1; i < 6; ++i) final = mdp(final, n, 64 / i);

para

for (unsigned i = 1; i < 6; ++i) {
  signed char** new_final = mdp(final, n, 64 / i);
  for (unsigned i = 0; i < n; ++i)
    delete[] final[i];
  delete[] final;
  final = new_final;
}

e adicione isso depois de escrever no arquivo tga:

for (unsigned i = 0; i < n; ++i)
  delete[] final[i];
delete[] final;
dma
fonte
Estou muito ciente de como limpar a memória, mas como esse era apenas um protótipo de algoritmo e seria reescrito para usar vetores, eu só queria ter certeza de que estava correto.
Deceleratedcaviar