Нехай контур багатокутника растеризувати і виведений на екран. Тоді його зафарбовування зводиться до заповнення в кожному рядку растра всіх проміжків виду [x2i-1. x2i]. де через xk позначені x-координати "включених" пікселів в цьому рядку, впорядковані по зростанню (див. рис. 6.4а).
Через I (x, y) позначимо стан пікселя з координатами (x, y). I (x, y) = 1. якщо піксель "включений", і I (x, y) = 0 в іншому випадку. Неважко переконатися, що послідовне виконання операції
для x = 1, 2, 3. X - 1 (де X - горизонтальний розмір растра) призведе до необхідного результату - з тією лише різницею, що останній піксель в кожному проміжку зафарбований НЕ буде (див. рис. 6.4б). Ця невелика неточність в більшості випадків некритична і візуально непомітна. Формально алгоритм записується так:
Лістинг 6.3. XOR-растеризация
Якщо ж потрібно отримати результат, відповідний рис. 6.4а. то можна або після зафарбовування повторно вивести на екран контур багатокутника, або скористатися наступною модифікацією наведеного алгоритму (званої "XOR з прапором"):
Лістинг 6.4. XOR-растеризация з прапором
Перевагою алгоритмів XOR є їх гранична простота. Недолік - неможливість роботи при наявності сторонніх зображень на екрані.
виняткові випадки
Зупинимося тепер на способах виключення випадків, наведених на рис. 6.1. У разі горизонтального ребра, очевидно, досить при растеризації цього ребра вивести лише його кінці.
Для виключення інших випадків можна поступити наступним чином. При растеризации кожного ребра багатокутника Не будемо виводити його нижній кінець (x2. Y2). а верхній кінець виведемо за допомогою операції I (x1. y1) = I (x2. y2) XOR 1. Це призведе до того, що верхні (нижні) кінці ребер, що потрапили в один і той же піксель, що не будуть виведені, а значить , "поодинокі" точки в рядках растра будуть виключені.
Мал. 6.5. Кроки зафарбовування багатокутника.
Алгоритм з операцією XOR з перегородкою
Алгоритм полягає в інвертуванні кольору всіх пікселів, розташованих правіше i -го ребра, виробленому послідовно для i = 1, 2. N (порядок нумерації ребер не має значення). Горизонтальні ребра при цьому ігноруються. Як видно з рис. 6.5. в результаті зафарбованими виявляться всі внутрішні пікселі багатокутника і тільки вони.
До переваг даного алгоритму можна віднести його простоту і оригінальність, а також відсутність додаткових структур даних. Недоліком є необхідність виконання великого числа операцій з пікселями (до N операцій з кожним пікселем), в тому числі і поза багатокутника. Зокрема, чим більше відстань між многоугольником і правої кордоном екрану, тим більше буде здійснено "зайвих" операцій.
Від цього недоліку вільна модифікація даного алгоритму - "XOR-2 з перегородкою". Ідея її полягає в тому, щоб інвертувати область не між ребром і правої кордоном екрану, а між ребром і вертикальної прямої ( "перегородкою"), подумки проведеної в будь-якому зручному місці - наприклад перетинає багатокутник (див. Рис. 6.6).
Мал. 6.6. Растеризация з операцією XOR з перегородкою.