ich muss zur Zeit für die Uni als Projekt einen kleinen Raytracer schreiben. Um den zu beschleunigen will ich jetzt die Geometrie in Bäume aufteilen, damit ich nicht BruteForce jeden Strahl mit jedem Objekt/Dreieck testen muss.
Nun habe ich allerdings das Problem, dass ich die Vorlesung "Algorithmen und Datenstrukturen" leider erst im kommenden Wintersemester hören werde, und bräuchte aber eine kurze Auffrischung im Thema Bäume.
Wenn ich das richtig überlege, wäre es sinnvoll, den Raum so aufzuteilen, dass möglichst immer die Hälfte der Objekte im einen Teil, die andere Hälfte im anderen Teil sind.
- Ein Octree teilt ja immer den Raum in 8 gleich große Würfel auf und ist daher meiner Meinung nach nicht optimal.
- Ein k-d-Baum ist in der Hinsicht schon besser, da werden die Hyperebenen ja immer so gewählt, dass diese Bedingung möglichst gut erfüllt ist.
- Allerdings gibts da ja auch noch die BSP-Bäume, die - sofern ich das richtig verstanden habe - gleich sind wie die k-d-Bäume mit dem Unterschied, dass hierbei die Hyperebenen nicht mehr an den Achsen ausgerichtet sind, sondern frei im Raum liegen können.
Wenn ja, dann würde ich sagen, dass ein BSP-Baum am schwierigsten zu berechnen ist und zudem auch noch die Kollision mit einem Ausschnitt schwerer zu berechnen ist, da es eben kein schöner Würfel mehr ist. Allerdings würde ein BSP-Baum die Geometrie am optimalsten aufteilen (Wie auch immer man das dann berechnen kann, da hab ich mir noch keine Gedanken dazu gemacht)
Ein k-d-Baum teilt die Geometrie auch noch recht sinnvoll auf und ist auch recht einfach zu berechnen (Mittelpunkt aller Objekte berechnen und dann aufteilen) und außerdem ist die Kollision von Strahl mit einer Achsenorientierten Box ja auch kein Hexenwerk.
Von dem Gesichtspunkt her würde ich mich spontan für einen k-d-Baum entscheiden, lasse mich allerdings auch eines Besseren belehren (falls ich mir z.B. die Kollision eines Strahls mit einem nicht-würfelförmigen Ausschnitts schwerer vorstelle als es wirklich ist :) )
Daher würde ich euch bitten, mir mal eure Meinung oder Erfahrungen dazu zu sagen (bzw. zu schreiben), was auch im Hinblick auf die Schnelligkeit des Raytracers sinnvoller ist (eine bessere Aufteilung nutzt evtl. nichts, wenn die Kollisionsberechnung dann langsamer ist)
Grüße und Danke
hundvdf
