Создание 3D-модели лабиринта с вертикальными стенами

Создание 3D-модели лабиринта с вертикальными стенами

Введение

В настоящее время одними из приоритетных направлений информационных технологий является трёхмерная графика и 3D-моделирование. Трёхмерная графика оперирует с объектами в трёхмерном пространстве, отображаемыми, как правило, на двумерном устройстве.

Компьютерная графика нашла широкое практическое применение. Речь идёт о компьютерных играх, пространственных моделях, удобном представлении изображений деталей устройств и машин, решении математических задач, связанных со свойствами поверхностей и геометрических тел, и т.д.

Инженеры и архитекторы используют трёхмерную графику для создания виртуальных моделей. Кинематографисты и разработчики компьютерных игр создают спецэффекты и анимацию, реалистичные ландшафты и прочие изображения объектов реального мира.

При разработке 3D-моделей в настоящее время часто применяется программный интерфейс OpenGL, который стандартизирует доступ к графической аппаратуре путём смещения ответственности за создание аппаратного драйвера на производителя графического устройства. [1] Это позволяет разработчикам программного обеспечения использовать более высокий уровень абстракции от графического оборудования, что значительно ускорило создание новых программных продуктов и снизило на них затраты. Например, не требуется предусматривать функции проецирования трёхмерных объектов на двумерную систему координат устройства вывода [3], что пришлось бы делать, например, если выполнять разработку, используя чисто функции GDI.

В данном проекте рассматривается работа с 3D-моделью лабиринта с помощью OpenGL, а также создание некоторых спецэффектов - тумана, снега, динамического освещения.

1. Техническое задание

В рамках данного курсового проекта требуется создать 3D-модель лабиринта с вертикальными стенами. Разработка программы должна осуществляться в любой визуальной среде с обязательным использованием графических библиотек OpenGL или аналогичных (например, DirectX). Необходимо обеспечить возможность рассмотреть сцену с разных сторон.

2. Разработка структур данных

.1 Иерархия объектов в пространстве

Модель лабиринта целесообразно представить как иерархическую, то есть состоящую из двух типов объектов: 1) отдельные полигоны; 2) модели частей лабиринта, состоящие из полигонов или моделей более малых частей. При такой формулировке естественно представить модель лабиринта в виде дерева (см. рис. 2.1). Отдельные полигоны в данном случае хранятся в листьях. Корень соответствует всей модели.

данная тип графический алгоритм

Рис. 2.1 - Дерево модели лабиринта

2.2 Пользовательские типы данных

Целесообразно ввести ряд пользовательских типов данных.

. Структура данных точка - в принципе не предоставляет некоторых новых функций, но позволяет работать с координатами точки как с данными одного объекта, а не разрозненными данными, а также задействовать элементы объектно-ориентированного программирования для более удобной работы с 3D-моделями.

struct Point3D /* структура ТОЧКА */

{x, y, z;

/* основные методы */

/* заполнение полей структуры */

void FillFields(double x, double y, double z)

{>x = x;>y = y;

this->z = z;

}

/* отрисовка точки либо выбор вершины полигона */

void Vertex() { glVertex3f(x, y, z); }

… /* другие методы */

};

Структура данные о клетке лабиринта - хранит данные о том, какие изображения будут использоваться на каждом из 4 кусков стен, соответствующих данной клетке. Каждому изображению соответствует его номер, а если соответствующего куска стены нет (например, если данная клетка находится у входа в лабиринт, то как минимум одного куска нет), то в качестве номера берётся специальное значение.

FieldInfo /* структура ДАННЫЕ О КЛЕТКЕ ЛАБИРИНТА */

{

/* номер изображений каждой из стенок

(0, если стенки нет) */

int TextureBack, TextureRight, TextureFront, TextureLeft;

… /* методы */

};

Структура данные о модели лабиринта - хранит данные обо всех клетках лабиринта. Содержит размеры лабиринта и матрицу типа FieldInfo. Такая организация данных может на первый взгляд показаться избыточной - если у двух клеток лабиринта есть общая стена, то факт её наличия указывается в двух местах. Но при такой организации данных можно предусмотреть ситуацию, когда эта общая стена выглядит по-разному со стороны каждой из клеток - например, с одной стороны это просто деревянная стена, с другой стороны на стене что-то нарисовано.

