Генерация рельефа с помощью шума Перлина

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



Изображение (или какой либо другой объем) – вне зависимости от диапазона значений его элементов – полностью накрывается сеткой, представляющей диапазон вещественных чисел. Таким образом, создается шум на сетке, представляющей по всему изображению значения между 0 и 4. Каждое число порождает линию сетки, а значит, все стороны каждого квадрата последней имеют длину, равную одной единице. Выбранный масштаб влияет на сложность шума. Большое число квадратов на сетке изображения создает более «плотно упакованный» шум, подобный белому шуму на экране плохо настроенного телевизора. Меньшее число квадратов на сетке порождает «клубящийся» шум, внешне похожий на облака.

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



Каждый угол ячейки сетки теперь является базой для двух векторов – случайного единичного вектора и вектора в направлении пикселя, который необходимо построить. Для каждой пары таких векторов находиться скалярное произведение. Оно даст скалярное значение высоты каждого из углов сетки. Далее необходимо объединить эти четыре значения и найти высоту пикселя, который надо сгенерировать. Делать это можно по-разному, получая различные результаты, однако чаще всего используется взвешенная интерполяция четырех значений с учетом близости текущей позиции к каждому углу сетки.

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

Генерация рельефов с использованием Холмового алгоритма (Hill Algoritm)

Это простой итерационный алгоритм, основанный на нескольких входных параметрах. Алгоритм изложен в следующих шагах:

·                    Создаем двухмерный массив и инициализируем его нулевым уровнем (заполняем все ячейки нолями);

·                    Берем случайную точку на ландшафте или около его границ (за границами), а также берем случайный радиус в заранее заданных пределах. Выбор этих пределов влияет на вид ландшафта - либо он будет пологим, либо скалистым;

·                    В выбранной точке "поднимаем" холм заданного радиуса;

·                    Возвращаемся ко второму шагу и так далее до выбранного количества шагов. От него потом будет зависеть внешний вид нашего ландшафта;

·                    Проводим нормализацию ландшафта;

·                    Проводим "долинизацию" ландшафта. Делаем его склоны более пологими.

Как сгенерировать один холм

Первый, второй и четвертый шаги тривиальны, пятый и шестой мы рассмотрим далее. Теперь же займемся третьим шагом. Что же означает "поднять" холм? Фактически холм - это в нашем случае половина шара, чем больше радиус - тем больше холм (и выше). Математически это похоже на перевернутую параболу. Что бы не быть голословным покажу как это выглядит: 



здесь (x1, y1) - заданная точка, r - выбранный радиус, (x2, y2) - высота холма. Вот как выглядит одиночный холм: 



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



Теперь у нас уже есть построенный ландшафт. Теперь пойдем далее - к нормализации полученного результата.

Нормализация Ландшафта

При генерации значений для ландшафта мы не учитывали выходы этих значений за некоторые пределы (например - если у нас потом ландшафт будет храниться в монохромной картинке, то нам необходимо, чтобы все значения находились в пределе от 0 до 256). Для этого нам необходимо произвести нормализацию значений. Математически нормализация - это процесс получения значений из одного предела, и перевод его в другие пределы. Вот как это выглядит графически: 



Чтобы нам это сделать мы производим следующие действия:

·                    сперва проходим по всему массиву и запоминаем наибольшее и наименьшее значения;

·                    после того, как мы узнали эти значения, мы заново проходим по всему ландшафту и производим нормализацию конкретных значений в пределы от 0 до 1. В виде формулы это выглядит так:


После этого мы имеем готовый ландшафт, нормализованный и готовый к дальнейшему использованию. Теперь перейдем к вопросу о "долинизации" ландшафта.

"Долинизация" ландшафта

Вообще говоря, данный ландшафт уже можно использовать. Что же мне еще не нравится? Конечно, ландшафт уже готов, но если присмотреться, то в нем достаточно мало долин. Склоны холмов излишне крутые, хочется сделать их более пологими. В этом нам поможет наш предыдущий шаг - нормализация. Все значения у нас сейчас находятся в пределах от 0 до 1. Идея "долинизации" состоит в следующем - взять от каждого значения квадратный корень. Это в большей степени влияет на средние значения, практически не затрагивая минимумов и максимумов. Графически это выглядит так: 



А вот, как это повлияло на наш ландшафт: 



Теперь с эти алгоритмом можно закончить.

В основном, рассмотренные нами алгоритмы предназначены для создания простого холмистого или гористого ландшафта. Но существуют и другие типы ландшафтов. Например, острова (точнее группы островов), озерные ландшафты. Их можно реализовать достаточно просто:

·                    создаем простой, достаточно холмистый ландшафт;

·                    затем перемещаем уровень воды вверх или вниз. (При этом следует оговориться, что мы примем за уровень воды, я обычно имею в виду нулевой уровень, там где координаты у=0).

Практически мы просто проходим весь массив высот и смещаем их на какое-то значение.

Теперь рассмотрим еще один тип ландшафтов - одиночные острова или горные плато, в зависимости от того, где мы затем "разместим" воду.

