Jeśli wielokąty są ścianami brył (obiektów z zamkniętą objętością), to korzystając z umowy, że wektor normalny płaszczyzny każdej ściany jest zorientowany ,,na zewnątrz bryły”, można odrzucić (uznać za niewidoczne w całości) ściany ,,odwrócone tyłem” do obserwatora. Ten wstępny test widoczności sprowadza się do zbadania znaku iloczynu skalarnego: jeśli punkt p jest dowolnym wierzchołkiem ściany, punkt o jest położeniem obserwatora, zaś n jest wektorem normalnym ściany to z warunku p-o,n≥0 wynika, że ściana jest niewidoczna.

Jeśli scena składa się z jednego wielościanu wypukłego, to wszystkie pozostałe ściany są w całości widoczne. Opisany test jest często stosowany jako wstępny etap innych algorytmów widoczności, zarówno działających w przestrzeni danych, jaki i obrazu. Przed zastosowaniem tego algorytmu trzeba się upewnić, że rysujemy bryły i położenie obserwatora nie jest wewnątrz jednej z nich.

W OpenGL-u można uaktywnić taki test, wywołując przed wyświetlaniem sceny procedury

Wyświetlane wielokąty muszą być wypukłe, a ich brzegi odpowienio zorientowane; jeśli v0, v1 i v2 są pierwszymi trzema wierzchołkami wielokąta (nie mogą one być współliniowe), to wektor v1-v0∧v2-v0 (który jest wektorem normalnym płaszczyzny ściany) musi być zorientowany na zewnątrz bryły.

Przypuśćmy, że mamy dane dwa odcinki w przestrzeni trójwymiarowej i punkt o, który jest położeniem obserwatora. Odcinki są określone za pomocą punktów końcowych, odpowiednio p1, p2 i q1, q2. Chcemy obliczyć (jeśli istnieją) punkty p i q, które leżą na odcinkach i na prostej przechodzącej przez punkt o.

Aby rozwiązać zadanie, przedstawimy poszukiwane punkty w taki sposób:

Warunkiem współliniowości punktów o, p i q jest istnienie liczby rzeczywistej u, takiej że p-o=u⁢q-o. Mamy tu układ trzech równań z trzema niewiadomymi, s, t, u:

Po przekształceniu otrzymujemy układ równań liniowych

z niewiadomym wektorem x=s,u,u⁢tT. Po jego rozwiązaniu możemy obliczyć punkty p i q. Dla celów rozsztrzygania zasłaniania trzeba jednak zinterpretować możliwe wyniki.

• Jeśli macierz układu ma rząd 0, to oba dane odcinki są zdegenerowane do punktów, a ponadto jeden z nich pokrywa się z położeniem obserwatora. Tego rodzaju dane są zwykle eliminowane przed przystąpieniem do rozstrzygania widoczności.

• Rząd 1 macierzy może wystąpić wtedy, gdy oba odcinki są równoległe i jeden z nich leży na prostej przechodzącej przez punkt o. Również ten przypadek nie wystąpi, jeśli odcinki są krawędziami ścian ,,odwróconych przodem” do obserwatora (test opisany przed chwilą odrzuca każdą ścianę, której płaszczyzna zawiera położenie obserwatora).

• Jeśli macierz ma rząd 2, to albo nie ma rozwiązań, czyli poszukiwane punkty p i q nie istnieją, albo rozwiązań jest nieskończenie wiele — oba odcinki leżą w płaszczyźnie zawierającej punkt o i mogą się zasłaniać, albo nie. Dokończenie dyskusji tego przypadku polecam jako ćwiczenie, przyda się ono podczas pisania procedur realizujących różne algorytmy widoczności (wskazówka: trzeba zbadać cztery rozwiązania odpowiadające ustalonym wartościom s i t, którym nadajemy kolejno wartości 0 i 1).

