Wykres sceny

Architektura OpenSceneGraph , otwartego interfejsu API grafiki 3D obsługującego bogatą w funkcje i szeroko stosowaną implementację wykresów scen.

Wykres sceny to ogólna struktura danych powszechnie używana w aplikacjach do edycji grafiki wektorowej i nowoczesnych grach komputerowych, która organizuje logiczną i często przestrzenną reprezentację sceny graficznej. Jest to zbiór węzłów w grafu lub drzewa . Węzeł drzewa może mieć wiele dzieci, ale tylko jednego rodzica, z efektem rodzica zastosowanym do wszystkich jego węzłów potomnych; operacja wykonana na grupie automatycznie przenosi jej efekt na wszystkich jej członków. W wielu programach asocjacja macierzy transformacji geometrycznej (patrz także transformacja i macierz ) na każdym poziomie grupy i łączenie takich macierzy razem jest wydajnym i naturalnym sposobem przetwarzania takich operacji. Wspólną cechą jest na przykład możliwość grupowania powiązanych kształtów i obiektów w obiekt złożony, którym można następnie manipulować równie łatwo, jak pojedynczym obiektem.

Wykresy scen w narzędziach do edycji grafiki

W edycji grafiki wektorowej każdy węzeł liścia na wykresie sceny reprezentuje pewną jednostkę atomową dokumentu, zwykle kształt, taki jak elipsa lub ścieżka Beziera . Chociaż same kształty (zwłaszcza ścieżki) można dalej rozłożyć na węzły, takie jak węzły splajnu , praktyczne jest myślenie o grafie sceny jako złożonym z kształtów, zamiast przechodzić na niższy poziom reprezentacji.

Inną przydatną i zorientowaną na użytkownika koncepcją węzła jest warstwa . Warstwa działa jak przezroczysty arkusz, na którym można umieścić dowolną liczbę kształtów i grup kształtów. Dokument staje się wtedy zbiorem warstw, z których każdą można wygodnie uczynić niewidoczną, przyciemnioną lub zablokowaną (przeznaczoną tylko do odczytu). Niektóre aplikacje umieszczają wszystkie warstwy na liście liniowej, podczas gdy inne obsługują warstwy w warstwach na dowolną głębokość.

Wewnętrznie może nie być żadnych rzeczywistych różnic strukturalnych między warstwami i grupami, ponieważ oba są tylko węzłami wykresu sceny. Jeśli potrzebne są różnice, typową deklaracją typu w C++ byłoby utworzenie ogólnej klasy węzła, a następnie wyprowadzenie warstw i grup jako podklas. Na przykład członek widoczności byłby elementem warstwy, ale niekoniecznie grupy.

Wykresy scen w grach i aplikacjach 3D

Wykresy scen są przydatne w nowoczesnych grach wykorzystujących grafikę 3D i coraz większe światy lub poziomy. W takich aplikacjach węzły na grafie sceny (ogólnie) reprezentują jednostki lub obiekty w scenie.

Na przykład gra może definiować logiczną relację między rycerzem a koniem, tak że rycerz jest uważany za przedłużenie konia. Wykres sceny miałby węzeł „koń” z dołączonym węzłem „rycerz”.

Wykres sceny może również opisywać przestrzenny, jak również logiczny związek różnych jednostek: rycerz porusza się w przestrzeni 3D, tak jak porusza się koń.

W tych dużych aplikacjach wymagania dotyczące pamięci są głównymi czynnikami branymi pod uwagę podczas projektowania wykresu sceny. Z tego powodu wiele dużych systemów wykresów scen wykorzystuje instancje geometrii w celu zmniejszenia kosztów pamięci i zwiększenia szybkości. W powyższym przykładzie każdy rycerz jest oddzielnym węzłem sceny, ale jego graficzna reprezentacja (składająca się z siatki 3D, tekstur, materiałów i shaderów) jest instancjonowana. Oznacza to, że przechowywana jest tylko jedna kopia danych, do której następnie odwołują się dowolne węzły „rycerza” na wykresie sceny. Pozwala to na zmniejszenie budżetu pamięci i zwiększenie szybkości, ponieważ po utworzeniu nowego węzła rycerza dane dotyczące wyglądu nie muszą być powielane.

