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

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

Шаги:

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

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