• Macierz rzędu 3 oznacza istnienie jednoznacznego rozwiązania. Po jego obliczeniu należy sprawdzić, czy s,t∈0,1; punkty p i q istnieją tylko w takim przypadku. Jeśli u<0, to punkty te znajdują się po przeciwnych stronach położenia obserwatora. Jeśli u∈0,1, to bliżej obserwatora jest punkt p, a jeśli u>1, to punkt q. Ta informacja jest potrzebna w testach widoczności.

Algorytm Ricciego jest algorytmem linii zasłoniętej dla sceny złożonej z wielokątów (np. ścian wielościanów), które nie przenikają się. Dane składają się ze zbioru ścian (ewentualnie tylko ,,odwróconych przodem” do obserwatora), zbioru ich krawędzi i położenia obserwatora. Przyjęte jest też założenie upraszczające — wszystkie ściany są wielokątami wypukłymi (w tym celu można je podzielić na wielokąty wypukłe, krawędzie wprowadzone podczas tego dzielenia nie są dołączane do zbioru krawędzi, których fragmenty mogą być widoczne).

Wykonując algorytm, kolejno dla każdej krawędzi k wykonujemy następujące czynności:

• Tworzymy reprezentację widocznych części krawędzi, w postaci listy par liczb. Liczby te są wartościami parametru, które odpowiadają punktom końcowym niezasłoniętym częściom krawędzi. Na początku każda taka lista zawiera tylko jedną parę liczb, 0,1, która reprezentuje całą krawędź.

• Kolejno dla każdej ściany s wykonujemy (specjalnie dostosowany) algorytm Lianga-Barsky'ego obcinania odcinka, czyli

  • wyznaczamy liczby a, b, które odpowiadają punktom przecięcia rzutów krawędzi k z krawędziami ściany s (jeśli takie punkty istnieją, to najwyżej dwa, ponieważ ściany są wypukłe).

  • Jeśli ściana s zasłania krawędź k, to od przedziałów parametrów reprezentujących niezasłoniętą część krawędzi k odejmujemy przedział a,b, przetwarzając odpowiednio listę (można to nazwać ,,konstrukcyjną geometrią odcinków”).

  Proces kończymy po przetworzeniu ostatniej ściany, albo po otrzymaniu pustej listy przedziałów (która oznacza, że krawędź k jest w całości niewidoczna).

• Kolejno dla każdego elementu listy obliczamy punkty na krawędzi k i wyprowadzamy (np. rysujemy) odcinek.

Koszt tego algorytmu jest proporcjonalny do kwadratu liczby krawędzi, czyli jest dość wysoki. Wśród algorytmów przestrzeni danych może to jednak być algorytm optymalny, ponieważ wynik (liczba widocznych fragmentów krawędzi albo ścian) może mieć wielkość tego rzędu. Przykład jest na rysunku 9.4.

Takie dane jak na rysunku zdarzają się jednak rzadko, w związku z czym implementując algorytm warto sięgnąć po techniki przyspieszające (obniżające średnią złożoność obliczeniową algorytmu). Najprostszy taki sposób polega na

• zrzutowaniu wierzchołków na płaszczyznę obrazu,

• posortowaniu krawędzi i ścian w kolejności rosnących najmniejszych współrzędnych x końców krawędzi lub wierzchołków ścian,

• utworzeniu (początkowo pustej) listy ścian aktywnych,

• następnie, kolejno dla każdej krawędzi k (w kolejności otrzymanej w wyniku sortowania)

  • wyrzucamy z listy ścian wszystkie ściany, których największa współrzędna x wierzchołka jest mniejsza od mniejszej współrzędnej x końca krawędzi k,

  • wstawiamy do listy wszystkie ściany, których najmniejsza współrzędna x wierzchołka jest mniejsza niż większa współrzędna x końca krawędzi k,

  • rozstrzygamy widoczność krawędzi k ze ścianami obecnymi w liście.

Na skuteczność tego sposobu ma wpływ scena oraz sposób jej zrzutowania. Metoda działa tym lepiej, im krótsze w stosunku do wielkości sceny są krawędzie i im mniejsze są ściany.