ModelInfo /* структура ДАННЫЕ О МОДЕЛИ ЛАБИРИНТА */

{Nx, Nz; /* размеры (всего будет Nx * Nz клеток) */FIELDS[10][10]; /* данные о клетках */

… /* методы */

};

Структура данных узел дерева модели - в случае листа хранит вершины соответствующего полигона и номер изображения, накладываемого на полигон, а в случае внутреннего узла - указатели на дочерние узлы и счётчик дочерних узлов. Теоретически дерево модели можно представить с помощью двух типов узлов - полезные (листья, хранят полигоны) и вспомогательные (внутренние узлы, хранят ссылки на другие узлы), но с точки зрения программной реализации проще ограничиться одним типом узлов, в качестве полей предусмотрев все возможные данных - как ссылочные, так и полезные. В этом случае признаком листа является нулевое значение счётчика дочерних узлов.

Node /* структура данных УЗЕЛ ДЕРЕВА МОДЕЛИ */

{D Square[4]; /* вершины соответствующего полигона (нужны только для листьев) */texture_type; /* номер изображения, которое нужно наложить на полигон (нужен только для листьев) */n_children; /* количество детей (для листьев равно 0, для остальных узлов чему угодно) */*Children[100]; /* дети (не используется при обработки листьев) */Draw(); /* отрисовка для поддерева, где текущий узел - корень */() {n_children = 0; } /* конструктор */

};

В файле лабиринт, содержащий m x n клеток, целесообразно хранить как таблицу из m x n четвёрок номеров. В каждой четвёрке - номера изображений стен соответствующей клетки. Если какая-то стена отсутствует, соответствующий номер приобретает специальное значение (в данной работе - нулевое).

2.3 Преимущества и недостатки подхода

Преимущества предложенного представления модели в виде дерева следующие:

) однообразная обработка разных частей модели;

) простота программной реализации;

) простота получения самых разных данных о модели - всё можно свести к обходу дерева;

) простота модификации модели до более сложной - сложность иерархии объектов и число уровней иерархии ограничено лишь объёмом доступной памяти.

Недостаток также есть - это далеко не оптимальное использование памяти. Даже при оптимальной организации отдельных узлов дерева внутренние узлы сами по себе не хранят полезных данных. При размере лабиринта m x n имеется (3 + mn) внутренних узлов. Количество полезных узлов не менее mn и не более 5mn. Если же учесть, что любая клетка лабиринта не может быть окружена стенами со всех сторон (иначе в неё нельзя попасть), то количество полезных узлов может достигать 4mn, то есть доля вспомогательных узлов составит не менее 20% от общего числа узлов.

3. Разработка графических алгоритмов

.1 Управление обзором сцены

Чтобы рассмотреть сцену с разных сторон, требуется ввести параметр, варьирование которого позволит как бы обойти сцену по кругу. Можно ввести угол обзора и воспользоваться функцией gluLookAt:

(DX, DY, DZ, DX + d * sin(fi), 0, DZ - d * cos(fi), 0, 1, 0);

Здесь (DX, DY, DZ) - точка, откуда мы смотрим, d - расстояние до точки, в которую мы смотрим. DY следует выбрать так, чтобы камера была чуть выше стен лабиринта - тогда мы видим, что находится внутри лабиринта. Варьируя параметр fi, мы можем «облететь» лабиринт, увидев его со всех сторон.

Для передвижения по сцене вводим понятия точки зрителя, задаваемой вектором , целевой точки, задаваемой вектором , скорости перемещения v и угла поворота w. Точка E определяет, где находится зритель (первые 3 параметра функции gluLookAt), точка C - куда он смотрит (вторые три параметра gluLookAt), от параметра v зависит смещение координат E и C при имитации шагов вперёд и назад. Параметр w определяет минимальный угол поворота направления движения и должен быть достаточно мал, в противном случае повороты будут резкими и неестественными. Направление движения определяется как вектор, проведённый между точками E и C, и будет обозначаться как .

Чтобы сместиться вперёд, нужно сместить вперёд координаты x и z точек E и C на величины  и . Очевидно, что смещение назад - обратная операция. Для поворота направления движения нужно выполнить преобразование

