Baumstrukturen mit verschiedenen Traversierung

[dronus]

Hi,

ich überlege gerade wie die optimalen Datenstrukturen für den "Weltenmotor" aussehen. Der Unterschied zu normalen Scenegraphen ist hauptsächlich, dass ich eine sehr große Anzahl hierarchischer Objekte mit jeweils eher kleiner Datenmenge (keine gespeicherte Geometrie) habe.

Da jedes Objekt das gerendert wird nur sehr wenig Geometrie liefert, muss ich dramatisch zusammenfassen. Das widerspricht aber dem rekursiven Traversieren, dass durch den Stack enorm viel Spiecher spart (z.b. Transformationsstack).

Zwei nötige Traversierungen:

* Rekursiv durch den Baum, nützlich für
** um die sichtbaren Objekte zu ermitteln
** die Objekte zu erzeugen
** die Transformationen zu berechnen

*Seitlich durch eine oder wenige Baumebenen
** um alle Grashalme eines Rasens zusammenzufassen
** um nachbarschaftliche Berechnungen zu machen, z.b. weiche Normalen fürs Shading

ich weiss nicht, wie ich das unter einen Hut kriege.
Wenn ich die Rekursion abschaffe und den Baum schichtenweise aufbaue, müssen alle berechneten Objekteingenschaften, und auch die Transformationsmatrizen gespeichert werden, da komme ich auf ein 1GB Daten bei moderatem Deteilgrad, ein Großteil davon wird pro Frame aktualisiert. Das klappt so nicht.
Ich kann aber auch nicht einfach rekursiv rendern, weil es dafür zu viele kleine Objekte sind, die den CPU-GPU Engpass verstopfen.

freue mich über Ideen..

[Chromanoid]

Wie wäre es mit einem nicht hierarchischem Graphen/Netz und keinem Baum?
Jeder Knoten hat dann einmal hierarchische Verbindungen für rekursives abklappern (normaler Scenegraph) und einmal Beziehungsverbindungen zu Objekten/bzw. Beziehungsfunktionen.
Wenn also mehrere Objekte nebeneinander liegen passiert folgendes:
Erstmal klapperst du den baum rekursiv ab. Trifft man auf ein Objekt, was eine Verbindung zu einem Beziehungsobjekt (z.B. ein Weiche-Normale-Berechnen-Berechnen-Objekt) hat, führst du weitere Berechnungen o.Ä. durch. Sobald ein "Mitglied" des Beziehungsobjektes die Berechnung für das Beziehungsobjekt aufruft, sollte evt. eine vollständige Berechnung aller Mitglieder der Beziehung erfolgen. Wird später im Baum wieder ein Mitglied aufgerufen wurde es dann bereits berechnet. Sind vor der Berechnung eines Beziehungsobjektes erst alle durch Rekursion erlangbaren Daten nötig müsste man zwei Durchgänge beim Abklappern machen oder die zu berechnenden Beziehungsobjekte in eine Liste aufnehmen.

[dronus]

Hm, das Problem mit dem Verlust des Stacks bleibt aber, oder? Wenn ich die Transformation rekursiv berechne, z.b. für die Sichtberechnung, muss ich sie für das spätere Rendern aufbewahren d.h. schonmal mindestens eine Matrix pro Objekt. Würde ich gleich rekursiv rendern wäre nur eine Matrix pro Ebene auf dem Stack und der Speicherbedarf reduziert sich drastisch.

Das ist ohnehin problematisch weil ich beim Zusammenfassen der Geometrie einer Ebene die Geometrie auf der CPU transformieren müsste, garnicht schön..

Möglich wäre vielleicht alle Transformationen einer Ebene als Textur in die GraKa zu schicken und den Verticies einen Index auf die zugehörige Matrix mitzugeben.. dann könnte die GPU transformieren.

Im Idealfall wird die tiefste Baumebe die nicht mehr so komplexe Algortihmen hat ohnehin auf der GPU berechnet, vielleicht mit einem Geometrieshader. Wenn "Transform Feedback" bei allen GPUs verfügbar wird kann man sogar mehrere Baumebenen vor der tiefsten auf der GPU rechnen. Jeder Vertex einer Ebene wird dann durch ein "Objekt" für die nächste Ebene erstetzt, das entweder aus Teilobjekten besteht (in Vertices codiert) oder letztendlich Geometrie. Ich weiss allerdings nicht wieviel Daten ein Vertex aufnehmen darf, darf man da eine ganze Matrix reinpacken?