Jeszcze jedna uwaga: dla każdej krawędzi trzeba znać ściany, które do niej przylegają. Testując widoczność pomijamy je, bo żadna ściana płaska nie zasłania swoich krawędzi, a błędy zaokrągleń mogłyby doprowadzić do innego wyniku.

Algorytm Weilera-Athertona powierzchni zasłoniętej może być użyty do znalezienia fragmentów ścian widocznych z danego punktu, który może być położeniem obserwatora lub źródła światła; jest to więc także algorytm wyznaczania cieni. Dane dla tego algorytmu reprezentują scenę złożoną z płaskich wielokątnych ścian, które mogą mieć otwory, być niespójne itd. Załóżmy, że nie ma ,,zapętlenia” relacji zasłaniania ścian, tj. nie występuje para ścian, z których każda zasłania część drugiej (w przeciwnym razie należy podzielić jedną ze ścian wzdłuż prostej wspólnej płaszczyzn ścian).

W algorytmie tym sprawdza się widoczność kolejno dla wszystkich par ścian w scenie. Jedną ze ścian testowanej pary rzutuje się na płaszczyznę drugiej ściany, a następnie wykonuje się algorytm Weilera-Athertona w celu wyznaczenia różnicy tych wielokątów. Argument odejmowany odpowiada ścianie leżącej bliżej obserwatora (test widoczności można przeprowadzić dla jednej, dowolnej pary punktów, z których jeden zasłania drugi).

Znaleziony wielokąt odpowiada widocznej części ściany. Od wielokąta tego odejmuje się rzuty wszystkich innych ścian, które ścianę daną zasłaniają. Przetwarzanie ściany kończymy po wyczerpaniu ścian, które mogą ją zasłaniać, albo po otrzymaniu zbioru pustego.

Opisany algorytm jest dość kosztowny (ponieważ wykonuje obliczenia dla każdej pary ścian), ale często można obniżyć jego koszt za pomocą podobnej metody, jak dla algorytmu Ricciego.

Przypuśćmy, że ściany nie przenikają się. Wtedy dowolna krawędź, która nie jest widoczna w całości, ma punkty zmiany widoczności; punkty te są zasłaniane przez punkty leżące na krawędziach konturowych, tj. takich krawędziach, do których przylegają ściany, z których jedna jest ,,obrócona przodem” do obserwatora, a druga jest ,,obrócona tyłem”.

Krawędzi konturowych jest często znacznie mniej niż wszystkich krawędzi w scenie, co pozwala otrzymać algorytm linii zasłoniętej o mniejszej złożoności obliczeniowej niż ma algorytm Ricciego.

W tym celu określamy graf krawędziowy, czyli graf skierowany, którego wierzchołkami są wierzchołki ścian, a krawędziami są krawędzie tych ścian. Orientacja krawędzi jest obojętna, ale musi być określona. Po utworzeniu tego grafu będziemy wprowadzać dodatkowe wierzchołki, dokonując podziału krawędzi w punktach wyznaczonych za pomocą algorytmu opisanego w p. 9.2.2.

Dodatkowo określimy stopień zasłonięcia, który jest funkcją w przestrzeni. Wartość tej funkcji w dowolnym punkcie p jest równa liczbie ścian, które znajdują się między punktem p i obserwatorem. Punkty widoczne to te, których stopień zasłonięcia jest równy 0.

Kolejne kroki algorytmu są następujące:

1. Wyznaczamy graf krawędziowy (na ogół jest on częścią reprezentacji sceny).

