Трехмерный фрактал - губка Менгера

Губка Менгера

Задача: построить фрактал, 3D-губка Менгера(ковер Серпинского в 3D).
Использованный API: OpenGL, GLUT.
Среда разработки: XCode(MacOS X), Code::Blocks(Linux & Windows)
Компилятор: GCC v4

Построение губки Менгера
Куб с ребром 1 делится плоскостями, параллельными его граням, на 27 равных кубов. Из куба удаляются центральный куб и все прилежащие к нему по двумерным граням кубы этого подразделения. Получается множество K1, состоящее из 20 оставшихся замкнутых кубов «первого ранга». Поступая точно так же с каждым из кубов первого ранга, получим множество K2, состоящее из 400 кубов второго ранга. Продолжая этот процесс бесконечно, получим бесконечную последовательность пересечение членов которой есть губка Менгера.

В программе куб строится рекурсивной функцией.

Алгоритм построения в программе:
1. Разбиваем куб на 27 частей
2. Тремя циклами (по x, y, z) перебираем все получившиеся кубы.
3. Проверяем необходимо ли изображать данный куб.
4. Если необходимо, проверяем достигли ли заданного уровня вложенности.
5. Если достигли - рисуем куб.
6. Если не достигли - рекурсивно вызываем эту же функцию, увеличивая уровень вложенности.

Таким образом, в результате работы этой рекурсивной функции на экране изображается губка Менгера.

Для вывода изображения на экран используется кроссплатформенная бибилиотека 3D графики OpenGL. Для построения оконного интерфейса используется уиверсальная библиотека GLUT.

Клавиши управления программой:

r : Автовращение
ESC : Выход
+/= : Увеличить уровень вложенности куба (до 7)
-/_: Уменьшить уровень вложенности куба (до 0)
i : Инверсия
w : Приблизить по Z
s : Отдалить по Z
left : вращение по часовой стрелке по y
right: вращение против часовой стрелки по y
up : Вращение по часовой стрелке(вверх) по х
down : Вращение против часовой стрелки(вниз) по х

/*
 *  main.c
 *  menger
 *
 *  Created by Egor Popovich on 26.02.10.
 *  Copyright 2010. All rights reserved.
 *
 */
 
#if defined(__APPLE__) || defined(MACOSX)
#include <GLUT/glut.h>
#else
#include <GL/glut.h>
#endif
#include <time.h>
#include <math.h>
#include <stdlib.h>
 
//Объявим логический тип bool
typedef enum{false,true} bool;
 
//Ограничение на максимальный уровень вложенности
#define MAX_SUBDIVISION 7
 
//Глобальные переменные
 
//Положение камеры
GLfloat eye[3] = { 0, 0, 9.0 };
//Положение центра экрана
GLfloat center[3] = {0, 0, -1 };
//Координаты вектора задающего поворот сцены
GLfloat up[3] = { 0, 1, 0};
//Положение освещения
GLfloat light0Pos[4] = { 10, 10, 100, 1 };
//Передний и задний план
GLfloat planes[2] = {1, 1000};
//Ширина и высота
int width= 640, height=480;
//Флаг отвечающий за автоматическое вращение
bool autoRotate = false;
//Переменная для сохранения предыдущего времени вызова
unsigned long last_idle_time;
//Массив углов поворота текущего положения куба
GLfloat rot[3] = { 15.0, 45.0, 15.0 };
//Текущий уровень вложенности куба
int subdivisions = 0;
//Флаг отвечающий за инвертирование.
bool invert = false;
//Состояние кнопок мыши
bool mouseButtonDown[3] = { false };
//Координаты щелчка мышью
int mouseButtonClick[3][2] = { { 0, 0 }, {0, 0}, {0, 0} };
 
//-----------------------------------------------------
//Рисование
//-----------------------------------------------------
 
/**
 * DrawCubeFace
 * Рисует один квадратный полигон заданных размеров, заданного цвета,
 * и с заданным параметром отражения
 **/
void DrawCubeFace(GLfloat size, GLfloat* color, GLfloat* specular)
{
	size /= 2.0;
	//Начинаем рисование в режиме четырехугольников
	glBegin(GL_QUADS);
	//Задаем коеффициент рассеивания света грани
	glMaterialfv(GL_FRONT, GL_DIFFUSE, color);
	//Задаем коеффициент отражения света грани
	glMaterialfv(GL_FRONT, GL_SPECULAR, specular);
	//Задаем цвет грани
	glColor3fv(color);
	//Рисуем прямоугольник по точкам
	glVertex3f(-size,-size,size);
	glVertex3f(size,-size,size);
	glVertex3f(size,size,size);
	glVertex3f(-size,size,size);
	//Заканчиваем рисование
	glEnd();
}
 
