Метод Гуро основывается на идее закрашивания плоской грани не одним цветом, а плавно изменяющимися оттенками, вычисляемыми путем билинейной интерполяции цветов примыкающих граней. Закрашивание граней по методу Гуро осуществляется в четыре этапа:

• вычисляются нормали к каждой грани;

• определяются усредненные нормали в вершинах - производится усреднение нормалей примыкающих граней. На иллюстрации приведен пример – вектор нормали в вершине a равен ;

Рис. 2.1.7.2.1. Нормаль в вершине

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

• производится закрашивание грани цветом, соответствующим линейной интерполяции значений интенсивности в вершинах.

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

Рис. 2.1.7.2.2. Интерполяция значений интенсивности

Интерполированная интенсивность I в точке (X, Y) определяется исходя из пропорции

.

Отсюда

.

Значения интенсивностей I₁ и I₂ на концах горизонтального отрезка представляет собой интерполяцию интенсивности в вершинах:

; или

, .

Рис. 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] of TPoint3

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]’;

  • последовательность записей типа THeightColor;

• окончание секции высот – строка '[ColorHeights End]';

• заголовок секции пикселей – строка '[Pixels Start]';

• ширина и высота карты в пикселях;

• информация о пикселях карты, сжатая с помощью метода группового кодирования (последовательность пар «Индекс цвета – Длина участка»);

• окончание секции пикселей – строка '[Pixels End]';

Метод группового кодирования используется для экономии дискового пространства, занимаемого файлами плоских карт. Суть метода состоит в том, что сохраняется информация не о каждом пикселе карты, а о группах пикселей, принадлежащих одной строке и имеющих общий цвет (запоминается длина участка и цвет его пикселей). Таким образом, можно добиться значительной экономии дискового пространства. Это можно проверить, сопоставив размер файла BMP, хранящего изображение карты, и размер соответствующего ему файла HCL. Однако экономия дискового пространства не всегда может быть достигнута при использовании данного метода. Можно привести такой пример изображения, при кодировании которого размер итогового файла будет превышать размер исходного BMP-файла. Строки этого изображения должны состоять из таких пикселей, что цвет любых двух соседних не совпадает. Но, несмотря на это, использование метода группового кодирования в данной работе вполне оправдано, так как карта в общем случае имеет вполне однородную структуру.