La salida del algoritmo Diamond-Square es aleatoria y ruidosa

8

He implementado una interpretación aproximada del algoritmo Diamond-Square en C ++ para crear un terreno fractal semi-realista, pero el resultado parece un valor aleatorio y en cada punto en lugar de formas rocosas suaves. He alterado los parámetros, pero siento que una mirada externa al código podría ayudarme a comprender el problema. Aquí hay ejemplos de la salida:

Como un mapa de bits (de arriba hacia abajo) con variación de altura reducida:

Cómo debería verse (esto se carga desde un archivo):

El 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
fuente
1
En el método diamondSquare, el Diamond-Step y el Square-Step parecen operar en las mismas esquinas. Pero en realidad se supone que debes realizar el paso cuadrado cuatro veces, una vez para cada uno de los subcuadrados generados por el paso de diamante anterior. Y luego el paso cuadrado debe hacer lo mismo y realizar cuatro pasos de diamante. Pero hay muchas otras cosas que huelen en ese código, como el bucle for en diamondStep que descarta y reescribe el valor de retorno de la función en cada iteración.
Philipp
44
Cuando implementé DS por primera vez, me aseguré de hacer que el proceso fuera interactivo para poder ver exactamente lo que estaba sucediendo en cada paso, comenzando con las cuatro esquinas de todo el espacio y avanzando en cada iteración posterior. Modificar datos, modificar vértices en consecuencia, enjuagar, repetir. Le sugiero que haga esto, ya que los algoritmos recursivos pueden ser difíciles de seguir.
Ingeniero
¿Cómo decidiste disminuir el tamaño del paso roughness *= 0.75f;?
Roflo
Necesito corregir mi comentario anterior: se supone que solo debes realizar un paso de diamante por cada paso cuadrado, no cuatro . Pero aún se supone que debes realizar cuatro pasos cuadrados después de cada paso de diamante. Esperaría una implementación adecuada para que diamondStep llame a squareStep y luego squareStep llame a diamondStep hasta alcanzar la profundidad de iteración deseada.
Philipp

Respuestas:

1

Creo que generalmente incluirías la altura del punto medio en el escalón cuadrado (y harías primero el escalón del diamante), lo que afectaría ligeramente lo puntiagudo que se ve, lo que lo convierte en una pendiente más gradual. ¿Lo intentaste con el desplazamiento aleatorio disminuido?

También parece que mientras las alturas sean positivas, no hay posibilidad de que el desplazamiento de altura sea negativo, por lo que cuanto más altos sean los puntos, mayor será el desplazamiento, lo que lo hará más puntiagudo.

Hice un programa bastante simple con este algoritmo dando buenos resultados y en lugar de basar el desplazamiento aleatorio en el promedio de las alturas, lo hice afectado por el ancho de cuadrícula actual.

Ben Beazley
fuente
-3

Para corregir la aleatoriedad de altura, puede implementar Ruido Perlin .

La altura de generación se basa en las alturas adyacentes y, por lo tanto, se obtienen resultados muy suaves.

Aquí hay alguna implementación en C ++

Ashe23
fuente
2
Esta no es una respuesta a la pregunta
Bálint
1
Bienvenido a gamedev.SE. Tenga en cuenta que esta es una comunidad de preguntas y respuestas. Solo respondemos preguntas tal como fueron escritas. Esta pregunta es explícitamente sobre un problema con la implementación del algoritmo de diamante cuadrado. "Usar un algoritmo completamente diferente" no es una buena respuesta a esa pregunta.
Philipp
1
El algoritmo Diamond Square y el ruido Perlin son dos algoritmos diferentes para generar ruido coherente. No usarías una para crear la otra.
MichaelHouse