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

 

Принцип: расширение алгоритма преобразования многоугольника в растровую форму; разница в том, что имеем дело не с одним многоугольником, а со всеми сразу.

Шаги:

· Создается таблица ребер (ТР). Она содержит все ребра многоугольников, отсортированные по меньшей y-координате.

Описание ребра содержит:

 

Указание на многоугольник

 

· Создается таблица многоугольников (ТМ).

Описание многоугольников содержит:

 

Коэффициенты уравнения плоскости (A, B, C, D) Цвет Флаг = 0 — вне
1 — внутри

· Создается ТАР.

Содержит все активные ребра на текущей сканирующей строке. Ребра упорядочены по возрастанию x-координаты.

Указание на многоугольник

Пример.

Строка — четыре ребра в ТАР.

, флаг 1 = 1, флаг 2 = 0, извлекаем цвет 1.

 

 

Рис. 12.3

 


Флаг 2 = 0
Флаг 1 = 0, цвет = фон

 

Флаг 2 = 1, цвет = цвет2
Флаг 1 = 0;

 

Флаг 2 = 0, цвет = фон
Флаг 1 = 0;

 

Строка — четыре ребра в ТАР.

 

Флаг 1 = 1, цвет = цвет1
Флаг 2 = 0;

 

Флаг 1 = 1,
Флаг 2 = 1, вычисляется z1 и z2 из уравнений плоскости цвет = цвет 2

 

Флаг 1 = 0,
Флаг 2 = 1, цвет = цвет2

 

Флаг 1 = 0, цвет = фон
Флаг 2 = 0;

 

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

 

 

Рис. 12.4

 

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

 






Дата добавления: 2016-07-18; просмотров: 1782; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.019 сек.