Для поворота в другую сторону нужно заменить w на -w.

Проще всего выполняется изменение высоты обзора - нужно лишь изменить ey на фиксированную величину.

Теперь для позиционирования камеры вызываем gluLookAt следующим образом:

gluLookAt(eye[0], eye[1], eye[2], center[0], center[1], center[2],  0, 1, 0);

Здесь eye - обозначение E, center - обозначение С. Данный вызов выполняем в режиме передвижения по сцене (в терминах программы - в «режиме полёта»), а вызов, описанный в начале раздела, - в режиме обзора.

3.2 Отрисовка модели

Используя дерево модели, отрисовку можно выполнить следующим образом: 1) если текущий узел листовой, рисуем соответствующее изображение, накладываемое на полигон; используются функции OpenGL для работы с текстурами - glBindTexture, glTexCoord2f [4]; 2) если текущий узел внутренний, рекурсивно вызываем функцию отрисовки для дочерних узлов. В приложении А приведён листинг функции отрисовки модели.

В приложении А приведён исходный код описанного алгоритма отрисовки.

В OpenGL существуют развитые средства обеспечения эффекта тумана. Фактически его обеспечение сводится лишь к последовательной установке параметров тумана с помощью функций glFogf, glFogfv, glFogi, glHint и вызову GL_ENABLE(GL_FOG). [5]

3.4 Эффект снегопада

Эффект снегопада можно реализовать, организовав крупную коллекцию частиц - точек - и имитируя их движение. Общая схема приведена на рис. 3.1. Сначала «снежинки» генерируются в «Верхнем слое атмосферы» - подпространстве, которое находится выше поля зрения, и тем самым невидимо. Далее с каждым тиком таймера «снежинки» смещаются вниз на заданную величину, и в «Нижнем слое атмосферы», находящемся в поле зрения, возникает иллюзия падения снежинок. Сначала их немного, как и при начале реального снегопада, затем их количество несколько увеличивается и вскоре стабилизируется - больше нет «снежинок», находящихся в «Верхнем слое атмосферы». Если какая-то из снежинок достигла «земли», то она перемещается на «границу слоёв». Это перемещение незаметно для пользователя, поскольку «снежинок» очень много - в данном проекте генерируется 4 тыс. точек. Перемещать снежинку в «верхний слой атмосферы» после её «приземления» нецелесообразно - когда часть снежинок уже «приземлилась», а часть ещё «падает», в верхней части «Нижнего слоя атмосферы» окажется заметная «брешь», где на протяжении ряда тиков таймера не будет «снежинок».

Рис. 3.1 - Общая схема имитации снегопада

Важным является вопрос о соотношении высот «слоёв атмосферы». Если высота верхнего меньше высоты нижнего, то произойдёт следующее. В некоторый момент все «снежинки» уже минуют часть «Нижнего слоя атмосферы» близ «Границы слоёв», но ни одна ещё не «приземлится». В результате пользователь заметит, как вверху поля зрения есть область, где вообще нет снежинок, то есть «снегопад» будет выглядеть крайне неестественно. Такой проблемы нет, если упомянутые высоты равны.

Для повышения эффективности отрисовки «снежинок» отсекаем те, которые находятся в «Верхнем слое атмосферы». Введение проверки на отсечение приводит к некоторым затратам времени, но они несравнимо меньше, чем вызов функции отрисовки для тех точек, которые заведомо не видны.

В приложении Б приведён исходный код описанного алгоритма.

3.5 Динамическое освещение

С помощью функций glLightf и glLightfv [6] создаём источники света с необходимыми характеристиками. С помощью таймера меняем характеристики источников, в данном проекте меняется цвет. Чтобы повысить реалистичность освещения, целесообразно обеспечить убывание интенсивности освещения по мере отдаление от источника. Простейший способ - задать линейный закон затухания, вызвав функцию glLightf со вторым параметром GL_CONSTANT_ATTENUATION и затем с GL_LINEAR_ATTENUATION [2], в качестве третьего параметра передавая необходимые коэффициенты.