2. Kolejno dla każdej krawędzi wyznaczamy jej punkty przecięcia w rzucie z krawędziami konturowymi i badamy każdy taki punkt, czy jest on bliżej, czy dalej od obserwatora niż odpowiedni punkt krawędzi konturowej. Jeśli krawędź konturowa zasłania ten punkt, to dzielimy krawędź, na której on leży na fragmenty i wprowadzamy dodatkowy wierzchołek grafu krawędziowego (dzieląc odpowiednią jego krawędź). Każdemu takiemu wierzchołkowi przypisujemy liczbę +1 albo -1, która odpowiada zmianie stopnia zasłonięcia krawędzi (znak tej zmiany zależy od położenia ściany, której krawędź konturową przetwarzaliśmy i od orientacji krawędzi, na której wprowadziliśmy dodatkowy punkt).

3. Wyznaczamy stopień zasłonięcia dowolnego wierzchołka grafu, a następnie, zaczynając od tego wierzchołka, przeszukujemy graf krawędziowy. W każdym wierzchołku, w którym widoczność zmienia się, dodajemy lub odejmujemy (to zależy od orientacji krawędzi i od kierunku ,,poruszania się” po niej) zmianę stopnia widoczności do lub od wartości stopnia widoczności fragmentu krawędzi przetwarzanego wcześniej. W ten sposób otrzymujemy stopień widoczności wszystkich krawędzi grafu (przeszukujemy w ten sposób wszystkie jego składowe spójne). Wyprowadzamy lub zaznaczamy jako widoczne krawędzie, których stopień zasłonięcia jest równy 0.

Stosując ten algorytm, trzeba uważać, bo sceny złożone z wielokątnych ścian bywają dość skomplikowane i pełna implementacja algorytmu musi być w stanie radzić sobie z wszystkimi przypadkami szczególnymi.

Kłopoty zdarzają się we wspólnych wierzchołkach wielu krawędzi, które mają rożne stopnie zasłonięcia. Przeszukując graf, doszedłszy do takiego wierzchołka, najbezpieczniej (w sensie odporności na błędy) jest bezpośrednio obliczyć stopień zasłonięcia krawędzi wychodzących z takiego wierzchołka.

W algorytmie Appela jest możliwa pewna kontrola poprawności; dochodząc do dowolnego odwiedzonego wcześciej wierzchołka grafu możemy porównać jego stopień zasłonięcia obliczony wcześniej ze stopniem zasłonięcia obliczonym ,,po drodze” do tego wierzchołka. Muszą one być równe.

W algorytmie Hornunga, którego dokładnie nie omówię z powodów, które (mam nadzieję) staną się za chwilę jasne, testy widoczności są ograniczone do par krawędzi konturowych. Jeśli liczba krawędzi konturowych jest dużo mniejsza niż wszystkich, to złożoność tego algorytmu jest jeszcze mniejsza niż złożoność algorytmu Appela. Jest to jednak algorytm skomplikowany. Implementacja algorytmu powierzchni zasłoniętej, opartego na tym algorytmie, miała ponad 5000 linii kodu źródłowego, a napisanie jej zajęło mi w swoim czasie ponad półtora roku. Nie obliczyłem, ile obrazków mógłbym otrzymać przez ten czas, gdybym zajął się innym, wolniejszym algorytmem, ale niewątpliwie dużo. Ponadto algorytm ten jest bardzo wrażliwy na błędy zaokrągleń, które mogą doprowadzić do załamania obliczeń lub całkowicie błędnych wyników.

Zasada działania algorytmu malarza jest następująca:

1. Posortuj ściany w kolejności od najdalszej do najbliższej obserwatora,

2. Namaluj je w tej kolejności.

Prosta idea niech nie przesłania faktu, że mogą istnieć konflikty widoczności, w których ściana położona w zasadzie dalej zasłania część ściany bliższej obserwatora. Dlatego po posortowaniu (np. ze względu na odległość od obserwatora najbliższego punktu każdej ściany) konieczne jest sprawdzenie i ewentualna modyfikacja uporządkowania ścian.

