Szenendiagramm – Wikipedia
![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Architecture_of_OpenSceneGraph.jpg/300px-Architecture_of_OpenSceneGraph.jpg)
EIN Szenendiagramm ist eine allgemeine Datenstruktur, die üblicherweise von vektorbasierten Grafikbearbeitungsanwendungen und modernen Computerspielen verwendet wird und die die logische und häufig räumliche Darstellung einer grafischen Szene anordnet. Es ist eine Sammlung von Knoten in einem Diagramm oder einer Baumstruktur. Ein Baumknoten kann viele untergeordnete Knoten haben, aber nur einen einzigen übergeordneten Knoten. Der Effekt eines übergeordneten Knotens wird auf alle untergeordneten Knoten angewendet. Eine Operation, die für eine Gruppe ausgeführt wird, überträgt ihre Wirkung automatisch auf alle ihre Mitglieder. In vielen Programmen ist das Zuordnen einer geometrischen Transformationsmatrix (siehe auch Transformation und Matrix) auf jeder Gruppenebene und das Verketten solcher Matrizen eine effiziente und natürliche Methode, um solche Operationen zu verarbeiten. Ein gemeinsames Merkmal ist beispielsweise die Möglichkeit, verwandte Formen und Objekte zu einem zusammengesetzten Objekt zu gruppieren, das dann so einfach wie ein einzelnes Objekt bearbeitet werden kann.
Szenendiagramme in Grafikbearbeitungswerkzeugen[edit]
Bei der vektorbasierten Grafikbearbeitung repräsentiert jeder Blattknoten in einem Szenendiagramm eine atomare Einheit des Dokuments, normalerweise eine Form wie eine Ellipse oder einen Bezier-Pfad. Obwohl Formen selbst (insbesondere Pfade) weiter in Knoten wie Spline-Knoten zerlegt werden können, ist es praktisch, sich das Szenendiagramm als aus Formen zusammengesetzt vorzustellen, anstatt zu einer niedrigeren Darstellungsebene zu wechseln.
Ein weiteres nützliches und benutzergesteuertes Knotenkonzept ist die Schicht. Eine Ebene wirkt wie ein transparentes Blatt, auf dem eine beliebige Anzahl von Formen und Formgruppen platziert werden kann. Das Dokument wird dann zu einer Reihe von Ebenen, von denen jede bequem unsichtbar, abgeblendet oder gesperrt werden kann (schreibgeschützt). Einige Anwendungen platzieren alle Ebenen in einer linearen Liste, während andere Ebenen innerhalb von Ebenen bis zu einer beliebigen Tiefe unterstützen.
Intern gibt es möglicherweise überhaupt keinen wirklichen strukturellen Unterschied zwischen Ebenen und Gruppen, da beide nur Knoten eines Szenendiagramms sind. Wenn Unterschiede erforderlich sind, besteht eine allgemeine Typdeklaration in C ++ darin, eine generische Knotenklasse zu erstellen und dann Ebenen und Gruppen als Unterklassen abzuleiten. Ein Sichtbarkeitselement wäre beispielsweise ein Merkmal einer Ebene, aber nicht unbedingt einer Gruppe.
Szenendiagramme in Spielen und 3D-Anwendungen[edit]
Szenendiagramme sind nützlich für moderne Spiele mit 3D-Grafiken und immer größeren Welten oder Ebenen. In solchen Anwendungen repräsentieren Knoten in einem Szenendiagramm (im Allgemeinen) Entitäten oder Objekte in der Szene.
Zum Beispiel könnte ein Spiel eine logische Beziehung zwischen einem Ritter und einem Pferd definieren, so dass der Ritter als Erweiterung des Pferdes betrachtet wird. Dem Szenendiagramm wäre ein “Pferde” -Knoten mit einem “Ritter” -Knoten zugeordnet.
Das Szenendiagramm kann auch die räumliche sowie die logische Beziehung der verschiedenen Entitäten beschreiben: Der Ritter bewegt sich durch den 3D-Raum, während sich das Pferd bewegt.
In diesen großen Anwendungen spielen die Speicheranforderungen beim Entwerfen eines Szenendiagramms eine wichtige Rolle. Aus diesem Grund verwenden viele große Szenendiagrammsysteme Geometrieinstanzen, um die Speicherkosten zu senken und die Geschwindigkeit zu erhöhen. In unserem obigen Beispiel ist jeder Ritter ein separater Szenenknoten, aber die grafische Darstellung des Ritters (bestehend aus einem 3D-Netz, Texturen, Materialien und Shadern) wird instanziiert. Dies bedeutet, dass nur eine einzige Kopie der Daten aufbewahrt wird, auf die dann alle Ritterknoten im Szenendiagramm verweisen. Dies ermöglicht ein reduziertes Speicherbudget und eine höhere Geschwindigkeit, da beim Erstellen eines neuen Ritterknotens die Erscheinungsdaten nicht dupliziert werden müssen.
Implementierung eines Szenendiagramms[edit]
Die einfachste Form eines Szenendiagramms verwendet ein Array oder eine verknüpfte Listendatenstruktur, und das Anzeigen seiner Formen besteht einfach darin, die Knoten einzeln linear zu iterieren. Andere häufig verwendete Vorgänge, z. B. das Überprüfen, welche Form den Mauszeiger schneidet, werden ebenfalls über lineare Suchen ausgeführt. Für kleine Szenendiagramme reicht dies in der Regel aus.
Szenendiagrammoperationen und Versand[edit]
Das Anwenden einer Operation auf ein Szenendiagramm erfordert eine Methode zum Versenden einer Operation basierend auf dem Knotentyp. Beispielsweise würde in einer Renderoperation ein Transformationsgruppenknoten seine Transformation durch Matrixmultiplikation, Vektorverschiebung, Quaternionen oder Eulerwinkel akkumulieren. Danach sendet ein Blattknoten das Objekt zum Rendern an den Renderer. Einige Implementierungen rendern das Objekt möglicherweise direkt, wodurch die zugrunde liegende Rendering-API aufgerufen wird, z. B. DirectX oder OpenGL. Da die zugrunde liegende Implementierung der Rendering-API normalerweise nicht portierbar ist, können stattdessen das Szenendiagramm und die Rendering-Systeme getrennt werden. Um diese Art des Versands zu erreichen, können verschiedene Ansätze verfolgt werden.
In objektorientierten Sprachen wie C ++ kann dies leicht durch virtuelle Funktionen erreicht werden, wobei jede eine Operation darstellt, die auf einem Knoten ausgeführt werden kann. Virtuelle Funktionen sind einfach zu schreiben, aber es ist normalerweise unmöglich, Knoten neue Operationen hinzuzufügen, ohne auf den Quellcode zuzugreifen. Alternativ kann die Besuchermuster kann verwendet werden. Dies hat einen ähnlichen Nachteil, da es ähnlich schwierig ist, neue Knotentypen hinzuzufügen.
Andere Techniken beinhalten die Verwendung von RTTI (Run-Time Type Information). Die Operation kann als Klasse realisiert werden, die an den aktuellen Knoten übergeben wird. Anschließend wird der Knotentyp mithilfe von RTTI abgefragt und die korrekte Operation in einer Reihe von Rückrufen oder Funktoren nachgeschlagen. Dies erfordert, dass die Zuordnung von Typen zu Rückrufen oder Funktoren zur Laufzeit initialisiert wird, bietet jedoch mehr Flexibilität, Geschwindigkeit und Erweiterbarkeit.
Es gibt Variationen dieser Techniken, und neue Methoden können zusätzliche Vorteile bieten. Eine Alternative ist die Neuerstellung von Szenendiagrammen, bei der das Szenendiagramm für jede der ausgeführten Operationen neu erstellt wird. Dies kann jedoch sehr langsam sein, erzeugt jedoch ein hochoptimiertes Szenendiagramm. Es zeigt, dass eine gute Implementierung eines Szenendiagramms stark von der Anwendung abhängt, in der es verwendet wird.
Durchquerungen[edit]
Durchquerungen sind der Schlüssel zur Anwendung von Operationen auf Szenendiagramme. Eine Durchquerung besteht im Allgemeinen darin, an einem beliebigen Knoten (häufig der Wurzel des Szenendiagramms) zu beginnen, die Operation (en) anzuwenden (häufig werden die Aktualisierungs- und Rendering-Operationen nacheinander angewendet) und das Szenendiagramm (Baum) rekursiv nach unten zu bewegen ) zu den untergeordneten Knoten, bis ein Blattknoten erreicht ist. Zu diesem Zeitpunkt durchlaufen viele Szenendiagramm-Engines dann den Baum zurück und wenden eine ähnliche Operation an. Stellen Sie sich beispielsweise eine Renderoperation vor, die Transformationen berücksichtigt: Während Sie die Szenendiagrammhierarchie rekursiv durchlaufen, wird eine Vor-Renderoperation aufgerufen. Wenn der Knoten ein Transformationsknoten ist, fügt er der aktuellen Transformationsmatrix eine eigene Transformation hinzu. Sobald die Operation das Durchlaufen aller untergeordneten Knoten eines Knotens abgeschlossen hat, ruft sie die Post-Render-Operation des Knotens auf, damit der Transformationsknoten die Transformation rückgängig machen kann. Dieser Ansatz reduziert die erforderliche Menge an Matrixmultiplikation drastisch.[citation needed]
Einige Szenendiagrammoperationen sind tatsächlich effizienter, wenn Knoten in einer anderen Reihenfolge durchlaufen werden. Hier implementieren einige Systeme die Neuerstellung von Szenendiagrammen, um das Szenendiagramm in ein einfacher zu analysierendes Format oder einen Baum zu ordnen.
In 2D-Fällen rendern sich Szenendiagramme normalerweise selbst, indem sie am Wurzelknoten des Baums beginnen und dann die untergeordneten Knoten rekursiv zeichnen. Die Blätter des Baumes repräsentieren die Objekte im Vordergrund. Da das Zeichnen von hinten nach vorne erfolgt, wobei nähere Objekte einfach weiter entfernte Objekte überschreiben, wird der Prozess als Verwendung des Painter-Algorithmus bezeichnet. In 3D-Systemen, in denen häufig Tiefenpuffer verwendet werden, ist es effizienter, zuerst die nächstgelegenen Objekte zu zeichnen, da weiter entfernte Objekte häufig nur in der Tiefe getestet und nicht tatsächlich gerendert werden müssen, da sie von näheren Objekten verdeckt werden.
Szenendiagramme und Bounding Volume Hierarchies (BVHs)[edit]
Bounding Volume Hierarchies (BVHs) sind für zahlreiche Aufgaben nützlich – einschließlich effizientes Keulen und Beschleunigen der Kollisionserkennung zwischen Objekten. Ein BVH ist eine räumliche Struktur, muss jedoch die Geometrie nicht partitionieren (siehe räumliche Partitionierung unten).
Ein BVH ist ein Baum von Begrenzungsvolumina (häufig Kugeln, achsenausgerichtete Begrenzungsrahmen oder orientierte Begrenzungsrahmen). Am Ende der Hierarchie ist die Größe des Volumens gerade groß genug, um ein einzelnes Objekt fest zu erfassen (oder möglicherweise sogar einen kleineren Teil eines Objekts in hochauflösenden BVHs). Wenn man die Hierarchie aufsteigt, hat jeder Knoten sein eigenes Volume, das alle darunter liegenden Volumes eng umfasst. An der Wurzel des Baums befindet sich ein Volume, das alle Volumes im Baum (die gesamte Szene) umfasst.
BVHs sind nützlich, um die Kollisionserkennung zwischen Objekten zu beschleunigen. Wenn das Begrenzungsvolumen eines Objekts kein höheres Volumen im Baum schneidet, kann es kein Objekt unterhalb dieses Knotens schneiden (daher werden alle sehr schnell zurückgewiesen).
Es gibt einige Ähnlichkeiten zwischen BVHs und Szenendiagrammen. Ein Szenendiagramm kann leicht angepasst werden, um einen BVH einzuschließen / zu werden – wenn jedem Knoten ein Volume zugeordnet ist oder ein speziell erstellter “gebundener Knoten” an einer geeigneten Stelle in der Hierarchie hinzugefügt wurde. Dies ist möglicherweise nicht die typische Ansicht eines Szenendiagramms, aber die Aufnahme eines BVH in ein Szenendiagramm bietet Vorteile.
Szenendiagramme und räumliche Aufteilung[edit]
Eine effektive Möglichkeit zum Kombinieren von räumlicher Partitionierung und Szenendiagrammen besteht darin, einen Szenenblattknoten zu erstellen, der die räumlichen Partitionierungsdaten enthält.[clarification needed] Dies kann die Recheneffizienz des Renderns erhöhen.
Geodaten sind normalerweise statisch und enthalten im Allgemeinen nicht bewegte Szenendaten in einer partitionierten Form.[clarification needed] Einige Systeme verfügen möglicherweise über separate Systeme und deren Darstellung. Dies ist in Ordnung und es gibt keine wirklichen Vorteile für beide Methoden. Insbesondere ist es schlecht, das Szenendiagramm im räumlichen Partitionierungssystem zu haben, da das Szenendiagramm besser als das größere System für die räumliche Partitionierung angesehen wird.[neutrality is disputed]
Sehr große Zeichnungen oder Szenendiagramme, die ausschließlich zur Laufzeit erstellt werden (wie dies bei Raytracing-Rendering-Programmen der Fall ist), erfordern eine automatisiertere Definition von Gruppenknoten. Ein Raytracer nimmt beispielsweise eine Szenenbeschreibung eines 3D-Modells und erstellt eine interne Darstellung, die seine einzelnen Teile in Begrenzungsrahmen (auch Begrenzungsplatten genannt) aufteilt. Diese Felder sind hierarchisch gruppiert, damit Strahlschnitt-Tests (als Teil der Sichtbarkeitsbestimmung) effizient berechnet werden können. Ein Gruppenfeld, das beispielsweise keinen Augenstrahl schneidet, kann das Testen eines seiner Mitglieder vollständig überspringen.
Eine ähnliche Effizienz gilt auch für 2D-Anwendungen. Wenn der Benutzer ein Dokument so vergrößert hat, dass nur ein Teil davon auf seinem Computerbildschirm sichtbar ist, und dann einen Bildlauf durchführt, ist es hilfreich, einen Begrenzungsrahmen (oder in diesem Fall ein Begrenzungsrechteckschema) zu verwenden, um schnell zu bestimmen, welche Szene Diagrammelemente sind sichtbar und müssen daher tatsächlich gezeichnet werden.
Abhängig von den Einzelheiten der Zeichenleistung der Anwendung kann ein großer Teil des Designs des Szenendiagramms durch Überlegungen zur Rendereffizienz beeinflusst werden. In 3D-Videospielen wie Quake werden BSP-Bäume (Binary Space Partitioning) stark bevorzugt, um Sichtbarkeitstests zu minimieren. Die Berechnung von BSP-Bäumen aus Entwurfsszenendiagrammen dauert jedoch sehr lange und muss neu berechnet werden, wenn sich der Entwurfsszenendiagramm ändert, sodass die Ebenen in der Regel statisch bleiben und dynamische Zeichen im räumlichen Partitionierungsschema im Allgemeinen nicht berücksichtigt werden.
Szenendiagramme für dichte reguläre Objekte wie Höhenfelder und Polygonnetze verwenden in der Regel Quadtrees und Octrees, die spezielle Varianten einer 3D-Begrenzungsrahmenhierarchie sind. Da ein Höhenfeld selbst ein Boxvolumen belegt, ist es effizient und natürlich, diese Box rekursiv in acht Subboxen (daher das “Okt” in Oktree) zu unterteilen, bis einzelne Höhenfeldelemente erreicht sind. Ein Quadtree ist einfach ein 2D-Octree.
Standards[edit]
PHIGS[edit]
PHIGS war die erste kommerzielle Szenendiagrammspezifikation und wurde 1988 zum ANSI-Standard. Unterschiedliche Implementierungen wurden von Unix-Hardwareanbietern bereitgestellt. Das HOOPS 3D-Grafiksystem scheint die erste kommerzielle Szenendiagrammbibliothek gewesen zu sein, die von einem einzelnen Softwareanbieter bereitgestellt wurde. Es wurde für die Ausführung auf unterschiedlichen 2D- und 3D-Schnittstellen auf niedrigerer Ebene entwickelt. Die erste große Produktionsversion (v3.0) wurde 1991 fertiggestellt. Kurz danach veröffentlichte Silicon Graphics IRIS Inventor 1.0 (1992), ein Szenendiagramm, auf dem aufgebaut wurde oben auf der IRIS GL 3D API. 1994 folgte Open Inventor, ein tragbares Szenendiagramm, das auf OpenGL aufbaut. Weitere 3D-Szenendiagrammbibliotheken finden Sie unter Kategorie: 3D-Szenegraph-APIs.
X3D[edit]
X3D ist ein lizenzfreies Open-Standards-Dateiformat und eine Laufzeitarchitektur zur Darstellung und Kommunikation von 3D-Szenen und -Objekten mithilfe von XML. Es handelt sich um einen ISO-ratifizierten Standard, der ein System zum Speichern, Abrufen und Wiedergeben von in Anwendungen eingebetteten Echtzeit-Grafikinhalten in einer offenen Architektur zur Unterstützung einer Vielzahl von Domänen und Benutzerszenarien bereitstellt.
Siehe auch[edit]
Verweise[edit]
Bücher[edit]
- Leler, Wm und Merry, Jim (1996) 3D mit HOOPS, Addison-Wesley
- Wernecke, Josie (1994) Der Inventor-Mentor: Programmieren objektorientierter 3D-Grafiken mit Open Inventor, Addison-Wesley, ISBN 0-201-62495-8 (Release 2)
Artikel[edit]
- Bar-Zeev, Avi. “Scenegraphs: Vergangenheit, Gegenwart und Zukunft”
- Carey, Rikk und Bell, Gavin (1997). “Das kommentierte VRML 97-Referenzhandbuch”
- James H. Clark (1976). “Hierarchische geometrische Modelle für Algorithmen für sichtbare Oberflächen”. Mitteilungen der ACM. 19 (10): 547–554. doi:10.1145 / 360349.360354.
- Helman, Jim; Rohlf, John (1994). “IRIS Performer: Ein leistungsstarkes Multiprocessing Toolkit für Echtzeit-3D-Grafiken”
- PEXTimes – “Inoffiziell die PHIGS-Erweiterung auf X. Offiziell war PEX kein Akronym.”
- Strauss, Paul (1993). “IRIS Inventor, ein 3D-Grafik-Toolkit”
Recent Comments