Algorytm Lianga-Barsky’ego

Algorytm Lianga-Barsky’ego – algorytm obcinania odcinka do prostokątnego okna[1], stosowany w grafice komputerowej. Nazwa algorytmu pochodzi od nazwisk autorów You-Dong Lianga i Briana A. Barsky’ego, którzy zaproponowali go w swojej pracy[2]. Algorytm wykorzystuje parametryczne równanie odcinka oraz nierówności opisujące prostokątne okno do określenia wartości współczynnika parametrycznego, dla których odcinek przecina się z bokami okna[3]. Na podstawie tak uzyskanych danych można określić, którą część odcinka można narysować. Ten algorytm jest bardziej wydajny niż algorytm Cohena-Sutherlanda[4] w przypadku gdy zachodzi konieczność przycięcia odcinka[5]. Pomysłem w algorytmie Lianga-Barsky’ego jest wykonywanie tylu porównań, na ile jest to możliwe przed właściwym obliczaniem końców przyciętego odcinka[5].

Opis

Argumenty przekazywane do algorytmu

1. Odcinek łączący punkty ( x 1 , y 1 ) {\displaystyle (x_{1},y_{1})} i ( x 2 , y 2 ) , {\displaystyle (x_{2},y_{2}),} przedstawiony parametrycznie równaniami[3]:

x ( t ) = x 1 + t ( x 2 − x 1 ) = x 1 + t Δ x y ( t ) = y 1 + t ( y 2 − y 1 ) = y 1 + t Δ y {\displaystyle {\begin{matrix}x(t)&=&x_{1}+t(x_{2}-x_{1})&=&x_{1}+t\,\Delta x\\y(t)&=&y_{1}+t(y_{2}-y_{1})&=&y_{1}+t\,\Delta y\end{matrix}}}

dla t ∈ [ 0 , 1 ] . {\displaystyle t\in [0,1].} Zmiana parametru od 0 {\displaystyle 0} do 1 {\displaystyle 1} opisuje też kierunek rysowania odcinka, do którego odnosi się działanie algorytmu.

2. Prostokątne okno o krawędziach równoległych do osi układu współrzędnych, zadane przez współrzędne swoich narożników[6]:

x min , {\displaystyle x_{\min },} x max , {\displaystyle x_{\max },} y min , {\displaystyle y_{\min },} y max . {\displaystyle y_{\max }.}

Wynik działania algorytmu

Dwie wartości parametru t 1 ⩽ t 2 {\displaystyle t_{1}\leqslant t_{2}} takie, że ( x ( t 1 ) , y ( t 1 ) ) {\displaystyle (x(t_{1}),y(t_{1}))} i ( x ( t 2 ) , y ( t 2 ) ) {\displaystyle (x(t_{2}),y(t_{2}))} są współrzędnymi punktów przecięcia odcinka z krawędziami okna[a], bądź informacja, że takie punkty nie istnieją.

W tej pierwszej sytuacji wejściowe równania parametryczne dla t ∈ [ t 1 , t 2 ] {\displaystyle t\in [t_{1},t_{2}]} opisują odcinek, który jest wynikiem przycięcia odcinka wejściowego do obszaru okna, w tej drugiej odcinek leży w całości na zewnątrz okna.

Działanie algorytmu

Punkt ( x ( t ) , y ( t ) ) {\displaystyle (x(t),y(t))} znajduje się wewnątrz okna będącego argumentem algorytmu dokładnie wtedy, gdy spełnione są nierówności[3]:

x min ⩽ x 1 + t Δ x ⩽ x max y min ⩽ y 1 + t Δ y ⩽ y max {\displaystyle {\begin{matrix}x_{\min }&\leqslant &x_{1}+t\,\Delta x&\leqslant &x_{\max }\\y_{\min }&\leqslant &y_{1}+t\,\Delta y&\leqslant &y_{\max }\end{matrix}}}

co można wyrazić równoważnie jako cztery nierówności[3]

t p k ⩽ q k , k = 1 , 2 , 3 , 4 , {\displaystyle t\,p_{k}\leqslant q_{k},\quad k=1,2,3,4,}

odpowiadające poszczególnym krawędziom okna w kolejności: lewa, prawa, dolna, górna. Wartości parametrów są następujące:

p 1 = − Δ x , q 1 = x 1 − x min p 2 = Δ x , q 2 = x max − x 1 p 3 = − Δ y , q 3 = y 1 − y min p 4 = Δ y , q 4 = y max − y 1 {\displaystyle {\begin{array}{lcllcl}p_{1}&=&-\Delta x,&\quad q_{1}&=&x_{1}-x_{\min }\\p_{2}&=&\Delta x,&\quad q_{2}&=&x_{\max }-x_{1}\\p_{3}&=&-\Delta y,&\quad q_{3}&=&y_{1}-y_{\min }\\p_{4}&=&\Delta y,&\quad q_{4}&=&y_{\max }-y_{1}\end{array}}}