Ponadto mogą wystąpić konflikty nierozstrzygalne, tj. może nie istnieć uporządkowanie ścian gwarantujące otrzymanie poprawnego obrazu. Klasyczny przykład takiego konfliktu jest na rys. 9.5. Jedyne wyjście w tej sytuacji polega na podzieleniu co najmniej jednej ściany na kawałki i wyświetlenie tych kawałków we właściwej kolejności. Dodatkowa wada algorytmu malarza i jego wariantów (o których będzie mowa dalej) to wielokrotne przemalowywanie pikseli. Jeśli wyznaczenie koloru z uwzględnieniem oświetlenia i tekstury jest czasochłonne, a piksel ostatecznie otrzyma kolor innej ściany, to cała praca wykonana w celu obliczenia koloru piksela, który na ostatecznym obrazie będzie inny, pójdzie na marne.

Algorytm widoczności z użyciem drzewa BSP jest dość trudny do jednoznacznego zaklasyfikowania; nie otrzymujemy w nim reprezentacji widocznych części ścian, a tylko obraz, utworzony podobnie jak w algorytmie malarza. Natomiast zasadniczy koszt obliczeń związanych z rozstrzyganiem zasłaniania wiąże się z budową drzewa, które nie zależy od rozdzielczości obrazu, ani nawet od położenia obserwatora i rzutni.

Zasadę działania algorytmu przedstawia płaski przypadek na rysunku 9.6, który pokazuje również drzewo BSP zbudowane dla danych czterech ścian. Spostrzeżenie, które leży u podstaw algorytmu jest następujące: jeśli obserwator znajduje się po pewnej stronie dowolnej płaskiej ściany, to ściana ta nie zasłania żadnych obiektów, które znajdują się po tej samej stronie. Zatem aby otrzymać obraz widocznych części ścian, obchodzimy drzewo algorytmem DFS. Dla każdego wierzchołka drzewa sprawdzamy, po której stronie jest obserwator. Jeśli jest on po stronie ,,in”, to rekurencyjnie wywołujemy procedurę obchodzenia poddrzewa ,,out”. Następnie rzutujemy i wyświetlamy (zamalowujemy odpowiednie piksele) ścianę w bieżącym wierzchołku i obchodzimy poddrzewo ,,in”. Jeśli obserwator znajduje się po stronie ,, out”, to poddrzewa danego wierzchołka przetwarzamy w odwrotnej kolejności. Jeśli położenie obserwatora zawiera się w płaszczyźnie ściany, to kolejność przeszukiwania poddrzew jest dowolna.

Dla położeń A, B, C obserwatora pokazanych na rysunku algorytm namaluje kolejno

Budowa drzewa BSP przejmuje rolę sortowania, rozstrzygania konfliktów widoczności i dzielenia ścian z algorytmu malarza. Przyjemną cechą tego algorytmu jest fakt, że drzewo wystarczy zbudować tylko raz (chyba, że scena ulega zmianie) i można wykonać wiele obrazów sceny, widzianej z różnych punktów.

Odpowiedni podział przestrzeni, poprzez konstrukcję drzew BSP, może być użyty do wyznaczenia fragmentów ścian oświetlonych przez ustalone punktowe źródło światła. Drzewa BSP w tym algorytmie spełniają dwie różne funkcje:

• Służą do rozstrzygania widoczności w scenie (w taki sposób jak w algorytmie opisanym wcześniej),

• Służą do reprezentowania tzw. bryły cienia, która jest zbiorem punktów zasłoniętych przez co najmniej jedną ścianę. Bryłę tę reprezentuje się w pewnym uproszczeniu, które jest możliwe dzięki odpowiedniemu uporządkowaniu ścian.

Przyjmiemy założenie, że wszystkie ściany są wypukłe, co upraszcza implementację (w razie czego można np. dokonać triangulacji ścian). Pierwszy etap algorytmu, niezależny od punktów, w których znajduje się obserwator i źródła światła, polega na zbudowaniu zwykłego drzewa BSP.

