Algorytm Lianga-Barsky’ego
Algorytm Lianga-Barsky’ego to technika obcinania odcinka do prostokątnego okna, wykorzystywana w grafice komputerowej. Jego nazwa pochodzi od autorów, You-Dong Lianga i Briana A. Barsky’ego, którzy zaprezentowali go w swojej publikacji. Algorytm ten opiera się na parametrycznym równaniu odcinka oraz na nierównościach definiujących prostokątne okno, które pozwalają na określenie wartości współczynnika parametrycznego, w ramach którego odcinek przecina boki okna. Dzięki uzyskanym danym możliwe jest ustalenie, która część odcinka powinna zostać narysowana. W porównaniu do algorytmu Cohena-Sutherlanda, algorytm Lianga-Barsky’ego charakteryzuje się większą efektywnością, szczególnie w sytuacjach, gdy konieczne jest przycięcie odcinka. Kluczowym pomysłem tego algorytmu jest minimalizacja liczby porównań przed przystąpieniem do obliczeń końców przyciętego odcinka.
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:
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 również kierunek rysowania odcinka, którego dotyczy działanie algorytmu.
2. Prostokątne okno, którego krawędzie są równoległe do osi układu współrzędnych, określone przez współrzędne swoich narożników:
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, lub informacją, że takie punkty nie istnieją.
W przypadku, gdy istnieją punkty przecięcia, parametryczne równania dla
t
∈
[
t
1
,
t
2
]
{\displaystyle t\in [t_{1},t_{2}]}
opisują odcinek powstały w wyniku przycięcia wejściowego odcinka do obszaru okna, natomiast w drugim przypadku odcinek znajduje się w całości poza oknem.
Działanie algorytmu
Punkt
(
x
(
t
)
,
y
(
t
)
)
{\displaystyle (x(t),y(t))}
znajduje się wewnątrz okna, jeśli spełnione są następujące nierówności:
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 zapisać jako cztery niezależne nierówności:
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:
Odcinek pionowy spełnia
p
1
=
p
2
=
0
,
{\displaystyle p_{1}=p_{2}=0,}
a odcinek poziomy
p
3
=
p
4
=
0
{\displaystyle p_{3}=p_{4}=0}
.
Jeśli dla pewnego
k
{\displaystyle k}
zachodzi
q
k
<
0
,
{\displaystyle q_{k}<0,}
to odcinek znajduje się na zewnątrz okna i dalsze obliczenia nie są konieczne.
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.
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.
Dla danego odcinka wyznacza się
t
1
{\displaystyle t_{1}}
i
t
2
{\displaystyle t_{2}}
(parametry wyznaczające oba przycięte końce):
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}}}
Jeśli
t
1
>
t
2
{\displaystyle t_{1}>t_{2}}
to cały odcinek znajduje się poza oknem, w przeciwnym razie obliczone wartości stanowią wynik działania algorytmu.
Własności
Współrzędne są obliczane wyłącznie dla dwóch punktów przecięcia.
Wystarczy obliczyć maksymalnie cztery parametry
t
{\displaystyle t}
.
Algorytm nie jest iteracyjny.
Można go również uogólnić na przypadki trójwymiarowe.
Uwagi
Przypisy
Bibliografia
Clipping, [w:] Max K.M.K. Agoston, 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.
James D.J.D. Foley, Computer Graphics: Principles and Practice, Addison-Wesley Professional, 1996, ISBN 978-0-201-84840-3 [dostęp 2015-11-30].
Michał M. Jankowski, Elementy grafiki komputerowej, Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, ISBN 83-204-1326-5.
You-Dong Y.D. Liang, B.A.B.A. Barsky, 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].
Linki zewnętrzne
Algorytm obcinania Lianga-Barsky’ego [online], Warsztat.GD [dostęp 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ł dotyczący Catmulla-Clarka.
Bimal Kumar B.K. Ray, 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].
