Fragen Sie nach Ressource über schnelle Raytracing-Algorithmus

Question

Zuerst tue mir leid für diese grobe Frage, aber ich will nicht zu viele Details vorstellen, so frage ich nur für verwandte Ressourcen wie Artikel , Bibliotheken oder Tipps .

Ihr Programm benötigt intensive Berechnung ray-Dreieck Kreuzung zu tun (es gibt Millionen von Strahlen und Dreiecken), und mein Ziel ist es, so schnell zu machen, wie ich kann.

Was ich getan habe ist:

1. die schnellste ray-Dreieck Algorithmus, die ich kenne.

2. Mit Octree. (Von Game Programming Gem 1, 4.10. 4.11)

3. Verwenden Sie Eine effiziente und robuste Ray-Box Kreuzung Algorithmus , die in Octree-Algorithmus verwendet wird.

Es ist schneller als bevor ich diese besseren Algorithmen angewandt, aber ich glaube, es könnte schneller sein, könnten Sie bitte Lichter an allen möglichen Orten Schuppen, die es schneller machen könnten?

Danke.

Answer 1

Der Ort, um diese Fragen zu stellen ist ompf2.com . Ein Forum mit Themen über Echtzeit (obwohl auch Nicht-Echtzeit) Raytracing

Answer 2

OMPF Forum ist der richtige Ort für diese Frage, aber da bin ich heute hier ...

Sie eine Kreuzung nicht für Octtree Traversal verwenden ray / Box. Sie können es für den Wurzelknoten des Baumes verwenden, aber das ist es. Nachdem Sie den Abstand zum Eintritt und Austritt des Wurzelfeldes kennen, kann man die Abstände zu den x, y, und z Trennebenen ermitteln - die Ebene, die die Box unterteilen. Ist der Abstand nach vorne und die Rückseite sind f und b jeweils dann kann man bestimmen, welche Kindknoten der Box durch die Analyse von f getroffen werden, b, x, y, z Entfernungen. Sie können auch die Reihenfolge bestimmen, die untergeordneten Knoten zu durchlaufen und vollständig viele von diesen zurückweisen.

Bei den meisten 4 der Kinder getroffen werden kann, da der Strahl in einem Oktanten beginnt und ändert nur Oktanten, wenn es durchquert eine der drei Trennebenen.

Da es auch rekursiv wird Sie die Eintritts- und Austrittswege für die untergeordneten Knoten werden müssen. Diese Abstände werden ausgewählt aus der Reihe (f, b, x, y, z), die Sie bereits berechnet.

Ich habe für eine sehr lange Zeit die Optimierung dieser und kann sicher sagen, Sie über eine Größenordnung Leistung noch auf dem Tisch für Bäume viele Ebenen tief. Ich begann genau dort, wo Sie jetzt sind.

Answer 3

Es gibt mehrere Optimierungen Sie tun können, aber alle von ihnen sind abhängig von der genauen Domäne des Problems. Soweit allgemeine Algorithmen gehen, sind Sie auf dem richtigen Weg. In Abhängigkeit von der Domain, können Sie:

1. Einführung ein Portal-Systems
2. Verschieben Sie die Berechnungen auf einer GPU und nutzen parallele Berechnung
3. Ein ganz beliebter Trend in Raytracing vor kurzem ist Volume Bounding Hierarchies

Answer 4

Sie haben bereits einen guten Start mit einer räumlichen Art gepaart mit schnellen Schnittalgorithmen bekommen. Für Einzelstrahlen zu einem Zeitpunkt, Tracing, einer der besten Strukturen gibt (für statische Szenen) ist ein K-d-Baum der Fläche Heuristic gebaut werden.

Doch für wirklich High-Speed-Ray-Tracing benötigen Sie zu nutzen:

• Coherent Pakete von Strahlen
• Frusta
• SIMD

Ich würde vorschlagen, dass Sie mit „ Ray Tracing animierte Szenen mit Coherent Grid Traversal starten “. Es gibt einen leicht zu folgen Beispiel für einen solchen modernen Ansatz. Sie können auch die Referenzen folgen, um zu sehen, wie diese Ideen K-d Bäume und BVHS werden angewendet.

Auf der gleichen Seite, auch check out "State of the Art in Raytracing Animierte Szenen".

Eine weitere große Gruppe von Ressourcen sind alle SIGGRAPH Publikationen über die Jahre. Dies ist eine sehr wettbewerbsfähige Konferenz, so dass diese Papiere sind in der Regel erstklassig sein.

Schließlich, wenn Sie bereit sind, vorhandenen Code zu verwenden, aktivieren Sie das Projekt-Seite für OpenRT .

Answer 5

Eine nützliche Ressource, die ich gesehen habe, ist die Zeitschrift von Grafik-Tools . Je nach Ihren Szenen, könnte ein weiterer BVH besser geeignet sein als ein Octree.

Auch wenn Sie nicht auf Ihre Leistung mit einem Profiler ausgesehen haben, dann sollten Sie. Shark ist groß auf OSX, und ich habe gute Ergebnisse bekommt mit sehr schläfrig auf Fenster.