Etap drugi polega na budowaniu reprezentacji bryły cienia, z jednoczesnym wyznaczaniem oświetlonych części ścian. W etapie tym przeszukujemy drzewo BSP sceny w kolejności odwrotnej niż podczas rysowania, przyjmując położenie obserwatora w punkcie położenia źródła światła. W ten sposób otrzymujemy najpierw ścianę lub fragment ściany, który jest cały oświetlony, a następnie ściany, które mogą być zasłonięte od światła tylko przez fragmenty wyprowadzone wcześniej. Każdy taki fragment ściany jest wielokątem wypukłym, bo jest on częścią wspólną wypukłej ściany i wypukłej komórki binarnego podziału przestrzeni.

Drzewo BSP bryły cienia jest początkowo puste. Procedura, która je tworzy, przetwarza kolejne wypukłe wielokąty. Każdy taki wielokąt jest podstawą nieograniczonego ściętego ostrosłupa, o wierzchołku w punkcie położenia źródła światła. Płaszczyzny, w których leżą brzegi komórek podziału, są wyznaczone przez punkt położenia źródła światła i odcinki — krawędzie bieżącego fragmentu ściany (a więc jeśli jest on np. trójkątem, to wstawimy trzy ściany, po jednej dla każdego boku).

Przed rozbudowaniem drzewa BSP bryły cienia możemy podzielić bieżący fragment ściany na część oświetloną i zacienioną, w ten sposób, że dzielimy go płaszczyznami podziału odpowiednich komórek (tak, jakbyśmy wstawiali fragment do drzewa). Dla każdej komórki dysponujemy informacją, czy jej punkty są oświetlone, czy nie.

Algorytm z buforem głębokości (tzw. z-buforem), powszechnie implementowany w sprzęcie, to tzw. algorytm brutalnej siły, która w tym przypadku polega na użyciu dużej ilości pamięci. W algorytmie tym mamy prostokątną tablicę liczb, o wymiarach równych wymiarom szerokości i wysokości obrazu w pikselach. Liczby te są rzeczywiste, ale najczęściej, dla przyspieszenia obliczeń są one reprezentowanne w postaci stałopozycyjnej, zwykle 16-, 24- lub 32-bitowej.

Algorytm:

1. Przypisz wszystkim elementom z-bufora wartość, która reprezentuje nieskończoność, albo największą dopuszczalną odległość od obserwatora.

2. Kolejno dla każdej ściany, narysuj jej rzut (tj. dokonaj jego rasteryzacji za pomocą algorytmu przeglądania liniami poziomymi). Dla każdego piksela, który należy do rzutu ściany, należy przy tym obliczyć współrzędną z (tj. głębokość) punktu w układzie obserwatora. Kolor danej ściany przypisujemy pikselowi tylko wtedy, gdy obliczona współrzędna z jest mniejsza niż aktualna zawartość bufora głębokości. Jednocześnie z przypisaniem koloru należy uaktualnić zawartość bufora.

Zaletami algorytmu są prostota, w tym łatwość implementowania algorytmu w sprzęcie, i duża niezawodność (odporność na błędy np. zaokrągleń — skutki takich błędów to pojedyncze piksele o złym kolorze, podczas gdy w algorytmach wyrafinowanych taki błąd może spowodować całkowite załamanie obliczeń). Niezawodność tego algorytmu jest być może ważniejsza od szybkości jego działania, jeśli rozpatrujemy przyczyny szerokiego rozpowszechnienia sprzętowych implementacji tego algorytmu.

Do wad tego algorytmu należy zaliczyć duże zapotrzebowanie na pamięć (np. 600kB dla obrazka o wymiarach 640×480 pikseli, przy 16 bitach bufora głębokości na każdy piksel). Wada ta skutecznie powstrzymywała stosowanie tego algorytmu na pecetach w czasach, gdy w powszechnym użyciu był system DOS, ale teraz jest mało istotna. Inne wady to: trudności w walce ze zjawiskiem intermodulacji (tzw. aliasu), niezbyt łatwa implementacja w celu wyświetlania powierzchni krzywoliniowych i niemożność tworzenia obrazów brył CSG na podstawie drzewa CSG (tj. bez jawnego wyznaczenia reprezentacji takiej bryły). Ponadto pewne typy sprzętu (akceleratorów graficznych) ukrywają zawartość z-bufora (nie można jej odczytać po wykonaniu obrazu, a informacja ta bywa nadzwyczaj cenna, np. do wyznaczenia cieni), a prawie żaden sprzęt nie jest w stanie wyświetlać powierzchni krzywoliniowych (zamiast tego wyświetla się zwykle duże ilości trójkątów).

