Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Algorytm obcinania Lianga-Barsky\ego

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest r.Q. Jeżeli został importowany poprawnie, usuń ten szablon!

"Algorytm Lianga-Barsky'ego."

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:
Wymiar odcinka wzrost wydajności
odcinki w przestrzeni 2D36%
odcinki w przestrzeni 3D40%
odcinki w przestrzeni 4D70%
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:

Odcinek to część prostej zawarta między dwoma jej punktami włączając te punkty.

Równanie ogólne odcinka ma postać:
x = x0 + t(x1 - x0)
y = y0 + t(y1 - y0)
przyczym 0 ≤ t ≤ 1
Skoro oznaczenia mamy już za sobą, postarajmy się teraz je zrozumieć. W naszych rozważaniach pomocny będzie rysunek. Przyjrzyjmy się mu:

Rysunek 1

Rysunek 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 = xA ; y = yA). Analogicznie dla t równego 1 otrzymamy położenie punktu B, czyli końca naszego odcinka (x = xA + dx ; y = yA + dy ; gdzie dx = xB - xA , a dy = yB - yA). 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(xA, yA)) znajdował się w obszarze obcinania (Xmin, Ymin, Xmax, Ymax), to punkt ten musi spełniać zależność:
Xmin ≤ xA ≤ Xmax
Ymin ≤ yA ≤ Ymax
Gdy skorzystamy z równania ogólnego odcinka, to otrzymamy
(1) Xmin ≤ xA + t(xB - xA) ≤ Xmax
(2) Ymin ≤ yA + t(yB - yA) ≤ Ymax
Jak widać, możemy to sobie rozpisać na cztery nierówności (jedna nierówność na poszczególną krawędź obszaru obcinania):

(1) -t(xB - xA) ≤ xA - Xmin [lewa krawędź obszaru obcinania]
(1) t(xB - xA) ≤ xmax - XA [prawa krawędź obszaru obcinania]
(2) -t(yB - yA) ≤ yA - Ymin [dolna krawędź obszaru obcinania]
(2) t(yB - yA) ≤ ymax - YA [górna krawędź obszaru obcinania]
Uwaga: Liczby w nawiasach okrągłych określają z której nierówności co się bierze.

W porządku. Teraz dla naszej wygody przyjmijmy sobie, że za (xB - xA) i (yB - yA) będziemy podstawiać odpowiednio dx i dy. Chcąc jeszcze bardziej ułatwić sobie zapis, powyższą nierówność zapiszmy jako:
tPk ≤ qk
gdzie k = 1, 2, 3, 4
W którym to zapisie:

P1 = -dx q1 = xA - xmin [lewa krawędź]
P2 = dx q2 = xmax - xA [prawa krawędź]
P3 = -dy q3 = yA - ymin [dolna krawędź]
P4 = dy q4 = ymax - yA [górna krawędź]

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 tPk = qk to wtedy punkt leży na krawędzi obszaru (w przeciwnym razie wewnątrz lub poza nim). Proste przekształcenie t = qk / Pk 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 (P1) okaże się, że otrzymamy zero, to oznacza że odcinek jest równoległy do lewej krawędzi. Jeśli jeszcze zmienna q1 będzie miała wartość ujemną to wiadomo już, że nasz odcinek w całości leży poza obszarem obcinania, ponieważ nierówność tP1 ≤ q1 nie jest spełniona (patrz rysunek poniżej).

Rysunek 2

Rysunek 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

Rysunek 3
Rysunek 3
Do opisu działania algorytmu Lianga-Barsy'ego najlepiej posłużyć się przykładem popartym odpowiednimi ilustracjami. Zatem spójrzmy na rysunek obok. 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ę t0 i t1 względem początku odcinka (punktu A). Zatem na samym początku przyjmą one wartości:
t0 = 0 i t1 = 1
Aby poznać wartości t0 i t1 musimy skorzystać ze wzoru, który wyprowadziliśmy sobie w poprzednim rozdziale tj. t = qk / Pk.
Jak widać, wcześniej musimy znaleźć qk i Pk. 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 Pk różnią się jedynie znakiem "-" przed dx i dy, więc te wartości obliczmy już sobie teraz:
dx = x1 - x0 = 9 - 3 = 6
dy = y1 - y0 = 9 - 2 = 7




a. Obcinanie lewej krawędzi

Rysunek 4
Rysunek 4
W tym wypadku wartości Pk i qk przyjmują postać (patrz rozdział "Warunki obcięcia"):

P1 = -dx oraz q1 = x0 - xmin.

Obliczymy sobie ich wartość:

P1 = -6 oraz q1 = 3 - 4 = -1

Jak widać po wartości q1, punkt początkowy odcinka leży na zewnątrz obszaru obcinania, jednak wartość P1 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 t0 (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 = qk / Pk. Otrzymamy wartośc 0,167. Musimy jeszcze sprawdzić, czy aby otrzymana wartość nie jest większa od wartości t1, 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 t0 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:

t0 = 0,167 i t1 = 1

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

b. Obcinanie prawej krawędzi

Rysunek 5
Rysunek 5
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.

P2 = dx oraz q2 = xmax - x0.

Obliczymy sobie ich wartość:

P2 = 6 oraz q2 = 9 - 3= 6

Widać, że "kierunek" odcinka jest zgodny z "kierunkiem" prawej krawędzi (P2 > 0), więc w tym wypadku powinniśmy szukać nowej wartości dla t1. Wyznaczona wartość t jest równa 1. Skoro to ustaliliśmy, to musimy sprawdzić, czy ta wartość nie jest mniejsza od wartości t0. Jeśli bowiem wyznaczona wartość t byłaby mniejsza od t0 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 t1. W tym momencie mamy:

t0 = 0,167 i t1 = 1

Lecimy dalej...

c. Obcinanie dolnej krawędzi

Rysunek 6
Rysunek 6

P3 = -dy oraz q3 = y0 - ymin.

Z tego mamy, że:

P3 = -7 oraz q3 = 2 - 4= -2

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 t1 (0,286 < 1), więc możemy zmiennej t0 przypisać nową wartość t. Mamy więc sobie:

t0 = 0,268 i t1 = 1





d. Obcinanie górnej krawędzi

Rysunek 7
Rysunek 7

P4 = dy oraz q4 = ymax - y0.

Z tego mamy, że:

P4 = 7 oraz q4 = 8 - 2= 6

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

t0 = 0,268 i t1 = 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:
xC = xA + t0(xB - xA)
yC = yA + t0(yB - yA)
xD = xA + t1(xB - xA)
yD = yA + t1(yB - yA)
Podstawiając sobie odpowiednie wartości otrzymamy:
xC = 3 + 0,268 * (9 - 3) = 4,6 ≈ 5
yC = 2 + 0,268 * (9 - 2) = 3,9 ≈ 4
xD = 3 + 0,875 * (9 - 3) = 8,3 ≈ 8
yD = 2 + 0,875 * (9 - 2) = 8,1 ≈ 8
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).

Rysunek 8

Rysunek 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 w implementacji algorytmu.
Tymczasem dziękuję za uwagę i pozdrawiam;)

r.Q

Tekst dodał:
r.Q
08.05.2007 17:01

Ostatnia edycja:
r.Q
08.05.2007 17:01

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 08.05.2007 17:01 r.Q 24.22 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • jjoker (@jjoker) 28 stycznia 2011 10:10
    witam, fajny artykuł ale niestety obrazki nie chodzą (sprawdzałem na operze, ie oraz mozilli). Jakbyś mógł je wrzucić jeszcze raz to byłbym wdzięczny
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)