Модификация холмового алгоритма для островов

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

В исходном алгоритме мы выбирали центральную точку случайным образом, и она могла располагаться в любой части ландшафта. Теперь же нам интересно, чтобы холмы были расположены ближе к центру. Чтобы сделать это, введем две переменных (которые потом будем случайным образом изменять), назовем их расстояние и угол. Расстояние будет означать, как далеко от центра находится центральная точка для одиночного холма. Оно может изменяться от ноля (прямо по центру карты высот) до половины величины карты высот минус радиус холма. Это позволит нам избежать ситуаций пересечения холмов с краем карты высот. Угол будет показывать, в каком направлении от центра нам нужно будет поставить холм. Изменяется в пределах от 0 до двух Пи. Используя эти два значения, мы можем получить значения (x, y) для центральной точки конкретного холма и использовать их как и в простом алгоритме. Вот как нам можно получить значения для x и y: 



здесь size - размер карты высот, distance - расстояние, theta - угол. Помните - радиус должен быть меньше половины размера карты высот.

Поработав с этими величинами, мы можем получить довольно прилично выглядящий остров: 





Вот мы и рассмотрели некоторые алгоритмы построения карт высот для ландшафтов. Рассмотрим еще некоторые сопутствующие операции:

·                    Сглаживание (или по-другому - размытие). Низкочастотный фильтр для уменьшения эффектов угловатости. При многократном применении позволяет добиться очень гладких очертаний ландшафта.

·                    Превращение гористой местности в холмистую. Я их различаю по очертанию вертикальных разрезов у вторых более пологие края.

·                    Создание пляжей и отмелей в случае с островами и берегами. Для этого места соприкосновения с водой сглаживают. Хотя могут существовать и скалистые пляжи и просто скалы.

Полный алгоритм генерации карты высот

        public void GenerateHeightmap(int SizeX, int SizeY, GenMethod LandGenMethod, Convolution[] Convs, bool Smoothing, bool Valley, bool Island)

        {

            this.SizeX = SizeX;

            this.SizeY = SizeY;

            Heightmap = new double[SizeX, SizeY];

            PerlinNoise Noise = new PerlinNoise(256);
            double min =  99999;

            double max = -99999;
            double[,] ar = new double[SizeX, SizeY];
            if (LandGenMethod == GenMethod.Perlin)

            {

                for (int i = 0; i < SizeX; i++)

                    for (int j = 0; j < SizeY; j++)

                    {

                        for (int l = 0; l < Convs.Length; l++)

                        {

                            if (Convs[l].Operation == Operation.Plus)

                                if (Convs[l].Coef != 0)

                                    ar[i, j] += Noise.Generate(i, j, Convs[l].Coef);

                            else

                                if (Convs[l].Coef != 0)

                                    ar[i, j] *= Noise.Generate(i, j, Convs[l].Coef);

                        }
                        if (max < ar[i, j]) max = ar[i, j];

                        if (min > ar[i, j]) min = ar[i, j];

                    }

            }

            else

            {

                Random rand = new Random();

                double theta;

                double distanceX, distanceY;

                double Radius;

                double x, y;

                double t;
                min = 0;

                for (int k = 0; k < Convs[0].Coef; k++)

                {

                    Radius = rand.NextDouble() * (SizeX * Convs[1].Coef);
                    if (Island)

                    {

                        theta = rand.NextDouble() * Math.PI * 2;

                        t = rand.NextDouble();

                        distanceX = t * (SizeX * Convs[2].Coef - Radius);

                        distanceY = t * (SizeY * Convs[2].Coef - Radius);

                        x = SizeX / 2.0 + Math.Cos(theta) * distanceX;

                        y = SizeY / 2.0 + Math.Sin(theta) * distanceY;   

                    }

                    else

                    {

                        x = SizeX * rand.NextDouble();

                        y = SizeY * rand.NextDouble();

                    }
                    for (int i = 0; i < SizeX; i++)

                        for (int j = 0; j < SizeY; j++)

                        {

                            t = Radius * Radius - ((i - x) * (i - x) + (j - y) * (j - y));

                            if (t > 0)

                                ar[i, j] += t;
                            if (max < ar[i, j]) max = ar[i, j];

                            //if (min > ar[i, j]) min = ar[i, j];

                        }

                }

            }
            double coef = 1 / ((max - min));

            for (int i = 1; i < SizeX-1; i++)

                for (int j = 1; j < SizeY-1; j++)

                {

                    if (Smoothing) 

                        Heightmap[i, j] =       (ar[i - 1, j - 1] + ar[i - 1, j] + ar[i - 1, j + 1] +

                                                 ar[i    , j - 1] + ar[i    , j] + ar[i    , j + 1] +

                                                 ar[i + 1, j - 1] + ar[i + 1, j] + ar[i + 1, j + 1] - 9.0*min) / (9.0*(max-min));

                    else

                        Heightmap[i, j] = (ar[i, j] - min) * coef;

                    if (Valley)

                        Heightmap[i, j] = Math.Sqrt(Heightmap[i, j]);

                }

Алгоритмы визуализации ландшафта и окружающей среды

Использование карт освещения

В широком смысле карта освещения – это структура данных, хранящая информацию об освещенности (яркости) поверхностей трехмерной сцены. Карты освещения рассчитываются предварительно для неподвижных объектов и позволяют ускорить рисование освещенной сцены. Впервые карты освещения были использованы в компьютерной игре Quake (1996 год).

Сейчас под картами освещения чаще всего подразумевают одну из их разновидностей – текстурные карты освещения. Они представляют собой изображения, накладываемые при рисовании «поверх» основных текстур; при этом яркость точки на карте освещения используется для модуляции яркости точки основной текстуры. Этот процесс продемонстрирован на рисунке:

Наложение карт освещения

Каждой поверхности в сцене соответствует своя карта освещения. Из-за того, что число поверхностей велико, карты освещения делают небольшого размера – как правило, не больше 128х128 точек. Поверхностям с большей площадью соответствуют более крупные карты освещения.

Часть набора карт освещения для небольшой сцены

Современные видеоадаптеры имеют функцию мультитекстурирования, позволяющую за одно действие нарисовать трехмерный объект с несколькими скомбинированными текстурами. Это делает использование карт освещения очень быстрым и эффективным.

Вычисление результирующего цвета

R = R_текст R_осв

G = G_текст G_осв

B = B_текст B_осв



Где значение компонентов цвета лежат в диапазоне [0, 1].

Проверка: если карта освещенности будет полностью белой, то результирующая текстура будет такой же, как и основная текстура (компоненты везде домножаются на 1, т.к. белый цвет это R = 1, G = 1, B = 1)

если карта освещенности будет полностью черной, то результирующая текстура тоже черной (компоненты везде домножаются на 0, т.к. черный цвет это R = 0, G = 0, B = 0), что соответствует отсутствие источников освещения).
Создание карт освещения будет рассмотрено позже

