A saída do algoritmo Diamond-Square é aleatória e barulhenta

8

Eu implementei uma interpretação aproximada do algoritmo Diamond-Square em C ++ para criar um terreno fractal semi-realista, mas a saída parece apenas um valor y aleatório em cada ponto, em vez de formas rochosas suaves. Alterei parâmetros, mas sinto que uma análise externa do código pode me ajudar a entender o problema. Aqui estão exemplos da saída:

Como um bitmap (de cima para baixo) com variação de altura reduzida:

Como deve ser (carregado de um arquivo):

O código:

//Diamond-square algorithm
HeightMap::HeightMap(float maxY) {
//type = GL_POINTS; 
//type = GL_LINES;
numVertices = RAW_WIDTH*RAW_HEIGHT; //256^2 squares => 257^2 vertices
numIndices = (RAW_WIDTH - 1)*(RAW_HEIGHT - 1) * 6; //each square is 2 triangles (6 indices)
vertices = new Vector3[numVertices];
textureCoords = new Vector2[numVertices];
indices = new GLuint[numIndices];
colours = new Vector4[numVertices];

int cornerA, cornerB, cornerC, cornerD; //Identify corners
cornerA = 0;
cornerB = RAW_WIDTH - 1;
cornerC = RAW_WIDTH*RAW_HEIGHT - RAW_WIDTH;
cornerD = RAW_WIDTH*RAW_HEIGHT - 1;

//Create vertices
for (int x = 0; x < RAW_WIDTH; ++x) {
    for (int z = 0; z < RAW_HEIGHT; ++z) {
        int offset = (x * RAW_WIDTH) + z;
        float y = 0; //Start with vertices set flat
        if (offset == cornerA ||
            offset == cornerB ||
            offset == cornerC ||
            offset == cornerD) {
            vertices[offset] = Vector3(x * HEIGHTMAP_X, maxY/2, z * HEIGHTMAP_Z); //Initialise corners to mid height
            std::cout << "Corners: " << offset << std::endl;
        }

        if (vertices[offset] == Vector3(0, 0, 0)) {
            vertices[offset] = Vector3(x * HEIGHTMAP_X, y * HEIGHTMAP_Y, z * HEIGHTMAP_Z);
        }
        //  textureCoords[offset] = Vector2(x * HEIGHTMAP_TEX_X, z * HEIGHTMAP_TEX_Z);
    }
}

Vector3 tl, tr, bl, br;
tl = vertices[cornerA];
tr = vertices[cornerB];
bl = vertices[cornerC];
br = vertices[cornerD];

float roughness = 1.0f;

Square square = Square(tl, tr, bl, br);
diamondSquare(vertices, numVertices, square, roughness);

//Colour
for (int x = 0; x < RAW_WIDTH; ++x) {
    for (int z = 0; z < RAW_HEIGHT; ++z) {
        int offset = (x*RAW_WIDTH) + z;
        float shade;
        if (vertices[offset].y > 0) {
            shade = 1 - 1.0f / (vertices[offset].y / maxY * 2);
        }
        else {
            shade = 0.1f;
        }
        colours[offset] = Vector4(shade, shade, shade, 1.0f);
        //Colour any vertex that hasn't been passed over red
        if (vertices[offset].y == maxY / 2 + 100) {
            colours[offset] = Vector4(1, 0, 0, 1);
        }
    }
}

//Create indices
numIndices = 0;
for (int x = 0; x < RAW_WIDTH - 1; ++x) {
    for (int z = 0; z < RAW_HEIGHT - 1; ++z) {
        int a = (x*(RAW_WIDTH)) + z;
        int b = ((x + 1)*(RAW_WIDTH)) + z;
        int c = ((x + 1)*(RAW_WIDTH)) + (z + 1);
        int d = (x*(RAW_WIDTH)) + (z + 1);

        indices[numIndices++] = c;
        indices[numIndices++] = b;
        indices[numIndices++] = a;
        indices[numIndices++] = a;
        indices[numIndices++] = d;
        indices[numIndices++] = c;

    }
}
BufferData();

}

void HeightMap::squareStep(Vector3 vertices[], int len, Vector3 tl, Vector3 tr, Vector3 bl, Vector3 br, float mid, float roughness) {
for (int i = 0; i < len; i++) {
    Vector3 top = (tl + tr) / 2;
    Vector3 bot = (bl + br) / 2;
    Vector3 left = (tl + bl) / 2;
    Vector3 right = (tr + br) / 2;
    top.y = 0;
    bot.y = 0;
    left.y = 0;
    right.y = 0;
    if (vertices[i] == top ||
        vertices[i] == bot ||
        vertices[i] == left ||
        vertices[i] == right) {
        float y = rand() % (int)(mid/5);
        y *= roughness;
        vertices[i] = Vector3(vertices[i].x, mid + y, vertices[i].z); //Set Diamond centre points to mid height + rand
        std::cout << "Square: " << vertices[i];
    }
}

}

