scenegraph mit grid beschleunigen

[foofel]

Ich versuche gerade mein scenegraph rendering über ein simples grid zu beschleuningen steh aber ein bischen auf dem schlauch wie ich die richtige reihenfolge beim render einhalte.
Was ich hab:
- Scenegraph welcher einfach nur angibt in welcher reihenfolge die objekte gezeichnet werden.
- grid: erlaubt aabb queries nach scenegraph nodes

Meine Idee war:
- grid nach gerade sichtbaren objekten fragen
- Insert_Magic_Sort
- diese rendern

leider fällt mir kein sonnvoller weg ein wie ich von den einzelnen nodes die mir das grid liefert wieder die richtige reihenfolge aus dem scenegraphen bekomme. Hab ich einen generellen denkfehler oder wie wird sowas gelößt?

[Schrompf]

Der Denkfehler scheint mir, dass Du tatsächlich eine Reihenfolge einhalten willst. Bei den allermeisten Objekten ist es doch aber wurstegal, in welcher Reihenfolge Du die renderst. Verschwende Deine wertvolle Rechenzeit nicht mit Tiefensortierung, um eine sehr beschränkte Version eines ZBuffers zu implementieren. Du solltest stattdessen nur grob in logische Einheiten aufteilen (z.b. Festes, dann Bodenbewuchs, zum Schluss Transparentes und Partikel) und innerhalb dieser Layer dann nach minimalen State Changes sortieren. Oder bei DX12/Vulkan dann einfach die DrawCalls raushauen, weil die StateChange-Sortierung praktisch nix mehr bringt.

Meine Engines sehen aber auch immer so aus:
- Grid (oder welche Beschleunigungsstruktur auch immer) abfragen
- pro Layer in einem Array sammeln
- optional pro Layer sortieren (für DX9 sehr wichtig, DX10/11 nicht mehr so)
- DrawCalls raushauen

[foofel]

Ich sollte vielleicht dazu sagen, dass das ganze in 2D ist. Es stimmt zwar das es bei einigen objekten nicht darauf ankommt, aber generell schon. Hmm aber vielleicht kann ich das aber über layer lösen wie du das schon angesprochen hast.

[Schrompf]

Dann sortiere halt nach virtueller Tiefe. Das Zusammensammeln aus dem Grid ist doch völlig unabhängig von der Art, wie Du es nachher renderst.

- Grid nach sichtbaren Objekten abklappern -> ergibt einen std::vector< ZuZeichnendeDinge >
- Vector sortieren - nach Kriterien Deiner Wahl
- Vector an Renderer übergeben, der das in DrawCalls verpackt und zeichnet

Wenn Dein SceneGraph die Objekte bereits in der richtigen Reihenfolge ausgibt, dann packe sie doch als std::pair<Objekt, SortierKriterium> in das Grid. Damit kannst Du sie nachher noch gegeneinander sortieren, wenn durch den Zwischenschritt die ursprüngliche Reihenfolge der Elemente verloren gegangen ist.

[foofel]

Das ist ja eigentlich was ich am liebsten hätte, aber wie kriege ich aus einer baumstruktur dieses sortierkriterium...

[Schrompf]

Du sagtest, die Baumstruktur ergibt automatisch die richtige Reihenfolge? Dann zähl doch einfach hoch und speichere den Zähler mit dem Objekt im Grid.

[foofel]

Das funktioniert zwar, aber dann müßte ich sobald ein element mal nicht ans ende einer node angefügt/entfernt wird ja alle nachfolgenden node indexes neu berechnen. Da der Tree ziemlich groß werden kann würde ich das gerne vermeiden. Wahr­schein­lich will ich zu viel vermeiden :D

[Schrompf]

Ne, musst Du nicht. Du denkst Dir das Problem irgendwie viel zu kompliziert. Das ist wirklich ganz banal: Sortierkriterium mit Objektref ausgeben, danach sortieren, rendern.

[foofel]

Ok, ich hab z.B. den baum:

Code: Alles auswählen

- root
    - hud
        - something 1
        - something 2
    - scene
        - foreground layer
            - object 1
                - sub node
                - sub node
            - object 2
                - sub node
                - sub node
                - sub node
            ...
            - object 1000
                - sub node
        - main layer
            - object x
                - sub node
        - background layer
            - object y    

mein grid gibt mir beliebige nodes zurück. Ich hab also sowas:

Code: Alles auswählen

[
    object 2,
    something 1,
    sub node,
    sub node,
    sub node,
    object x
]

Bis hier hin alles ok. Jetzt der teil den ich immer noch nicht verstehe: was muss ich machen damit die nodes ein sortier kriterium enthalten. Vielleicht ists total einfach aber irgendein gedankengang scheint mir zu fehlen. Nodes einfach zu nummerieren kann nicht gehen weil durchweg neue eingefügt/entfernt werden. das würde dazu führen das ich jedes mal den baum durchlaufen muss um die ids zu updaten.

edit: ich bin zu doof für die formatierung, der zeigt die einrückung nicht an?!