Ostateczne wyznaczenie odcinka:

  1. Odcinek pionowy spełnia p 1 = p 2 = 0 , {\displaystyle p_{1}=p_{2}=0,} a poziomy p 3 = p 4 = 0 {\displaystyle p_{3}=p_{4}=0} [3].
  2. Jeśli dla pewnego k {\displaystyle k} zachodzi q k < 0 , {\displaystyle q_{k}<0,} to odcinek znajduje się na zewnątrz okna i dalszych obliczeń nie trzeba prowadzić[3].
  3. Jeśli p k < 0 {\displaystyle p_{k}<0} to odcinek przecina bok z zewnątrz do wewnątrz, natomiast dla p k > 0 , {\displaystyle p_{k}>0,} odcinek przebiega z wewnątrz na zewnątrz.
  4. Dla niezerowego p k , {\displaystyle p_{k},} wartość parametru t = q k p k {\displaystyle t={\frac {q_{k}}{p_{k}}}} określa punkt przecięcia z bokiem okna[3].
  5. Dla danego odcinka wyznacza się t 1 {\displaystyle t_{1}} i t 2 {\displaystyle t_{2}} (parametry wyznaczające oba przycięte końce)[3]:
    t 1 = max { 0 , max p k < 0 q k p k } , t 2 = min { 1 , min p k > 0 q k p k } . {\displaystyle {\begin{array}{lcl}t_{1}&=&\max {\left\{0,\max \limits _{p_{k}<0}{\frac {q_{k}}{p_{k}}}\right\}},\\t_{2}&=&\min {\left\{1,\min \limits _{p_{k}>0}{\frac {q_{k}}{p_{k}}}\right\}}.\end{array}}}
  6. Jeśli t 1 > t 2 {\displaystyle t_{1}>t_{2}} to cały odcinek znajduje się poza oknem[1], w przeciwnym razie obliczone wartości stanowią wynik działania algorytmu.

Własności

  • Współrzędne są obliczane tylko dla dwóch punktów przecięcia[7].
  • Wystarcza obliczenie nie więcej niż czterech parametrów t {\displaystyle t} [7].
  • Algorytm nie jest iteracyjny[7].
  • Algorytm można uogólnić na przypadki trójwymiarowe[b][7].

Uwagi

  1. ↑ W brzegowym przypadku t 1 = t 2 {\displaystyle t_{1}=t_{2}} wynikiem przycięcia odcinka do okna jest jeden punkt.
  2. ↑ Ograniczeniem jest prostopadłościan wraz z dodatkową nierównością dla trzeciego wymiaru[8]:
    z min ⩽ z 1 + t Δ z ⩽ z max . {\displaystyle z_{\min }\quad \leqslant \quad z_{1}+t\,\Delta z\quad \leqslant \quad z_{\max }.}

Przypisy

  1. ↑ a b Jankowski 1990 ↓, s. 59.
  2. ↑ Liang i Barsky 1984 ↓.
  3. ↑ a b c d e f g h Jankowski 1990 ↓, s. 58.
  4. ↑ Agoston 2005 ↓, s. 80.
  5. ↑ a b Foley 1996 ↓, s. 123.
  6. ↑ Jankowski 1990 ↓, s. 53–54, 59.
  7. ↑ a b c d Clipping ↓, s. 20.
  8. ↑ Jankowski 1990 ↓, s. 104–105.

Bibliografia

  • Clipping, [w:] Max K.M.K. Agoston Max K.M.K., Computer graphics and geometric modeling. Implementation and algorithms, Springer London, 2005, s. 69–110, DOI: 10.1007/1-84628-108-3_3, ISBN 978-1-84628-108-2  (ang.).
  • James D.J.D. Foley James D.J.D., Computer Graphics: Principles and Practice, Addison-Wesley Professional, 1996, ISBN 978-0-201-84840-3 [dostęp 2015-11-30]  (ang.).
  • MichałM. Jankowski MichałM., Elementy grafiki komputerowej, Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, ISBN 83-204-1326-5 .
  • You-DongY.D. Liang You-DongY.D., B.A.B.A. Barsky B.A.B.A., A New Concept and Method for Line Clipping, „ACM Trans. Graph.”, 3 (1), 1984, s. 1–22, DOI: 10.1145/357332.357333, ISSN 0730-0301 [dostęp 2015-11-22] .
  • CS355. Graphics and Multimedia. Clipping. [dostęp 2015-11-22] [zarchiwizowane 2018-03-28]  (ang.).

Linki zewnętrzne

  • Algorytm obcinania Lianga-Barsky\ego [online], Warsztat.GD [dostęp 2015-11-22] [zarchiwizowane z adresu 2015-11-22] .
  • Grafika komputerowa I – 3. Obcinanie linii i wielokątów – MIM UW [online], mst.mimuw.edu.pl [dostęp 2015-11-22] .
  • Artykuł dot. Catmulla-Clarka
  • Bimal KumarB.K. Ray Bimal KumarB.K., A Line Segment Clipping Algorithm in 2D, „International Journal of Computer Graphics”, 3 (2), listopad 2012 [dostęp 2015-11-30] [zarchiwizowane z adresu 2017-08-08]  (ang.).