Наложение текстур

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

Как правило, трехмерная модель, созданная в пакете трехмерного моделирования, содержит не только информацию о геометрии, но и текстурные координаты – пары чисел U и V, указывающие на точку текстуры. Текстурные координаты задаются в вершинах граней, и задача наложения текстур сводится к интерполяции текстурных координат U и V по всем точкам грани.

В аффинном текстурировании (affine
mapping) используется линейная интерполяция:


 
, где u
₀ и u
₁ – значения текстурной координаты U, заданные на концах некоторого отрезка, и . Точно такая же формула используется для координаты V.

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


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

,
где z
₀, z
₁ – глубины концов отрезка, на котором проводится интерполяция.



Рис. Сравнение методов текстурирования

Все современные видеоадаптеры используют перспективно-корректное текстурирование.

Смешивание текстур

Смешивание с учетом цвета:

Смешивание без учета текстуры:


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

Расчет результирующего цвета каждого пикселя:

res=с_src*k₁+c_dst*k₂

Параметр src определяет, как получить коэффициент k₁ исходного цвета пикселя, a dst задает способ получения коэффициента k₂ для цвета в буфере кадра. Для получения результирующего цвета используется следующая формула:, где с_src – цвет исходного пикселя, c_dst – цвет пикселя в буфере кадра (res, k₁, k₁, с_src, c_dst – четырехкомпонентные RGBA-векторы).

Приведем наиболее часто используемые значения аргументов src и dst.

SRC_ALPHA	k=(As,As,As,As)
SRC_ONE_MINUS_ALPHA	k=(1,1,1,1)-(As,As,As,As)
DST_COLOR	k=(Rd,Gd,Bd)
ONE_MINUS_DST_COLOR	k=(1,1,1,1)- (Rd,Gd,Bd,Аd)
DST_ALPHA	k=(Ad,Ad,Ad,Ad)
DST_ONE_MINUS_ALPHA	k=(1,1,1,1)-(Ad,Ad,Ad,Ad)
SRC_COLOR	k=(Rs,Gs,Bs)
ONE_MINUS_SRC_COLOR	k=(1,1,1,1)- (Rs,Gs,Bs,As)

Если в сцене есть несколько прозрачных объектов, которые могут перекрывать друг друга, корректный вывод можно гарантировать только в случае выполнения следующих условий:

Все прозрачные объекты выводятся после непрозрачных.

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

В нашем программном комплексе коэффициент ALPHA для воды = 0.45

А режим смешения SRC_ONE_MINUS_ALPHA

Мипмапы

Мипмапы (MipMaps) или Мип-карты  — предрассчитанный, оптимизированный набор изображений связанных с одной текстурой и предназначенный для увеличения скорости рендеринга и улучшения качества изображения.

Каждое следующее изображение в наборе вдвое меньше предыдущего. То есть самое первое имеет размер равный размеру текстуры, второе вдвое меньший, третье — вчетверо и т.д. до размера 1х1 тексель.



Смысл такого вот предрассчитанного набора состоит в том, что при текстурировании будет выбираться изображение с наиболее подходящим размером.

