scenegraph mit grid beschleunigen

Einstiegsfragen, Mathematik, Physik, künstliche Intelligenz, Engine Design

scenegraph mit grid beschleunigen

Beitragvon 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?
foofel
 
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitragvon 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.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3713
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: scenegraph mit grid beschleunigen

Beitragvon 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.
foofel
 
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitragvon 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.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3713
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: scenegraph mit grid beschleunigen

Beitragvon 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...
foofel
 
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitragvon 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.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3713
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: scenegraph mit grid beschleunigen

Beitragvon 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
foofel
 
Beiträge: 10
Registriert: 03.03.2014, 13:34

Re: scenegraph mit grid beschleunigen

Beitragvon 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.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3713
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: scenegraph mit grid beschleunigen

Beitragvon foofel » 13.07.2016, 11:07

Ok, ich hab z.B. den baum:
Code: Ansicht erweitern :: 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: Ansicht erweitern :: 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
foofel
 
Beiträge: 10
Registriert: 03.03.2014, 13:34


Zurück zu Allgemeine Fragen der Spieleentwicklung

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste