La sortie de l'algorithme Diamond-Square est aléatoire et bruyante

8

J'ai implémenté une interprétation approximative de l' algorithme Diamond-Square en C ++ pour créer un terrain fractal semi-réaliste, mais la sortie semble être une valeur y aléatoire à chaque point plutôt que des formes rocheuses lisses. J'ai modifié des paramètres, mais j'ai l'impression qu'un examen extérieur du code pourrait m'aider à comprendre le problème. Voici des exemples de sortie:

En tant que bitmap (de haut en bas) avec variation de hauteur réduite:

À quoi cela devrait ressembler (il est chargé à partir d'un fichier):

Le code:

//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
la source
1
Dans la méthode diamondSquare, le diamond-step et le square-step semblent opérer sur les mêmes coins. Mais en réalité, vous êtes censé effectuer le carré à quatre reprises, une fois pour chacun des sous-carrés générés par le diamant précédent. Et puis, le carré doit faire de même et effectuer quatre pas de diamant. Mais il y a beaucoup d'autres choses qui sentent dans ce code, comme la boucle for dans diamondStep qui rejette et réécrit la valeur de retour de la fonction à chaque itération.
Philipp
4
Lorsque j'ai implémenté DS pour la première fois, je me suis assuré de rendre le processus interactif afin que je puisse voir exactement ce qui se passait à chaque étape, en commençant par les quatre coins de l'espace entier et en progressant à chaque itération suivante. Modifiez les données, modifiez les sommets en conséquence, rincez, répétez. Je vous suggère de le faire, car les algorithmes récursifs peuvent être difficiles à suivre autrement.
Ingénieur
Comment avez-vous décidé de diminuer la taille du pas roughness *= 0.75f;?
Roflo
Je dois corriger mon commentaire précédent: vous n'êtes censé effectuer qu'un pas de diamant pour chaque pas carré, pas quatre . Mais vous êtes toujours censé effectuer quatre pas carrés après chaque pas de diamant. Je m'attendrais à une implémentation appropriée pour que diamondStep appelle squareStep, puis squareStep appelle diamondStep jusqu'à ce que la profondeur d'itération souhaitée soit atteinte.
Philipp

Réponses:

1

Je pense qu'en général, vous incluriez la hauteur du point central dans l'étape carrée (et faites d'abord l'étape de diamant. Qui) affecterait légèrement la façon dont elle semble épineuse, ce qui en fait une pente plus progressive. L'avez-vous essayé avec le décalage aléatoire diminué?

Il semble également que tant que les hauteurs sont positives, il n'y a aucune chance que le décalage de hauteur soit négatif, donc plus les points sont élevés, plus le décalage est élevé, ce qui le rend plus épineux.

J'ai fait un programme assez simple avec cet algoritihm donnant des résultats corrects et au lieu de baser le décalage aléatoire sur la moyenne des hauteurs, je l'ai rendu affecté par la largeur de grille actuelle.

Ben Beazley
la source
-3

Pour corriger l'aléatoire de la hauteur, vous pouvez implémenter Perlin Noise .

Quelle hauteur de génération basée sur les hauteurs ajustées et donc vous avez obtenu des résultats très lisses.

Voici quelques implémentations sur C ++

Ashe23
la source
2
Ce n'est pas une réponse à la question
Bálint
1
Bienvenue sur gamedev.SE. Veuillez noter qu'il s'agit d'une communauté de questions et réponses. Nous répondons uniquement aux questions telles qu'elles ont été écrites. Cette question pose explicitement un problème avec l'implémentation de l'algorithme du carré de diamant. "Utiliser un algorithme complètement différent" n'est pas une bonne réponse à une telle question.
Philipp
1
L'algorithme Diamond Square et Perlin Noise sont deux algorithmes différents pour générer un bruit cohérent. Vous n'utiliseriez pas l'un pour créer l'autre.
MichaelHouse