Obcinanie linii
W grafice komputerowej przycinanie linii to proces usuwania ( przycinania ) linii lub części linii poza obszarem zainteresowania ( rzutnią lub objętością widoku ). Zazwyczaj usuwana jest każda część linii, która znajduje się poza obszarem wyświetlania.
Istnieją dwa popularne algorytmy obcinania linii: Cohena-Sutherlanda i Lianga-Barsky'ego .
Metoda obcinania linii składa się z różnych części. Testy są przeprowadzane na danym odcinku linii, aby dowiedzieć się, czy leży on poza obszarem widoku lub objętością. Następnie przeprowadzane są obliczenia przecięć z jedną lub większą liczbą obwiedni tnących. Określenie, która część linii znajduje się wewnątrz lub na zewnątrz obszaru przycinania, odbywa się poprzez przetwarzanie punktów końcowych linii w odniesieniu do przecięcia.
Cohen-Sutherland
W grafice komputerowej algorytm Cohena-Sutherlanda (nazwany na cześć Danny'ego Cohena i Ivana Sutherlanda) jest algorytmem obcinania linii. Algorytm dzieli przestrzeń 2D na 9 regionów, z których widoczna jest tylko środkowa część (rzutnia).
W 1967 r. Symulacja lotu prowadzona przez Danny'ego Cohena doprowadziła do opracowania dwu- i trójwymiarowych algorytmów obcinania linii grafiki komputerowej Cohena-Sutherlanda, stworzonych wraz z Ivanem Sutherlandem.
Liang-Barsky
Algorytm Lianga-Barsky'ego wykorzystuje równanie parametryczne linii i nierówności opisujące zakres obcinania w celu określenia przecięć między linią a obcinaniem. Dzięki tym przecięciom wie, która część linii powinna zostać narysowana. Algorytm ten jest znacznie bardziej wydajny niż algorytm Cohena-Sutherlanda, ale Cohen-Sutherland wykonuje trywialne akceptacje i odrzucanie znacznie szybciej, dlatego zamiast tego należy rozważyć, czy większość linii, które należy przyciąć, będzie całkowicie w oknie klipu lub poza nim .
Cyrus-Beck
Bardzo podobny do algorytmu obcinania linii Lianga-Barsky'ego. Różnica polega na tym, że Liang-Barsky jest uproszczoną odmianą Cyrusa-Becka, która została zoptymalizowana pod kątem prostokątnego okna klipu.
Algorytm Cyrusa-Becka jest przeznaczony przede wszystkim do przycinania linii w postaci parametrycznej z wypukłym wielokątem w 2 wymiarach lub z wypukłym wielościanem w 3 wymiarach.
Nicholl – Lee – Nicholl
Algorytm Nicholl – Lee – Nicholl to szybki algorytm obcinania linii, który zmniejsza szanse na wielokrotne przycinanie pojedynczego segmentu linii, co może się zdarzyć w algorytmie Cohena – Sutherlanda. Okno przycinania jest podzielone na kilka różnych obszarów, w zależności od położenia początkowego punktu linii do przycięcia.
Szybkie przycinanie
Algorytm ten ma podobieństwa z algorytmem Cohena-Sutherlanda. Pozycje początkowa i końcowa są klasyfikowane według zajmowanej części siatki 9-obszarów. Duża instrukcja switch przeskakuje do wyspecjalizowanej procedury obsługi dla tej sprawy. W przeciwieństwie do tego, Cohen-Sutherland może być zmuszony do kilkukrotnej iteracji, aby obsłużyć ten sam przypadek.
Algorytm O (lgN ) .
Algorytm ten klasyfikuje wierzchołki względem podanej linii w domniemanej postaci p : ax + by + c = 0. Ponieważ przyjmuje się, że wielokąt jest wypukły, a wierzchołki są uporządkowane zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara, można zastosować wyszukiwanie binarne, które prowadzi do O (lg N ) złożoność czasu wykonania.
Skala
Algorytm ten opiera się na jednorodnych współrzędnych i dualności . Może być używany do przycinania linii lub odcinków linii do prostokątnego okna, jak również do wypukłego wielokąta. Algorytm opiera się na klasyfikacji wierzchołka okna obcinania względem półprzestrzeni określonej przez prostą p : ax + przez + c = 0. Wynik klasyfikacji określa krawędzie przecięte przez prostą p . Algorytm jest prosty, łatwy do wdrożenia i rozszerzalny również do okna wypukłego. Linia lub odcinek linii p można obliczyć z punktów r 1 , r 2 podanych we współrzędnych jednorodnych bezpośrednio za pomocą iloczynu krzyżowego jako
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
lub jako
- p = r 1 × r 2 = ( x 1 , y 1 , 1) × ( x 2 , y 2 , 1).