[OpenGL] 随机分形地形生成

reference : 《随机分形地形生成及其浏览》

* 本项目属于游戏程序设计5000行计划

        算法实现起来很简单，分形也很有意思，我们假设我们越靠近一个物体，它的细节就会显示出来，那么对于具有分形特性的物体而言，我们看到的细节和整体并没有什么区别。正如我们不断zoom in观察这个 Koch 雪花，每个突出的角又能长出三个角，如此递归，永无止境……

       

        地形也有这样的特性，对于两张不同尺度上的地形俯拍图，我们看到的细节也是类似的，也就是说，对于下图中的蓝色区域的地面，我们截取两个不同大小的橙色框所得到的图片，在人眼看来是差不多的。

        

        利用这样的特性，我们就可以用分形的思想来生成随机地形。

        具体的算法在开头给出的论文已经说的非常明白了，虽然这个论文并不是该算法(diamand - square algorithm)的最早版本，但中文看起来比英文要好理解一些。在这里只给出一些概述。

        一维分形地形

       类似于二分法，取线段中点，使y值为线段两段的平均值加上一个随机数，得到两条线段，再分别取两个线段的中点，重复前面的过程。

       二维分形地形

       

        由一维扩展而成，利用已知的a,b,c,d高度值，计算e,h,f,g, 设r为随机数（r随着迭代的次数，取值范围不断缩小）其中

        h(e) = (h(a) + h(b)) / 2 + r(e)

        h(f) = (h(b) + h(c)) / 2 + r(f)

        h(g) = (h(c) + h(d)) / 2 + r(g)

        h(h) = (h(a) + h(d)) / 2 + r(h)

        然后利用e,f,g,h,计算m

        h(m) = (h(e) + h(f) + h(g) + h(h))/4 + r(m)

        如此得到一次递归流程，然后再对四个正方形进行同样的操作……

        Diamand - Square 算法

       同样适用于二维，但是对上述算法的改进。

       

        上图反映的是两次递归过程，以下只描述一次递归中做的事情。

         先计算h(E) = (h(A) + h(B) + h(C) + h(D)) / 4 + r（E）

         再计算：

         h(F) = (h(A) + h(B) + h(E) + h(E)) / 4 + r(F)

         h(I) = (h(A) + h(C) + h(E) + h(E)) / 4 + r(I)

         h(S) = (h(B) + h(D) + h(E) + h(E)) / 4 + r(S)

         h(H) = (h(C) + h(D) + h(E) + h(E)) / 4 + r(H)

         然后再对新的四个正方形做同样的操作。

fractal.h

#pragma once class fractal { private: enum { MAX = 10000 }; float roughness; int times; int height; float minHeight; float maxHeight; int n; int D; int indiceNum; float** data; float* vertex; int* indice; float step; void genIndice(); void chooseColor(float height); public: void draw(); void calculate(); fractal(int _height, int _times, float _step, int D,int seed); }; fractal.cpp

