Spis treści

1. Wstęp
2. Teoria
   1. Odcinek
   2. Warunki obcięcia
3. Opis działania algorytmu
   1. Obcinanie lewej krawędzi
   2. Obcinanie prawej krawędzi
   3. Obcinanie dolnej krawędzi
   4. Obcinanie górnej krawędzi
4. Implementacja w języku C
5. Od autora

1. Wstęp

Widok i Okno to dwa pojęcia używane w grafice komputerowej, które są ściśle związane z przenoszeniem obrazu rzeczywistego na ekran komputera. Obraz rzeczywisty zostaje objęty oknem, które to jest przenoszone na pole widoku, lub inaczej widok (czyli w naszym przypadku ekran komputera). Przenoszenie obrazu z okna do pola widoczności powoduje obcięcie tego, co znajduje się poza tym oknem (patrz rysunek poniżej).

Sama problematyka przenoszenia obrazu rzeczywistego na ekran komputera stanowi materiał na oddzielny artykuł, więc nie będziemy się tutaj nią zajmować. Skupię się bardziej na samej problematyce obcinania obrazu na podstawie jednego z ciekawszych algorytmów - algorytmu Lianga-Barskyego. Algorytm ten zasługuje na uwagę z tego względu, że jest o wiele bardziej wydajny od bardziej popularnego algorytmu Cohena-Sutherlanda, co obrazuje poniższa tabela:

Pisząc artykuł starałem się w możliwie najbardziej przystępny i intuicyjny sposób przybliżyć matematyczne podstawy pomagające w zrozumieniu działania algorytmu, unikając przy tym wyświechtanej matematyki, tysięcy wzorów i wszelkiego innego "kujoństwa". Tyle słowem wstępu, zapraszam do lektury;)

2. Teoria

a. Odcinek

Na początek troszkę teorii, której poznanie pewnie pomoże nam w lepszym zrozumieniu. Zaczniemy od definicji odcinka, która brzmi:

Równanie ogólne odcinka ma postać:

Skoro oznaczenia mamy juz za soba, postarajmy sie teraz je zrozumiec. W naszych rozwazaniach pomocny bedzie rysunek. Przyjrzyjmy sie mu:

rys. 1

Posługując się równaniem ogólnym odcinka, możemy odczytać sobie współrzędne dowolnego punktu należącego do tego odcinka. Do określenia miejsca w którym znajduje się zadany punkt, służy właśnie liczba t. Liczba ta wyraża stosunek położenia naszego punktu względem początku odcinka, do długości rzutu prostopadłego odcinka na którąś z osi. I tak, gdy liczba t przyjmie wartość skrajną np. 0, to odnosi się do punktu A, który jest początkiem naszego odcinka ( x = x_A ; y = y_A). Analogicznie dla t równego 1 otrzymamy położenie punktu B, czyli końca naszego odcinka (x = x_A + dx ; y = y_A + dy ; gdzie dx = x_B - x_A , a dy = y_B - y_A). Gdy 0 < t < 1 to odnosimy się do dowolnego punktu należącego do odcinka (patrz rys. 1).
Opisane powyżej równanie ogólne odcinka bardzo nam się przyda , ponieważ 99% algorytmu polega właśnie na wyznaczeniu odpowiednich wartości t, która to będzie użyta do wyznaczenia miejsca przecięcia się odcinka z brzegiem obszaru obcinania.

b. Warunki obcięcia

Gdy chcemy, aby jakiś punkt (np. początek odcinka A(x_A, y_A)) znajdował się w obszarze obcinania (X_min, Y_min, X_max, Y_max), to punkt ten musi spełniać zależność:

Gdy skorzystamy z równania ogólnego odcinka, to otrzymamy

Jak widać, możemy to sobie rozpisać na cztery nierówności (jedna nierówność na poszczególną krawędź obszaru obcinania):

W porządku. Teraz dla naszej wygody przyjmijmy sobie, że za (x_B - x_A) i (y_B - y_A) będziemy podstawiać odpowiednio dx i dy. Chcąc jeszcze bardziej ułatwić sobie zapis, powyższą nierówność zapiszmy jako:

W którym to zapisie:

Jak pisałem wcześniej 99% algorytm polega na wyznaczeniu odpowiednich wartości t, która określa położenie punktów odcinka leżących na krawędzi obszaru obcinania. Zastanówmy się teraz jak wyznaczyć tę wielkość. Z powyższych nierówności jasno wynika fakt, że gdy tP_k = q_k to wtedy punkt leży na krawędzi obszaru (w przeciwnym razie wewnątrz lub poza nim). Proste przekształcenie t = q_k / P_k wskazuje na szukaną wartość. Właśnie ten prosty wzorek jest właściwie samym sercem algorytmu więc jeśli go rozumiesz to masz już połowę drogi za sobą;).
Ok. Myślę, że wystarczy już tych przekształceń. Ważne aby uzmysłowić sobie fakt, że w ogólności zmienna P określa nam kierunek, w którym "zwrócony" jest odcinek w odniesieniu do danej krawędzi (gdy P < 0 to "kierunek" jest przeciwny, natomiast gry P > 0 to oba "kierunki" są zgodne), oraz że zmienna q określa odległość danego punku odcinka od danej krawędzi obszaru obcinania. Dla przykładu, gdy chcąc określić zmienną P względem np. lewej krawędzi (P₁) okaże się, że otrzymamy zero, to oznacza że odcinek jest równoległy do lewej krawędzi. Jeśli jeszcze zmienna q₁ będzie miała wartość ujemną to wiadomo już, że nasz odcinek w całości leży poza obszarem obcinania, ponieważ nierówność tP₁ ≤ q₁ nie jest spełniona (patrz rysunek poniżej).

