« poprzedni punkt | następny punkt » |
Operacja obcinania może być potrzebna wtedy, gdy zaprojektowany rysunek jest na tyle duży, że nie może być w całości wyświetlony na ekranie. W takiej sytuacji sensowne jest wybranie z rysunku tylko tego fragmentu, który może pojawić się na ekranie i poddać przetwarzaniu tylko te obiekty, które znajdą się w wybranym fragmencie (oknie). Znanych jest kilka różnych metod obcinania. Tutaj ograniczymy się do omówienia klasycznej metody obcinania odcinków Cohena-Sutherlanda oraz metody Sutherlanda-Hodgmana obcinania wielokątów.
Zacznijmy od problemu obcinania odcinków. Algorytm jest realizowany w dwóch fazach. W pierwszej fazie chodzi o to, żeby z procesu obcinania wyeliminować te odcinki, które z pewnością nie wymagają obcinania: albo leżą poza oknem albo całkowicie mieszczą się w oknie. Przykłady różnego usytuowania odcinków względem okna pokazuje rysunek VII.7. W drugiej fazie każdy odcinek z tych, które pozostaną po pierwszej fazie, jest niezależnie obcinany.
![]() |
Rys. VII.7. Przykładowe położenia odcinków względem okna obcinania
Dla celów szybkiego sprawdzania, czy odcinek może być wyeliminowany z dalszej procedury obcinania Cohen i Sutherland zaproponowali, żeby podzielić płaszczyznę okna na dziewięć części uzyskanych w wyniku przedłużenia krawędzi okna. Każdej części został przypisany kod czterobitowy. Ilustruje to rysunek VII.8. Zasada przypisania kodów jest następująca. Wszystkie części leżące z lewej strony okna mają jedynkę na pierwszej pozycji kodu. Wszystkie części leżące z prawej strony okna mają jedynkę na drugiej pozycji kodu itd.
![]() |
Rys. VII.8. a) Podział obszaru na części i sposób przypisania kodów; b) przykładowe analizowane odcinki
Decyzję co do możliwości wyeliminowania odcinka podejmuje się w następujący sposób. Każdemu końcowi odcinka przypisywany jest kod obszaru, w którym ten koniec znajduje się. Następnie znajduje się iloczyn logiczny tych kodów (wyznacza się iloczyn logiczny dla każdej pary odpowiadających sobie bitów niezależnie). Jeżeli iloczyn jest różny od zera to odcinek można odrzucić (na przykład odcinek A na rysunku) jako leżący poza oknem. Można również wyeliminować z dalszej procedury obcinania odcinki, których oba końce leżą w oknie (odcinek D na rysunku). Innych odcinków nie można wyeliminować, nawet mimo tego, że z pewnością leżą poza oknem, tak jak na przykład odcinek B na rysunku. Wynika to stąd, że tak prosta procedura nie może rozróżnić odcinków takich jak B i C na rysunku. Niemniej mimo, że skuteczność procedury nie jest stuprocentowa, jest ona stosowana ze względu na prostotę. Wszystkie odcinki, które nie zostaną wyeliminowane są poddawane dalszej procedurze obcinania.
Przykład
Sprawdzić czy odcinki A i C z rysunku VII.8 można wyeliminować z dalszej procedury obcinania.
Końce odcinka A znajdują się w obszarach o kodach 1001 oraz 1000. Iloczyn tych kodów jest równy 1000, a więc jest różny od zera. Wobec tego odcinek może być wyeliminowany.
Końce odcinka C znajdują się w obszarach o kodach 1000 oraz 0010. Iloczyn tych kodów jest równy 0000, a więc jest równy zeru. Wobec tego odcinek nie może być wyeliminowany.
Procedura obcinania składa się z czterech kroków. W każdym z nich dokonuje się obcięcia przez jedną krawędź okna, zawsze w ustalonej kolejności. W kroku obcinania przez wybraną krawędź znajduje się przecięcie odcinka z krawędzią i usuwa się tę część odcinka, która leży na zewnątrz okna. Procedurę ilustruje rysunek VII.9.
![]() |
Rys. VII.9. Procedura obcinania odcinka przez kolejne krawędzie okna
Procedurę obcinania wielokątów wypukłych można zrealizować następująco. Najpierw warto sprawdzić relację położenia wielokąta i okna. Możliwe przypadki są pokazane na rysunku VII.10.
![]() |
Rys. VII.10. Możliwe relacje położenia wielokąta i okna. a) Obiekty są rozłączne, b) wielokąt leży wewnątrz okna, c) wielokąt przecina się z oknem, d) okno zawiera się w wielokącie
W trzech przypadkach sposób postępowania jest oczywisty. Jedynie w przypadku c) konieczne jest kontynuowanie procedury. Można ją zrealizować w czterech krokach. W każdym kroku można dokonywać obcinania przez kolejną krawędź okna (a ściślej przez linię, na której leży krawędź). Za każdym razem odrzucana jest część wielokąta leżąca po zewnętrznej stronie okna. Ilustruje to rysunek VII.11. W tym przypadku wystarczyło obcięcie przez dwie krawędzie okna.
![]() |
Rys. VII.11. Przykład obcinania wielokąta
W procedurze, w najprostszym przypadku, można bezpośrednio wykorzystać algorytm obcinania odcinków w odniesieniu do poszczególnych krawędzi obcinanego wielokąta. Wygodniejsze może się jednak okazać skorzystanie z pomysłu zaproponowanego przez Sutherlanda i Hodgmana.
Załóżmy, że będziemy przeglądali krawędzie wielokąta w kierunku przeciwnym do ruchu wskazówek zegara. Załóżmy też, że dla każdej linii, na której leży krawędź okna wyróżniamy stronę zewnętrzną i wewnętrzną - po stronie wewnętrznej leży okno. Istotę pomysłu ilustruje rysunek VII.12. Wyróżniono na nim cztery sytuacje jakie mogą wystąpić przy analizie relacji krawędzi wielokąta z rozpatrywaną krawędzią okna (linią). Krawędź wielokąta może przechodzić ze strony zewnętrznej na stronę wewnętrzną rozpatrywanej krawędzi okna. Wtedy znajdujemy punkt przecięcia P i na pomocniczą listę wpisujemy ten punkt przecięcia P oraz docelowy koniec krawędzi wielokąta W. Jeżeli krawędź wielokąta leży całkowicie po wewnętrznej stronie krawędzi okna, to na pomocniczą listę wpisujemy docelowy wierzchołek krawędzi wielokąta W. Jeżeli krawędź wielokąta przechodzi na stronę zewnętrzną krawędzi okna, to na pomocniczą listę wpisujemy punkt przecięcia z krawędzią okna. Jeżeli krawędź wielokąta leży w całości po stronie zewnętrznej, to nic nie wprowadzamy na pomocniczą listę.
![]() |
Rys. VII.12. Cztery przypadki usytuowania krawędzi wielokąta względem krawędzi okna. Dla każdego przypadku zaznaczono informacje jakie należy wprowadzić na pomocniczą listę
Na rysunku VII.13 pokazano poprzedni przykład obcinania wielokąta przez okno z uwzględnieniem przedstawionych reguł. Dla uproszczenia zamiast tworzyć pomocniczą listę bezpośrednio na rysunku zaznaczano odpowiednie punkty, przypisując im numery w kolejności pojawiania się. W każdym kroku analizę zaczynano od krawędzi oznaczonej literą A. Każdorazowo, po ustaleniu pomocniczej listy, łączy się punkty w kolejności pojawiania się na liście: od pierwszego do ostatniego i do pierwszego. Zewnętrzną część wielokąta usuwa się.
![]() |
Rys. VII.13. Kolejne kroki algorytmu obcinania
Proponuję samodzielnie wykonać algorytm obcinania dla wielokąta pokazanego na rysunku VII.14.
![]() |
Rys. VII.14. Przykład do samodzielnego wykonania obcinania
« poprzedni punkt | następny punkt » |