Смену цветов можно организовать следующим образом. Пусть есть N источников и M возможных комбинаций цветов, K - номер текущей комбинации. В массиве A хранятся цвета источников, точнее, их коды. Очевидно, что коды цветов могут повторяться. Элемент A[NK + p] содержит код цвета, которая должна приобрести p-ая лампа при выборе K-ой комбинации (p = 0…N-1, K = 0…M-1). При очередном тике таймера меняем номер текущей комбинации, затем для p-ой лампы (p = 0…N-1) устанавливаем цвет A[NK + p], где K-номер новой комбинации.

Приложение А

Отрисовка модели, представленной деревом

Для структуры данных Node, описанной в разделе 2.2, предусматривается рекурсивный метод Draw. Чтобы отрисовать модель, требуется вызвать метод для корня дерева.

Node::Draw() /* отрисовка модели, представленной в виде дерева с корнем this */

{(this->n_children == 0) /* признак листового узла */

{

/* именно в листовых узлах хранятся полезные данные (сведения о полигонах) */

/* чтобы накладывалось нужное нам изображение */

glEnable (GL_TEXTURE_2D);(GL_TEXTURE_2D, TEXTURE_ID + this->texture_type);

/* а здесь накладываем это изображение на полигон, рисуем его */(GL_QUADS);

/* связываем углы изображения и вершины полигона; рисуем полигон с картинкой на нём */

glTexCoord2f(0.0f, 0.0f); this->Square[0].Vertex();f(0.0f, 1.0f); this->Square[1].Vertex();f(1.0f, 1.0f); this->Square[3].Vertex();f(1.0f, 0.0f); this->Square[2].Vertex();();(GL_TEXTURE_2D);

return;

}

/* этот код выполняется только если узел внутренний;

здесь рекурсивно вызываем функцию отрисовки для потомков узла */

for(int i = 0; i < this->n_children; i++)>Children[i]->Draw();

}

Приложение Б

Эффект снегопада

Генерация случайной коллекции «снежинок» может быть выполнена следующим образом.

Здесь xmin, xmax, ymin, ymax, zmin, zmax описывают подпространство, в котором генерируются «снежинки» («Верхний слой атмосферы» в разделе 3.4).

/* генерация случайной целой величины на [xmin; xmax] */

int RandomF(int xmin, int xmax) { return xmin + rand() % (xmax - xmin + 1); }

/* генерация снежинок случайным образом в заданном подпространстве */

void SetSnow(int snow_x[], int snow_y[], int snow_z[], int n, int xmin, int xmax, int ymin, int ymax, int zmin, int zmax)

{(int i = 0; i < n; i++)

{

/* координаты снежинки задаются случайным образом */

snow_x[i] = RandomF(xmin, xmax);_y[i] = RandomF(ymin, ymax);_z[i] = RandomF(zmin, zmax);

}

}

Следующие функции выполняют соответственно отрисовку и за перерасчёт координат «снежинок» при падении.

/* отрисовка снежинок; рисуются только те, у которых Y находится в [min_y; max_y] */

void Draw(int snow_x[], int snow_y[], int snow_z[], int n, int min_y, int max_y)

{

/* если Y вне [min_y; max_y], то не отрисовываем снежинку;

это нужно, чтобы не рисовать те снежинки, которые заведомо выше нашего обзора */

for(int i = 0; i < n; i++)(snow_y[i] >= min_y && snow_y[i] <= max_y)f(snow_x[i], snow_y[i], snow_z[i]);

}

/* имитация падения снежинок */Fall(int snow_y[], int n, int min_y, int max_y)

{(int i = 0; i < n; i++)

{_y[i]-=15; /* уменьшаем высоту снежинки */

/* если снежинка "достигла земли", то она опять начинает падать с "неба" - когда их много, пользователь не увидит такой детали */

if(snow_y[i] <= min_y) snow_y[i] = max_y;

}

}

Коллекция генерируется в функции окна приложения при получении сообщения WM_CREATE и сообщения от пункта меню, включающего эффект снегопада. Падение имитируется с тиками таймера (сообщение WM_TIMER).

Для отрисовки «снежинок» в обработчике сообщения WM_PAINT предусмотрен следующий фрагмент кода:

glColor3f(1, 1, 1);(2);(GL_POINTS);(snow_x, snow_y, snow_z, nSnow, -200, 400);

glEnd();