Преимущества предложенного представления модели в виде дерева следующие:
) однообразная обработка разных частей модели;
) простота программной реализации;
) простота получения самых разных данных о модели - всё можно свести к обходу дерева;
) простота модификации модели до более сложной - сложность иерархии объектов и число уровней иерархии ограничено лишь объёмом доступной памяти.
Недостаток также есть - это далеко не оптимальное использование памяти. Даже при оптимальной организации отдельных узлов дерева внутренние узлы сами по себе не хранят полезных данных. При размере лабиринта m x n имеется (3 + mn) внутренних узлов. Количество полезных узлов не менее mn и не более 5mn. Если же учесть, что любая клетка лабиринта не может быть окружена стенами со всех сторон (иначе в неё нельзя попасть), то количество полезных узлов может достигать 4mn, то есть доля вспомогательных узлов составит не менее 20% от общего числа узлов.
Разработка графических алгоритмов
Управление обзором сцены
Чтобы рассмотреть сцену с разных сторон, требуется ввести параметр, варьирование которого позволит как бы обойти сцену по кругу. Можно ввести угол обзора и воспользоваться функцией 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 - обозначение С. Данный вызов выполняем в режиме передвижения по сцене (в терминах программы - в «режиме полёта»), а вызов, описанный в начале раздела, - в режиме обзора.
Отрисовка модели
Используя дерево модели, отрисовку можно выполнить следующим образом: 1) если текущий узел листовой, рисуем соответствующее изображение, накладываемое на полигон; используются функции OpenGL для работы с текстурами - glBindTexture, glTexCoord2f [4]; 2) если текущий узел внутренний, рекурсивно вызываем функцию отрисовки для дочерних узлов. В приложении А приведён листинг функции отрисовки модели.
В приложении А приведён исходный код описанного алгоритма отрисовки.
Эффект тумана
В OpenGL существуют развитые средства обеспечения эффекта тумана. Фактически его обеспечение сводится лишь к последовательной установке параметров тумана с помощью функций glFogf, glFogfv, glFogi, glHint и вызову GL_ENABLE(GL_FOG). [5]
Эффект снегопада
Эффект снегопада можно реализовать, организовав крупную коллекцию частиц - точек - и имитируя их движение. Общая схема приведена на рис. 3.1. Сначала «снежинки» генерируются в «Верхнем слое атмосферы» - подпространстве, которое находится выше поля зрения, и тем самым невидимо. Далее с каждым тиком таймера «снежинки» смещаются вниз на заданную величину, и в «Нижнем слое атмосферы», находящемся в поле зрения, возникает иллюзия падения снежинок. Сначала их немного, как и при начале реального снегопада, затем их количество несколько увеличивается и вскоре стабилизируется - больше нет «снежинок», находящихся в «Верхнем слое атмосферы». Если какая-то из снежинок достигла «земли», то она перемещается на «границу слоёв». Это перемещение незаметно для пользователя, поскольку «снежинок» очень много - в данном проекте генерируется 4 тыс. точек. Перемещать снежинку в «верхний слой атмосферы» после её «приземления» нецелесообразно - когда часть снежинок уже «приземлилась», а часть ещё «падает», в верхней части «Нижнего слоя атмосферы» окажется заметная «брешь», где на протяжении ряда тиков таймера не будет «снежинок».
Рис. 3.1 - Общая схема имитации снегопада
Важным является вопрос о соотношении высот «слоёв атмосферы». Если высота верхнего меньше высоты нижнего, то произойдёт следующее. В некоторый момент все «снежинки» уже минуют часть «Нижнего слоя атмосферы» близ «Границы слоёв», но ни одна ещё не «приземлится». В результате пользователь заметит, как вверху поля зрения есть область, где вообще нет снежинок, то есть «снегопад» будет выглядеть крайне неестественно. Такой проблемы нет, если упомянутые высоты равны.
Для повышения эффективности отрисовки «снежинок» отсекаем те, которые находятся в «Верхнем слое атмосферы». Введение проверки на отсечение приводит к некоторым затратам времени, но они несравнимо меньше, чем вызов функции отрисовки для тех точек, которые заведомо не видны.
В приложении Б приведён исходный код описанного алгоритма.
Динамическое освещение
С помощью функций 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();