Podręcznik Grafika komputerowa i wizualizacja

9.1. Wprowadzenie

Zadanie eliminacji elementów zasłoniętych (zwany także zadaniem rozstrzygania widoczności lub zadaniem wyznaczania powierzchni widocznych) polega na określeniu, które fragmenty obiektów sceny mogą być widoczne przez wirtualną kamerę (przez obserwatora). Problem wydaje się nam banalny, ale aby w wirtualnym świecie zaszło naturalne dla naszego widzenia zasłanianie jednych obiektów przez drugie, to trzeba to opisać odpowiednim algorytmem.

Jest to przykład zadania, dla którego nie jest znane jedno, uniwersalne rozwiązanie.

Rys.9.1. Zadanie rozstrzygania widoczności.

Generalnie rzecz biorąc, zadanie to można traktować jako szeroko rozumiany problem sortowania. Z punkt widzenia obserwatora obiekty leżące dalej są zasłonięte przez obiekty leżące bliżej. Niestety to proste stwierdzenie nie przekłada się na równie prosty algorytm. Już samo określenie „jeden obiekt leżący dalej od drugiego” może prowadzić do niejednoznaczności, gdyż trudno przypisać jedną miarę odległości obiektowi zajmującemu pewien obszar w przestrzeni. Jak więc porównać położenia tych obiektów, a tym bardziej wyciągnąć wnioski o ich wzajemnym zasłanianiu. W skrajnym przypadku można wyobrazić sobie sytuację, że dwa obiekty zasłaniają się w taki sposób, że każdy jest częściowo zasłonięty przez drugi z nich. Do tego relacja częściowego zasłaniania nie jest relacją przechodnią. A zatem wyciągnięcie właściwego wniosku dotyczącego zasłaniania na podstawie wzajemnego położenia obiektów jest zadaniem trudnym.

Znanych jest bardzo wiele różnych algorytmów rozstrzygania widoczności. W latach siedemdziesiątych i osiemdziesiątych XX wieku powstało ich rzeczywiście dużo. Warto wspomnieć przynajmniej o kilku z nich.