/**
 * DrawCube
 * Рисует куб заданных размеров
 **/
void DrawCube(GLfloat size)
{
	//Зададим цвета граней(red, green, blue, yellow, cyan, magenta)
	float colors[6][4] = { 
		{ 1.0, 0.0, 0.0, 1.0 },
		{ 0.0, 1.0, 0.0, 1.0 },
		{ 0.0, 0.0, 1.0, 1.0 },
		{ 0.0, 1.0, 1.0, 1.0 },
		{ 1.0, 0.0, 1.0, 1.0 },
		{ 1.0, 1.0, 0.0, 1.0 }
	};
	//Зададим коеффициент отражения
	float glSpecular[4] = { 0.0, 0.0, 0.0, 0.0 };
	//Сохраняем матрицу
	glPushMatrix();
	//Переменная-счетчик, будет увеличиватся для выбора цвета
	int c = 0;
	//Рисуем поверхность, поворачиваем, рисуем следующую..
	DrawCubeFace(size, colors[c++], glSpecular);
	glRotatef(90, 1, 0, 0);
	DrawCubeFace(size, colors[c++], glSpecular);
	glRotatef(90, 1, 0, 0);
	DrawCubeFace(size, colors[c++], glSpecular);
	glRotatef(90, 1, 0, 0);
	DrawCubeFace(size, colors[c++], glSpecular);
	glRotatef(90, 0, 1, 0);
	DrawCubeFace(size, colors[c++], glSpecular);
	glRotatef(180, 0, 1, 0);
	DrawCubeFace(size, colors[c++], glSpecular);
	//Возвращаем матрицу
	glPopMatrix();
}
 
 
/**
 * BuildSponge
 * Это рекурсивная функция, которая вызывает себя для каждого подкуба.
 * Вызывает себя пока step>0, иначе рисует куб.
 **/
void BuildSponge(GLfloat size, int step)
{
	int x,y,z;
	//Сохраняем матрицу
	glPushMatrix();
	//Проверяем уровень вложенности
	if(step > 0) {
		//Если больше 0, то нужно делить куб на части
		//Делим текущий размер на 3
		GLfloat delta = size/3.0;
 
		//Обычный куб
		//Нижняя сторона
		//{-1, -1, -1} {0, -1, -1} {1, -1, -1}	задняя часть
		//{-1, -1, 0}				{1, -1, 0}	середина
		//{-1, -1, 1} {0, -1, 1} {1, -1, 1}		передняя часть
 
		//Середина
		//{-1, 0, -1}		{1, 0, -1}			задняя часть
		//										середина
		//{-1, 0, 1}		{1, 0, 1}			передняя часть
 
		//Верхняя сторона
		//{-1, 1, -1} {0, 1, -1} {1, 1, -1}		задняя часть
		//{-1, 1, 0}			{1, -1, 0}		середина
		//{-1, 1, 1} {0, 1, 1} {1, 1, 1}		передняя часть
		//
		//Инвертированный куб
		//Нижняя сторона y=-1
		//										задняя часть z=-1
		//			{0, -1, 0}					середина z=0
		//										передняя часть z=1
		//Середина y=0
		//			{0, 0, -1}					задняя часть z=-1
		//{-1, 0, 0} {0, 0, 0} {1, 0, 0}		середина z=0
		//			{0, 0, 1}					передняя часть z=1
		//Верхняя сторона y=1
		//										задняя часть z=-1
		//			{0, 1, 0}					середина z=0
		//										передняя часть z=1
 
		//Цикл по сторонам
		for(y = -1; y <= 1; y++) {
			//Цикл из задней части к передней
			for(z=-1; z <= 1; z++) {
				//Цикл с лева на право
				for(x=-1; x <= 1; x++) {
					//Проверяем нужно ли рисовать. Два больших условия которые проверяют
					//для инвертированного и неинвертированного куба, если рисовать не нужно
					//переходим на следующий шаг цикла
					if(!invert){
						if((z == 0 && x == 0) || (y == 0 && (x == 0 || z == 0))) continue;
					} else {
						if((y!=0 && z!=0) || (y!=0 && z==0 && x!=0) || (y==0 && z!=0 && x!=0)) continue;
					}
					//Сохраняем текущую матрицу
					glPushMatrix();
					//Переносим систему координат для подкуба
					glTranslatef(x*delta,y*delta,z*delta);
					//Рекурсивно вызываем для следующего шага 
					BuildSponge(delta,step-1);
					//Возвращаем матрицу
					glPopMatrix();
				}
			}
		}
	} else {
		//Если шаг = 0, значит вложений больше нет, просто рисуем куб
		DrawCube(size);
	}
	//Возвращаем матрицу
	glPopMatrix();
}
 
 
/**
 * RenderObject
 * Инициализирует данные, необходимые для вызова функции рисования
 **/
