Podręcznik Grafika komputerowa i wizualizacja

2.3. Algorytmy obcinania

Większość rysowanych obiektów jest definiowana w rzeczywistym układzie kartezjańskim. Przedstawienie takiego obiektu na ekranie monitora (lub z wykorzystaniem innego urządzenia) wymaga określenia fragmentu, który jest obrazowany. Jeśli tylko część prymitywu jest zobrazowana, to oprócz algorytmu rysowania prymitywu jest potrzebny algorytm obcinania go do widocznego fragmentu.

Obcinanie jest to operacja rastrowa pozwalająca wydzielić fragment figury, który mieści się w prostokątnym oknie (rys.2.13).

Rys.2.13. Zadanie obcinania. Przerywane odcinki powinny zostać usunięte.

Algorytm Cohena-Sutherlanda (1974) służy do obcinania odcinków do prostokątnego okna. Oznacza to, że należy wybrać odcinki (lub ich fragmenty) do obcięcia na podstawie położenia ich końców.

Rys.2.14. Podział płaszczyzny na obszary w algorytmie Cohena i Sutherlanda.
Kolejne bity od lewej: ograniczenie górne, dolne, prawe, lewe.

Płaszczyzna została podzielona na 9 obszarów . Prostokąt centralny odpowiada obszarowi okna. Jednocześnie krawędzie okna wyznaczają cztery proste: prawą, lewą, górna i dolną. Każdemu obszarowi został przypisany czterobitowy kod. Kolejne bity kodu określają poziome i pionowe pasy. Operacja AND przeprowadzona na kodach końców odcinka pozwala odrzucić te odcinki, które na pewno są poza oknem. Spośród pozostałych odcinków należy wybrać te, które rzeczywiście mają wspólne punkty z oknem oraz przyciąć do jego rozmiaru. Operacja AND pozwala w tym przypadku wybrać prostą obcinającą.

Rys.2.15. Rozważane przypadki w algorytmie obcinania Cohena i Sutherlanda.

• Jeśli wynik operacji AND jest różny od zera – należy odrzucić odcinek jako nie mający na pewno punktów wspólnych z oknem.
• Jeśli wynik operacji AND jest zerowy – odcinek może przecinać okno.
• W takiej sytuacji należy rozważyć przypadek szczególny gdy kody obu końców są zerowe (punkty P1 i K1 na rysunku), wtedy cały rysunek leży wewnątrz okna.
• Natomiast jeśli kody końców są niezerowe to określają one którymi prostymi należy przyciąć odcinek. Odcinek należy przyciąć prostą prawą (K2=0010). Odcinek prostymi lewą i dolną (P3=0101) oraz prawą i górną (K3=1010).

Algorytm Cohena-Sutherlanda bardzo efektywnie klasyfikuje odcinki i jednocześnie jest bardzo prosty w implementacji. Powoduje to, że jest chyba najczęściej stosowanym algorytmem przycinania odcinków do prostokątnego okna. Ma jednak jedną wadę. Często odcinki są przycinane kilka razy (różnymi prostymi) zanim uzyskają końcową postać. Z punktu widzenia wyznaczania przecięcia nie jest to efektywne. W 1978 roku Cyrus i Beck zaproponowali całkowicie inne podejście do problemu obcinania.

Rys.2.16. Wykorzystanie zorientowania do przyspieszenia obcinania. Algorytm Cyrusa-Becka.

Jeśli opiszemy prostą parametrycznie, to wzrost parametru określi naturalny zwrot prostej. Niech punkty P0 i Pk odpowiadają odpowiednio parametrom t=0 i t=tk dla k>0. Wektor  określa zwrot prostej. Można przeanalizować iloczyn skalarny tego wektora i wektora normalnego (skierowanego na zewnątrz) do boku wielokąta. Jeśli to parametr tk określa punkt Pk., który może być „maksymalnym” punktem przecięcia z wielokątem (np. punkt dla t=t2 na rysunku 2.16).

Jeśli  to parametr tk określa punkt Pk., który może być „minimalnym” punktem przecięcia z wielokątem (np. punkt dla t=t1 na rysunku 2.16).

Cyrus i Beck zaproponowali efektywny zestaw operacji parametrycznych do analizy całego wielokąta. Algorytm ten został w 1984 roku rozszerzony przez Lianga i Barsky’ego do ogólnego przypadku 2D obcinania prostymi równoległymi do osi układu współrzędnych oraz 3D obcinania płaszczyznami prostopadłymi do osi układu współrzędnych.

 Zestawiając wybrane algorytmy przycinania można zwrócić uwagę na cechy je wyróżniające.:

• Cohen-Sutherland
  • Skomplikowane powtarzanie przycinania
  • Najefektywniejsze wykorzystanie gdy możliwa prosta akceptacja/odrzucenie dla wielu odcinków
  • Efektywny dla implementacji sprzętowej

• Cyrus-Beck
  • Upraszcza wyznaczanie przecięcia parametrycznego
  • Jednokrotne obliczenia punktu przycięcia
  • Algorytm nie jest oparty na prostej akceptacji/odrzuceniu
  • Najlepsze efekty gdy wiele odcinków musi być przyciętych

• Liang-Barsky 
  • Optymalizacja algorytmu Cyrus-Beck

W przypadku obcinania wielokąta, zastosowanie algorytmu obcinania odcinków przynosi tylko połowiczny sukces. Wielokąt tworzy bowiem zbiór uporządkowanych wierzchołków. Każdy wierzchołek jest początkiem pewnego boku i jednocześnie jest końcem poprzedniego boku w danym uporządkowaniu. Potraktowanie boków wielokąta jako zbioru odcinków i przycięcie ich powoduje, że tracimy informacje o ich połączeniach.

Przykładem algorytmu rozwiązującego ten problem jest algorytm Sutherlanda-Hodgmana obcinania wielokąta.