F
@Rav1642 sagte in An std::thread übergebenen Raw-Pointer löschen:
@manni66 sagte in An std::thread übergebenen Raw-Pointer löschen:
Warum benutzt du nicht std::sort?
Ich möchte ganz gerne den RadixSort nutzen, der eine Laufzeit von O(n * m) hat, wobei m fest 10 ist, so dass die Laufzeit in O(n) liegt.
std::sort ist O(nlogn)\mathcal{O}(n\log n)O(nlogn).
logn\log nlogn ist aber gerade die Anzahl an Bits, die du mindestens für die Schlüssel brauchst, damit diese überhaupt nnn voneinander verschiedene Werte annehmen können.
Wenn deine Schlüssellänge also maximal 10 Bits ist, wie du hier implizierst, dann kannst du eh nur maximal 2102^{10}210 voneinander verschiedene Schlüssel zum Sortieren haben (es sei denn, du erlaubst mehrfache Elemente mit dem selben Schlüssel). Dann ist logn≤10\log n \leq 10logn≤10 und damit für dieses praktische Szenario effektiv ebenfalls konstant.
Man könnte sogar argumentieren, dass ein O(nlogn)\mathcal{O}(n\log n)O(nlogn) -Algorithmus für n≤210n \leq 2^{10}n≤210 in O(1)\mathcal{O}(1)O(1) liegt, da er nie mehr als 210⋅10=102402^{10}\cdot10=10240210⋅10=10240 Schritte benötigt.
Das ist natürlich wenig hilfreich um die Laufzeit des Algorithmus für Probleme beliebiger Größe zu bewerten. Ich will hier nur deutlich machen, dass du dich nicht von dem O(n)\mathcal{O}(n)O(n) täuschen lassen solltest. Das heisst nicht automatisch, dass der Algorithmus für dein Problem auch tatsächlich schneller ist. Der betrachtet das Problem lediglich aus einer anderen Perspektive.
@Finnegan sagte in An std::thread übergebenen Raw-Pointer löschen:
Ich empfehle eher einen std::vector<float> für anglesals einen manuell verwalteten C-Array-Pointer. Den kannst du bei Bedarf auch in einen Smartpointer packen oder auch moven (std::move), wenn du den Besitz an dem herumreichen willst.
Es gibt zwei Gründe, weshalb ich mich dazu entschied: mein superschneller RadixSort sortiert nur auf Arrays (übergeben per Pointer und der Größe). Zudem bin ich bisher davon überzeugt, dass das Tempo von vector plus "normalem" sort nicht reichen.
Bezüglich std::move muss ich mich noch einmal einlesen, ich danke dir also für den Hinweis!
Wie schon andere erwähnt haben, kannst du dir von einem std::vector-Objekt auch einen C-Array-Pointer geben lassen, wenn du den tatsächlich benötigen solltest (std::sort braucht den nicht).
Mit std::move kannst du im Prinzip nur den internen Pointer auf das Array weiterreichen (ohne den gesamten std::vector kopieren zu müssen). Das ist so effizient wie einen rohen Pointer zu übergeben, allerdings mit dem Vorteil, dass das Ganze im std::vector mit seinem sauberen Interface verpackt bleibt (kein manuelles delete und sowas).
@Finnegan sagte in An std::thread übergebenen Raw-Pointer löschen:
Welches Problem möchtest du eigentlich mit der Sortierung lösen?
Jetzt kommt die Besonderheit von SFML:
SFML kennt VertexArrays, mit denen ich ausgehend von einer gemeinsamen Mitte (der Lichtquelle) Dreiecke erstellen kann, die alle an dieser Mitte hängen. Es ist wie bei Kreisen, die wie geschnittene Pizzen aus Triangles bestehen.
Schon verstanden, dein Problem. Triangle Fan.
Ich kann es umsetzen, aber mir ist die Performance sehr wichtig. Je besser dieses Lichtsystem läuft, desto weniger Einschränkungen habe ich an anderen Stellen. Da ich einen 144-Hertz-Monitor habe, bin ich ebenfalls etwas fps-geschädigt und hätte gerne den besten Weg, auch wenn ich weiß, dass ich möglicherweise noch nicht die beste Richtung eingeschlagen habe. Ich bin sehr bereit, weite Teile zu verwerfen, wenn mir etwas Besseres aufgezeigt wird.
Ich denke, dass du die Leistungsfähigkeit moderner Computer unterschätzt. Doom 2 von 1994 hat z.B. ein ähnliches Verfahren verwendet um die Wände zu rendern. Und zwar mit einem Strahl für jede Pixelspalte. Das war selbst auf den Computern vor 26 Jahren schon ziemlich flott (auch wenn natürlich John Carmack ziemlich brilliant war, was gerade solche Optimierungen in Spielen anging). Da würde ich mir keinen allzu grossen Kopf drum machen. Für die paar Vertices und Lichtquellen die du in solchen 2D-Szenen wie in der von dir verlinkten Demo hast, wirst du da keinen Unterschied bemerken, wenn du da nicht etwas super-ineffizientes programmierst. Premature Optimization und so.
Ich würde an der Stelle erst dann optimieren, wenn die Framerate tatsächlich zum Problem werden sollte. Dann weisst du auch besser, wo dein Code tatsächlich Performance-Probleme hat, und ich wette, dass es nicht der Sortieralgorithmus sein wird. Da wirst du dann lieber solche Optimierungen machen wollen wie z.B. diese Berechnung nicht 144 mal pro Sekunde durchzuführen, sondern z.B. nur dann, wenn z.B. eine Lichtquelle oder eine Wand bewegt wurde (nur dann ändert sich auch die Geometrie deines Triangle Fan) oder auch nicht mit allen Vertices für alle Lichtquellen, sondern nur in einem gewissen Falloff-Bereich des Lichtes. Licht reicht zwar physikalisch ewig weit, aber für praktische Computergrafik wird es ab einer gewissen Entfernung so schwach, dass man einfach sagen kann, dass der Lichtkegel da zuende ist - also alle Vertices nicht mit in die Berechnung einbezieht, die außerhalb des maximalen Ausbreitungsbereichs des Lichtes liegen.
Ich würde gerne die GPU einbeziehen, habe dort angefangen zu lesen und habe das mit mehr Aufwand assoziiert. Vielleicht täusche ich mich. Das Lichtsystem sollte bis spätestens Ende des Monats stehen, lieber früher, damit ich nicht in Verzug gerate. Ich muss zugeben, dass ich die Sorge habe, mit GPU-Berechnungen zu viel Aufwand zu betreiben, welchen ich bereuen könnte.
Ja, wenn du das noch nie gemacht hast und unter Zeitdruck stehst, dann mach besser erstmal mit deiner derzeitigen Idee weiter.
Die Anzahl der Lichtquellen ist noch die große Frage. Ich wollte eigentlich mehrere einzelne Lichtquellen zu einer zusammenschließen, um die Schatten smooth zu bekommen, aber der aktuelle Ansatz ist dafür ungeeignet, da nach wie vor zu rechenintensiv. Es fehlen noch die Schnittpunktberechnungen und Spiellogik ist ebenfalls nicht implementiert.
Bei wahrscheinlich übertriebenen 2000 Vertices und 12 Lichtquellen bin ich bei 37 fps (4770k@4,4GHz (4/8C), GTX 1070, Windows).
700 Vertices, 8 Lichter machen 87 fps.
100 Vertices, 50 Lichter machen 31 fps.
Das ist mit deinem aktuellen Code gemessen? Da würde ich mal genau untersuchen, woran das liegt. 2000 Vertices und 12 Lichter macht 24.000 Vertex-Licht-Paare, sehe ich das richtig? 24.000 Einträge mit sowas wie std::sort zu sortieren ist eigentlich fast nix. Mich wundert, dass du da nur auf 31 fps kommst. Geh dem mal genauer auf den Grund (Profiler und so).
Ansonsten schau nochmal was ich oben beschrieben habe: Du must die Lichtausbreitungs-Geometrie für eine Lichtquelle nur dann neu berechnen, wenn sich auch deren Position oder eine der Wände verändert haben und nicht mit jedem Frame. Und bedenke, dass das Licht ab einer gewissen Entfernung so schwach ist, dass es "praktisch nicht mehr da ist". Schau auch, ob das Problem nicht eher beim Rendering selbst liegt und die Funktionen, mit denen du die Szene zeichnest, vielleicht nicht die effizientesten für deinen Anwendungsfall sind.