Implementacja wykresu sceny

Najprostsza forma wykresu sceny wykorzystuje strukturę danych tablicy lub listy połączonej , a wyświetlanie jej kształtów polega po prostu na liniowym iterowaniu węzłów jeden po drugim. Inne typowe operacje, takie jak sprawdzanie, który kształt przecina wskaźnik myszy, są również wykonywane za pomocą wyszukiwania liniowego. W przypadku wykresów małych scen to zwykle wystarcza.

Operacje i wysyłka grafu scen

Zastosowanie operacji na grafie sceny wymaga pewnego sposobu wysłania operacji w oparciu o typ węzła. Na przykład w operacji renderowania węzeł grupy transformacji akumulowałby swoją transformację przez mnożenie macierzy, przemieszczenie wektorów, kwaterniony lub kąty Eulera . Po czym węzeł liścia wysyła obiekt do renderowania do renderera. Niektóre implementacje mogą renderować obiekt bezpośrednio, co wywołuje podstawowy interfejs API renderowania , taki jak DirectX lub OpenGL . Ale ponieważ podstawowa implementacja interfejsu API renderowania zwykle brakuje przenośności, zamiast tego można oddzielić wykres sceny i systemy renderowania. Aby zrealizować ten typ wysyłki, można zastosować kilka różnych podejść.

W językach zorientowanych obiektowo, takich jak C++ , można to łatwo osiągnąć za pomocą funkcji wirtualnych , z których każda reprezentuje operację, którą można wykonać na węźle. Funkcje wirtualne są proste do napisania, ale zwykle nie da się dodać nowych operacji do węzłów bez dostępu do kodu źródłowego. Alternatywnie można zastosować wzorzec odwiedzającego . Ma to podobną wadę, ponieważ podobnie trudno jest dodawać nowe typy węzłów.

Inne techniki obejmują wykorzystanie RTTI ( informacje o typie czasu wykonywania ). Operacja może być zrealizowana jako klasa, która jest przekazywana do bieżącego węzła; następnie sprawdza typ węzła za pomocą RTTI i wyszukuje poprawną operację w tablicy wywołań zwrotnych lub funktorów . Wymaga to zainicjowania mapy typów wywołań zwrotnych lub funktorów w czasie wykonywania, ale zapewnia większą elastyczność, szybkość i rozszerzalność.

Istnieją odmiany tych technik, a nowe metody mogą przynieść dodatkowe korzyści. Jedną z alternatyw jest przebudowa wykresu sceny, w której wykres sceny jest odbudowywany dla każdej wykonanej operacji. To jednak może być bardzo powolne, ale tworzy wysoce zoptymalizowany wykres sceny. Pokazuje, że dobra implementacja wykresu sceny zależy w dużym stopniu od aplikacji, w której jest używana.

Trawersy

Trawersy są kluczem do potęgi stosowania operacji na wykresach scen. Przechodzenie zazwyczaj polega na rozpoczęciu w dowolnym węźle (często w korzeniu wykresu sceny), zastosowaniu operacji (operacje aktualizacji i renderowania są często wykonywane jedna po drugiej) i rekurencyjnego poruszania się w dół wykresu sceny (drzewo ) do węzłów podrzędnych, aż do osiągnięcia węzła liścia. W tym momencie wiele silników wykresów scen przechodzi z powrotem w górę drzewa, stosując podobną operację. Rozważmy na przykład operację renderowania, która uwzględnia transformacje: podczas rekurencyjnego przechodzenia w dół hierarchii grafu sceny wywoływana jest operacja wstępnego renderowania. Jeśli węzeł jest węzłem transformacji, dodaje własną transformację do bieżącej macierzy transformacji. Gdy operacja zakończy przechodzenie przez wszystkie elementy podrzędne węzła, wywołuje operację po renderowaniu węzła, aby węzeł transformacji mógł cofnąć transformację. Takie podejście drastycznie zmniejsza niezbędną ilość mnożenia macierzy. [ potrzebne źródło ]