#include <time.h>   #include <math.h>   #include <stdlib.h>   #include <iostream> #include "fractal.h"   #include "gl/glut.h" using namespace std; // height : 值越大，地形起伏越大 // times : 迭代次数，次数越多，tire越多 // step : 绘制时一个网格的程度 // D : 随机数衰减因子，越大随机数随迭代的取值越小 // seed : 随机数种子 fractal::fractal(int _height, int _times, float _step, int _D,int seed) { srand(seed); step = _step; times = _times; height = _height; D = _D; n = pow(2, times) + 1; indiceNum = 6 * (n - 1)*(n - 1); vertex = new float[3 * n*n]; indice = new int[indiceNum]; data = new float*[n]; for (int i = 0; i < n; i++) { data[i] = new float[n]; for (int j = 0; j < n; j++) { data[i][j] = 0; } } } // 生成顶点索引数据 void fractal::genIndice() { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1; j++) { indice[3 * ((n - 1) * i + j)] = (n * i + j); indice[3 * ((n - 1) * i + j) + 1] = (n * i + j + 1); indice[3 * ((n - 1) * i + j) + 2] = (n * (i + 1) + j + 1); } } cout << endl; int off = 3 * (n - 1)*(n - 1); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1; j++) { indice[off + 3 * ((n - 1) * i + j)] = (n * i + j); indice[off + 3 * ((n - 1) * i + j) + 1] = (n * (i + 1) + j); indice[off + 3 * ((n - 1)* i + j) + 2] = (n * (i + 1) + j + 1); } } } // 生成[-num,num]之间的随机数 static float randnum(float num) { float max = num; float min = -num; int r; float x; r = rand(); x = (float)(r & 0x7fff) / (float)0x7fff; return (x * (max - min) + min); } // 计算顶点高度 void fractal::calculate() { int size = n - 1; int number = 1; int ratio = pow(2, D); roughness = height; //times为迭代次数 for (int t = 0; t < times; t++) { // diamand阶段 for (int i = 0; i < number; i++) { for (int j = 0; j < number; j++) { float r = randnum(.5) * roughness; int center_x = (size >> 1) + size * i; int center_y = (size >> 1) + size * j; data[center_x][center_y] = (data[size * i][size * j] + data[size*i + size][size * j] + data[size * i][size * j + size] + data[size * i + size][size * j + size]) / 4 + r; } } // square阶段 int pointNum = ((t + 1) << 1) + 1; int pointStep = (n - 1) / (pointNum - 1); for (int i = 0; i < pointNum; i++) { for (int j = 0; j < pointNum; j++) { if ((i + j) % 2 == 1){ float r = randnum(.5) * roughness; if (i == 0){ data[i*pointStep][j*pointStep] = (data[n - pointStep][j*pointStep] + data[(i + 1)*pointStep][j*pointStep] + data[i*pointStep][(j + 1)*pointStep] + data[i*pointStep][(j-1)*pointStep]) / 4 + r; } else if (j == 0){ data[i*pointStep][j*pointStep] = (data[(i-1)*pointStep][j*pointStep] + data[(i + 1)*pointStep][j*pointStep] + data[i*pointStep][(j + 1)*pointStep] + data[i*pointStep][n - pointStep]) / 4 + r; } else if (i == pointNum - 1){ data[i*pointStep][j*pointStep] = (data[pointStep][j*pointStep] + data[(i - 1)*pointStep][j*pointStep] + data[i*pointStep][(j + 1)*pointStep] + data[i*pointStep][(j - 1)*pointStep]) / 4 + r; } else if (j == pointNum - 1){ data[i*pointStep][j*pointStep] = (data[(i-1)*pointStep][j*pointStep] + data[(i + 1)*pointStep][j*pointStep] + data[i*pointStep][pointStep] + data[i*pointStep][(j - 1)*pointStep]) / 4 + r; } else { data[i*pointStep][j*pointStep] = (data[(i - 1)*pointStep][j*pointStep] + data[(i + 1)*pointStep][j*pointStep] + data[i*pointStep][(j + 1)*pointStep] + data[i*pointStep][(j - 1)*pointStep]) / 4 + r; } } } } roughness = roughness / ratio; size >>= 1; number <<= 1; } // 把data映射到vertex数据上，并删除data,同时计算出最大高度和最小高度 minHeight = 10000; maxHeight = -10000; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { vertex[3 * (i*n + j)] = i* step - n*step / 2; vertex[3 * (i*n + j) + 1] = data[i][j]; vertex[3 * (i*n + j) + 2] = j*step - n*step / 2; if (maxHeight < data[i][j]) { maxHeight = data[i][j]; } if (minHeight > data[i][j]) { minHeight = data[i][j]; } } delete[] data[i]; } delete[] data; // 生成索引 genIndice(); } // 根据高度选择颜色 void fractal::chooseColor(float height) { const GLfloat blue[] = { 1.0 * 65 / 255, 1.0 * 127 / 255, 1.0 * 219 / 255 }; const GLfloat green[] = { 1.0 * 73 / 255, 1.0 * 161 / 255, 1.0 * 101 / 255 }; const GLfloat yellow[] = { 1.0 * 172 / 255, 1.0 * 189 / 255, 1.0 * 117 / 255 }; const GLfloat brown[] = { 1.0 * 153 / 255, 1.0 * 123 / 255, 1.0 * 46 / 255 }; float interval = maxHeight - minHeight; if (height < minHeight + interval / 4){ glColor3fv(blue); } else if (height < minHeight + interval / 2){ glColor3fv(green); } else if (height < minHeight + 3 * interval / 4){ glColor3fv(yellow); } else if (height < maxHeight) { glColor3fv(brown); } } void fractal::draw() { glPushMatrix(); glBegin(GL_TRIANGLES); for (int i = 0; i < indiceNum / 3; i++) { chooseColor(vertex[3 * indice[3 * i] + 1]); glVertex3f(vertex[3 * indice[3 * i]], vertex[3 * indice[3 * i] + 1], vertex[3 * indice[3 * i] + 2]); chooseColor(vertex[3 * indice[3 * i + 1] + 1]); glVertex3f(vertex[3 * indice[3 * i + 1]], vertex[3 * indice[3 * i + 1] + 1], vertex[3 * indice[3 * i + 1] + 2]); chooseColor(vertex[3 * indice[3 * i + 2] + 1]); glVertex3f(vertex[3 * indice[3 * i + 2]], vertex[3 * indice[3 * i + 2] + 1], vertex[3 * indice[3 * i + 2] + 2]); } glColor3f(1,1,1); glEnd(); glPopMatrix(); } main.cpp

