Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

OpenGL Octrees

Werbeanzeige

EuadeLuxe

Alter Hase

  • »EuadeLuxe« ist der Autor dieses Themas

Beiträge: 412

  • Private Nachricht senden

1

20.10.2013, 14:14

OpenGL Octrees

Liebe Community,

ich beschäftige mich gerade mit Space Partitioning, und speziell den Octrees. Das generelle Prinzip mti der Unterteilung in 8 Würfel, die wiederum in 8 Würfel unterteilt werden können, und die anderen rekursiven Elemente habe ich verstanden. Meine Frage dreht sich eher um den praktischen Einsatz: So wie ich das sehe, muss man dem Octree doch die Vertices mitgeben, oder? Doch wie macht man das, wenn man die Vertices in einem VBO abspeichert? Und generell: was macht man, wenn sich die Objekte bewegen? Muss der Octree dann jeden Frame ganz neu gebaut werden? Ich nehme stark an, man benutzt den Octree nur für statische Geometrie, aber wie sieht das dann mit einem Terrain aus? Gerade ein Terrain würde ich in einem VBO abspeichern, und das kann ich dann nicht wirklich trennen, um nur bestimmte Regionen zu rendern. Folglich muss der Octree mit jedem einzelnen Vertex verbunden werden? Wie bewerkstelligt man das?

Es wäre toll, wenn mir jemand, der evtl. sogar schon einmal selbst so etwas implementiert hat, mir diese Fragen beantworten könnte.

Liebe Grüße,
~ EuadeLuxe ~

DeKugelschieber

Community-Fossil

Beiträge: 2 641

Wohnort: Rheda-Wiedenbrück

Beruf: Software-Entwickler

  • Private Nachricht senden

2

20.10.2013, 14:42

Naja eigentlich kannst du ja immer alles so machen wie du willst ;)

Ich füge statische Objekte in einen Octree ein, die Objekte selbst haben dann alle Buffer usw. Dann wird in einem durchlauf der Octree getestet und entsprechend für die Objekte "visible = true" oder eben false gesetzt.
Terrain würde ich anders cullen... aber auch das kann man zerstückeln wenn man möchte.

Bei den beweglichen Objekten kommt es darauf an wie schnell und wie groß die Objekte sind. Wenn sie langsam und riesig sind kannst du auch jedes mal prüfen in welchem Kasten/Kästen das Ding ist. Oder du lässt es einfach raus und cullst normal über Frustum culling. Für sehr schnelle Objekte die nicht zwischendurch 10 Minuten rumstehen macht das natürlich keinen Sinn, die dann einfach normal cullen...
Grüße, Kugel

GitHub Meine Firma Pirsch Analytics

EuadeLuxe

Alter Hase

  • »EuadeLuxe« ist der Autor dieses Themas

Beiträge: 412

  • Private Nachricht senden

3

20.10.2013, 16:06

Das heißt, du suchst nur für statische Objekte (ausgenommen Terrain) den kleinstmöglichen Würfel, und fügst in diesen dann den Mesh ein? Mal noch eine Frage, was könnte man dann für Verbesserungen für dynamische Objekte (wie etwa Gegner, oder so) einbauen, wenn man nicht nur das einfache Frustrum culling einbauen möchte (mal angenommen ich hätte 10.000 Gegner)? Und bringt das wirklich Performance? Gibt es überhaupt dafür noch etwas?

Noch ein anderes Thema: Lohnt es sich ein Portal System zugleich mit anderen Methoden, wie etwa dem Octree zu verwenden, oder reicht normalerweise eine Verbesserung?

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

4

20.10.2013, 21:13

- Vertices haben in einem Octree nichts mehr zu suchen, man cullt schon lange keine einzelnen Dreiecke mehr. Auf Modell- bzw. Meshebene ist es viel effizienter, wenn ein Drawcall nicht genügend Dreiecke hat, fällt der Verwaltungsaufwand drum herum viel zu stark ins Gewicht und du kannst weniger pro Sekunde rendern. Ein großes Terrain wird vermutlich sowieso LOD-Stufen haben, das wären dann gute Meshs zum Cullen. Ein kleines Terrain dürftest du auch komplett so rendern können.

