Registriert: Di Mai 18, 2004 16:45 Beiträge: 2622 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.
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
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
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2622 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:
usingnamespace RF_Lazy;
auto bla = Lazy(RF_Math::Float32::Sin(), // Lazy erwartet eine funktion mit 1 parameter und speichert den Funktionspointer und den Parameter by-reference.
Literal(2.0f* PI)*// Compiler rechnet 2.0*PI aus und gibt eine compile time Konstante zurück, Literal nimmt den Wert by-value.
Variable(alpha)/// Compiler nimmt alpha als reference auf.
180.0_lf);// _lf ist ein numeric user literal und ruft Literal(180.0f) auf.
if(input == a){
float r = bla.Execute();// Execute läuft durch die Klassentypen rekursive und führt die Operationen aus.
// Arbeit
}
elseif(input == b){
float r = bla.Execute();// Execute läuft durch die Klassentypen rekursive und führt die Operationen aus.
// Arbeit
}
else
{
// Arbeit ohne bla.
}
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 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
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
Registriert: Di Mai 18, 2004 16:45 Beiträge: 2622 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
Mitglieder in diesem Forum: 0 Mitglieder und 9 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.