Niektóre operacje na wykresie sceny są w rzeczywistości bardziej wydajne, gdy węzły są przemierzane w innej kolejności — w tym przypadku niektóre systemy implementują przebudowę wykresu sceny, aby zmienić kolejność wykresu sceny w łatwiejszy do przeanalizowania format lub drzewo.

Na przykład w przypadkach 2D wykresy scen zwykle renderują się, zaczynając od węzła głównego drzewa, a następnie rekurencyjnie rysują węzły potomne. Liście drzewa reprezentują najwięcej obiektów pierwszego planu. Ponieważ rysowanie odbywa się od tyłu do przodu, a bliższe obiekty po prostu nadpisują dalsze, proces ten jest znany jako algorytm malarza . W systemach 3D, które często wykorzystują bufory głębi , bardziej wydajne jest rysowanie najpierw najbliższych obiektów, ponieważ dalsze obiekty często wymagają jedynie przetestowania głębokości zamiast faktycznego renderowania, ponieważ są zasłaniane przez bliższe obiekty.

Wykresy scen i hierarchie objętości granicznej (BVH)

Bounding Volume Hierarchies (BVH) są przydatne w wielu zadaniach – w tym w wydajnym usuwaniu i przyspieszaniu wykrywania kolizji między obiektami. BVH jest strukturą przestrzenną, ale nie musi dzielić geometrii (patrz partycjonowanie przestrzenne poniżej).

BVH to drzewo objętości ograniczających (często sfer, prostokątów granicznych ustawionych w osiach lub zorientowanych prostokątów granicznych). Na dole hierarchii rozmiar objętości jest wystarczająco duży, aby ciasno objąć pojedynczy obiekt (lub nawet jakiś mniejszy ułamek obiektu w BVH o wysokiej rozdzielczości). Gdy ktoś wspina się po hierarchii, każdy węzeł ma swój własny wolumin, który ściśle obejmuje wszystkie woluminy pod nim. U podstawy drzewa znajduje się wolumin obejmujący wszystkie woluminy w drzewie (cała scena).

BVH są przydatne do przyspieszenia wykrywania kolizji między obiektami. Jeśli objętość ograniczająca obiektu nie przecina objętości wyżej w drzewie, nie może przecinać żadnego obiektu poniżej tego węzła (więc wszystkie są odrzucane bardzo szybko).

Istnieją pewne podobieństwa między BVH a wykresami scen. Wykres sceny można łatwo dostosować tak, aby zawierał/stał się BVH – jeśli każdy węzeł ma powiązany wolumin lub istnieje specjalnie zbudowany „węzeł powiązany” dodany w dogodnej lokalizacji w hierarchii. Może to nie być typowy widok wykresu sceny, ale włączenie BVH do wykresu sceny ma zalety.

Wykresy scen i partycjonowanie przestrzenne

Skutecznym sposobem łączenia partycjonowania przestrzennego i wykresów scen jest utworzenie węzła liścia sceny, który zawiera dane partycjonowania przestrzennego. [ potrzebne wyjaśnienie ] Może to zwiększyć wydajność obliczeniową renderowania.

Dane przestrzenne są zwykle statyczne i zazwyczaj zawierają nieruchome dane sceny w jakiejś podzielonej formie. [ wymagane wyjaśnienie ] Niektóre systemy mogą mieć oddzielne systemy i ich renderowanie. To jest w porządku i żadna z tych metod nie ma prawdziwych zalet. W szczególności źle jest mieć wykres sceny zawarty w systemie partycjonowania przestrzennego, ponieważ lepiej jest myśleć o grafie sceny jako o wspanialszym systemie partycjonowania przestrzennego. [ neutralność jest kwestionowana ]

Bardzo duże rysunki lub wykresy scen, które są generowane wyłącznie w czasie wykonywania (jak to ma miejsce w programach renderujących ray tracing ), wymagają zdefiniowania węzłów grupy w bardziej zautomatyzowany sposób. Na przykład raytracer wykona opis sceny w 3D modelować i budować wewnętrzną reprezentację, która dzieli poszczególne części na obwiednie (zwane również płytami ograniczającymi). Te pola są pogrupowane hierarchicznie, dzięki czemu testy przecięcia promieni (w ramach określania widoczności) mogą być efektywnie obliczane. Na przykład ramka grupy, która nie przecina promienia oka, może całkowicie pominąć testowanie któregokolwiek z jej członków.

