Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Mär 29, 2024 00:10

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Moderne Octrees
BeitragVerfasst: Do Jan 25, 2018 09:46 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Ich belese mich gerade zu Octrees und was so im letzten Jahrzehnt passiert ist.
Die Antwort ist positiv. Es gab viele neue Ansätze und Experimente.
Octree ist ein Spatial dividing system und dient dazu Entscheidungen in einem 3D Raum zu beschleunigen.
Es gibt noch diverse andere Techniken aber Octrees sind sehr einfach, schnell und sind für dynamische Szenen einsetzbar.

Octrees leiden unter Rekursion, was eine parallelisierung stark erschwert.
Des weiterem benötigt man diverse Nodes, die bei zu kleinen Nutzdaten sehr speicherineffizient sind.
Die Daten tendieren stark zu random access, was der Tot für Caches und Branch prediction sind.
Für wirklich alle Probleme hab ich nun Papers, Code und Lösungen gefunden und bin noch am sondieren.

Zugriffs optimierung
https://www.yumpu.com/en/document/view/51094778/statistical-optimization-of-octree-searches-puc-rio
libmorton

Speicheroptimierung
Pefect hash

Multithreading
Per Achsen Kontruktion
Per Achsen Kontruktion
Per Achsen Kontruktion
Sweep and prune
Task stealing and micro task generation
Gefällt mir garnicht, es ist extrem inefizient, ja man kann mehr Kerne nutzen, die schaukeln sich schnell auf 100% CPU-Last aber man hat sehr viel stalling, da die Tasks viel zu klein sind und viel Zeit in Cold-Caches und kämpfen um Tasks verbraucht. Ich hab task stealing queues in mein ThreadPool implementiert und wenn man nicht ein paar komplexe Operationen macht, dann ist es schneller Single Threaded und multithreading unsafe zu machen.

Ich versuche die papers zu verlinken und weitere sachen zu finden.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Moderne Octrees
BeitragVerfasst: Mo Jan 29, 2018 11:37 
Offline
DGL Member

Registriert: Fr Mai 11, 2012 13:25
Beiträge: 229
Programmiersprache: c++, c, JavaScript
Würde es nicht reichen, einen einzelnen Thread auf den Octree loszulassen, und den die Visibility updaten zu lassen?
Oder hast Du sehr komplexe Octrees im Sinn?

_________________
"Pixel, ich bin dein Vater."
-Darf Shader


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Moderne Octrees
BeitragVerfasst: Mo Jan 29, 2018 12:32 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Ja ich will auch sehr komplexe Szenen realisieren und möglichst parallelisieren können(notfalls wirklich task stealing).

Am Wochenende hab ich angefangen es zu implementieren, ich hab am Fr/Sa sehr grob lazy evaluation für scalar eingebaut.
Lazy scalar math
Code:
  1. using namespace RF_Lazy;
  2. auto bla = Lazy(RF_Math::Float32::Sin(), // Lazy erwartet eine funktion mit 1 parameter und speichert den Funktionspointer und den Parameter by-reference.
  3.   Literal(2.0f * PI) * // Compiler rechnet 2.0*PI aus und gibt eine compile time Konstante zurück, Literal nimmt den Wert by-value.
  4.   Variable(alpha)/ // Compiler nimmt alpha als reference auf.
  5.   180.0_lf); // _lf ist ein numeric user literal und ruft Literal(180.0f) auf.
  6. if (input == a){
  7. float r = bla.Execute();// Execute läuft durch die Klassentypen rekursive und führt die Operationen aus.
  8. // Arbeit
  9. }
  10. else if (input == b){
  11. float r = bla.Execute();// Execute läuft durch die Klassentypen rekursive und führt die Operationen aus.
  12. // Arbeit
  13. }
  14. else
  15. {
  16.   // Arbeit ohne bla.
  17. }

Lineare Algebra folgt bald und dann macht obiges hoffentlich Sinn, wenn man Projections matrix aufbauen und andere komplexe scalar Operationen lazy ausführt.

Octree Header und Source hab ich gestern angefangen zu schreiben.
Ich wollte erstmal perfect hash implementieren aber hab mich entschieden erstmal die Morton Variante zu machen.
Für Morton braucht man eine Hash-List und da hab ich eine SIMD optimierte bereits geschrieben also kommt die als erstes(low hanging fruites und so).
Wenn ich so drüber nachdenke, macht eine Ray Intersection garkein Sinn :shock: brauch ne Plane-AABB Intersection.

Perfect hash und spatial octree(über morton) benötigen ein statische Baumdimension, also die Weltgröße sollte sich nicht ändern, da man sonnst den Baum neu aufbauen muss.
Ich will aktuell es intern Normalisieren [(-1.0) - 1.0] und extern eine Userspezifizierte Ausmaße nutzen, um maximale Auflösung nutzen zu können.
Spatial Octree ist noch speicherfreundlicher als Perfect hash aber nicht so cache freundlich.
Ich versuche immer noch die stärken und schwächen zu verstehen, also so ganz bin ich da noch nicht durchgestiegen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Moderne Octrees
BeitragVerfasst: Fr Feb 02, 2018 01:08 
Offline
DGL Member

Registriert: Fr Mai 11, 2012 13:25
Beiträge: 229
Programmiersprache: c++, c, JavaScript
Was für Szenen schweben Dir denn vor?
Evtl. könntest Du den octree sogar auf der GPU machen, z.B. mit compute shader, glaube für point cloud data wird das ganz gern gemacht.

_________________
"Pixel, ich bin dein Vater."
-Darf Shader


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Moderne Octrees
BeitragVerfasst: Fr Feb 02, 2018 09:25 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Auf GPU werden sehr kleine Sparse und Perfect Hash Octrees verwendet.
Die sind aber nicht gut bei Änderungen und sind sehr unfreundlich für GPUs.
Die CPU hat den Vorteil, dass die ekelige scalar operationen, die für die intersection tests nötig sind, gut kann und man hat viel mehr Speicher und größere Caches, die gerade bei Sparse Octrees massive Performance steigerungen bringen, denn die Berechnungen können teilweise in lookuptables vor gehalten werden.
GPUs gehen von voll toll/Zocker PC bis bullshit Raspberry Pi, da will ich nicht auf ne GPU setzen.
Das Octree wird hier auch nicht für Global Illumination oder das rendern von Voxeln und Minecraftblöcken benötigt, sondern für das schnellst mögliche raus werfen von Objekten, aus der Renderpipeline.
Also nach dem das Octree die Sichtbarkeit im Frustum fest gestellt hat, kommt ein occlussion query per Software, damit es keine Latenz, wie bei GPU basierten querries, gibt und die Befehle nicht in die Renderpipeline gehen.

Ich hab gestern Nacht eine sortierte Trefferliste, von AABB-Plane Schnitttests eingebaut. Jeden Frame prüfe ich die planes, die im vorigen Frame die meisten treffer hatten und breche beim ersten treffer ab. Eine neue liste wird beim prüfen befüllt und mit der alten getauscht. So kann ich viel schneller berechnen, da ich die Plane mit der höchsten Wahrscheinlichkeit als erstes prüfe und liegt das Objekt ausserhalb des Frustumsegments, dann brauch ich keine 5 weiteren tests fahren. Das ist eine Form der Statistischen test optimierung.

Ich brauche demnächst mal ein performance test, damit ich dann anfangen kann die Optimierungen zu bewerten.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: Google [Bot] und 37 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.159s | 18 Queries | GZIP : On ]