20. Алгоритм построчного сканирования.

Использует пространственную когерентность:

• пиксели в строке меняются только на границах;

• при перемещении к следующей строке размер заполняемой строки

скорее всего, или неизменен или меняется на 1 пиксель.

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

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

1. Начало алгоритма заполнения с затравкой.

2. Координаты затравочной точки помещается в стек.

3. Начало цикла заполнения области:

Пока стек не пуст:

3. 1. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксель. Пусть это Х лев и Х прав, соответственно.

3. 2. Анализируется строка ниже закрашиваемой в пределах от Х лев до Хправ и в ней находятся крайние правые пиксели всех незакрашенных фрагментов. Их координаты заносятся в стек.

3. 3. То же самое проделывается для строки выше закрашиваемой.

4. Конец цикла заполнения.

5. Конец алгоритма заполнения.

Рассмотрим пример работы алгоритма. Координаты затравочного пикселя (5,5):

Стек: Шаг 1. (5,5)

Шаг 2. (7,6) (3,4) (7,4)

Шаг 3. (7,6) (3,4) (7,3)

Р ис. 3.3. Пример работы построчного алгоритма заполнения с затравкой.

21. Алгоритм “художника”.

Пусть имеется некий набор граней (т.е. сцена), который требуется нарисовать. Отсортируем грани по удаленности от камеры и отрисуем все грани, начиная с самых удаленных. Довольно распространенная характеристика удаленности для грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь алгоритм. Просто, и обычно достаточно быстро.

Существует, правда, несколько проблем.

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

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

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

22. Модели освещения. Flat-закраска.

Модели освещения

Находить освещенность точки можно двумя способами.

Способ первый.

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

Второй способ.

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

Цвет объекта определяется поглощаемыми длинами волн, т.е. если объект поглощает волны всего видимого диапазона, то он является черным. Если наоборот, то белым.

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

а) Диффузная составляющая модели освещения

Свет точечного источника отражается от идеального рассеивателя по закону косинусов Ламберта. Интенсивность отраженного света пропорциональна косинусу угла между направлением света и нормалью поверхности.

где I - интенсивность отраженного света;

I_l - интенсивность точечного источника;

k_d - коэффициент диффузного отражения (постоянная величина, );

- угол между направлением на источник света и (внешней) нормалью к поверхности. Если >90 градусов, то источник находиться за объектом.

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

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

б) Рассеянная составляющая простой модели освещения

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

, где - интенсивность рассеянного света, - коэффициент диффузного отражения рассеянного света .

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

где K – произвольная постоянная.

d – расстояние от источника до поверхности.

в) Зеркальная составляющая простой модели освещения.

Интенсивность зеркально отраженного света зависит от угла па­дения, длины волны и свойств вещества. Угол отражения от идеально отражающей поверхности равен углу падения. Если поверхность не идеальна, то количество света достигшего наблюдателя зависит от пространственного распределения зеркально отраженного света. У гладких поверхностей распределение узкое или сфокусированное. У шероховатых более широкое. Благодаря зеркальному отражению на блестящих поверхностях появляются световые блики, из-за того, что отраженный свет сфокусирован вдоль вектора отражения. При движении наблюдателя блики тоже двигаются. В простых моделях ос­вещения обычно пользуются следующей эмпирической моделью (моделью Фонга):

- кривая отражения, представляющая отношение зеркально отраженного света к падающему, как функцию угла падения и длины волны ;

- угол между направлением света и направлением на наблюдателя;

n –степень, аппроксимирующая пространственное распределение зеркально отраженного света.

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

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

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

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

Функцию закраски, используя единичные векторы внешней нор­мали n, а также единичные векторы, определяющие направления: на источник (вектор l), отраженного луча (вектор r) и наблюдения (вектор s), можно записать в следующем виде:

Для учета цвета поверхности, функцию закраски модифицируют следующим образом:

где C() – цвет объекта. Эта формула рассчитывается для каждой из 3-х, составляющий RGB основных цветов.

- цвет в точке.

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

Определение вектора отражения.

Существуют следующие способы определения вектора отражения:

1) Случай, когда 1 источник света. Для простоты подсчета в этом способе система координат разворачивается так, чтобы ось OZ была направлена на источник света.

Е сли спроецировать эти вектора на XOY, то с учетом того, что все 3 вектора лежат в 1 плоскости, а эта плоскость проходит через OZ перпендикулярно XOY. Соответственно эта плоскость будет перпендикулярно XOY и будет лежать на 1 прямой.

2 ) Для нескольких источников света. В этом способе система координат разворачивается так, чтобы ось OZ совпадала с нормалью в исходной точке поверхности.

x и y – составляющие единичных векторов падения и отражения будут иметь разные знаки, а z составляющие будут равны.

3) Математический. Основывается на том, что, во-первых, так как вектора падения нормали и вектор отражения лежат в одной плоскости, то равны их попарно векторные произведения, то есть nL= Rn, и второе, это равенство углов между L и n, n и R (то есть ), так как векторные произведения равны и если равны их составляющие, то получаем 3 уравнения один из которых всегда линейно зависимо. Соответственно третьим недостающим уравнением будет равенство в скалярных произведениях:

n*L = n*R. Решая полученную систему, находим отсюда 3 составляющих вектора . Система уравнений в матричном виде:

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

Flat-закраска.

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

I = Ka*Ia + Kd(n,l) (6.1)

I = Ka*Ia + Kd(n,l) + Ks(n,h)p (6.2)

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

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