rys 2

Uff. Wyjaśniliśmy sobie pokrótce wszystkie zmienne potrzebne do zastosowania algorytmu Lianga-Barsky'ego. Nie pozostaje już nic innego jak zabrać się za jego konkretny opis.

3. Opis działania algorytmu

Do opisu działania algorytmu Lianga-Barsy'ego najlepiej posłużyć się przykładem popartym odpowiednimi ilustracjami. Zatem spójrzmy na rysunek.

rys. 3

Naszym zadaniem jest "obcięcie" odcinka oznaczonego jako AB tak by swymi rozmiarami mieścił się w obszarze obcinania. Musimy zatem odnaleźć dwa punkty, które będą leżały na krawędziach tego obszaru. Te punkty będą miały pozycję t₀ i t₁ względem początku odcinka (punktu A). Zatem na samym początku przyjmą one wartości:
t₀ = 0 i t₁ = 1
Aby poznać wartości t₀ i t₁ musimy skorzystać ze wzoru, który wyprowadziliśmy sobie w poprzednim rozdziale tj. t = q_k / P_k.
Jak widać, wcześniej musimy znaleźć q_k i P_k. Wartości te różnią się od siebie w zależności od krawędzi obszaru obcinania, dlatego omówię każdą z sytuacji oddzielnie. Niemniej wartości P_k różnią się jedynie znakiem "-" przed dx i dy, więc te wartości obliczmy już sobie teraz:

dx = x₁ - x₀ = 9 - 3 = 6

dy = y₁ - y₀ = 9 - 2 = 7

a. Obcinanie lewej krawędzi

W tym wypadku wartości P_k i q_k przyjmują postać (patrz rozdział "Warunki obcięcia"):

P₁ = -dx oraz q₁ = x₀ - x_min.

Obliczymy sobie ich wartość:

P₁ = -6 oraz q₁ = 3 - 4 = -1

rys. 4

Jak widać po wartości q₁, punkt początkowy odcinka leży na zewnątrz obszaru obcinania, jednak wartość P₁ jest ujemna, co oznacza, że odcinek ma "kierunek" przeciwny do "kierunku" krawędzi (czyli kierunek "do wnętrza" obszaru). Skoro tak, to zmianie powinna ulec wartość zmiennej t₀ (ponieważ nie interesuje nas to, co leży w "kierunku" zgodnym z lewą krawędzią a więc to, co leży poza obszarem obcinania). Sprawdźmy jednak czy tak się stanie. Wyznaczmy sobie wartość t według wzoru t = q_k / P_k. Otrzymamy wartość 0,167. Musimy jeszcze sprawdzić, czy aby otrzymana wartość nie jest większa od wartości t₁, co oznaczałoby że odcinek w całości leży poza omawianą krawędzią. Całe szczęście tak nie jest (0, 167 < 1) więc z czystym sumieniem możemy przypisać zmiennej t₀ nową wartość t, która to określa nam położenie punktu przecięcia się naszego odcinka z lewą krawędzią obszaru obcinania (patrz rysunek 4).
W tym momencie nasze zmienne t maja następujące wartości:

t₀ = 0,167 i t₁ = 1

Zabierzmy się teraz za prawą krawędź.

b. Obcinanie prawej krawędzi

Dalszy sposób postępowania jest bardzo zbliżony do tego co robiliśmy poprzednio, jednak w gwoli jasności prześledźmy dalsze czynności.

P₂ = dx oraz q₂ = x_max - x₀.

Obliczymy sobie ich wartość:

P₂ = 6 oraz q₂ = 9 - 3= 6

rys. 5

Widać, że "kierunek" odcinka jest zgodny z "kierunkiem" prawej krawędzi (P₂ > 0), więc w tym wypadku powinniśmy szukać nowej wartości dla t₁. Wyznaczona wartość t jest równa 1. Skoro to ustaliliśmy, to musimy sprawdzić, czy ta wartość nie jest mniejsza od wartośći t₀. Jeśli bowiem wyznaczona wartość t byłaby mniejsza od t₀ oznaczałoby to, że odcinek całkowicie leży poza prawą krawędzią obcinania. U nas 1 > 0 więc nie mamy się o co martwić;) Jesteśmy w momencie w którym możemy powiedzieć, że znaleźliśmy "nową" wartość dla t₁. W tym momencie mamy:

