Факультет «Информатика и системыуправления»
Кафедра «Программное обеспечение ЭВМ и информационныетехнологии»
Курсовой проект
по машинной графике
Расчётно-пояснительная записка
Тема:
«Построение изображений ландшафта в реальном времени»
Оглавление
1. Введение
2. Конструкторская часть
2.1 Выбор, обоснование и описаниеиспользуемых алгоритмов и понятий машинной графики
2.1.1 Равномерная сетка высот
2.1.2 Сглаживание ландшафта
2.1.3 Трехмерные аффинныепреобразования
2.1.4 Проецирование
2.1.5 Отображение в окне
2.1.6 Алгоритм Z-буфера
2.1.7 Освещение
2.1.7.1 Однотонная закраска (методгранения)
2.1.7.2 Метод Гуро
2.1.7.3 Метод Фонга
2.1.7.4 Анализ методов Гуро и Фонга
2.1.8 Последовательность действий привизуализации сцены
2.2 Типы, структуры данных и функции,использованные при реализации программного комплекса
2.2.1 Представление исходных данных
2.2.2 Программа «Редактор карт»
2.2.2.1 Изообласти высоты
2.2.2.2 Равномерная сетка высот иландшафт
2.2.2.3 Тип и структура файла дляхранения карт изообластей
2.2.2.4 Распределение программы помодулям
2.2.2.5 Связи между модулямипрограммы
2.2.3 Программа «Просмотр ландшафта»
2.2.3.1 Процедуры манипуляцииизображением ландшафта
2.2.3.2 Z-буфер
2.2.3.3 Буфер кадра
2.2.3.4 Процедуры визуализацииландшафта
2.2.3.2 Тип и структура файла дляхранения ландшафта
2.2.3.3 Распределение программы помодулям
2.2.3.4 Связи между модулямипрограммы
3. Технологическая часть
3.1 Выбор языка программирования
3.2 Описание программного комплекса
3.2.1 Программа «Редактор карт»
3.2.1.1 Общие сведения
3.2.1.2 Интерфейс программы
3.2.1.3 Работа программы
3.2.2 Программа «Просмотр ландшафта»
3.2.2.1 Общие сведения
3.2.2.2 Интерфейс программы
3.2.2.3 Работа программы
3.2.3 Системные требования
4. Экспериментально-исследовательскаячасть
4.1 Исследование № 1
4.2 Исследование № 2
4.3 Исследование № 3
5. Заключение
6. Список литературы
1. Введение
Решениезадачи построения поверхности на основе карты изолиний или изообластей высотявляется одним из этапов создания геоинформационной системы (компьютернаясистема, которая хранит в базе данных описание и обеспечивает анализ объектов,расположенных на поверхности Земли). Описание поверхности изолиниями высотычасто используется, например, в картографии. В данной работе решается задачапостроения изображения ландшафта на основе карты изообластей высот в реальномвремени.
В своюочередь задача построения изображения ландшафта на основе карты изообластей включаетв себя следующие задачи:
· преобразованиеданной карты в равномерную сетку высот;
· триангуляцияполученной сетки высот;
· при необходимости– сглаживание триангулированной сетки для получения изображений ландшафтов,близких по очертаниям к реальным.
Требованиек скорости построения изображений ландшафта (для комфортной работы необходимапроизводительность порядка 30 кадров в секунду [1]) определяет выбор алгоритмамашинной графики, используемого для визуализации сцены – алгоритм Z-буфера в наибольшей степени отвечаетэтому требованию, так как он является наиболее простым в своей группе и требуетнаименьшего количества вычислительных ресурсов.
Кромеэтого, в данной работе затронуты другие алгоритмы машинной графики:преобразование координат, проецирование, освещение.
Приработе с освещением реализованы следующие алгоритмы заполнения плоских граней(в данной работе — треугольников):
· метод гранения (однотоннойзакраски с учетом ориентации нормали к плоскости грани);
· метод Гуро –метод закрашивания граней трехмерных объектов, который использует билинейную интерполяциюинтенсивности цвета в вершинах граней;
· метод Фонга –метод, основанный на билинейной интерполяции векторов нормалей в вершинахграней.
Цельданной работы – реализовать перечисленные алгоритмы в разрабатываемомпрограммном комплексе.
Впрограмме также предусмотрен удобный русскоязычный пользовательский интерфейс,позволяющий редактировать карты изообластей высот, а также управлять получаемымизображением ландшафта (вращать его относительно координатных осей, масштабировать,изменять цвет поверхности и т.д.).
2. Конструкторская часть
2.1 Выбор, обоснование и описание используемых
алгоритмов и понятий машинной графики
2.1.1 Равномернаясетка высот
Существуетбольшое количество моделей описания поверхностей. Наиболее распространенными изних являются:
· аналитическаямодель – для описания поверхности используются математические формулы, напримерфункции от двух аргументов z = f(x, y);
· векторнаяполигональная модель – для описания пространственных объектов используютсятакие элементы, как вершины, векторы, полилинии, полигоны, полигональные поверхности;
· воксельная модель– представляет собой трехмерный растр. Подобно тому, как пиксели располагаютсяна плоском изображении, воксели образуют трехмерные объекты в некотором объеме;
· неравномернаясетка – в этой модели поверхность описывается в виде множества отдельных точек,принадлежащих поверхности.
Вданной работе в качестве модели описания поверхности (ландшафта) используетсяравномерная сетка высот. Эта модель описывает координаты отдельных точекповерхности способом, показанным на рисунке:
/>
Рис.2.1.1.1. Общий вид равномерной сетки высот
Каждомуузлу сетки с индексами (i, j) приписывается значение высоты Zij. Индексам (i, j) отвечаютопределенные значения координат (x, y). Расстояние между узлами одинаковое– dX по оси X и dY пооси Y.
Фактическитакая модель представляет собой двумерный массив, растр, матрицу, каждый элементкоторой сохраняет значение высоты.
Следуетотметить, что не каждая поверхность может быть представлена с помощью этой модели,так как если в каждом узле записывается только одно значение высоты, то этоозначает, что поверхность описывается однозначной функцией z = f(x, y). Кроме того, невозможномоделирование вертикальных граней.
Вслучае представления ландшафта в виде равномерной сетки высот эти ограниченияявляются незначительными и вполне допустимыми. Равномерная сетка частоиспользуется для описания рельефа земной поверхности [2].
Следуетвыделить следующие положительные черты модели равномерной сетки:
· простота описанияповерхностей;
· возможностьбыстро узнать высоту любой точки поверхности простой интерполяцией.
Ноэта модель также имеет и недостатки:
· для описаниясложных поверхностей необходимо большое количество узлов, которое может бытьограничено объемом памяти компьютера;
· поверхности,которые соответствуют неоднозначной функции высоты в узлах сетки, не могутмоделироваться (как уже говорилось, это ограничение незначительно в условияхданной работы).
Нов данной работе равномерная сетка используется опосредованно – сразу же приполучении она разбивается на треугольники (производится ее триангуляция),поскольку реализация необходимых в процессе работы алгоритмов машинной графикидля этого примитива наиболее проста. Разбиение на треугольники производитсяпутем проведения диагонали из точки (i, j) в точку (i – 1, j +1).
2.1.2 Сглаживаниеландшафта
Построениеландшафта может быть произведено сразу после триангуляции равномерной сетки, нов этом случае очертания ландшафта будут резкими. Если это нежелательно, томожно воспользоваться методом сглаживания, реализованным в данной работе.
Егосуть заключается в следующем. В процессе сглаживания в цикле производитсяусреднение высот 4 соседних пикселей. Для повешения качества и эффективностисглаживания, оно производится в 4 последовательных циклах – “слева направо”,“справа налево”, “сверху вниз” и “снизу вверх”.
/>
Рис.2.1.2.1. Циклы сглаживания ландшафта
Пикселидля усреднения высот выбираются следующим образом: на K-ой итерации цикла производится усреднение высот пикселей синдексами (i – 1, j — 1), (i – 1,j), (i, j — 1) и (i, j), на (K +1)-ой же, в зависимости от номера цикла, усредняются высоты следующих пикселей:
· в I цикле – пиксели тех же двух строк синдексами столбцов, увеличенными на 1;
· во II цикле – пиксели тех же двух строк синдексами столбцов, уменьшенными на 1;
· в III цикле – пиксели тех же столбцов сострочными индексами, увеличенными на 1;
· в IV цикле – пиксели тех же столбцов сострочными индексами, уменьшенными на 1.
Нижеприведена иллюстрация, демонстрирующая результаты сглаживания тестовоголандшафта:
/>
Рис.2.1.2.2. Результаты сглаживания – без сглаживания, 1 цикл, 10 циклов.
2.1.3 Трехмерныеаффинные преобразования
Впроцессе работы программы может возникать необходимость преобразования объектовсцены – их сдвига, масштабирования, поворота.
Длятрехмерного пространства любое аффинное преобразование может быть представленопоследовательностью простейших операций [3].
Нижеприводятся уравнения и матрицы преобразований:
· сдвиг точки вдолькоординатных осей на dx, dy, dz:
/> />;
· масштабированиеотносительно начала координат с коэффициентами kx, ky, kz:
/> />;
· поворототносительно осей x, y, z на угол />:
o ось x:
/> />
o ось y:
/> />
o ось z:
/> />
2.1.4Проецирование
Внастоящее время наиболее распространены устройства отображения, которые синтезируютизображение на плоскости, например – экране монитора. Устройства, которыесоздают по-настоящему объемные изображения, пока достаточно редки. Но все чащепоявляются сведения о подобных разработках, например, об объемных мониторах [2].
Прииспользовании графических устройств обычно используют проекции. Проекция задаетспособ отображения объекта на графическом устройстве.
Приотображении пространственных объектов на экране необходимо знать координатыобъектов. Рассмотрим две системы координат. Первая – мировые координаты, которыеописывают истинное положение объектов в пространстве с заданной точностью.Другая – экранная система координат – система координат монитора, на экранкоторого осуществляется вывод изображения.
Пустьмировые координаты будут трехмерными декартовыми координатами. Для синтезаизображения на плоскости достаточно, казалось бы, двумерной экранной системы координат,однако из-за использования алгоритма Z-буфера (этот алгоритм будет описан далее), они должны быть трехмерными.
Вкомпьютерной графике распространены параллельная и центральная (перспективная)проекции.
/>
Рис. 2.1.4.1.Параллельная и центральная проекции
Дляцентральной проекции лучи проецирования исходят из одной точки, размещенной наконечном расстоянии от объектов и плоскости проецирования. Для параллельнойпроекции лучи проецирования параллельны.
Вданной работе для визуализации сцены использовалась аксонометрическая (разновидностьпараллельной) проекция, для нее все лучи располагаются под прямым углом к плоскостипроецирования.
Какправило, расположение плоскости проецирования задается с помощью двух углов — />и />.
/>
Рис. 2.1.4.2.Аксонометрическая проекция
Длятого, чтобы найти соотношения между координатами (x, y, z) и (X, Y, Z) для любой точки в трехмерномпространстве, рассмотрим преобразование системы координат (x, y, z) в систему (X, Y, Z). Такоепреобразование может быть задано двумя шагами:
· поворот системыкоординат относительно оси z наугол />. Такойповорот описывается матрицей
/>;
· поворот новойсистемы координат (x, y, z) относительно оси x на угол /> - получение координаты (X, Y, Z). Матрицаповорота:
/>.
Преобразованиекоординат выражается произведением матриц />
/>
Это жепреобразование можно записать в формульном виде:
/>
2.1.5 Отображениев окне
Приформировании изображения на экране монитора, как уже было сказано, необходимыдополнительные преобразования, поскольку система координат в плоскости проецированияможет не совпадать с системой координат устройства отображения.
Пусть (Xэ, Yэ, Zэ) –это экранные координаты объектов в графическом устройстве отображения.Координаты проецирования обозначим как (X, Y, Z).
Преобразованиекоординат проекции в экранные координаты можно представить какрастяжение/сжатие и сдвиг:
/>.
Такоепреобразование сохраняет пропорции объектов благодаря одинаковому коэффициентурастяжения/сжатия k для всехкоординат. Следует отметить, что для плоского отображения координату Z можно отбросить. 2.1.6 АлгоритмZ-буфера
Послеполучения треугольников ландшафта (триангуляции равномерной сетки) и проецированияих на экранную плоскость следует построение изображения ландшафта. В процессеего построения для удаления невидимых поверхностей используется алгоритм Z-буфера.
Этоодин из простейших алгоритмов удаления невидимых поверхностей. Работает этоталгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра.Буфер кадра используется для запоминания атрибутов (интенсивности) каждогопикселя в пространстве изображения, Z-буфер — это отдельный буфер глубины, используемый для запоминаниякоординаты Z (глубины) каждого видимого пикселя впространстве изображения. В процессе работы глубина или значение Z каждого нового пикселя, который нужно занести в буфер кадра,сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнениепоказывает, что новый пиксель расположен впереди пикселя, находящегося в буферекадра, то новый пиксель заносится в этот буфер и, кроме того, производитсякорректировка Z-буфера новым значением Z. Если же сравнение даетпротивоположный результат, то никаких действий не производится. По сути,алгоритм является поиском по x и y наибольшего значения функции Z(x, у). Блок-схемаалгоритма выглядит следующим образом:
/>
Рис. 2.1.6.1.Блок-схема алгоритма Z-буфера
Как ужебыло отмечено, главное преимущество алгоритма — его простота. Так как габаритыпространства изображения фиксированы, оценка вычислительной трудоемкостиалгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заноситьв буфер кадра или в Z-буфер впроизвольном порядке, их не нужно предварительно сортировать по приоритетуглубины. Поэтому экономится вычислительное время, затрачиваемое на сортировкупо глубине, например в алгоритме художника.
Существеннымнедостатком алгоритма является потребность в значительном объеме памяти. Но всвязи с тем, что стоимость оперативной памяти постоянно снижается, и установкадополнительных модулей памяти на индивидуальном компьютере стала привычнымделом, этому недостатку перестали уделять особое внимание.
Другойнедостаток алгоритма Z-буферасостоит в трудоемкости устранения лестничного эффекта, а также реализацииэффектов прозрачности и просвечивания. Но так как в этой работе не ставиласьзадача реализации этих эффектов, то использование алгоритма Z-буфера вполне обоснованно.
Математическоесодержание алгоритма заключается в следующем: если известно уравнениеплоскости, несущей каждый многоугольник, то вычисление глубины каждого пикселяна сканирующей строке можно проделать пошаговым способом. Уравнение плоскостиимеет вид:
/>
/>
Длясканирующей строки/>, поэтому глубина пикселя на этойстроке, у которого />, равна
/>
или
/>,
но />, поэтому />.
Нахождениеже абсцисс точек пересечения горизонтали со сторонами треугольника (этоединственный вид многоугольников, используемый при визуализации в даннойработе) производится следующим образом:
· для всех сторонтреугольника записываются параметрические уравнения вида
/>;
· затем для каждойстороны находится параметр t припересечении с горизонталью />:
/>;
· если />, торассчитывается абсцисса точки пересечения горизонтали со стороной треугольника:
/>.
/>
Рис. 2.1.6.2.Поиск абсцисс точек пересечения горизонтали со сторонами треугольника
2.1.7 Освещение
В любомтрёхмерном приложении использование какой-либо модели освещения всегда придаётреалистичность обрабатываемой сцене. Как правило, в неё включается закон, покоторому рассчитывается освещённость точки в пространстве, и метод закраски освещённогомногоугольника. От выбора той или иной модели освещения зависит качествоизображения, построенного компьютером, и скорость работы программы.
Обычноосвещённость некоторой точки, принадлежащей грани в пространстве, складываетсяиз рассеянной освещённости и диффузного отражения — потока света, отражающегосяот поверхности объекта. Иногда к ним добавляют зеркальное отражение — потоксвета, отражающийся от внешней поверхности объекта под тем же углом, подкоторым он падал на эту поверхность. Однако в данной работе зеркальноеотражение света не учитывается, так как расчёт интенсивности зеркальногоотражения, например по модели Фонга, требует немалых вычислительных затрат. Длянего требуется рассчитывать угол между вектором наблюдения и вектором отраженияи возводить косинус этого угла в некоторую степень, зависящую от свойствповерхности.
Диффузноеотражение присуще матовым поверхностям. Матовой можно считать такуюповерхность, размер шероховатостей которой настолько велик, что падающий лучрассеивается неравномерно во все стороны. Такой тип отражения характерен,например, для гипса, песка, бумаги. Диффузное отражение описывается закономЛамберта, согласно которому интенсивность отраженного света пропорциональнакосинусу угла между направлением на точечный источник света и нормалью кповерхности.
/>
Рис. 2.1.7.1.Матовая поверхность
/>,
где /> — интенсивностьисточника света, /> — коэффициент, который учитываетсвойства материала поверхности. Интенсивность отраженного света не зависит отрасположения наблюдателя.
Матоваяповерхность имеет свой цвет. Наблюдаемый цвет матовой поверхности определяется комбинациейсобственного цвета поверхности и цвета излучения источника света (в даннойработе цвет излучения источника считается белым, поэтому учитывается толькоцвет поверхности).
Можноеще усовершенствовать модель отражения, если учесть, что энергия от точечногоисточника света уменьшается пропорционально квадрату расстояния. Использованиетакого правила вызывает сложности, поэтому на практике часто реализуют модель,выражаемую эмпирической формулой
/>,
где R – расстояние от источника света до рассматриваемойточки поверхности, k – произвольнаяконстанта, предотвращающая деление на 0.
Для определениякосинуса угла между вектором нормали к поверхности и вектором, определяющимположение источника света в пространстве, следует воспользоваться скалярнымпроизведением. Пусть имеется вектор нормали /> и две точки – />, принадлежащаяповерхности, и />, определяющая положениеисточника. Вектор, направленный от точки поверхности к источнику света, имеетследующие координаты: />. Тогда
/>,
/>,
/>,
или
/>.
Следовательно
/>.
Однаков программе используются, как правило, единичные вектора нормалей, что в данномслучае позволяет уменьшить количество требуемых вычислений. В итоге:
/>,
или,более развернуто,
/>.
Далеерассматриваются методы закрашивания поверхности, реализованные в данной работе.
2.1.7.1Однотонная закраска (метод гранения)
Этонаиболее простой и требующий наименьших вычислительных ресурсов метод закраскиповерхности. Цвет всей поверхности рассчитывается согласно закону Ламберта. Врезультате, при малом количестве граней, многогранник выглядит именно как многогранник,так как цвета отдельных граней существенно отличаются. Тем не менее, создаетсяэффект объемности изображения.
Методгранения позволяет получать изображения, сравнимые по качеству с реальнымиобъектами, лишь при выполнении следующих условий:
· источник светанаходится на большом расстоянии от объекта;
· наблюдатель находитсяна большом расстоянии от объекта;
· каждая грань телаявляется гранью многогранника, а не аппроксимирующей поверхностью;
· поверхностьаппроксимирована большим числом небольших плоских граней.
/>
Рис. 2.1.7.1.1.Изображение, полученное методом гранения
2.1.7.2Метод Гуро
Этотметод предназначен для создания иллюзий гладкой криволинейной поверхности,описанной в виде многогранников или полигональной сетки с плоскими гранями.Если каждая плоская грань имеет один постоянный цвет, определенный с учетомотражения, то различные цвета соседних граней очень заметны, и поверхностьвыглядит именно как многогранник. Казалось бы, этот дефект можно замаскироватьс помощью увеличения количества граней при аппроксимации поверхности, Но зрениечеловека имеет способность подчеркивать перепады яркости на границах смежныхграней – такой эффект называется эффектом полос Маха. Поэтому для созданияиллюзии гладкости нужно намного увеличить количество граней, что приводит ксущественному замедлению визуализации.
МетодГуро основывается на идее закрашивания плоской грани не одним цветом, а плавноизменяющимися оттенками, вычисляемыми путем билинейной интерполяции цветовпримыкающих граней. Закрашивание граней по методу Гуро осуществляется в четыреэтапа:
· вычисляютсянормали к каждой грани;
· определяютсяусредненные нормали в вершинах — производится усреднение нормалей примыкающихграней. На иллюстрации приведен пример – вектор нормали в вершине a равен />;
·
/>
Рис. 2.1.7.2.1.Нормаль в вершине
· на основеусредненных нормалей в вершинах вычисляются значения интенсивностей в вершинахсогласно принятой модели отражения;
· производитсязакрашивание грани цветом, соответствующим линейной интерполяции значенийинтенсивности в вершинах.
Определениеинтерполированных значений интенсивности отраженного света в каждой точке грани(и, следовательно, цвет каждого пикселя) удобно выполнять во время циклазаполнения полигона (например, совместить его с реализацией алгоритма Z-буфера). Далее рассматриваетсязаполнение грани горизонталями в экранных координатах.
/>
Рис. 2.1.7.2.2.Интерполяция значений интенсивности
Интерполированнаяинтенсивность I в точке (X, Y) определяетсяисходя из пропорции
/>.
Отсюда
/>.
Значенияинтенсивностей I1 и I2 на концах горизонтального отрезка представляет собой интерполяциюинтенсивности в вершинах:
/>; /> или
/>, />.
/>
Рис. 2.1.7.2.3.Изображение, получено методом Гуро
2.1.7.3Метод Фонга
Этотметод закраски аналогичен методу Гуро, но при использовании метода Фонга дляопределения цвета в каждой точке интерполируются не интенсивности отраженногосвета, а векторы нормалей.
Последовательностьдействий такова:
· определяютсянормали к граням;
· по нормалям кграням определяются усредненные нормали в вершинах. В каждой точке закрашиваемойграни определяется интерполированный вектор нормали;
· по направлениювекторов нормали определяется цвет точек грани в соответствии с принятоймоделью отражения цвета.
Как ужебыло сказано, метод заключается в интерполяции вектора нормали. Для интерполяциибудут использоваться векторы />, исходящие из начала координатплоскости проецирования и параллельными соответствующим нормалям /> в вершинах a, b и c.
/>
Рис. 2.1.7.3.1.Интерполяция векторов нормалей
Нахождение/> и /> производитсяследующим образом:
/>,
/>.
где /> – координатывекторов />.Теперь необходимо найти координаты вектора />:
/>.
Вектор /> параллеленвектору/>длянормали в точке />, поэтому его можно использоватьдля расчета отражения света так же, как и вектор нормали />.
/>
Рис. 2.1.7.3.2.Изображение, полученное методом Фонга
2.1.7.4Анализ методов Гуро и Фонга
МетодФонга сложнее, чем метод Гуро. Для каждого пикселя поверхности необходимовыполнять намного больше вычислительных операций. Тем не менее, он дает лучшиерезультаты, в особенности при имитации зеркальных поверхностей.
Общиечерты и отличия методов Фонга и Гуро можно показать на примере цилиндрическойповерхности, аппроксимированной многогранником. Пусть источник света находитсяза нами. Проанализируем закрашивание боковых граней.
/>
Рис. 2.1.7.4.1.Отличия закрашивания Фонга и Гуро
/>Ребра гранейпоказаны черным цветом для иллюстрации особенностей закрашивания, на самом делепосле закрашивания никакого каркаса не будет, и поверхность будет выглядетьгладкой.
Основныеотличия заметны на передней грани. Она перпендикулярна направлению лучей света,поэтому нормали в вершинах этой грани располагаются симметрично – они образуютпопарно равные по абсолютной величине углы с лучами света. Для метода Гуро этообусловливает одинаковые интенсивности в вершинах передней грани. А разинтенсивности одинаковые, то и для любой точки внутри этой грани интенсивностьостается постоянной. Это обусловливает единый цвет закрашивания, а это,очевидно, неправильно.
МетодФонга дает правильное закрашивание. Если интерполировать нормали переднейграни, то по центру будут интерполированные нормали, параллельные лучам света.Поэтому центр передней грани будет светлее, чем края.
2.1.8Последовательность действий при визуализации сцены
Пландействий, необходимых для визуализации сцены приведен на следующей схеме:
/>
Рис. 2.1.8.1.Схема визуализации сцены
2.2 Типы, структуры данныхи функции, использованные при реализации программного комплекса
2.2.1Представление исходных данных
Припроектировании программы важно сразу решить, как будут представлены исходныеданные, то есть, в условиях данной работы – как будет описана карта изообластейвысот и трехмерный ландшафт, какими будут форматы файлов для хранения информациио карте и ландшафте.
Вданной работе был выбран полигональный способ аппроксимации пространственныхфигур. Сущность полигональной модели состоит в том, что каждое тело представляетсяв виде определенного набора граней-многоугольников, с определенной точностьюприближающих форму исходного тела. В качестве грани-многоугольника был выбрантреугольник, так как это наиболее простой многоугольник, его точки всегда лежатв одной плоскости и любой более сложный многоугольник можно разбить нанесколько треугольников.
Разработанныетипы данных и форматы файлов подробно описаны в последующих разделах.
2.2.2 Программа«Редактор карт»
2.2.2.1Изообласти высоты
Изообластьхарактеризуется цветом и высотой, поэтому для хранения информации о каждом типеизообластей используется следующая запись:
THeightColor = record
Color: TRGBColor;
Height: Single;
end;
Поляэтой записи имеют следующее значение:
· Color– цвет изообласти;
· Height– представляемая высота.
Размерзаписи – 8 байт (компилятор Delphiпроизводит выравнивание полей в записи, поэтому размер записи оказываетсяравным 8 байтам, а не 7, как должно быть).
Тип TRGBColor используется для хранения RGB-цвета. Представим его структуру:
TRGBColor = record
R, G, B: Byte;
end;
Размерзаписи – 3 байта (по неизвестным причинам в этом случае выравнивания непроизошло).
Впроцессе создания каждой карты создается динамический массив, для хранения информацииобо всех типах изообластей:
THeightColors= array of THeightColor;
2.2.2.2Равномерная сетка высот и ландшафт
Для храненияузлов исходной равномерной сетки (с шагом 1) используется динамический массивэлементов типа Single:
TZBitMap = array of array of Single;
Тип Single использован для экономии оперативнойпамяти и дискового пространства, точность этого типа – 8 знаков после запятой,что вполне достаточно в рамках этой работы, при этом переменная этого типазанимает в памяти 4 байта, вдвое меньше, чем переменная типа Real.
Притриангуляции равномерной сетки создается динамический массив треугольниковландшафта. Для хранения информации о треугольнике используется следующий тип данных:
TTriangle= record
P: array [0..2] ofTPoint3
N: TPoint3
pD: Single;
aN: array [0..2] of TPoint3;
Color:TRGBColor;
end;
Поляэтой записи имеют следующие значения:
· P – массив точек треугольника;
· N – нормаль к плоскости треугольника;
· pD – свободный член уравненияплоскости, несущей треугольник;
· aN – массив усредненных нормалей ввершинах треугольника;
· Color– базовый цветтреугольника.
Поля N и pD в совокупности образуют уравнение плоскости, несущейтреугольник.
Размерзаписи – 92 байта (реальный размер, без выравнивания – 91 байт).
Необходимопривести описания типов, использованных в записи TTriangle:
TPoint3 = record
X, Y, Z: Single;
end; — запись служит для хранения координат точки.
Размерзаписи – 12 байт.
Дляработы с равномерной сеткой высот предусмотрены следующие процедуры и функции:
· function CreateZBitMap(Width, Height: Integer): TZBitMap – выделение памяти для первичнойсетки высот, ее размеры — Widthи Height, совпадают с размерами областивывода;
· procedure FreeZBitMap(var ZBMP: TZBitMap) – освобождение памяти, занимаемой первичной сеткой высот;
· function FillZBitMap(Image: TImage;Colors: THeightColors): TZBitMap — заполнение первичной сетки высотна основе изображения, хранимого в Image и соответствий «Цвет-высота», содержащихся в массиве Colors;
· function DivideZBitMapIntoTriangles(BitMap: TZBitMap; StepX, StepY: Integer): TTriangles – функция преобразования первичнойравномерной сетки BitMap в болееразреженную сетку с шагами StepXи StepY по горизонтали и вертикалисоответственно. После этого преобразования полученная сетка разбивается натреугольники, на основе которых будет построен ландшафт;
· procedure SmoothMap(var BitMap: TZBitMap) – процедура для проведения одного цикла сглаживания первичной сеткивысот;
Дляработы с треугольниками ландшафта предназначены следующие процедуры:
· procedure FillTrianglesNormals(var Triangles: TTriangles) – расчет и заполнение всех полейзаписи TTriangle, кроме координат точек и цвета;
Впроцедуре FillTrianglesNormals используются следующиевспомогательные функции:
· function GetNormal(T: TTriangle): TPoint3 – процедура для вычисления координатвектора нормали к плоскости треугольника;
· function CorrectNormal(N: TPoint3): TPoint3 – процедура нормализации векторанормали;
· procedure AddNormal(var N: TPoint3;NAdd: TPoint3; var Count: Integer), procedure DivideNormal(var N: TPoint3;Count: Integer) – эти процедуры в совокупности служат для вычисленияусредненной нормали в вершине треугольника;
2.2.2.3Тип и структура файла для хранения карт изообластей
Файлдля хранения информации о разметке карты изообластей высот является текстовым. Онимеет расширение HCL и разбит насекции, разделенные строками–маркерами. Ниже приведена его структура:
· заголовок файла –строка 'Landscape heights map';
· заголовок секциивысот – строка ‘[ColorHeights Start]’;
o последовательностьзаписей типа THeightColor;
· окончание секциивысот – строка '[ColorHeights End]';
· заголовок секциипикселей – строка '[Pixels Start]';
o ширина и высотакарты в пикселях;
o информация опикселях карты, сжатая с помощью метода группового кодирования(последовательность пар «Индекс цвета – Длина участка»);
· окончание секциипикселей – строка '[Pixels End]';
Методгруппового кодирования используется для экономии дискового пространства,занимаемого файлами плоских карт. Суть метода состоит в том, что сохраняетсяинформация не о каждом пикселе карты, а о группах пикселей, принадлежащих однойстроке и имеющих общий цвет (запоминается длина участка и цвет его пикселей).Таким образом, можно добиться значительной экономии дискового пространства. Этоможно проверить, сопоставив размер файла BMP, хранящего изображение карты, и размерсоответствующего ему файла HCL.Однако экономия дискового пространства не всегда может быть достигнута прииспользовании данного метода. Можно привести такой пример изображения, при кодированиикоторого размер итогового файла будет превышать размер исходного BMP-файла. Строки этого изображениядолжны состоять из таких пикселей, что цвет любых двух соседних не совпадает.Но, несмотря на это, использование метода группового кодирования в даннойработе вполне оправдано, так как карта в общем случае имеет вполне однороднуюструктуру.
Дляработы c файлами карт изообластей высотпредусмотрены следующие процедуры:
· procedure LoadFromHeightsMap(FileName: string; var Image: TImage; var Colors: THeightColors) — процедура для загрузки из файла HCL карты изообластей высот и соответствий цвет-высота.Информация загружается из файла FileName. Разметка карты выводится на Image, а соответствия «Цвет-высота» помещаются в динамический массив Colors;
· procedureSaveAsHeightsMap(Image: TImage; Colors: THeightColors; FileName: string) – процедура для сохранения разметки карты в файл HCL. Разметка считывается из Image, соответствия «Цвет-высота» из массива Colors, эта информация помещается в файл c именем FileName.
2.2.2.4Распределение программы по модулям
Таблица2.2.2.4.1. Распределение программы «Редактор карт» по модулямИмя модуля Описанные типы Назначение модуля AboutUnit.pas - Модуль формы «О программе» ColorUnit.pas - Модуль формы определения соответствия «Цвет-высота» HelpUnit.pas - Модуль формы «Помощь» MainUnit.pas - Главный модуль программы ME_ExtRegUnit.pas - Модуль регистрации расширения HCL ME_FileUnit.pas - Модуль работы с файлами ME_GraphicsUnit.pas - Модуль реализации процедур визуализации ME_MathUnit.pas TRGBColor, TPoint3, TTriangle, TTriangles, THeightColor, THeightColors, TZBitMap Модуль реализации вычислений MLEditorUnit.pas - Модуль инструментальной формы «Обработка карт» NewPictureUnit.pas - Модуль формы определения размеров новой карты SectionUnit.pas - Модуль формы «Разрез»
2.2.2.5Связи между модулями программы
/>
Рис.2.2.2.5.1. Связи между модулями программы «Редактор карт»
2.2.3Программа «Просмотр ландшафта»
Впрограмме «Просмотр ландшафта» также используется тип TTriangle. Он полностью аналогичен типу TTriangle, используемому в программе «Редакторкарт». Ландшафт, как уже говорилось, представляется как совокупностьтреугольников, поэтому для его хранения в программе предусмотрен тип,представляющий собой динамический массив:
TTriangles= array of TTriangle.
2.2.3.1Процедуры манипуляции изображением ландшафта
Вначале работы программы, при загрузке ландшафта из файла, должны быть выполненынекоторые подготовительные действия, в частности, вычисление масштаба иэкранных смещений для вывода изображения ландшафта. Для этого предусмотрена функция
· functionGetScale(Triangles: TTriangles; Width, Height: Integer): Single;
Необходимопояснить значения аргументов представленной функции:
Triangles –треугольники ландшафта;
Width, Height – размеры области вывода.
Дляприменения вычисленного масштаба и экранных смещений к треугольникам ландшафтаслужит функция
· functionMulTrianglesScale(Triangles: TTriangles; dX, dY: Integer; Scale: Real):TTriangles;
Значенияаргументов:
Triangles –исходные треугольники сцены;
dX, dY – экранные смещения по горизонтали ипо вертикали;
Scale –коэффициент масштабирования.
Впроцессе работы с полученным изображением может возникать необходимость еговращения относительно координатных осей. Для этих целей введены 3 группыфункций, разделенных по уровням абстракции:
· functionRotatePointX(P, Center: TPoint3; Alpha: Real): TPoint3;
· functionRotatePointY(P, Center: TPoint3; Alpha: Real): TPoint3;
· functionRotatePointZ(P, Center: TPoint3; Alpha: Real): TPoint3;
· functionRotateTriangleX(T: TTriangle; Center: TPoint3; Alpha: Real): TTriangle;
· functionRotateTriangleY(T: TTriangle; Center: TPoint3; Alpha: Real): TTriangle;
· functionRotateTriangleZ(T: TTriangle; Center: TPoint3; Alpha: Real): TTriangle;
· functionRotateTrianglesX(Triangles: TTriangles; Center: TPoint3; Alpha: Real):TTriangles;
· functionRotateTrianglesY(Triangles: TTriangles; Center: TPoint3; Alpha: Real):TTriangles;
· functionRotateTrianglesZ(Triangles: TTriangles; Center: TPoint3; Alpha: Real):TTriangles;
Аргументывсех функций однотипны: первый – объект, который должен быть повернут, второй –центр поворота; третий – угол поворота.
2.2.3.2Z-буфер
Привизуализации ландшафта используется Z-буфер. Для его хранения используется тип, представляющий собойдинамический массив:
TBuffer = array of array of Single.
Дляработы с Z-буфером используются следующиепроцедуры:
· procedure CreateBuffer(out Buffer: TBuffer)– процедура для выделения памяти для Z-буфера;
· procedure ClearBuffer(var Buffer: TBuffer)– очистка буфера – его заполнение минимальным значением глубины;
· procedure FreeBuffer(var Buffer: TBuffer)– освобождение памяти, занимаемой буфером.
2.2.3.3Буфер кадра
Крометого, необходим и буфер кадра. Буфер кадра в данной работе представленстатическим массивом (это ограничение обусловлено использованием функции BitBlt, обеспечивающей быстрый выводизображения):
sWidth = 500;
sHeight = 650;
TScreen = array [0..sWidth — 1, 0..sHeight — 1] of Integer.
Передвыводом очередного кадра буфер кадра должен быть очищен. Для этого предназначенапроцедура
· procedure ClearScreenBuffer;
2.2.3.4Процедуры визуализации ландшафта
Длявизуализации треугольников ландшафта и ландшафта в целом предназначеныследующие процедуры:
· procedureFillTriangleNormal (T: TTriangle; var Buffer: TBuffer; dX, dY: Integer;Scale: Real; LightPos: TPoint3) – закрашивание треугольника T методом гранения.Используется Z-буфер Buffer, используются экранные смещения dX и dY, коэффициент масштабирования Scale, положение источника света задается точкой LightPos;
· procedureFillTriangleGouraud(T: TTriangle; var Buffer: TBuffer; dX, dY: Integer;Scale: Real; LightPos: TPoint3) – процедура, реализующая метод закраски Гуро. Аргументыаналогичны аргументам предыдущей процедуры;
· procedureFillTrianglePhong(T: TTriangle; var Buffer: TBuffer; dX, dY: Integer; Scale:Real; LightPos: TPoint3) – процедура, реализующая метод закраски Фонга. Аргументыаналогичны аргументам предыдущей процедуры;
· procedure DrawLightSource(P: TPoint3;dX, dY: Integer;Scale: Real; Buffer: TBuffer) – процедура для вывода окружности(по алгоритму Брезенхема), обозначающей положение источника света. Положениеисточника цвета задается точкой P.Остальные параметры аналогичны параметрам предыдущих функций;
· procedure DrawLine(S, E: TPoint; Color: TRGBColor) – процедура вывода линии по алгоритму ЦДА. Аргументы S и E – точки начала и конца отрезка, Color определяет цвет отрезка;
· procedure DrawTriangle(T: TTriangle) – вывод каркаса треугольника в буфер кадра;
· procedure DrawWireTriangles(Triangles: TTriangles; dX, dY: Integer; Scale: Real)– вывод треугольников ландшафта в каркасном режиме;
· procedure DrawSolidTriangles(Triangles: TTriangles; var Buffer: TBuffer;dX, dY: Integer;Scale: Real; Light: TLightType; LightPos: TPoint3; ShowLightSource: boolean)– вывод треугольников ландшафта в режиме сплошной закраски. Параметрыпроцедуры:
o Triangles– треугольники ландшафта;
o Buffer – Z-буфер, используемый при визуализации;
o dX, dY – экранные смещения по горизонтали и вертикали;
o Scale – коэффициент масштабирования;
o Light – определяет метод закраскитреугольников. TLightType — перечисляемый тип, он определяется следующим образом:
TLightType = (Normal, Gouraud, Phong);
o LightPos – точка, задающая положениеисточника света;
o ShowLightSource – логическая переменная, определяющая,отображается ли источник света;
· procedure DrawScene(Triangles: TTriangles; View: TViewType; Light: TLightType; LightPos: TPoint3; ShowLightSource: boolean;var Buffer: TBuffer;dX, dY: Integer;Scale: Real; DC: Integer; NHDC: HDC; HBMP: HBITMAP) – основная процедура, объединяющая в себе все методым режимы вывода сцены.
Аргументы,которые не были описаны в процедуре DrawSolidTriangles:
o View – переменная определяющая режимотображения треугольников — каркасный или сплошной. TViewType – перечисляемый тип, его описание — TViewType = (Wire, Solid);
o DC, NHDC, HBMP –переменные, используемые при выводе изображения с помощью функции BitBlt.
2.2.3.2Тип и структура файла для хранения ландшафта
Файлы,используемые для хранения информации о треугольниках ландшафта, имеютрасширение LND и являются типизированными. Былвыбран именно этот тип файлов, так как использование текстовых файловзначительно замедлило бы процесс загрузки ландшафтов, а для работы снетипизированными файлами пришлось бы разрабатывать сложные процедурыввода/вывода (на основе доступных процедур низкого уровня для работы с файлами),в то время как прирост производительности был бы незначительным.
Впрограмме файлы ландшафтов описываются следующим образом: File of TTriangle;
Дляработы с файлами ландшафта предусмотрена следующая функция:
function LoadTrianglesFromFile(FileName: string): TTriangles;
Единственныйее аргумент — имя файла, из которого будет считываться информация отреугольниках ландшафта.
2.2.3.3Распределение программы по модулям
Таблица2.2.3.3.1. Распределение программы «Просмотр ландшафта» по модулямИмя модуля Описанные типы Назначение модуля AboutUnit.pas - Модуль формы «О программе» HelpUnit.pas - Модуль формы «Помощь» L_ExtRegUnit.pas - Модуль регистрации расширения LND L_FileUnit.pas - Модуль работы с файлами L_GraphicsUnit.pas TBuffer, TScreen, TViewType, TLightType Модуль реализации процедур визуализации L_MathUnit.pas TRGBColor, TPoint3, TTriangle, TTriangles Модуль реализации вычислений LandscapePositionUnit.pas - Модуль формы «Положение ландшафта» LightParamsUnit.pas - Модуль формы «Параметры источника света» MainUnit.pas - Главный модуль программы StatisticsUnit.pas - Модуль формы «Статистика» ViewParamsUnit.pas - Модуль формы «Визуальные параметры»
2.2.3.4Связи между модулями программы
/>
Рис.2.2.3.4.1. Связи между модулями программы «Просмотр ландшафта»
3. Технологическая часть
3.1 Выбор языка программирования
Приразработке программного комплекса использовался язык программирования высокогоуровня Object Pascal в составе среды визуального программирования Borland Delphi 7.
Выборбыл остановлен именно на этом языке программирования, так как он позволяетсоздавать программы с четкой модульной организацией, позволяющей реализовыватьстрогое разделение уровней абстракции. Кроме того, среда Delphi предоставляет программисту обширнуюбиблиотеку визуальных компонентов, позволяющих создавать качественный интерфейспроизвольной сложности.
3.2 Описание программного комплекса
Всостав программного комплекса входят два приложения: «Редактор карт» и«Просмотр ландшафта».
3.2.1 Программа«Редактор карт»
3.2.1.1Общие сведения
Программа“Редактор карт” служит для создания ландшафтов на основе плоских картизообластей. Данные карты могут быть созданы с помощью средств редактирования,предоставляемых “Редактором карт” или загружены в редактор из BMP-файлов (требуемая глубина цвета — 24бита).
Получаемыекарты хранятся в файлах с расширением HCL. Файлы этого типа являются текстовыми, они содержат информацию о цветах,использованных для задания изообластей, о высотах, соответствующих перечисленнымцветам, а также непосредственно о разметке карты. При этом для записи пикселейкарты используется групповое кодирование.
3.2.1.2Интерфейс программы
Призапуске программы на экране появляется главная и инструментальная формы.
/>
Рис.3.2.1.2.1. Формы, отображаемые при запуске «Редактора карт»
Главноеменю программы содержит следующие подменю:
1) Файл:
· Создать — создатьновую карту;
· Открыть — открытьуже существующую карту с помощью специального диалога;
· Сохранить — сохранить текущую карту в файл;
· Выход — прекратить работу с программой;
2) Инструменты иокна:
· Обработка карты — определяет видимость инструментальной формы «Обработка карты»;
· Запустить«Просмотр ландшафта» — запускает приложение «Просмотрландшафта», в которое загружается ландшафт, соответствующий текущей карте;
· Зарегистрироватьсобственное расширение — зарегистрировать в реестре расширение HCL, что даст возможность открывать файлыданного типа двойным щелчком мыши;
· Отменитьрегистрацию расширения — удалить из реестра информацию о расширении HCL;
3) О программе:
· О программе — вывод формы с некоторой информацией о данной программе;
· Помощь — выводсправочной информации о программе.
Справаот некоторых пунктов меню указаны сочетания клавиш, реализующие действия,соответствующие данному пункту меню.
3.2.1.2.1 Инструментальнаяформа «Обработка карты»
/>
Рис.3.2.1.2.1.1. Инструментальная форма «Обработка карты»
Плоскаякарта, редактируемая и создаваемая с помощью «Редактора карт» представляетсобой совокупность изообластей высот. Для задания этих областей используются соответствия«Цвет-Высота», то есть карте, размеченной цветами, соответствует bitmap высот, каждая точка которогохарактеризуется высотой. Для создания трехмерного ландшафта на основе плоскойкарты, bitmap высот разбивается на треугольники снекоторым заданным шагом, то есть ландшафт состоит из трехмерных треугольников.
Шагразбиения на треугольники по горизонтали и вертикали задается с помощью полейввода «Шаг по X» и «Шаг по Y». Единица измерения этихвеличин — пиксель.
Кнопка«Разбить на треугольники» служит для вывода плоских треугольниковразбиения на карту.
Кнопка«Обновить карту» удаляет с карты выведенные треугольники.
Кнопка«Обновить ландшафт» предназначена для создания bitmap’а высот и, на его основе, с заданнымишагами разбиения, — ландшафта.
Группа«Сглаживание ландшафта» позволяет сгладить ландшафт — придать егоочертаниям большую плавность.
Кнопка«Показать разрез» выводит специальную форму, на которой отображаетсяразрез ландшафта вертикальной плоскостью, заданной ранее на карте прямой.
3.2.1.2.2 Инструментыглавной формы
Большуючасть главной формы занимает область рисования, которая отображает и позволяетредактировать карту.
Еслисоздается новая карта, то сначала необходимо задать соответствия«Цвет-высота», это делается с помощью кнопки «Добавитьцвет» или нажатия клавиши Insert,когда фокус ввода находится на списке цветов. После выполнения этих действийпоявляется форма «Определение цвета», которая позволяет добавлять илиредактировать существующие соответствия «Цвет-высота». Список цветовсодержит информацию о существующих соответствиях. Его элементы можно удалять спомощью кнопки «Удалить цвет» или нажатия клавиши Delete, когда фокус ввода находится насписке. При удалении, области, занимаемые удаляемым цветом, заполняются цветомнулевой высоты.
Дляредактирования карты служат следующие инструменты:
· «Карандаш»- позволяет чертить произвольные кривые;
· «Кисть»- заполнение областей карты;
· «Отрезок»;
· «Контурныйпрямоугольник»;
· «Заполненныйпрямоугольник»;
· «Контурныйэллипс»;
· «Заполненныйэллипс».
Рисованиеэтих примитивов осуществляется с помощью мыши при удерживаемой левой кнопке.Цвет рисуемых примитивов определяется с помощью списка цветов и отображается наспециальной панели в нижнем правом углу формы.
Кромеописанных, существуют также следующие инструменты:
· «Ножницы»- для задания на карте прямой, определяющей вертикальную плоскость сечения.Просмотр сечений позволяет получать представление о ландшафте без егопостроения. Для получения разреза следует сначала задать секущую, а затемнажать на кнопку «Получить разрез» формы «Обработка карты»;
· «Пипетка»- служит для определения цвета произвольного пикселя на карте.
3.2.1.3Работа программы
3.2.1.3.1 Требованияк расположению файлов программы
Исполняемыйфайл программы — MapEditorProj.exe. В папке, где размещен этот файл должнанаходиться пиктограмма HCL_Icon.ico. Эта пиктограмма потребуется при регистрациирасширения HCL — она будет присвоена файлам с этим расширением. Кроме того, в основнойпапке MapEditorProj должна находиться программа LandscapeProj, т.к. в противномслучае будет невозможна их интеграция. Желательно наличие в основной папкепрограммы каталогов ScreenShots и Landscapes. В каталоге ScreenShots будутпомещаться сохраненные изображения ландшафтов (в формате BMP, размер каждогофайла ~ 1.23 МБ), создаваемые программой «Просмотр ландшафта». Вкаталоге Landscapes предполагается хранение файлов ландшафтов(*.lnd) и плоскихкарт(*.hcl), на основе которых строятся ландшафты.
3.2.1.3.2 Созданиекарт
Создатькарту изообластей можно двумя способами:
· загрузить ужеимеющееся изображение в формате BMP (поддерживается работа только с 24-битнымцветом). В этом случае программа автоматически выделит все имеющиеся наизображении цвета и поместит их в список. Далее останется только задать всоответствие цветам высоты, т.к. по умолчанию присваивается значение-2147483648 (треугольники, имеющие вершины с такой высотой, не выводятся при построенииландшафта).
· создать новуюкарту и разметить ее самостоятельно, добавляя соответствия по своему желанию.Создание новой карты начинается с появления формы «Параметрыизображения», которая позволяет задать размер создаваемой карты.
3.2.1.3.3 Сохранениекарт
Сохранениепроизводится с помощью специального диалога, в котором определятся путь сохраненияфайлов. При сохранении создаются 3 файла:
· карта изообластей*.hcl;
· ландшафт *.lnd;
· *.bmp сизображением полученной карты.
3.2.1.3.4 Открытиекарт
Возможназагрузка двух типов файлов — BMP и HCL. Загрузка может происходить тремяспособами:
· через диалоготкрытия в самой программе;
· двойным щелчкомпо файлу (только для HCL-файлов после регистрации этого расширения);
· путемперетаскивания файла на форму приложения c помощью мыши.
3.2.2 Программа«Просмотр ландшафта»
3.2.2.1Общие сведения
Программа«Просмотр ландшафта» предназначена, как следует из ее названия, для просмотраландшафтов, создаваемых на основе карт изообластей, с помощью программы «Редакторкарт».
3.2.2.2Интерфейс программы
Призапуске программы на экране появляется главная и инструментальная формы.
/>
Рис.3.2.2.2.1. Формы, отображаемые при запуске «Просмотра ландшафта»
Главноеменю программы содержит следующие подменю:
1) Файл:
· Открыть — загрузить ландшафт с помощью диалога открытия файлов;
· Выход — прекратить работу с программой;
2) Настройки и окна:
· Положениеландшафта — определяет видимость инструментальной формы «Положениеландшафта»;
· Визуальныепараметры — видимость формы «Визуальные параметры»;
· Параметрыисточника света — видимость формы «Параметры источника света»;
· Статистика — видимость формы «Статистика»;
· Сохранитьизображение — сохранить текущее изображение загруженного ландшафта в видеграфического файла, помещаемого в папку ScreenShots, расположенную в основномкаталоге программы;
· Зарегистрироватьсобственное расширение — зарегистрировать в реестре расширение LND, что даст возможность открыватьфайлы данного типа двойным щелчком мыши;
· Отменитьрегистрацию расширения — удалить из реестра информацию о расширении LND;
3) О программе:
· О программе — вывод формы с некоторой информацией о данной программе;
· Помощь — выводсправочной информации о программе.
Справаот некоторых пунктов меню указаны сочетания клавиш, реализующие действия,соответствующие данному пункту меню.
3.2.2.2.1 Инструментальнаяформа «Положение ландшафта»
/>
Рис.3.2.2.2.1.1. Инструментальная форма «Положение ландшафта»
Даннаяформа предназначена для управления положением ландшафта в пространстве. Онасодержит следующие элементы управления:
· поле ввода«Приращение координат» — предназначено для задания величины шагаперемещения ландшафта в экранной системе координат;
· поле ввода«Изменение масштаба» — задание величины процентного изменения коэффициентамасштабирования;
· поле ввода«Приращение угла» — задание величины шага поворота ландшафта(задается в градусах);
· поле ввода«Центр вращение» — ввод трех координат центра вращения ландшафта всистеме координат ландшафта;
· кнопки группы«Переместить» предназначены для перемещения и масштабированияландшафта. Эти же действия можно выполнять с помощью мыши или клавиатуры. Мышь:перемещение осуществляется при удерживаемой клавише Shift, для масштабированияиспользуется колесико мыши; Клавиатура: стрелочные клавиши для перемещения,клавиши '+', '-' для масштабирования;
· кнопки группы«Повернуть» используются для вращения ландшафта относительносоответствующих осей. Вращение ландшафта также может производиться с помощьюмыши или клавиатуры. Мышь: горизонтальное смещение — поворот относительно осиZ, вертикальное — относительно X, горизонтальное с удерживаемой клавишей Alt — относительно Y; Клавиатура: относительно X — Insert и Delete, Y — Home и End, Z — PageUp и PageDown;
· кнопка «Висходное положение» предназначена для возвращения ландшафта и источникасвета в то положение, в котором они находились непосредственно после загрузки.
3.2.2.2.2 Инструментальнаяформа «Визуальные параметры»
/>
Рис.3.2.2.2.21. Инструментальная форма «Визуальные параметры»
Этаформа предназначена для выбора методов и параметров визуализации ландшафта. Дляэтого служат следующие элементы интерфейса:
· группа «Видландшафта» позволяет выбрать метод построения ландшафта;
· группа«Закраска» определяет метод визуализации треугольников ландшафта;
· панель «Цветландшафта» определяет базовый цвет ландшафта. Выбор цвета осуществляется спомощью диалога, вызываемого щелчком по панели.
3.2.2.2.3 Инструментальнаяформа «Параметры источника света»
/>
Рис.3.2.2.2.3.1. Инструментальная форма «Параметры источника света»
Даннаяформа предназначена для управления источником света. Присутствуют следующие элементыинтерфейса:
· поле ввода«Координаты» позволяет задавать координаты источника света в системекоординат ландшафта;
· кнопки группы«Переместить» предназначены для переноса источника света вдольсоответствующих осей. Используется приращение координат, заданное на форме«Положение ландшафта». Перемещение источника возможно также и спомощью мыши и клавиатуры. Мышь (с удерживаемой клавишей Ctrl): горизонтальноеперемещение — перемещение вдоль X, вертикальное — вдоль Y; Клавиатура (приудержании Ctrl): стрелочные клавиши — перемещение вдоль соответствующих осей,клавиши '+' и '-' — вдоль оси Z,
· кнопки группы«Повернуть» позволяют вращать источник света относительно соответствующихосей. Используется приращение угла с формы «Положение ландшафта».Вращение источника света предусмотрено также и с помощью клавиатуры (приудержании Ctrl): клавиши Insert и Delete, Home и End, Page Up и Page Down — вращение относительно осей X, Y и Z соответственно;
· переключатель«Показывать источник» определяет видимость источника света. Онсхематично изображается в виде желтого кружочка. Кружочек сплошной, еслиисточник находится между наблюдателем и ландшафтом, в противном случае он контурный;
· группа«Вращение по таймеру» позволяет инициировать вращение источника светаотносительно выбранных осей по таймеру;
3.2.2.2.4 Инструментальнаяформа «Статистика»
/>
Рис.3.2.2.2.4.1. Инструментальная форма «Статистика»
Этаформа содержит информацию о программе и текущем ландшафте. В частности, послезагрузки ландшафта на нее выводится информация о времени загрузки (в миллисекундах),числе треугольников ландшафта, его линейных размерах (в пикселях), а также ораспределении памяти для хранения ландшафта, Z-буфера, буфера кадра.
Кнопка«Определить» позволяет определить число кадров вывода ландшафта,рассчитываемых и выводимых за 1 секунду.
3.2.2.3Работа программы
3.2.2.3.1 Требованияк расположению файлов программы
Исполняемыйфайл программы — LandscapeProj.exe. В папке, где размещен этот файл, должнанаходиться пиктограмма LND_Icon.ico. Эта пиктограмма потребуется при регистрациирасширения LND — она будет присвоена файлам с этим расширением. Остальные требованияаналогичны описанным в Разделе, касающемся программы “Редактор карт”.
3.2.2.3.2 Открытиефайлов ландшафтов
Открытиефайлов *.lnd возможно тремя способами:
· непосредственночерез меню программы с помощью специального диалога;
· двойным щелчкомпо файлу ландшафта (после регистрации расширения);
· путемперетаскивания файла на форму приложения. После открытия файла просмотрландшафта осуществляется с помощью уже описанных инструментальных форм.
3.2.3 Системныетребования
Системныетребования программного комплекса создаются главным образом приложением«Просмотр ландшафта», так как оно намного более требовательно к системным ресурсам,чем «Редактор карт». Они таковы:
· операционнаясистема Windows 98/Me/2000/XP/2003Server;
· процессор c тактовой частотой 400 МГц;
· объем оперативнойпамяти 64 МБ;
· видеокарта,обеспечивающая графическое разрешение 1024x768 и глубину цвета 24 бита;
· 35 МБ дисковогопространства.
4. Экспериментально-исследовательскаячасть
Тестированиепроводилось на компьютере Pentium IV — 2.67 GHz/768 Mb/GeForce4 MX-440, AGP 8x, DDR 128 Mb.
Былипроведены следующие исследования:
1) исследованиевременных характеристик алгоритмов закраски – для 3 реализованных в работеалгоритмов были произведены исследования зависимости скорости работы от числатреугольников ландшафта;
2) исследованиевременных характеристик загрузки различных типов LND-файлов (текстового и типизированного);
3) исследованиерезультатов использования метода группового кодирования при создании HCL-файлов.
Вкачестве тестовой карты в исследованиях № 1 и 2 была взята карта “Алтай.hcl”. Размеры карты “Алтай.hcl”: 430x409x39 пикселей(X x Y x Z).
4.1. Исследование № 1
Условиятеста: в «Редактор карт» была загружена выбранная карта, далее, с изменяемым от1 до 20 пикселей, шагом разбиения карты, строились ландшафты. Во время тестовникаких манипуляций с изображением ландшафта не производилось – оно оставалосьв том положении, в котором находилось непосредственно после загрузки. Результатытеста приведены в таблице:
Таблица4.1.1. Результаты исследования № 1
Метод закраски и
число кадров в секунду
Число
треугольников ландшафта
Шаг разбиения
(X x Y) Однотонная Гуро Фонг 3 3 3 350064 1 x 1 8 7 6 87720 2 x 2 12 11 9 38896 3 x 3 17 15 10 22032 4 x 4 21 18 12 14104 5 x 5 24 21 12 9792 6 x 6 27 23 13 7316 7 x 7 30 25 14 5508 8 x 8 33 27 14 4416 9 x 9 35 28 14 3526 10 x 10 37 29 15 2964 11 x 11 39 30 15 2448 12 x 12 40 31 15 2112 13 x 13 41 32 15 1860 14 x 14 42 32 15 1624 15 x 15 43 33 16 1404 16 x 16 44 34 16 1248 17 x 17 46 35 16 1104 18 x 18 46 35 16 1012 19 x 19 49 36 16 924 20 x 20
Длябольшей наглядности приведем графики зависимости числа кадров, обрабатываемыхза 1 секунду, от шага разбиения и числа треугольников ландшафта:
/>
Рис.4.1.1. Результаты исследования № 1
Изприведенных выше таблицы и диаграммы можно сделать следующие выводы:
· увеличение числатреугольников ландшафта вызывает уменьшение числа кадров, обрабатываемых за 1секунду;
· закраска по Фонгутребует наибольших вычислительных ресурсов по сравнению со всеми остальнымиметодами, в тоже время скорость ее работы меньше всего зависит от числатреугольников ландшафта;
· при увеличениичисла треугольников ландшафта разница в скорости работы рассмотренныхалгоритмов уменьшается. Когда карта разбивается на треугольники с шагом 1 x 1, различие между алгоритмамистановится минимальным – как по скорости работы, так и по качеству получаемогоизображения (однотонная закраска выглядит менее качественно, чем закраска Фонгаи Гуро).
4.2. Исследование № 2
Приразработке программного комплекса формат файла LND (для хранения информации о треугольниках ландшафта)менялся. На начальной стадии разработки эти изменения касались толькодобавления новых полей в записи, хранимые в файле, тип файла был текстовым. Нопостепенно карты ландшафтов, разрабатываемых в «Редакторе карт», становилисьвсе более сложными, они требовали все большей детализации. Поэтому возрасталиобъемы LND-файлов, При этом время загрузкизначительно увеличивалось и становилось совершенно неудовлетворительным. Врезультате было принято решение изменить тип LND-файла, сделать его типизированным. После этого времязагрузки LND-файлов в «Просмотр ландшафта»значительно сократилось. Следует заметить, что скорость записи информации втекстовый и типизированный файлы практически не отличается. Ниже приведенывременные характеристики загрузки текстовых и типизированных LND-файлов.
Таблица4.2.1. Результаты исследования № 2Шаг разбиения (X x Y) Тип LND-файла Текстовый Типизированный
Объем файла
(Мб) Время загрузки (с) Объем файла (Мб) Время загрузки (с) 1 x 1 0,113 1,469 0,310 0,016 2 x 2 0,140 2,657 0,390 0,016 3 x 3 0,175 4,609 0,480 0,031 4 x 4 0,233 7,140 0,640 0,047 5 x 5 0,313 10,828 0,860 0,047 6 x 6 0,451 19,515 1,240 0,078 7 x 7 0,704 46,968 1,930 0,125 8 x 8 1,210 157,812 3,410 0,187 9 x 9 2,740 662,781 7,700 0,437 10 x 10 10,90 4102,093 30,71 1,922
Для большейнаглядности построены графики зависимости времени загрузки файла от его объема:
/>
/>
Рис.4.2.1. Результаты исследования № 2
Изпроведенного исследования можно сделать следующие выводы:
· время загрузкиландшафта из текстового файла значительно больше времени загрузки из типизированногофайла (при малых объемах файлов это различие составляет десятки раз, приувеличении объемов оно достигает тысяч (!!!) раз);
· такое отличиевремени загрузки, очевидно, объясняется постоянным преобразованием информациииз символьного представления в числовое (работой функций Val или StrToFloat) при загрузке из текстового файла, вто время как при чтении из типизированного файла такого преобразования нетребуется;
· использованиетипизированных файлов полностью оправдано за счет колоссального увеличенияскорости загрузки ландшафтов, даже несмотря на почти троекратное увеличениеобъема получаемых LND-файлов.
4.3 Исследование № 3
Как ужеговорилось, при создании HCL-файлов, хранящих информацию о разметке карт,используется метод группового кодирования. Этот метод уже был описан выше,поэтому в данном разделе будет приведена информация, доказывающая эффективностьиспользования метода, и выяснена степень этой эффективности.
Демонстрациярезультатов использования метода была проведена на следующем наборе карт(размеры приведены в пикселях):
· Австралия.hcl (500 x 395);
· Алтай.hcl (430 x 409);
· Африка.hcl (700 x 730);
· Несжимаемый.hcl (200 x 200);
· Тест сглаживания.hcl (400 x 200);
· Южная Америка.hcl (735 x 1125).
Нижеприведена таблица, которая позволила бы выяснить степень сжатия изображения прииспользовании метода группового кодирования:
Таблица4.3.1. Результаты исследования № 3Название карты
Размеры карты
(пиксели)
Размер BMP-файла
(Кб)
Размер HCL-файла
(Кб) Отношение сжатия Австралия.hcl 500 x 395 771 36 21:1 Алтай.hcl 430 x 409 687 78 9:1 Африка.hcl 700 x 730 1460 60 24:1 Несжимаемый.hcl 200 x 200 117 156 1:1,3 Тест сглаживания.hcl 400 x 200 312 10 31:1 Южная Америка.hcl 735 x 1125 3150 107 29:1
Изпроведенного исследования можно сделать следующие выводы:
· применение методагруппового кодирования в данной работе полностью оправдано, поскольку прииспользовании его в отношении карт изообластей высот, наблюдаются достаточновысокие показатели сжатия (от 9:1 до 29:1, карта «Тест сглаживания» неучитывается, так как она не является реальной картой). Единственным недостаткомиспользования этого метода является незначительное увеличение времени загрузкикодированных файлов в программу «Редактор карт» (это не демонстрировалось вданном исследовании);
· единственныйслучай, когда размер кодированного файла превышает размер исходного файла,наблюдается на специальном примере, призванном продемонстрировать недостатокметода.
5. Заключение
Разработанныйпрограммный комплекс отвечает всем предъявляемым к нему требованиям. Онобеспечивает возможность создания карт изообластей («Редактор карт») ипостроения в реальном времени на их основе трехмерных изображений ландшафтов(«Просмотр ландшафта»). В нем реализованы все рассмотренные в данной работеалгоритмы машинной графики. Проведены исследования работы алгоритмов наразличных наборах исходных данных. Тем не менее, существует множество путейусовершенствования описанного программного комплекса.
Во-первых,построение ландшафта возможно только на основе четко размеченной картыизообластей высот – невозможно использование, например, файла, полученного врезультате сканирования некоторой карты. Но подготовка (разметка) картыизообластей вручную – очень трудоемкий процесс. Автоматизация процесса разметкизначительно расширила бы возможности программного комплекса.
Во-вторых,получаемые изображения трехмерных ландшафтов выглядят не реалистично – они лишьпозволяют получить представление о рельефе рассматриваемой области. Кроме того,изображение просматриваемого ландшафта не предоставляет пользователю информациио географических объектах, присутствующих в области, представляемой ландшафтом.Добавление возможности текстурирования и подписи географических объектовповысили бы информативность получаемого изображения ландшафта.
Однако,описанные проблемы очень сложны (распознавание и разметка карт), а некоторые изних выходят за рамки машинной графики.
6. Список литературы
1. Роджерс Д. Алгоритмическиеосновы машинной графики: пер. с англ.— М.: Мир, 1989.— 512 с.: ил.
2. Порев В. Н.Компьютерная графика. – СПб.: БХВ-Петербург, 2002. – 432 с.: ил.
3. Никулин Е. А.Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. – 560с.: ил.
4. Авдеева С.М.,Куров А.В. Алгоритмы трехмерной машинной графики: Учебное пособие. – М.: Изд-воМГТУ им. Н.Э. Баумана, 1996. – 60 с.: ил.
5. АрхангельскийА.Я. Приемы программирования в Delphi.– М.: ООО «Бином-Пресс», 2003. – 784 с.: ил.
6. http://www.xdev.ru– «Генерация трехмерных ландшафтов».