[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;
}