Algorytm widoczności dla powierzchni Béziera. Aby narysować obraz powierzchni Béziera można (podobnie jak inne powierzchnie zakrzywione) przybliżyć ją dostatecznie dużą liczbą trójkątów i wyświetlić je; metoda opisana niżej prowadzi do otrzymania obrazu, którego dokładność zależy tylko od jego rozdzielczości (a nie od parametrów takich jak liczba trójkątów).

Mając siatkę kontrolną płata Béziera

1. Dokonaj rzutowania punktów kontrolnych,

2. Jeśli największa odległość obrazów tych punktów jest nie większa niż średnica piksela, to oblicz dowolny punkt płata i wektor normalny w tym punkcie, a następnie zbadaj widoczność w z-buforze, oblicz kolor i przypisz go pikselowi,

3. W przeciwnym razie podziel płat na mniejsze fragmenty (za pomocą algorytmu de Casteljau) i wywołaj procedurę rekurencyjnie.

Głębokość podziału płata w tym algorytmie adaptacyjnie dopasowuje się do rozdzielczości obrazu. Okazuje się, że podczas działania tego algorytmu łatwo może się zdarzyć, że w wyniku błędu zaokrągleń na obrazie pozostają dziurki (to jest spowodowane zaokrąglaniem współrzędnych obrazu punktu do całkowitych współrzędnych piksela). Ponadto zdarzają się błędy rozstrzygnięcia widoczności, spowodowane arbitralnym wyborem punktu płata, którego głębokość jest badana w teście widoczności. Uodpornienie algorytmu na takie błędy jest nietrywialne, ale możliwe.

Główną motywacją tego algorytmu była chęć obniżenia kosztu pamięciowego algorytmu z buforem głębokości (ta motywacja ma już znaczenie tylko historyczne). Algorytm przeglądania liniami poziomymi ma wiele wariantów, które umożliwiają m.in. tworzenie obrazów cieni oraz obrazów brył CSG bez wyznaczania jawnej ich reprezentacji. Poniżej jest opisana wersja podstawowa. Jest w niej przyjęte założenie, że ściany są płaskie i nie przenikają się.

1. Zrzutuj wierzchołki ścian na obraz; dla każdej krawędzi znajdź wierzchołek, którego obraz ma mniejszą współrzędną y, a ponadto, zbadaj, czy obraz wnętrza ściany leży po lewej, czy po prawej stronie (krawędzie, których obraz jest poziomy, pomijamy).

2. Posortuj tablicę krawędzi w kolejności rosnących mniejszych współrzędnych y.

3. Utwórz początkowo pustą tablicę krawędzi aktywnych.