#define _CRT_SECURE_NO_WARNINGS #include <stdlib.h> #include<time.h> #include"fractal.h" #include"texture.h" fractal* f; float center[] = { 0, 0, 0 }; float eye[] = { 0, 0, 20 }; float tx, ty = 10, ax, ay=10, mx, my, zoom = 0; bool isLine = false; bool isDown = false; void reshape(int width, int height) { if (height == 0) { height = 1; } glViewport(0, 0, width, height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); float whRatio = (GLfloat)width / (GLfloat)height; gluPerspective(45, whRatio, 1, 500); glMatrixMode(GL_MODELVIEW); } void idle() { glutPostRedisplay(); } void init(void) { glClearColor(1.0, 0.0, 0.0, 0.0); glShadeModel(GL_SMOOTH); glEnable(GL_DEPTH_TEST); glColor4f(1.0, 1.0, 1.0, 1.0f); glBlendFunc(GL_SRC_ALPHA, GL_ONE); glEnable(GL_COLOR_MATERIAL); glColorMaterial(GL_FRONT, GL_AMBIENT_AND_DIFFUSE); // height : 值越大，地形起伏越大 // times : 迭代次数，次数越多，tire越多 // step : 绘制时一个网格的程度 // D : 随机数衰减因子，越大随机数随迭代的取值越小（大于1） // seed : 随机数种子 f = new fractal(5, 3, 2, 2, 23); f->calculate(); } void redraw() { glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glClearColor(0, 0, 0, 1); glMatrixMode(GL_MODELVIEW); glLoadIdentity(); gluLookAt(eye[0], eye[1], eye[2], center[0], center[1], center[2], 0, 1, 0); if(isLine)glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); else glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); glTranslatef(tx,ty,zoom); glRotatef(ax, 1.0f, 0.0f, 0.0f); glRotatef(ay, 0.0f, 1.0f, 0.0f); glPushMatrix(); glTranslatef(0, -roomSizeY / 2,0); f->draw(); glPopMatrix(); glutSwapBuffers(); } void myMouse(int button, int state, int x, int y) { if (button == GLUT_LEFT_BUTTON) { if (state == GLUT_DOWN) { isDown = true; mx = x; my = y; } else if (state == GLUT_UP) { isDown = false; } } glutPostRedisplay(); } void mouseMotion(int x, int y) { if (isDown) { ax += 1.0f*(y - my) / 10.0f; ay += 1.0f*(x - mx) / 10.0f; mx = x; my = y; } glutPostRedisplay(); } void myKeyboard(unsigned char key, int x, int y) { switch (key) { case 'a': { //左移 tx -= 1; break; } case 'd': { //右移 tx += 1; break; } case 'w': { //上移 ty += 1; break; } case 's': { //下移 ty -= 1; break; } case 'z': { //后移 zoom += 1; break; } case 'c': { //前移 zoom -= 1; break; } case 'p': { // 切换绘制模式 if (isLine) { isLine = false; } else isLine = true; } } glutPostRedisplay(); } int main(int argc, char *argv[]) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGBA | GLUT_DEPTH | GLUT_DOUBLE); glutInitWindowSize(800, 600); int windowHandle = glutCreateWindow("Simple GLUT App"); glutDisplayFunc(redraw); glutReshapeFunc(reshape); glutMouseFunc(myMouse); glutMotionFunc(mouseMotion); glutKeyboardFunc(myKeyboard); glutIdleFunc(idle); init(); glutMainLoop(); system("pause"); return 0; }