Двовимірний алгоритм Коена-Сазерленда

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

· більшість примітивів містяться цілком у великому вікні

· більшість примітивів лежать цілком зовні щодо маленького вікна.

Ідея алгоритму полягає в наступному:

Вікно відсікання і прилеглі до нього частини площини разом утворюють 9 областей (рис. 1). Кожною з областей привласнений 4-х розрядний код.

Дві кінцеві точки відрізка отримують 4-х розрядні коди, відповідні областям, в які вони потрапили. Сенс розрядів коду:

1 рр = 1 - крапка над верхнім краєм вікна;

2 рр = 1 - крапка під нижнім краєм вікна;

3 рр = 1 - крапка праворуч від правого краю вікна;

4 рр = 1 - крапка зліва від лівого краю вікна.

Визначення того чи лежить відрізок цілком усередині вікна або цілком поза вікном виконується таким чином:

· якщо коди обох кінців відрізка рівні 0 те відрізок цілком усередині вікна, відсікання не потрібне, відрізок приймається як тривіально видимий (відрізок AB на рис. 1);

· якщо логічне значення кодів обох кінців відрізка не рівно нулю, то відрізок цілком поза вікном, відсікання не потрібне, відрізок відкидається як тривіально невидимий (відрізок KL на рис. 1);

· якщо логічне значення кодів обох кінців відрізка рівно нулю, то відрізок підозрілий, він може бути частковий видимим (відрізки CD, EF, GH) або цілком невидимим (відрізок IJ); для нього потрібно визначити координати перетинів із сторонами вікна і для кожної отриманої частини визначити тривіальну видимість або невидимість. При цьому для відрізків CD і IJ буде потрібно обчислення одного перетину, для інших (EF і GH) - два.

При розрахунку перетину використовується горизонтальність або вертикальність сторін вікна, що дозволяє визначити координату X або Y точки перетину без обчислень.

рис. 1 Відсікання по методу Коена-Сазерленда

При безпосередньому використанні описаного вище способу відбору цілком видимого або цілком невидимого відрізка після розрахунку перетину було б потрібно обчислення коду розташування точки перетину. Для прикладу розглянемо відрізок CD. Точка перетину позначена як P. Внаслідок того, що межа вікна вважається такою, що належить вікну, то можна просто прийняти тільки частину відрізка PD, що потрапила у вікно. Частина ж відрізка CP, що насправді опинилася поза вікном, зажадає подальшого розгляду, оскільки логічне І кодів точок C і P дасть 0, тобто відрізок CP не можна просто відкинути. Для вирішення цієї проблеми Коен і Сазерленд запропонували замінювати кінцеву крапку з ненульовим кодом кінця на крапку, лежачу на стороні вікна, або на її продовженні.