Podręcznik

Uniwersalną formą zapisu  obiektów 3D, zarówno powierzchni  jak i brył,  są siatki wielościanowe (polygon meshes). Najczęściej są to siatki trójkątów, mające tę zaletę, że są to zawsze ściany płaskie. Spotyka się też siatki wypukłych  czworokątów  lub innych, zwykle  wypukłych,  wieloboków.  Siatki wielościanowe są zazwyczaj wynikiem aproksymacji następujących struktur:

• powierzchni w reprezentacji NURBS
• powierzchni typu subdivision (o których opowiemy dalej)
• chmur punktów, najczęściej pozyskiwanych metodą skanowania obiektów
• innych struktur, których tu nie omawiamy, np. brył CSG

 

Taka uniwersalna forma zapisu pozwala w jednolity sposób traktować wszystkie obiekty poddawane renderingowi, co ułatwia stosowanie zaawansowanych metod  realistycznej wizualizacji.

 

W wielu przypadkach strukturę ścian zapamiętuje się bardzo prosto - jako listę wszystkich wierzchołków i listę ścian, z których każda określona jest przez adresy wierzchołków (Rysunek 84).

 

Rysunek 85.

 

Bardziej złożone struktury polegają na tworzeniu dodatkowo listy krawędzi, dzięki czemu krawędzie przy wyświetlaniu nie są rysowane dwukrotnie (dla każdej przyległej ściany osobno); znak lambda (λ)  na Rys.  85 oznacza wskaźnik NULL/nil.

 

Rysunek 86.

 

Jeszcze bardziej złożona struktura, o nazwie half-edge, jest budowana na wskaźnikach. Spójrzmy na Rysunek 86:

 

Rysunek 87. Struktura half-edge w reprezentacji brył.

W tym przypadku każda krawędź jest reprezentowana przez dwie bliźniacze półkrawędzie, zwrócone w kierunkach przeciwnych. Każda półkrawędź (half-edge), zaznaczona tu na czerwono, zawiera wskaźnik na:

• półkrawędź przeciwną do danej
• wierzchołek końcowy półkrawędzi danej
• ścianę przyległą do danej półkrawędzi
• następną półkrawędź tej ściany, liczoną w kierunku przeciwnym do ruchu wskazówek zegara
• poprzednią półkrawędź tej ściany.

Jest to typowa, aczkolwiek nie minimalna reprezentacja struktury half-edge. Minimalna postać half-edge zawiera tylko wskaźnik na półkrawędź przeciwną i następną, wygodniejsza w użyciu jest jednak struktura taka jak pokazaliśmy, bardziej rozbudowana. Dzięki złożonej strukturze half-edge różnorodne. operacje (np  związane z algorytmem podpodziału, którym zajmiemy się w następnym rozdziale) stają się znacznie bardziej efektywne. Przykładowo, żeby obejść wszystkie krawędzie zbiegające się w jakimś wierzchołku, będącym końcem danej półkrawędzi (Rysunek 87),

 

Rysunek 88

 

należy wykonać następujące kroki:

• z danej półkrawędzi przejść na półkrawędź następną
• z tej następnej przejść na przeciwną do niej
• z tej przeciwnej (która "wpada" do wierzchołka) na półkrawędź następną
• z tej następnej znów na przeciwną
• itd., aż wrócimy na półkrawędź pierwotną.

Przejście z jakiejś półkrawędzi na przeciwną lub następną to tylko użycie jednego wskaźnika - błyskawiczna zmiana adresu. Cały obieg krawędzi w wierzchołku zapisuje się więc bardzo zwięźle i wykonuje niezwykle szybko. A spróbujmy to samo wykonać posługując się reprezentacją prostszą, jedną z tych, co na początku rozdziału. To będzie nieporównanie bardziej złożone!