4. Dla kolejnych wartości y odpowiedających poziomym liniom rastra obrazu, wykonaj następujące czynności:

   1. Wyrzuć z tablicy krawędzi aktywnych te, których rzut jest rozłączny z bieżącą poziomą linią rastra.

   2. Dołącz do tablicy krawędzi aktywnych te, których obraz przecina się z bieżącą linią poziomą.

   3. Oblicz współrzędną x (ekranową) i z (głębokość) punktu przecięcia każdej krawędzi aktywnej z bieżącą poziomą linią rastra i posortuj tablicę krawędzi aktywnych w kolejności rosnących x.

   4. Utwórz (początkowo pustą) listę aktywnych ścian; wstaw do niej ściany, których lewa krawędź ma najmniejszą współrzędną x, porządkując je w kolejności rosnących głębokości.

   5. Dla pierwszej w liście ściany wyznacz jej prawą krawędź aktywną i współrzędną x tej krawędzi (a), lub ścianę nieaktywną o najmniejszej współrzędnej x lewej krawędzi (b) (zależnie od tego, co jest mniejsze).

   6. Narysuj poziomy odcinek w kolorze pierwszej w liście aktywnej ściany; w przypadku (a) usuń ścianę z listy.

   7. Usuń z listy wszystkie ściany, których prawa krawędź ma współrzędną x mniejszą lub równą wsp. x końca narysowanego odcinka.

   8. Jeśli lista jest niepusta, to dołącz do listy ścian aktywnych ściany, których współrzędna x lewej krawędzi jest mniejsza lub równa współrzędnej x ostatnio narysowanego odcinka. W przeciwnym razie wstaw do listy nieprzetworzone jeszcze ściany, których lewe krawędzie mają najmniejszą współrzędną x.

   9. Uporządkuj listę i idź do kroku 4.5, chyba, że lista jest pusta.

Wariant algorytmu dla konstrukcyjnej geometrii brył korzysta z uproszczenia zadania przez obniżenie wymiaru; przecięcia płaszczyzny wyznaczonej przez położenie obserwatora i bieżąco przeglądaną linię rastra z wielościennymi prymitywami to wielokąty. Zamiast wykonywać działania CSG na wielościanach, można zatem wyznaczyć przecięcia, sumy, różnice lub dopełnienia wielokątów, a następnie poddać je regularyzacji. Jest to oczywiście zadanie prostsze (ale takie zadanie trzeba rozwiązać dla każdej poziomej linii rastra).

Podobne uproszczenie dotyczy wyznaczania cieni; po wyznaczeniu widocznych odcinków można znaleźć ich części oświetlone. Również to zadanie jest prostsze od wyznaczania oświetlonych części wielokątów, na których leżą te odcinki.

Algorytm z buforem głębokości umożliwia narysowanie obrazu z cieniami. Jest to wprawdzie dość kłopotliwe, ale można to zrobić za pomocą sprzętu (np. działającego w standardzie OpenGL, konieczne są pewne rozszerzenia) i wtedy możliwa jest animacja w czasie rzeczywistym, tj. wyświetlanie kilkudziesięciu obrazów na sekundę, przedstawiających poruszające się obiekty. Są jednak pewne ograniczenia: źródło światła musi być reflektorem, emitującym wiązkę promieni świetlnych w pewnym stożku (nie może to być np. nieosłonięta świeca w pokoju), ponadto implementacja tego algorytmu może ,,zawłaszczyć” mechanizm teksturowania (ta trudność jest do ominięcia, jeśli istnieje możliwość bezpośredniego programowania karty graficznej np. w języku GLSL).

Algorytm działa tak: w pierwszym kroku rysujemy scenę, umieszczając obserwatora w punkcie położenia źródła światła; rzutnia jest prostopadłą do osi stożka światła. Po tym etapie nie jest potrzebny obraz, tylko zawartość buforu głębokości.

W etapie drugim zawartość buforu głębokości otrzymaną w pierwszym etapie wykorzytujemy do określenia tekstury trójwymiarowej; dla dowolnego punktu w przestrzeni możemy określić, czy jest on oświetlony, porównując jego współrzędną z w układzie źródła światła (tj. w układzie kamery wykorzstywanym podczas pierwszego etapu) z zawartością buforu głębokości. Wartość tej tekstury, jedna z dwóch, umożliwia wybranie właściwego koloru piksela.

W implementacji konieczne jest przeciwdziałanie skutkom błędów zaokrągleń, które mogą spowodować zacienienie obiektu przez samego siebie. Dodatkową wadą jest ograniczona rozdzielczość obrazu wykonanego w pierwszym etapie. Brzeg cienia jest w efekcie ,,schodkowany” — na końcowym obrazie są widoczne piksele obrazu z położenia źródła światła. Przykłądowa implementacja jest w dodatku B.