float HeightMap::diamondStep(Vector3 vertices[], int len, Vector3 tl, Vector3 tr, Vector3 bl, Vector3 br, float roughness) {
float avg;
float y;
    for (int i = 0; i < len; i++) {
        Vector3 corners = (tl + tr + bl + br) / 4;
        avg = corners.y;
        y = rand() % (int)(avg/5);
        y *= roughness;
        corners.y = 0;
        if (vertices[i] == corners) {
            vertices[i] = Vector3(vertices[i].x, avg + y, vertices[i].z);         //Set Square centre point to avg height of corners + rand
            std::cout << "Diamond: " << vertices[i];
        }
    }
return avg + y;

}

void HeightMap::diamondSquare(Vector3 vertices[], int numVertices, Square s, float roughness) {
Vector3 tl = s.tl;
Vector3 tr = s.tr;
Vector3 bl = s.bl;
Vector3 br = s.br;
float mid = diamondStep(vertices, numVertices, tl, tr, bl, br, roughness);
squareStep(vertices, numVertices, tl, tr, bl, br, mid, roughness);
roughness *= 0.75f;
if (s.width > 2 * HEIGHTMAP_X) {
    std::vector<Square> squares = s.split();
    for (int i = 0; i < 4; i++) {
        diamondSquare(vertices, numVertices, squares[i], roughness);
    }
}

}

Joe Parker
fonte
11
No método diamondSquare, o diamante-passo e o quadrado-passo parecem operar nos mesmos cantos. Mas, na verdade, você deve executar o passo quadrado quatro vezes, uma vez para cada um dos sub-quadrados gerados pelo passo anterior do diamante. E então a etapa quadrada deve fazer o mesmo e executar quatro etapas em losango. Mas existem muitas outras coisas que cheiram nesse código, como o loop for no diamondStep, que descarta e reescreve o valor de retorno da função em todas as iterações.
Philipp
4
Quando implementei o DS pela primeira vez, certifiquei-me de tornar o processo interativo para que eu pudesse ver exatamente o que estava acontecendo em cada etapa, começando pelos quatro cantos de todo o espaço e trabalhando em cada iteração subsequente. Modifique os dados, modifique os vértices de acordo, enxague e repita. Eu sugiro que você faça isso, pois algoritmos recursivos podem ser difíceis de acompanhar.
Engenheiro
Como você decidiu diminuir o tamanho da etapa roughness *= 0.75f;?
Roflo
Preciso corrigir meu comentário anterior: você deve executar apenas uma etapa de diamante para cada etapa quadrada, não quatro . Mas você ainda deve executar quatro etapas quadradas após cada etapa de diamante. Eu esperaria que uma implementação adequada fizesse com que diamondStep chame squareStep e squareStep chame diamondStep até que a profundidade de iteração desejada seja atingida.
Philipp

Respostas:

1

Eu acho que geralmente você incluiria a altura do ponto do meio no degrau quadrado (e faria o diamante primeiro. O que) afetaria levemente a aparência espetada, tornando-o uma inclinação mais gradual. Você tentou com o deslocamento aleatório diminuído?

Parece também que, enquanto as alturas forem positivas, não há chance de o deslocamento da altura ser negativo; portanto, quanto mais altos os pontos, maior o deslocamento, tornando-o mais espetado.

Eu criei um programa bastante simples com esse algoritmo, fornecendo bons resultados e, em vez de basear o deslocamento aleatório na média das alturas, o tornei afetado pela largura de grade atual.

Ben Beazley
fonte
-3

Para corrigir a aleatoriedade da altura, você pode implementar o Perlin Noise .

Qual altura de geração com base nas alturas adjecent e, assim, você obteve resultados muito suaves.

Aqui está alguma implementação em C ++

Ashe23
fonte
2
Esta não é uma resposta para a pergunta
Bálint
11
Bem-vindo ao gamedev.SE. Observe que esta é uma comunidade de perguntas e respostas. Nós apenas respondemos às perguntas como elas foram escritas. Esta pergunta está explicitamente perguntando sobre um problema na implementação do algoritmo de diamante-quadrado. "Usar um algoritmo completamente diferente" não é uma boa resposta para essa pergunta.
Philipp
11
O algoritmo Diamond Square e o Perlin Noise são dois algoritmos diferentes para gerar ruído coerente. Você não usaria um para criar o outro.
MichaelHouse