scenegraph mit grid beschleunigen

Einstiegsfragen, Mathematik, Physik, künstliche Intelligenz, Engine Design
Antworten
foofel
Beiträge: 10
Registriert: 03.03.2014, 13:34

scenegraph mit grid beschleunigen

Beitrag von foofel » 11.07.2016, 14:52

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?

Benutzeravatar
Schrompf
Moderator
Beiträge: 3783
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: scenegraph mit grid beschleunigen

Beitrag von Schrompf » 11.07.2016, 15:25

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
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

foofel
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitrag von foofel » 11.07.2016, 15:44

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.

Benutzeravatar
Schrompf
Moderator
Beiträge: 3783
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: scenegraph mit grid beschleunigen

Beitrag von Schrompf » 11.07.2016, 16:48

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.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

foofel
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitrag von foofel » 11.07.2016, 18:15

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

Benutzeravatar
Schrompf
Moderator
Beiträge: 3783
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: scenegraph mit grid beschleunigen

Beitrag von Schrompf » 12.07.2016, 08:52

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.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

foofel
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitrag von foofel » 12.07.2016, 10:53

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

Benutzeravatar
Schrompf
Moderator
Beiträge: 3783
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: scenegraph mit grid beschleunigen

Beitrag von Schrompf » 12.07.2016, 11:20

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.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

foofel
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitrag von foofel » 13.07.2016, 11:07

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?!
Zuletzt geändert von Chromanoid am 13.07.2016, 12:53, insgesamt 1-mal geändert.
Grund: code-Tag parametrisiert, um Einrückung anzuzeigen

Antworten