Tough Terrain Generator

Авторы:

1.	Авдеев Игорь	Avdeev Igor	10-2 класс
2.	Золотов Владимир	Zolotov Vladimir	8-2 класс
3.	Марчукова Татьяна	Marchukova Tatjana	10-3 класс
4.	Николаенко Валерия	Nikolaenko Valerija	10-3 класс
5.	Петров Юрий	Petrov Jury	8-1 класс
6.	Письмак Дарья	Pis'mak Darija	9-1 класс
7.	Столяров Андрей	Stoljarov Andrey	10-3 класс
8.	Тимофеев Антон	Timofeev Anton	9-1 класс

Научный руководитель проекта: Галинский Виталий Александрович

Presentation

Введение

Данный программный комплекс предназначен для моделирования рельефа местности. Разработанный алгоритм позволяет синтезировать ландшафты по заданному пользователем очертанию с помощью набора изолиний или карты высот. При построении изображений на основе карты высот, производится триангуляция точек с последующей детализацией посредством фрактального подразделения. Для получения изображения на основе изолиний (горизонталей) строится регулярная сетка посредством интерполяции высот для промежуточных точек. При выводе синтезированного результата разработаны различные методы визуализации.

Реализация

Исходные данные

Поставленные задачи предполагают два вида исходных данных: задание макета рельефа отдельными точками и изолиниями, что и определяет работу пользователя с программой. Разработанный графический редактор позволяет осуществлять набор исходной геометрии посредством ввода параметров пикетов (точек на местности) и изолиний (горизонталей). Для каждой точки исходных данных задается позиция и высота. Для ускорения функций редактирования (изменения параметров, удаления и т.п.) реализован алгоритм поиска на основе квадратичных деревьев (quad-tree).

Построение и синтезирование

Для построения рельефа местности нами были разработаны два различных алгоритма перевода исходной геометрической информации в полигональный вид. Оба алгоритма адоптированы под конкретный способ задания исходных данных: отдельными пикетами и набором изолиний.

Полигонизация по пикетам

Для обработки отдельных точечных данных - пикетов - с целью построения поверхности рельефа местности реализован алгоритм триангуляции точек на плоскости. В качестве критерия триангуляции выбран критерий Делоне - в процессе получения треугольников на плоскости ни одна из исходных точек не может попасть в описанную окружность вокруг любого из полученных треугольников.

Детализация

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

Построение карт высот

При обработке изолиний используется альтернативный способ задания геометрии - регулярная сетка, некоторым узлам которой сопоставляется конкретная высота, в соответствии с начальными данными. Далее идет заполнение остальных узлов сетки, на основе интерполяции высот.

Визуализация

Для визуализации синтезированного рельефа местности используется два способа вывода: вывод произвольного множества треугольников (triangles mesh) и регулярных сеток высот (grid - height fields). Оба способа позволяют получать изображение в проволочном виде (wire frame) и посредством закрашенных многоугольников. В последнем случае применяется модель освещения Гуро.

Заключение

Разработанная система является удобным и простым средством для моделирования рельефа местности. Благодаря разработанным алгоритмам оптимизации достигнута приемлемая скорость получения результата.

Литература

• Michael J. Laszlo. "Computation Geometry and Computer Graphics in C++". Prentice Hall, Inc., A Simon & Schuster Company, 1996.
• В. Н. Порев. "Компьютерная графика". С.-Петербург: BHV-Петербург, 2002.
• Р. Саймон "Microsoft WindowsR 2000 API. Энциклопедия программиста". , 2000.