t₀ = 0,167 i t₁ = 1

Lecimy dalej...

c. Obcinanie dolnej krawędzi

P₃ = -dy oraz q₃ = y₀ - y_min.

Z tego mamy, że:

P₃ = -7 oraz q₃ = 2 - 4= -2

rys. 6

Jak widać sytuacja jest bardzo podobna do tej jaką zastaliśmy przy obcinaniu lewą krawędzią obcinania. Nasze t w tym wypadku wynosi 0,286 i jest ono mniejsze od t₁ (0,286 < 1), więc możemy zmiennej t₀ przypisać nową wartość t. Mamy więc sobie:

t₀ = 0,268 i t₁ = 1

d. Obcinanie górnej krawędzi

P₄ = dy oraz q₄ = y_max - y₀.

Z tego mamy, że:

P₄ = 7 oraz q₄ = 8 - 2= 6

rys. 7

Z tego t = 0,857, która to wartość oczywiście nie jest mniejsza od t₀ (0,857 > 0,268), więc tak oto wyznaczyliśmy sobie nową wartość dla t₁. W ostatecznym rozrachunku, otrzymaliśmy następujące wartości dla t₀ i t₁:

t₀ = 0,268 i t₁ = 0,875

Uff trochę było liczenia, ale to jeszcze nie koniec. W ten oto sposób wyznaczyliśmy sobie położenie punktów względem odcinka, a nam zależy na poznaniu współrzędnych tych punktów. Jak zapewne słusznie się domyślasz, musimy skorzystać ze wzoru ogólnego odcinka (patrz rozd. Teoria). Nowe punkty nazwiemy sobie jako C i D. Mamy zatem::

Podstawiając sobie odpowiednie wartości otrzymamy:

W ten oto sposób wyznaczyliśmy sobie dwa punkty tj. C(5, 4) i D(8, 8), które punktami przecięcia się naszego "starego" odcinka z krawędziami obszaru obcinania (patrz rysunek poniżej).

rys. 8

To już koniec. Nie było to trudne prawda? ;)

4. Implementacja w języku C

Poniżej przedstawiam prostą implementację. Jest ona przepisaniem "słowo w słowo" algorytmu, więc można w poniższym kodzie wiele zoptymalizować. Niemniej dla celów dydaktycznych implementację algorytmy Lianga-Barskyego można przedstawić tak:
UWAGA: Poniższa implementacja odnosi się do prawoskrętnego układu współrzędnych, w którym początek układu znajduje się w górnym lewym rogu ekranu, a wartości na osi Y wzrastają ku dołowi. Z takim układem mamy zazwyczaj do czynienia w grafice komputerowej.

#include <windows.h>
#include <math.h>
void LiangBarsky(RECT rcClip, POINT* ptA, POINT* ptB) {
     float t0, t1, R, dx, dy, P, q;
     unsigned char k;
     t0 = 0;
     t1 = 1;
     dx = ptB->x - ptA->x;
     dy = ptA->y - ptB->y;
     for(k = 1; k <= 4; k++) {
           switch(k) {
                     case 1: {      // lewo
                          P = -dx;
                          q = ptA->x - rcClip.left;
                          break;
                     }
                     case 2: {      // prawo
                          P = dx;
                          q = rcClip.right - ptA->x;
                          break;
                     }
                     case 3: {      // dol
                          P = -dy;
                          q = rcClip.bottom - ptA->y;
                          break;    
                     }
                     case 4: {      // gora
                          P = dy;
                          q = ptA->y - rcClip.top;
                     }
           }
           if((P != 0) || (q != 0)) {
                if(P != 0) {
                     R = q / P;
                     if(P > 0) {
                          if(R > t0) {
                               t1 = min(t1, R);
                          } else
                                 return;
                     } else {
                            if(R < t1) {
                                 t0 = max(t0, R);
                            } else
                                  return;
                     }
                } else
                       continue;
           } else
                  return;
     }
     ptB->x = lroundf(ptA->x + t1 * dx);
     ptB->y = lroundf(ptA->y - t1 * dy);
     ptA->x = lroundf(ptA->x + t0 * dx);
     ptA->y = lroundf(ptA->y - t0 * dy);
}

5. Od autora

Mam nadzieje, że ów artykuł okazał się pomocny w zrozumieniu algorytmu Lianga-Barskyego. Jeśli masz jakieś sugestie bądź spostrzeżenia dotyczące tego artykułu, to bardzo proszę o kontakt ze mną poprzez mój adres e-mail. Będę wdzięczny za wszelkie uwagi. Na koniec pragnę jeszcze podziękować Morituriusowi z Warsztatu za cenne uwagi i sugestie dzięki którym macie przed sobą doskonalszą wersję artykułu, oraz Demonowi dzięki któremu wykryłem i usunąłem błędy i niedomówienia w implementacji algorytmu.
Tymczasem dziękuję za uwagę i pozdrawiam;)

r.Q