void RenderObject()
{
	//Сохраняем матрицу
	glPushMatrix();
	//Рисуем губку максимального размера 4.0 и заданным уровнем вложенности
	BuildSponge(4.0, subdivisions);
	//Возвращаем сохраненную матрицу
	glPopMatrix();
}
 
 
//-----------------------------------------------------
//Функции отвечающие за события.
//-----------------------------------------------------
 
 
/**
 * ReshapeCallback
 * Вызывается GLUT при изменении размера окна
 * 
 * 
 **/
 
void ReshapeCallback(GLint iWidth, GLint iHeight) {	
	//Увеличиваем размер области просмотра
	glViewport(0, 0, iWidth, iHeight);
	//Загружаем поективную матрицу
	glMatrixMode(GL_PROJECTION);
	//Делаем ее единичной
	glLoadIdentity();
	//Задаем перспективу
	gluPerspective(45.0, (float)iWidth/iHeight, planes[0], planes[1]);
	//Загружаем объектно-видовую матрицу
	glMatrixMode(GL_MODELVIEW);
	//Обновляем переменные
	width = iWidth;
	height = iHeight;
}
 
/**
 * DisplayCallback
 * Вызывается GLUT для отрисовки экрана
 * Данная функция устанавливает камеру и поворачивает сцену
 * по данным из массива rot[]
 **/
void DisplayCallback()
{
	//Очищаем изображение
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	//Загружаем единичную матрицу
	glLoadIdentity();
	//Переводим внешнюю систему координат в систему координат камеры 
	gluLookAt(eye[0], eye[1], eye[2], center[0], center[1], center[2], up[0], up[1], up[2]);
	//Добавляем освещение
	glLightfv(GL_LIGHT0, GL_POSITION, light0Pos);
	//Поворачиваем сцену по данным из rot[] 
	glRotatef(rot[0], 1, 0, 0);
	glRotatef(rot[1], 0, 1, 0);
	glRotatef(rot[2], 0, 0, 1);
	//Вызываем рисование фрактала
	RenderObject();
	//Переключаем буффер (двойная буфферизация)
	glutSwapBuffers();
}
 
/**
 * Animate
 * Если установлен флаг autoRotate и с предыдущего выщова прошло более
 * 15 миллисекнуд, тогда поворачиваем картину на 1.0
 *  и перерисовываем
 **/
void Animate()
{
	if(autoRotate) {
		int i;
		float dt;
		//Получаем текущее время
		unsigned long time_now = clock(); 
		//Вычисляем промежуток времени от предыдущего вызова
		dt = (float)(time_now - last_idle_time);
		//Если больше 25мс значит нужно повернуть и перерисовать
		if(dt/CLOCKS_PER_SEC >= 0.025) {
			//Увеличиваем градус поворота для 3-х осей
			for(i = 0; i < 3; i++)
				rot[i] = fmod(rot[i]+1.0f, 360.0f);
			//Сохраняем текущее время
			last_idle_time = time_now;
			//Даем сигнал на перерисовку
			glutPostRedisplay();
		}
	}
}
 
/**
 * KeyboardCallback
 * Вызывается при нажатии на клавишу
 * r	: Автовращение
 * ESC	: Выход
 * +/=	: Увеличить уровень (до 7)
 * -/_	: Уменьшить уровень (до 0)
 * i	: Инверсия
 * w	: Приблизить по Z
 * s	: Отдалить по Z
 */
