7.11. Растрова розгортка багатокутників

Можна розробити більш ефективний метод, ніж тест на належність внутрішньої частини, якщо скористатися тим фактом, що сусідні пікселі, ймовірно, мають однакові характеристики (крім пікселів граничних ребер). Ця властивість називається просторовою когерентністю. Для растрових графічних пристроїв сусідні пікселі на скануючому рядку, ймовірно, мають однакові характеристики. Це когерентність растрових рядків.

Характеристики пікселів на цьому рядку змінюються лише там, де ребро багатокутника перетинає рядок. Ці перетини ділять скануючий рядок на області.

Для простого багатокутника на рис. 7.23 рядок 2 перетинає багатокутник при х = 1 і х = 8. Отримуємо три області:

х < 1 поза багатокутником

1 ≤ х ≤ 8 всередині багатокутника

х > 8 поза багатокутником

Рядок 4 ділиться на 5 областей:

х < 1 поза багатокутника

1 ≤ х ≤ 4 всередині багатокутника

4 < х < 6 поза багатокутника

6 ≤ х ≤ 8 всередині багатокутника

х > 8 поза багатокутника

Зовсім необов'язково, щоб точки перетину для рядка 4 відразу визначалися у фіксованому порядку (зліва направо). Наприклад, якщо багатокутник задається списком вершин Р₁ Р₂ Р₃ Р₄ Р₅, а список ребер - послідовними парами вершин Р₁Р₂, Р₂ Р_3, Р₃ Р_4, Р₄ Р_5, Р₅ Р₁, то для рядка 4 будуть знайдені наступні точки перетину з ребрами багатокутника: 8, 6, 4, 1. Ці точки потрібно відсортувати у зростаючому порядку по х, тобто отримати 1, 4, 6, 8.

При визначенні інтенсивності, кольору і відтінку пікселів на скануючому рядку розглядаються пари відсортованих точкових перетинів. Для кожного інтервалу, що задається парою пересічень, використовується інтенсивність або колір багатогранника, що заповнюється. Для інтервалів між парами перетинів і крайніх (від початку рядка до першої точки перетину і від останньої точки перетину до кінця рядка) використовується фонова інтенсивність або колір. На рис. 7.23 для рядка 4 у фоновий колір встановлені пікселі: від 0 до 1, від 4 до 6, від 8 до 10, тоді як пікселі від 1 до 4 та від 5 до 8 зафарбовані в колір багатокутника.

Рис. 7.23. Растрова розгортка суцільної області

Точне визначення пікселів, які повинні активуватися, вимагає деякої обережності. Розглянемо простий прямокутник, наведений на рис. 7.24. Прямокутник має координати (1,1) (5,1), (5,4), (1,4). Скануючі рядки з 1 по 4 мають перетин з ребрами багатокутника при х=1 і х=5. Оскільки піксель адресується координатами свого лівого нижнього кута, то для кожного з цих скануючих рядків будуть активовані пікселі з координатами 1, 2, 3, 4 і 5. На рис. 7.24,а наведений результат. Зауважимо, що площа, яка покривається активованими пікселями, дорівнює 20, в той час як справжня площа прямокутника дорівнює 12.

a) б)

Рис. 7.24. Системи координат рядків сканування

Модифікація системи координат скануючого рядка і тесту активації усуває цю проблему, як це наведено на рис. 7.24,б. Вважається, що скануючі рядки проходять через центр рядків пікселів, тобто через середину інтервалу, як це наведено на рис. 7.24,б. Тест активації модифікується наступним чином: перевіряється, чи лежить всередині інтервалу центр пікселя, що розташований праворуч від перетину. Однак пікселі все ще адресуються координатами лівого нижнього кута. Як наведено на рис. 7.24,б, результат даного методу є коректним.

Горизонтальні ребра не можуть перетинати скануючий рядок і, таким чином, ігноруються. Це зовсім не означає, що їх немає на рисунку. Ці ребра формуються верхніми і нижніми рядками пікселів, як наведено на рис. 7.24. Він ілюструє коректність верхнього та нижнього ребер багатокутника, що отримані в результаті модифікації системи координат скануючих рядків.

Додаткова складність виникає при перетині скануючого рядка і багатокутника точно по вершині, як це наведено на рис. 7.25. При використанні погодження про середину інтервала між скануючими рядками отримуємо, що рядок у=3.5 перетне багатокутник в 2, 2 і 8, тобто вийде непарна кількість перетинів. Отже, розбивання пікселів на пари дасть невірний результат, тобто пікселі (0, 3), (1, 3) і від (3, 3) до (7, 3) будуть фоновими, а пікселі (2, 3), (8, 3), (9, 3) зафарбуються в колір багатокутника. Тому виникає ідея враховувати лише одну точку перетину з вершиною. Тоді для рядка у=3.5 отримаємо правильний результат. Проте результат застосування методу до рядка у=1.5, що має два перетини в (5, 1), показує, що метод невірний. Для цього рядка саме розбиття на пари дасть вірний результат, тобто зафарбований буде лише піксель (5, 1). Якщо ж враховувати у вершині лише одне перетинання, то пікселі від (0, 1) до (4, 1) будуть фоновими, а пікселі від (5, 1) до (9, 1) будуть зафарбовані в колір багатокутника.

Рис. 7.25. Особливості перетину з рядками сканування

Правильний результат можна отримати, враховуючи точку перетину у вершині два рази, якщо вона є точкою локального мінімуму або максимуму і враховувати її лише один раз в протилежному випадку. Визначити локальний максимум або мінімум багатокутника у розглянутій вершині можна за допомогою перевірки кінцевих точок двох ребер, що з'єднані у вершині. Якщо у обох кінців координати у більше, ніж у вершини, то вершина є точкою локального мінімуму. Якщо менше, то вершина − точка локального максимуму. Якщо одна більша, а інша менша, то, вершина не є ні точкою локального мінімуму, ні точкою локального максимуму. На рис. 7.25 точка Р₁ − локальний мінімум, Р₃ − локальний максимум, а Р₂ і Р₄ − ні те й ні інше. Отже, в точках Р₁ і Р₃ враховуються два перетини з скануючими рядками, а в Р₂ і Р₄ − один.