Podobna wydajność utrzymuje się również w aplikacjach 2D. Jeśli użytkownik powiększył dokument tak, że tylko jego część jest widoczna na ekranie jego komputera, a następnie przewija go, przydatne jest użycie ramki ograniczającej (lub w tym przypadku schematu prostokąta ograniczającego), aby szybko określić, która scena elementy wykresu są widoczne i dlatego rzeczywiście należy je narysować.

W zależności od szczegółów wydajności rysowania aplikacji, na dużą część projektu wykresu sceny mogą mieć wpływ względy wydajności renderowania. W grach wideo 3D, takich jak Quake , drzewa binarnego partycjonowania przestrzeni (BSP) są bardzo preferowane, aby zminimalizować testy widoczności. Obliczenia drzew BSP na podstawie wykresów scen projektowych zajmują jednak bardzo dużo czasu i muszą zostać ponownie obliczone, jeśli wykres sceny projektowej ulegnie zmianie, więc poziomy mają tendencję do pozostawania statycznymi, a znaki dynamiczne nie są generalnie uwzględniane w schemacie partycjonowania przestrzennego.

Wykresy scen dla gęstych regularnych obiektów, takich jak pola wysokości i siatki wielokątów, zwykle wykorzystują drzewa czworokątne i ośmiornice , które są wyspecjalizowanymi wariantami hierarchii ramek ograniczających 3D. Ponieważ pole wysokości samo zajmuje objętość pudełka, rekurencyjne dzielenie tego pudełka na osiem podpola (stąd „oct” w octree), aż do osiągnięcia poszczególnych elementów pola wysokości, jest wydajne i naturalne. Drzewo czwórkowe to po prostu ośmiornica 2D.

Normy

FIG

PHIGS był pierwszą komercyjną specyfikacją grafów sceny i stał się standardem ANSI w 1988 roku. Dostawcy sprzętu Unix dostarczyli różne implementacje . Wydaje się, że system grafiki 3D HOOPS był pierwszą komercyjną biblioteką wykresów scen dostarczoną przez jednego dostawcę oprogramowania. Został zaprojektowany do działania na różnych interfejsach 2D i 3D niższego poziomu, a pierwsza główna wersja produkcyjna (v3.0) została ukończona w 1991 roku.

SGI

Silicon Graphics (SGI) wypuścił OpenGL Performer lub częściej nazywany Performer w 1991 roku, który był głównym systemem scenografów dla większości produktów SGI w przyszłości. IRIS Inventor 1.0 (1992) został wydany przez SGI, który był wykresem sceny wysokiego poziomu zbudowanym na szczycie Performera. Następnie w 1994 roku pojawił się Open Inventor , kolejna iteracja wykresu sceny wysokiego poziomu zbudowana na nowszych wersjach Performera. Więcej bibliotek wykresów scen 3D można znaleźć w kategorii:Interfejsy API scenografów 3D .

X3D

X3D to wolny od tantiem format plików o otwartych standardach i architektura czasu wykonywania do przedstawiania i komunikowania scen i obiektów 3D za pomocą XML . Jest to ISO , który zapewnia system do przechowywania, wyszukiwania i odtwarzania treści graficznych w czasie rzeczywistym osadzonych w aplikacjach, a wszystko to w ramach otwartej architektury obsługującej szeroki wachlarz domen i scenariuszy użytkowników.

Zobacz też

Książki

  • Leler, Wm and Merry, Jim (1996) 3D z HOOPS , Addison-Wesley
  •   Wernecke, Josie (1994) The Inventor Mentor: Programowanie zorientowanej obiektowo grafiki 3D za pomocą Open Inventor , Addison-Wesley, ISBN 0-201-62495-8 (wydanie 2)

Artykuły

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Scene_graph&oldid=1126444216 ”