- Unterschätze nie die Relevanz von Chaches. Ein nettes Beispiel ist der Aufwand, ein Objekt aus einem std::vector und einer std::list zu löschen. Der Vector ist entgegen aller Erwartung viel schneller, obwohl im Schnitt der halbe Vektor elementweise umkopiert werden muss (die Liste muss nur 2 Zeiger ändern). Der Grund ist, dass alle Vektorelemente sequentiell im Speicher stehen, die Listenelemente aber über den ganzen Speicher verstreut sind.
Was ich damit sagen will: Ein Bruteforce cullen aller Objekte (auch von 10.000), also BoundingSphere/Viewfrustum-Test ist leichter zu implementieren und zu pflegen als eine komplexe Culling-Hierarchie und kann sogar schneller sein.

- Oft unterschätzt sind unnötige State-Changes, wie Textur- oder Shaderneusetzen. Alle Draw-Jobs nach Shader/Textur sortieren und nur neu setzen, wenn sich auch wirklich etwas ändert bringt enorm viel.
Lieber dumm fragen, als dumm bleiben!

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

5

20.10.2013, 21:50

Wenn es um Culling auf Objektebene in dynamischen Szenen geht, so wäre evtl. generell z.B. eine Bounding Volume Hierarchy effizienter...oder auch einfach nur ein simples Array oder ein Grid, wenn es nicht zu viele Objekte gut verteilt in nicht zu großen Szenen sind...
m4studios

EuadeLuxe

Alter Hase

  • »EuadeLuxe« ist der Autor dieses Themas

Beiträge: 412

  • Private Nachricht senden

6

21.10.2013, 16:37

Danke erstmal für die ganzen Antworten. Bedeutet das dann generell, dass ich, wenn ich 10.000 Gegner habe, die einfach per Frustrum culling ausschließe? Ich glaube ich denke mal wieder einfach zu kompliziert. Den Frustrum culling Algorithmus habe ich schon implementiert, und irgendwann stellte sich mir die Frage, ob ich wohl einen Octree implementieren könnte. Doch schon bald kam ich an ein riesiges Problem: Wie übergebe ich dem Octree die ganzen Modelle / Meshs? Ich glaube, das mit dem Frustrum culling für Gegner hält sich noch in Grenzen, ich werd´s mal probieren. Die Bounding Volume Hierarchy werde ich mal implementieren, dazu aber gleich eine Frage: Muss ich diese jeden Frame neu berechnen?
Zu den Caches: Ist es dementsprechend sinnvoll, wenn ich eine Art Suchfunktion nach Shader / Program bzw. Texturen implementiere?


Danke für all die guten Antworten!

Liebe Grüße,
~ EuadeLuxe ~

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

21.10.2013, 16:39

Ein genereller Tipp:
Erst dann anfangen zu optimieren, wenn es nötig wird.
Aber halte dein Design von Anfang an flexibel genug, damit der eventuelle Einbau einer räumlichen Datenstruktur (Octree, Grid, ...) einfach möglich ist.

Was meinst du jetzt mit Caches?
Das Wort wurde in diesem Thread bislang gar nicht erwähnt. ;)
David Scherfgens Website | Konzentrationstest Polizei

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

8

21.10.2013, 17:08

Zitat von »David Scherfgen«

Was meinst du jetzt mit Caches?
Das Wort wurde in diesem Thread bislang gar nicht erwähnt. ;)
Außer in Post #4 natürlich ;)
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

EuadeLuxe

Alter Hase

  • »EuadeLuxe« ist der Autor dieses Themas

Beiträge: 412

  • Private Nachricht senden

9

21.10.2013, 17:33

Ich war mir ehrlich gesagt nicht ganz sicher, ob jonatha_klein nicht eher changes meinte... Aber ich habe mich dann für Caches entschieden. Generell habe ich eine ziemlich flexible Struktur. So leite ich zum Beispiel alle möglichen SzenenGraphen (wie den ganz normalen) von einer Basisklasse ab. Ich frage mich eben nur, wie ich die VBOs mit diesen Strukturen verbinden soll. Das geht doch generell einfach nicht, oder?

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

10

21.10.2013, 17:51

Zitat von »BlueCobold«

Zitat von »David Scherfgen«

Was meinst du jetzt mit Caches?
Das Wort wurde in diesem Thread bislang gar nicht erwähnt. ;)
Außer in Post #4 natürlich ;)

Oh, da wurde es falsch geschrieben.
Das erklärt, warum ich es nicht gefunden habe.
David Scherfgens Website | Konzentrationstest Polizei

Werbeanzeige

Ähnliche Themen