РЕФЕРАТ
ЛАНДШАФТ, АЛГОРИТМ, DIAMOND-SQUARE, ШУМ, ПЕРЛИН, КАМЕРА, ОСВЕЩЕНИЕ, ТЕКСТУРА, ШЕЙДЕР, DIRECTX, C++
В данной работе представлена реализация генерации и отображения ландшафта
в трехмерной плоскости, с помощью средств языка C++, C# и DirectX, в среде
Visual Studio 2015.
В настоящее время компьютерная графика используется во многих областях, таких как наука, медицина, архитектура, производство кино, реклама и компьютерные игры. Конструкторы, разрабатывая новые модели автомобилей и самолетов, используют трехмерные графические объекты, чтобы представить окончательный вид изделия. Архитекторы создают на экране монитора объемное изображение здания, и это позволяет им увидеть, как оно впишется в ландшафт.
В некоторых задачах решают проблему построения реалистичных ландшафтов. Особенно это касается игр жанров RPG и MMORPG. Разработка RPG занимает более 2 лет, а MMORPG более 5 лет. Более того стоимость разработки подобных проектов очень высока. Один из способов удешевить стоимость изготовления это автоматизировать некоторые процессы.
Один из трудоемких процессов это моделирование, в частности ландшафтов. Ландшафт - достаточно большой, обозримый простым глазом участок поверхности, отличающийся от соседних участков характерными индивидуальными чертами.
Ландшафты можно создавать вручную, но этот процесс занимает достаточное
продолжительное время. Можно автоматизировать процесс создания грубой модели
ландшафта с последующей обработкой.
Существует различные определения ландшафта, но одно наиболее точно отражает его.
Ландшафт - достаточно большой, обозримый простым глазом участок поверхности, отличающийся от соседних участков характерными индивидуальными чертами.
Под понятием реалистичный ландшафт подразумевается, то, что ландшафт, полученный каким-то не естественным способом, будет выглядеть похоже по ряду признаков на естественный ландшафт. К таким признакам относят:
- гладкий переход между поверхностями не подверженные эрозии;
- эрозия влияет на рельеф с точки зрения воздействия воды на природный материал;
- однородный рельеф;
- единый геологический фундамент;
- иметь уникальную структуру.
Другими словами полученная территория должна представлять собой не делимое по внешним признакам территорию с особыми факторами развития.
В настоящее время компьютерная графика используется все чаще. Она используется в видео играх и различного рода рендер такого как рекламные ролики, фильмы и мультфильмы.
Процесс создание 3D-моделей занимает достаточно продолжительное время. Чтобы сократить время на создание ландшафтов можно автоматизировать этот процесс.
На рынке представлены готовые решения, такие как Vue Espri и Terragen.Esprit это профессиональная программа для моделирования окружающей среды, ориентированный на 3D-художников. Есть возможность экспортировать в различные 3D-форматы, такие как 3ds, lwo, obj, dfx и как рендар в форматов tiff, tga, pict, bmp, gif, jpeg, png. Распространяется по цене 199 долларов США в месяц.это программа для ландшафтного моделирование и анимации. Имеет следующие достоинства:
- импорт карты высот;
- малый объем дистрибутива;
- моделирование неба и облаков.
Так же он имеет ряд недостатков:
- не предусмотрена возможность повтора или отмены действий;
- невозможно создать растительность;
- невозможность импорта 3D-моделей.
Распространяется по цене 349 долларов США за базовый набор и за 699 за полную комплектацию.
Создание комплекса для генерации ландшафтов подразумевает решение следующих задач:
- генерация ландшафта с учетом заданных высот, размера карт, количество гор и крутизны гор;
- предоставление библиотеки для внедрения в приложение;
- программа для взаимодействия с библиотекой для получения 3D-модели или карты высот.
- визуализатор для демонстрации результата;
- экспорт 3D-модели в формате obj;
- экспорт карты высот в формате bmp.
Алгоритм diamond-square это алгоритм для генерации фрактальных ландшафтов. Он основан на одномерном алгоритме midpoint displacemet.
Суть алгоритма заключается в следующем. Сначала задается высота на концах отрезка и разбивается точкой посередине на два подотрезка. Высота этой точки определяется по формуле:
Суть его заключается в следующем. Изначально мы любым образом задаем высоту на концах отрезка и разбиваем его точкой посередине на два под-отрезка. Эту точку мы смещаем на случайную величину по формуле:
= (hL + hR) / 2 + random(- R * l, R * l)
где hL - левая граница отрезка;R - правая граница отрезка;- длина отрезка;- коэффициент «шероховатости».
Далее, повторяем разбиение и смещение для каждого из полученных подотрезков. И так далее - пока отрезки не станут длиной в одну условную единицу. Пример работы алгоритма можно увидеть в приложении А на рисунке А.1.
Существует два способа обобщения данного алгоритма. Здесь и далее считается, что карта квадратная и ее размер ее стороны является равным значение степени двойки.
Первый алгоритм называется midpoint displacement. Присваиваем случайные значения высот на всех четырех угла карты и разбиваем ее на четыре равные части. Центральная точка получается усреднением высот с 4 угловых точек и серединная точка на стороне усреднением пары точек лежащих на концах этой стороны. Так же необходимо добавить случайного отклонение путем сдвига точки вверх или вниз пропорционально стороне квадрата. Повторяем данный шаг для под квадратов [1].
Начнем с присвоения случайных высот четырем углам всей карты целиком и разобьем её на четыре равных квадрата. В каждом из них известно значение в одном из углов. Точка в центре получается усреднением высот всех 4 угловых точек, а каждая серединная точка на стороне большого квадрата - усреднением пары точек, лежащих на концах соответствующей стороны. Нужно добавить немного шума - сдвинуть случайным образом центральную точку вверх или вниз (в пределах, пропорциональных стороне квадрата) - и можно повторять рекурсивно наши действия для полученных подквадратов.
Данный алгоритм имеет существенный недостаток, в результате наблюдается линейная зависимость. Второй способ уже носит имя diamond-square. Работа данного алгоритма состоит из двух шагов. Первым шагом square определяется центральная точка путем усреднением крайних точек с добавлением случайного отклонения «displacement». Вторым шагом diamond определяется высота точек лежащих на серединах сторон квадрата. Усредняются не две точки, как в алгоритме midpoint displacement, но и точки с «слева» и с «право», то есть еще две точки, полученные на шаге square. Эти точки должны быть посчитанными на предыдущем шаге, поэтому расчет необходимо вести «слоями», для всех квадратов выполняется шаг square и для всех ромбов шаг diamond, затем идет переход к меньшим квадратам. Пример работы представлен в приложении А на рисунке А.3.
Данный алгоритм имеет следующие недостатки. Для расчетов на шаге diamond используются точки, которые находятся за пределами текущей области или даже возможно за пределами карты.
Следующий недостаток это при детальном просмотре карты видны «шероховатости», множество мелких островков или просто сплошной шум.
Шум Перлина - это градиентный шум, состоящий из набора псевдослучайных единичных векторов (направлениях градиента), расположенных в определенных точках пространства и интерполированных функцией сглаживания между этими точками.
Чтобы создать функцию шума Перлина необходимы две функции: функция шума и функция интерполяции. Функция шума это специальная функция, которая принимает целое число в качестве параметра и возвращает случайное число. Важно чтобы при передаче функции два раза и более одного и того же числа, она возвращала всегда одно и тоже число. В приложении Б на рисунке Б.1 показан пример функции шума.
По плавной интерполяции между значениями, мы можем определить непрерывную функцию, которая принимает не целое в качестве параметра.
Для дальнейшего описание алгоритма необходимо ввести некоторые определения.
Синусоидальная волна, представлена в приложении Б на рисунке Б.3. Длина волны (wavelength) - это расстояние от одной вершины к другой. Амплитуда (amplitude) - это высота волны. Частота (frequency) определяется как 1/(длина волны).
Шумовая волна. В приложении Б на рисунке Б.4 представлен график функции шума, красные точки указывают на случайные значения, определенные по измерению функции. В этом случае амплитуда - это разница между минимальным и максимальным значениями, которые у функции могут быть. Длина волны - это есть расстояние от одного красного пятна к другому. Опять же частота определяется как 1/(длина волны).
Создание функции шума Перлина. Если взять много таких гладких функций, с различной частотой и амплитудой, вы можете добавить их все вместе, чтобы создать хорошо зашумленную функцию. Пример можно увидеть в приложении Б на рисунке Б.5.
Стойкость. Возникает вопрос, какая именно амплитуда и частота использована каждой из них. В одномерном примере использованы двойная частота и половина амплитуды для каждой последующей добавляемой функции шума. Это довольно распространенное явление. Таким образом, фактически, многие не рассматриваю возможность использования всего остального. Тем не менее, можно создать шум функции Перлина с различными характеристиками и с использованием других частот и амплитуд на каждом шагу. Например, чтобы создать гладкие холмы, можно использовать функции шума Перлина с большими амплитудами на низких частотах, и очень малой амплитудой на высоких частотах. Чтобы объяснить это проще, и, чтобы избежать повторения слов «амплитуда» и «частота» все время, используется единственное число для определения каждой амплитуды и каждой частоты. Эта величина называется настойчивостью (Persistence). Существует некоторая неопределенность относительно его точного смысла.
Определение настойчивости заключается в следующем: частота равняется 2 в степени i, амплитуда равно стойкость в степени i, где i - это i - тая добавочная функция шума.
Каждую добавленную последующую шумовую функцию называют октавой. Причиной этого является то, что каждая функция шума имеет частоту в два раза большую, чем предыдущая. В музыке октава также обладают этим свойством.
Если вы используете функции шума Перлина для рендеринга изображения на
экран, наступит момент, когда октава может иметь слишком высокую частоту, чтобы
быть отображаемой. Там просто может не быть достаточно пикселей на экране,
чтобы воспроизводить все мелкие детали на очень высокой функции шума. Некоторые
реализации шума Перлина автоматически складываются из шумовых функций, до тех
пор, пока пределы разрешения экрана (или другой среды) не будут достигнуты.
Кроме того, разумно остановиться при добавлении шумовой функции, когда их
амплитуда становится слишком мала, чтобы оказывать влияние на результат. Когда
именно это произойдет, зависит от уровня стойкости, общей амплитуды функции
Перлина и бита разрешения экрана [2].
Создание шумовой функции. По существу шумовая функция это генератор случайных чисел. Однако, в отличие от других генераторов случайных чисел, которые дают вам различные случайные числа каждый раз, когда вы их вызываете, эти шумовые функции выдают случайное число рассчитываемое из одного или нескольких параметров. То есть каждый раз, когда вы вводите то же число, шумовая функция будет отвечать тем же числом, что и раньше для этого числа. Но вводя другое число, она и вернет другое число.
Медианная фильтрация - метод нелинейной обработки сигналов, разработанный Тьюки. Медианный фильтр используется для подавления шума на изображениях [3].
Медианный фильтр представляет собой скользящее окно, охватывающее не четное количество элементов, изображения. Медиана всех элементов окна заменяет центральный элемент. Другими словами берутся все элементы, попадающие в окно сортируются, берется средний элемент, он заменяет собой центральный элемент в окне. Медианный фильтр может обеспечивать как подавления шума, так и к потере четкости изображения.
Существуют различные варианты применения медианного фильтра для ликвидации шума. Первый вариант это начинать с окна, состоящего из трех элементов, если ослабление незначительное, то окно увеличивается до пяти, и так пока медианный не будет значительно искажать. Второй вариант заключается в том, что применять медианный фильтр с использование фиксированным или изменяемой шириной окна, те области которые не изменились после однократной обработки не изменяются и при повторной.
Концепция медианного фильтра легко обобщается для двух измерений. Применяя двумерное окно желаемой формы, чаще всего квадратное. Двумерный фильтр с окном NxN обеспечивает эффективное подавление шума на изображении, чем применение по очередного применения медианных фильтров с окнами Nx1 и 1xN, но приводит к более существенному подавлению сигнала.
Все современные видеокарты имеют аппаратную поддержку возможностей
DirectX и OpenGL последних версий, причем для совместимости с разным софтом
(использующим ту или иную версию) производители встраивают в чипы реализацию
сразу обеих библиотек. Различия их состоят в способе обработки графической
информации, причем от версии к версии добавляются новые функции и возможности,
позволяющие создавать более реалистичную графику. Чтобы выполнить обработку
(весьма сложную) графической информации и снять с программистов заботу
разработки собственного драйвера для доступа к функциям видеокарты и были
созданы данные библиотеки.
DirectX и OpenGL это библиотеки графического API (Application Programming
Interface), они обрабатывают графическую информацию и осуществляют прямой
доступ к железу. Основу обоих API составляют несколько файлов, в которых
содержатся как низкоуровневые функции, так и более сложные модули. Базовые
функции реализованы аппаратно, в виде части GPU, более сложные функции
представляют собой программные модули, построенные на базовых командах.
Видеокарта не всегда аппаратно поддерживает нужные для работы приложения
функции, и в этом случае библиотека использует программные модули, эмулирующие
требующиеся возможности.это изначально это только графическая библиотека.
Основой для этой API является ядро, которое «умеет» обрабатывать примитивные
объекты (треугольники). Интерфейс содержит огромное количество процедур и
функций, необходимых для создания высококачественных графических изображений.
Чтобы аппаратно реализовать многие функции от видеокарты требуется наличие
framebuffer'а (кадровый буфер), причем некоторые операции могут выполняться
исключительно в нем [4].
Для работы с библиотекой программа сначала должна открыть окно во framebuffer (где будет происходить все операции), и потом уже контекст библиотеки связывается с этим окном. Такую операцию нужно проделать один раз, а далее все действия определяются через параметры обработки (рисование простых геометрических объектов: линии, точки, полигоны; рендеринг примитивов, включая их положение и цвет).
Плюсы:
- разработчик может напрямую работать с железом при использовании соответствующего расширения;
- переносимость между различными платформами (насколько это возможно);
- простата использования.
Недостатки:
- производит только рендер;
Чтобы начать работать с графической библиотекой, требуется открыть окно программы, но далее нужно также создать устройство отрисовки и тем самым произвести инициализацию Direct3D. После выполнения этого шага идет процесс просчета и отображения сцены [5].
Достоинства:
1) позволяет не только производить рендер, но и работать со звуком, видео, устройствами ввода-вывода;
2) хорошо продуманные библиотеки;
) COM интерфейсы.
Недостатки:
1) переносимость только в экосистеме Microsoft (windows, windows phone, xbox);