void KeyboardCallback(unsigned char k, GLint x, GLint y)
{
	if(k == 'r')
		autoRotate = !autoRotate;
	else if (k == 27)
		exit(0);
	else {
		switch(k) {
			case '+':
			case '=':
				if(subdivisions < MAX_SUBDIVISION)
					subdivisions += 1;
				break;
			case '-':
			case '_':
				if(subdivisions > 0)
					subdivisions -= 1;
				break;
			case 'i':
				invert = !invert;
				break;
			case 'w':
				eye[2] -= 0.5f;
				break;
			case 's':
				eye[2] += 0.5f;
				break;
		}
		//Даем сигнал на перерисовку
		glutPostRedisplay();
	}
}
 
/**
 * SpecialKeyboardCallback
 * Вызывается при нажатии стрелок
 * left	: вращение по часовой стрелке по y
 * right: вращение против часовой стрелки по y
 * up	: Вращение по часовой стрелке(вверх) по х
 * down	: Вращение против часовой стрелки(вниз) по х
 **/
void SpecialKeyboardCallback(GLint key, GLint x, GLint y)
{
	GLfloat delta = 2.5f;
	switch(key) {
		case GLUT_KEY_LEFT:
			autoRotate = false;
			rot[1] = fmod(rot[1]-delta, 360.0f);
			glutPostRedisplay();
			break;
		case GLUT_KEY_RIGHT:
			autoRotate = false;
			rot[1] = fmod(rot[1]+delta, 360.0f);
			glutPostRedisplay();
			break;
		case GLUT_KEY_UP:
			autoRotate = false;
			rot[0] = fmod(rot[0]+delta, 360.0f);
			glutPostRedisplay();
			break;
		case GLUT_KEY_DOWN:
			autoRotate = false;
			rot[0] = fmod(rot[0]-delta, 360.0f);
			glutPostRedisplay();
			break;
	}
}
 
/**
 * MouseButtonCallback
 * Вызывается при щелчке мышью по экрану
 * Записываем нажатие и его координаты в массив
 **/
void MouseButtonCallback(GLint button, GLint state, GLint x, GLint y)
{
	mouseButtonDown[button] = (state == GLUT_DOWN);
	mouseButtonClick[button][0] = x;
	mouseButtonClick[button][1] = y;
}
 
/**
 * MouseMotionCallback
 * Вызывается при передвижении мыши.
 **/
void MouseMotionCallback(GLint x, GLint y)
{
	//Если левая кнопка нажата
	if(mouseButtonDown[0]) {
		//Рассчитываем процент смещения от начальной точки клика
		float percentX = (float)(mouseButtonClick[0][0]-x)/(width/2.0),
		percentY = (float)(mouseButtonClick[0][1]-y)/(height/2.0);
		//Изменяем координаты вектора вращения
		rot[1] = -percentX*360.0f;
		rot[0] = -percentY*360.0f;
		//Выключаем автовращение
		autoRotate = false;
		glutPostRedisplay();
	}
}
 
//-----------------------------------------------------
//Main. Инициализация GLUT.
//-----------------------------------------------------
 
int main(int argc, char* argv[]) {
	//Заносим текущее время
	last_idle_time = clock();
	//Инициализация GLUT
	glutInit(&argc, argv);
	//Задаем размеры окна.
	glutInitWindowSize(width, height);
	//Задаем режимы отображения: цвет в формате RGB, двойная буфферизация, буфер глубины
	glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_DEPTH);
	//Создаем окно. Задаем его имя.
	glutCreateWindow("Губка Менгера");
	//Настройка OpenGL
	//Включаем перекрытие объектов
	glEnable(GL_DEPTH_TEST);
	//Сравнение "если меньше"
	glDepthFunc(GL_LESS);
	//Включаем тени путем интерполяции
	glShadeModel(GL_SMOOTH);
	//Включаем освещение
	glEnable(GL_LIGHTING);
	//Включаем 0 точку освещения
	glEnable(GL_LIGHT0);
	//Регистрируем callback функции
	glutReshapeFunc(ReshapeCallback);
	glutDisplayFunc(DisplayCallback);
	glutIdleFunc(Animate);
	glutKeyboardFunc(KeyboardCallback);
	glutSpecialFunc(SpecialKeyboardCallback);
	glutMouseFunc(MouseButtonCallback);
	glutMotionFunc(MouseMotionCallback);
	//Запускаем основной цикл GLUT
	glutMainLoop();
 
	return 0;
}

Ключевые слова: 
фрактал, 3D, ковер Серпинского, губка Менгера, OpenGL
ВложениеРазмер
menger.zip5.21 кб