Предположим, что на модель натянута текстура размером 512х512. Модель стоит далеко от камеры и геометрические размеры на экране у нее малы (скажем 3 пикселя)

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

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

При применении Трилинейной Фильтрации или Билинейной фильтрации с мипмапингом можно получить более размытые текстуры на поверхностях вдали или под углом. Для улучшения качества желательно применять Анизотропную фильтрацию.

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

Генерацию мип-уровней можно сделать несколькими способами:

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

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

Принцип действия

Создаётся так называемая MIP-пирамида — последовательность текстур с разрешением от максимального до 1×1. Например: 1×1, 2×2, 4×4, 8×8, 16×16, 32×32, 64×64, 128×128, 256×256 и 512×512. Каждая из этих текстур называется MIP-уровнем или уровнем детализации

На всех этих текстурах находится одно и то же изображение. Таким образом, MIP-текстурирование увеличивает расход видеопамяти на треть:  .

При наложении текстур вычисляется расстояние до объекта, соответственно находится номер текстуры как  ,

 где resolution  -  разрешение виртуальной камеры (количество пикселей, которое будет в объекте размером в 1 ед., расположенном в 1 ед. от камеры),
texelsize — размер текселя в единицах трёхмерного мира,

dist — расстояние до объекта в тех же единицах,

mip bias — число, позволяющее выбирать более или менее детальную текстуру, чем даёт формула. Эта цифра округляется до целого, и текстура с соответствующим номером (нулевая — самая детальная, первая — вдвое меньшая и т. д.) накладывается на объект.
Недостатки, способы решения

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

MIP-текстурирование не решает проблему текстур, находящихся под острым углом к зрителю (например, дорога ). У таких текстур разрешение по одной оси сильно отличается от разрешения по другой — и, например, по оси X изображение явно размыто, в то время как по оси Y видны мерцания, свойственные завышенному разрешению текстуры.
Есть сразу несколько способов решения этого (начиная с наименее качественного):

1.         Установить наиболее комфортное значение mip bias — числа, которое отвечает за выбор номера текстуры в пирамиде. Если оно отрицательное, видеоплата берёт более детальные текстуры, если положительное — менее детальные.

2.         Воспользоваться анизотропной фильтрацией — методом текстурирования, который направлен именно на решение этой проблемы.

Наконец, видна чёткая граница между MIP-уровнями. Это решается трилинейной фильтрацией.

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

Трилинейная фильтрация — усовершенствованный вариант билинейной фильтрации. Цвет пикселя высчитывается как средневзвешенное восьми текселей: по четыре на двух соседних MIP-текстурах. В случае, если формулы MIP-текстурирования дают самую крупную или самую маленькую из MIP-текстур, трилинейная фильтрация вырождается в билинейную.

MIP-текстурирование, повышая чёткость изображения и процент попаданий в кэш на дальних расстояниях, имеет серьёзный недостаток: ясно видны границы раздела между MIP-уровнями. Трилинейная фильтрация позволяет исправить этот недостаток ценой некоторого снижения резкости текстур.С недостаточной резкостью борются, устанавливая отрицательный mip bias — то есть, текстуры берутся более детальные, чем нужно было бы без трилинейной фильтрации.

Алгоритм, использующий Z-буфер

Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, z-буфер – это отдельный буфер глубины, используемый для запоминания координаты z, или глубины каждого видимого пикселя в пространстве изображения.

Главное преимущество алгоритма – его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине. При этом, алгоритм z-буфера, будучи реализованный аппаратно, является самым быстрым алгоритмом удаления невидимых поверхностей.

Основной недостаток алгоритма – большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат г значений, то можно использовать z-буфер с фиксированной точностью. Для обработки информации о глубине достаточно 32 бит. z-буфер размером 1280*1024*32 бит требует 40 Mb памяти. Но в настоящее время этот недостаток перестал быть актуальным из-за удешевления и миниатюризации элементов памяти.

Альтернативой созданию специальной памяти для z-буфера является использование для этой цели видео памяти.

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

При визуализации изображения, как пиксельная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512х512х24 бита, использующее z-буфер размером 20 бит на пиксель, разрешение которого повышено в 2 раза по осям х и у, и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 Mb памяти.

Описание алгоритма z-буфера таково:

Заполнить буфер кадра фоновым значением интенсивности или цвета.
Заполнить z-буфер минимальным значением z.
Преобразовать каждый многоугольник в растровую форму в произвольном порядке.
Для каждого Пиксель(x, y) в многоугольнике вычислить его глубину z(х, у).
Сравнить глубину z(x, у) со значением Z буфер(x, у), хранящимся в z-буфере в этой же позиции.
Если z(х, у) > Z буфер(x, у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Z буфер( х, у) на z(х, у).
В противном случае никаких действий не производить.
В качестве предварительного шага там, где это целесообразно, применяется удаление нелицевых граней.
    Если известно уравнение плоскости, несущей каждый многоугольник, то вычисление глубины каждого пикселя на сканирующей строке можно проделать пошаговым способом. Напомним, что уравнение плоскости имеет вид
ах + by + cz + d = 0

z = -(ах + by + d)/с
Для сканирующей строки y = const. Поэтому глубина пикселя на этой строке, у которого х1 = x + Dх, равна

z1 – z = -(ах1 + d)/c + (ах + d)/с = а(х – х1)/с

или

z1 = z-(a/c)Dx
Но Dx = 1, поэтому z1 = z – (а/с).

Освещение

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

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

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

Рис. 2.1.7.1. Матовая поверхность
,

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

Матовая поверхность имеет свой цвет. Наблюдаемый цвет матовой поверхности определяется комбинацией собственного цвета поверхности и цвета излучения источника света (в данной работе цвет излучения источника считается белым, поэтому учитывается только цвет поверхности).

Для точечного источника света можно еще усовершенствовать модель отражения, если учесть, что энергия уменьшается пропорционально квадрату расстояния и пропорционально расстоянию.

Кроме того, в данной программе вместо интенсивности света используется расширенная величина цвет света, которая состоит из трех компонент (R, G, B)
Итак, цвет в данной точке для одного источника направленного освещения рассчитывается по следующей формуле:



Для точечного источника света:



Где I – это интенсивности источников света (R, G, B)

K_d - способность материала отражать диффузный свет (тоже имеет R, G, B)

d – Расстояние от источника света до рассматриваемой точки поверхности,

c₁, c₃, c₃ – произвольные коэффициенты угасания, которые находятся эмпирическим путем

Для определения косинуса угла между вектором нормали к поверхности и вектором, определяющим положение источника света в пространстве, следует воспользоваться скалярным произведением. Пусть имеется вектор нормали  и две точки – , принадлежащая поверхности, и , определяющая положение источника. Вектор, направленный от точки поверхности к источнику света, имеет следующие координаты: . Тогда

,

,

,
или

.

Следовательно

.

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

,

или, более развернуто,

.

Модель освещения Фонга и просчет теней

При использовании метода Фонга для определения цвета в каждой точке интерполируются не интенсивности отраженного света, а векторы нормалей.

Последовательность действий такова:

·        определяются нормали к граням;

·        по нормалям к граням определяются усредненные нормали в вершинах. В каждой точке закрашиваемой грани определяется интерполированный вектор нормали;

·        по направлению векторов нормали определяется цвет точек грани в соответствии с принятой моделью отражения цвета.

Как уже было сказано, метод заключается в интерполяции вектора нормали. Для интерполяции будут использоваться векторы , исходящие из начала координат плоскости проецирования и параллельными соответствующим нормалям  в вершинах a, b и c.



Нахождение  и  производится следующим образом:

,

.

где  – координаты векторов .

В данном случае необходимости в вычислении некоторых величин на каждом шаге нет. Так что их можно вычислить заранее

Теперь необходимо найти координаты вектора :

.

Вектор  параллелен векторудля нормали в точке , поэтому его можно использовать для расчета отражения света так же, как и вектор нормали .
Метод Фонга дает правильное закрашивание. Если интерполировать нормали передней грани, то по центру будут интерполированные нормали, параллельные лучам света. Поэтому центр передней грани будет светлее, чем края.

Просчет теней

            Для построения сплошных теней на этапе вычисления «локальной» интенсивности цвета в точке объекта проверяется «видимость» каждого источника света из этой точки.

            Принцип работы алгоритма.

1.      Из проверяемой точки строится луч, направленный на источник света.

2.      Производится поиск пересечений этого луча с примитивами сцены между проверяемой точкой и источником.

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

4.      Если пересечений не найдено, точка не в тени. При расчете ее цвета учитываем

проверяемый источник.

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

Вычисление точки пересечения луча с Треугольником для построения тени.

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

            Уравнение плоскости выглядит следующим образом:
                                   Q(x, y, z) = Ax + By + Cz +D = 0.                                         (2.2.5.3)
            Здесь коэффициенты A, B, C совпадают с координатами нормали к этой плоскости. Координаты нормали плоскости совпадают с координатами нормали треугольника, которые мы посчитали на этапе загрузки сцены.

            Для нахождения свободного члена D необходимо подставить координаты любой точки треугольника, например, одной из вершин.
                                               D = –Ax –By – Cz.                                                    (2.2.5.4)
            По ходу выполнения программы значение D меняться не будет, поэтому его целесообразно посчитать при инициализации сцены и хранить, как и координаты нормали. Пересчитывать его необходимо только при изменении положения треугольника.

            Теперь для нахождения точки пересечения подставим уравнения луча в

уравнение плоскости.
                        A (x₁ + at) + B (y₁ + bt) + C (z₁ + ct)  + D = 0
Откуда получим
                        t = – (Ax₁ + By₁ + Cz₁ + D) / (Aa + Bb + Cc)                                   (2.2.5.5)
            Если  знаменатель этой дроби равен нулю, значит луч параллелен плоскости, в которой лежит треугольник. Точки пересечения нет.

            Для нахождения координат точки пересечения надо подставить найденное значение параметра t в уравнения луча (2). Назовем точку пересечения D. Мы получим координаты x_D, y_D, z_D.

            Теперь необходимо определить, попала ли точка D внутрь треугольника. Найдем координаты векторов AB, BC, CA (A, B, C – вершины треугольника) и координаты векторов AD, BD, CD. Затем найдем три векторных произведения:
nA = AB x AD,

nB = BC x BD,                                                          (2.2.5.6)

nC = CA x CD.
            Эти вектора будут коллинеарные. Если все три вектора сонаправлены, то точка D лежит внутри треугольника. Сонаправленность определяется равенству знаков соответствующих координат всех трех векторов.

            Операцию проверки принадлежности точки D треугольнику ABC можно ускорить. Если ортогонально спроецировать треугольник ABC и точку D на одну из плоскостей xOy, yOz или xOz, то попадание проекции точки в проекцию треугольника будет означить попадание самой точки в треугольник (конечно же, если уже известно, что точка D лежит в плоскости, содержащей треугольник ABC). При этом число операций заметно сокращается. Так для поиска координат  всех векторов нужно искать по две координаты на каждый вектор, а при поиске векторных произведений нужно искать только одну координату (остальные равны нулю).

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

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

Остается добавить, что для проецирования лучше выбирать ту из плоскостей, площадь проекции треугольника на которую больше. При таком условии исключается случай проецирования треугольника в отрезок (при условии, что проверяемый треугольник не вырожден в отрезок). Кроме того, при увеличении площади проекции уменьшается вероятность ошибки. Для определения такой плоскости проецирования достаточно проверить три координаты нормали треугольника. Если z-координата нормали больше (по абсолютному значению) x и y, то проецировать надо на плоскость xOy. Если y больше чем x и z, то проецируем на xOz. В оставшемся случае – на yOz.
bool RayTriangleIntersect(Vector RayPos, Vector RayDir, Vector P1, Vector P2, Vector P3,

                                     out Vector ResultPoint, out Vector ResultNormal)

        {

            const double EPSILON2 = 0.00001;

              Vector v1 = P2 - P1;

              Vector v2 = P3 - P1;

              Vector pvec = RayDir ^ v2;

              double det = v1 * pvec;

              ResultPoint = new Vector();

            ResultNormal = new Vector();

            if ((det < EPSILON2) && (det > -EPSILON2))

              {

                    return false;

              }

            double invDet = 1 / det;

              Vector tvec = RayPos - P1;

            double u = (tvec * pvec) * invDet;

              if ((u < 0) || (u > 1))

                    return false;

              else

              {

                    Vector qvec = tvec ^ v1;

                double v = (RayDir * qvec) * invDet;

                    if ((v < 0) || (u+v > 1))

                          return false;

                double t = (v2 * qvec) * invDet;

                    if (t > 0)

                    {

                          ResultPoint =  RayPos + RayDir * t;

                          ResultNormal = v1 ^ v2;

                    return true;

                    }

                    else

                          return false;

              }

        }

Перемещение и вращение камеры

Представление камеры с помощью векторов:

Матрица вращения вокруг единичного вектора v на угол омега:
     

 Вычисление матрицы камеры:
      // вектор бинормали

      Vector      sideVec(viewMat.p[0], viewMat.p[1], viewMat.p[2]);

      //вектор нормали (указывает "верх" камеры)

      Vector      upVec(viewMat.p[3], viewMat.p[4], viewMat.p[5]);

      // вектор направления

      Vector      dirVec(viewMat.p[6], viewMat.p[7], viewMat.p[8]);

     

      // построение матрицы поворота (по формуле выше на рисунке)

      Matrix Rot(camAng.y, (dirVec ^ upVec).Normalize());

      // добавление вращения по оси Y (он указывает верх камеры), которое зависит от смещение мыши по х

      Rot.AddRotationY(-camAng.x);

      // обновление векторов камеры (домножение на матрицу поворота)

      upVec = Rot * upVec;

      dirVec = Rot * dirVec;

      sideVec = Rot * sideVec;

      // обновление матрицы камеры

      viewMat.p[0] = sideVec.x; viewMat.p[1] = sideVec.y; viewMat.p[2] = sideVec.z;

      viewMat.p[3] = upVec.x; viewMat.p[4] = upVec.y; viewMat.p[5] = upVec.z;

      viewMat.p[6] = dirVec.x; viewMat.p[7] = dirVec.y; viewMat.p[8] = dirVec.z;
      // обновление матрицы камеры с учетом ее позиции

      float m[16] = {

            viewMat.p[0], viewMat.p[3], -viewMat.p[6], 0,

            viewMat.p[1], viewMat.p[4], -viewMat.p[7], 0,

            viewMat.p[2], viewMat.p[5], -viewMat.p[8], 0,

            -(viewMat.p[0]*camSrc.x + viewMat.p[1]*camSrc.y + viewMat.p[2]*camSrc.z),

            -(viewMat.p[3]*camSrc.x + viewMat.p[4]*camSrc.y + viewMat.p[5]*camSrc.z),

             (viewMat.p[6]*camSrc.x + viewMat.p[7]*camSrc.y + viewMat.p[8]*camSrc.z),

             1

      };

Технологический раздел

Выбор среды разработки и технологии программирования

После подготовки и изучения алгоритмов встал еще ряд вопросов:

-под какую операционную систему реализовывать программный продукт;

-какой язык программирования и среду разработки  использовать;

-какую технологию программирования положить в основу проекта.
В качестве операционной системы была выбрана система Widows XP и более новые Vista и 7. Это обусловлено тем, что Windows XP — самая распространенная на сегодняшний день ОС. И для нее написано больше всего IDE и программного обеспечения для разработки.

Программный комплекс состоит из двух модулей: редактора и просмотра ландшафта.

Языком программирования для написания программы «Редактор» был выбран язык C#. С помощью C# можно быстро писать программы под Windows или интернет-приложения, благодаря удобному синтаксису, интеллектуальным подсказкам и управляемому коду. Используя управляемый код, не нужно заботится о сборке мусора, об указателях и о некоторых базовых структурах и алгоритмах – все это уже реализовано. Минусом разработки на C#  .Net является низкая производительность программ. Но это уже компенсируется современным аппаратным обеспечением. Кроме того, в редакторе нам и не требуется высокая производительность, потому что там рассчитываются только карты (изображение) и нет интерактивных элементов, в отличие от программы просмотра.

Языком программирования для написания программы просмотра ландшафтов был выбран язык С++. Язык С++ сочетает в себе удобство с точки зрения структуры кода (объекты, перегрузка функций, операторов, обработка исключений и др.) и программирование на низком уровне (арифметика указателей, ассемблерные вставки, выравнивание памяти, директивы компилятора). Кроме того, среда разработки Visual Studio 2008 может сильно оптимизировать код, используя раскрытие циклов, встраивание функций, использование суперскалярных команд процессора SSE и др., тем самым увеличив производительность.

Минусы языка С++ тоже имеются: ручная сборка мусора (возможные утечки памяти из-за этого).

В качестве технологического подхода к разработке проекта был выбран объектно-ориентированный подход. Этот выбор обуславливается легкостью и быстротой разработки программы, хотя взамен ее скорости.
Так же встал вопрос о том, как можно использовать аппаратные возможности современных вычислительных систем. Дело в том, что выполнение данной задачи без использования аппаратно-реализованных алгоритмов (например, алгоритм, использующий Z-буфер) не дало бы требуемых результатов. Можно было бы говорить об изображении ландшафта, но не в реальном времени, т.к. даже современные процессоры не в состоянии одновременно обрабатывать и выводить такое количество информации. При том, в настоящее время, когда большинство стандартных алгоритмов реализовано аппаратно, было бы глупо не использовать эти возможности. Это заведомо определяло бы несостоятельность программного продукта в свете современных тенденций. К тому же мне было интереснее сосредоточиться на алгоритме изображения ландшафтов, чем реализовывать стандартные алгоритмы, пройденные в прошлом семестре.

Выбор библиотек, поддерживающих аппаратные возможности современных компьютеров, был не велик: Direct3D или OpenGL. Я выбрал OpenGL, как более распространенную и простую для понимания. OpenGL является открытым графическим стандартом, разработанным и утвержденным несколькими ведущими фирмами, такими как Nvidia corporation, AMD, Intel, и др. В число ее достоинств входят стабильность, надежность, переносимость, простота использования. Хотя следует отметить, что Direct3D немного выигрывает в скорости и в возможностях.

Структура программы

Программа «Просмотр ландшафта»

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

void LoadSettings(char *FileName)

        
// В этом событии указываются действии, совершаемые в момент старта программы

bool appPreInit()
// В этом событии указывается последовательность действий при визуализации каждого кадра (несколько раз в секунду)

bool appRender()
// В этом событии указываются действия, совершаемые при закрытии программы (освобождение ресурсов)

void appShutdown()

// Обработчик нажатий клавиш

bool ProcessKey(HWND hWnd,WPARAM wParam)
Terrain – Описывает непосредственно геометрию ландшафта (вершины, индексы, нормали), текстуры ландшафта, неба, воды.

Также этот класс отвечает за визуализацию всех этих объектов.

            DynamicCamera – Реализация камеры, ее передвижения, вращения, а также связь с ландшафтом (передвижение по нему).

            Font – модуль для инициализации и вывода текста на экран

            Render – модуль для реализации визуализации в 3-мерном и 2-мерном режимах

            Image – модуль для загрузки и обработки изображений

            Texture – модуль для загрузки изображений и инициализаций структур

            Vector – модуль для работы с векторами (сложение, вычитание, скалярное произведение, векторное произведение)

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

            Base – модуль для включения основных стандартных библиотек

            Win32 – модуль, связанный с включением библиотек среды Windows

Представление исходных данных

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

В данной работе был выбран полигональный способ аппроксимации пространственных фигур. Сущность полигональной модели состоит в том, что каждое тело представляется в виде определенного набора граней-многоугольников, с определенной точностью приближающих форму исходного тела. В качестве грани-многоугольника был выбран треугольник, так как это наиболее простой многоугольник, его точки всегда лежат в одной плоскости и любой более сложный многоугольник можно разбить на несколько треугольников. Но ускорения вычислений я не стал вводить тип треугольник в моей программе. Вместо этого есть массив вершин и массив индексов, которые и указывают на определенные треугольники (0, 1, 2 – первый треугольник; 1, 2, 3 – второй треугольник и т.д.)

Разработанные типы данных и форматы файлов подробно описаны в последующих разделах.

Программа «Редактор ландшафта»

   

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

class Light

    {

        public Vector Ambient;

        public Vector Diffuse;

        public Vector Mirror;
        public Light() { }

        public Light(Vector Ambient, Vector Diffuse, Vector Mirror)

        {

            this.Ambient = Ambient;

            this.Diffuse = Diffuse;

            this.Mirror = Mirror;

        }

    }
    class DirLight : Light

    {

        public Vector Dir;
        public DirLight() { }

        public DirLight(Vector Ambient, Vector Diffuse, Vector Mirror, Vector Dir)

            : base(Ambient, Diffuse, Mirror)

        {

            this.Dir = Dir;

        }

    }
    class PointLight : Light

    {

        public Vector Point;

        public double c1, c2, c3;
        public PointLight(Vector Ambient, Vector Diffuse, Vector Mirror, double c1, double c2, double c3, Vector Point)

            : base(Ambient, Diffuse, Mirror)

        {

            this.Point = Point;

            this.c1 = c1;

            this.c2 = c2;

            this.c3 = c3;

        }

    }
class Material

    {

        public Vector Ambient;

        public Vector Diffuse;       

        public Vector Mirror;
        public Material(Vector Ambient, Vector Diffuse, Vector Mirror)

        {

            this.Ambient = Ambient;

            this.Diffuse = Diffuse;

            this.Mirror = Mirror;

        }

    }
class PerlinNoise

    {

        int TableSize;

        int TableMask;
         struct vec2

         {

             public double x, y;

             public vec2(double x, double y) { this.x = x; this.y = y; }

         };
         vec2[] VectorTable;

         byte[] lut;
        public PerlinNoise(int TableSize)
        void setup()
     // вычисляется значение шумовой функции (в данной программе высота) с коэффициентом scale (чем больше scale, тем более изломанная карта) в координате x y

        public double Generate(double x, double y, double scale)
        public double Generate(int x, int y, double scale)

    }
class Landscape

    {

        GenMethod LandGenMethod;

        Convolution[] Convs;

        bool Smoothing;

        bool Valley;

        bool Island;
        public double[,] Heightmap;

        int[,] Lightmap;

        int[,] Colormap;

       

        public int SizeX, SizeY;

        int LSizeX, LSizeY;

        int CSizeX, CSizeY;
        Vector[,] Points;

        int[] Indexes;

        Vector[] FaceNormals;

        Vector[,] VertexNormals;
        Vector Pos;

        Vector Dimen;
        public Material Ground;
               public Landscape() { }
        // генерирует карту высот с размером SizeX, SizeY, по методу LandGenMethod c коэффициентами Convs, со сглаживанием или нет (Smoothing) с долинизацией (Valley)

        public void GenerateHeightmap(int SizeX, int SizeY, GenMethod LandGenMethod, Convolution[] Convs, bool Smoothing, bool Valley, bool Island)
        // строить трехмерную модель ландшафта с размерами Dimen.X Dimen.Y Dimen.Z

        // Также просчитываются нормали к граням FaceNormals и к вершинам VertexNormals

        public void BuildMesh(Vector Dimen)
        // Цвет данной точки ландшафта с координатами Pos нормальную Normal добавляется к результирующему Color

        public void AddColor(Vector Pos, Vector Normal, Light Source, ref int Color)
        // построение карты освещенности с учетом Sources источников света. Размер карты SizeX*Size SizeY*Size

        public void BuildLightmap(Light[] Sources, int Size)
        // построение карты теней и смешение ее с картой освещенности

        public void BuildShadowmap(Light[] Lights, int Size)
        // построение "цветовой" карты (или текстуры) на основе массива Colors

        public void GenerateColormap(Color[] Colors, int Size)
        // сохранение карты высот в файл BMP

        public void SaveHeightmap(string FileName, out Bitmap Result)
        // сохранение карты освещенности в файл BMP

        public void SaveLightmap(string FileName, out Bitmap Result)
        // сохранение текстуры в файл BMP

        public void SaveColormap(string FileName, out Bitmap Result)

}

1. Реферат на тему Book Report On Beowulf Essay Research Paper
2. Реферат на тему Divorce And Children Essay Research Paper It
3. Реферат Bembix rostrata
4. Шпаргалка Шпоры по менеджменту 2
5. Реферат Совершенствование управления и маркетинг
6. Реферат на тему Vikings 4 Essay Research Paper Throughout history
7. Реферат Развитие интеграционных процессов на постсоветском пространстве
8. Курсовая на тему К. Дебюсси Детский уголок
9. Биография на тему Воротынский Иван Михайлович
10. Реферат Арцах