RayTracing Optimieren (Idee)

blub* 0

Hallo,

ich bin noch nicht wirklich in der Materie drin, kann also sein dass es das was mir eingefallen ist schon gibt. Wie auch immer, die Idee ist um jedes Objekt eine Kugel zu legen und im voraus über den Winkel zu prüfen ob sich der "Strahl" überhaupt mit dem Objekt schneiden kann.

1. Auf den Vektor der vom Pixel zur Kugelmitte geht einen Vektor konstruieren der rechtwinklig auf diesem steht
2. Die beiden Vektoren addieren
3. Punktprodukt der beiden Vektoren -> maximaler Winkel
4. Punktprodukt meines "Strahlvektors" mit dem Vektor vom Pixel zur Kugelmitte
5. Wenn das Ergebnis von 4. innerhalb des Ergebnisses von 3. liegt gibt es einen Schnittpunkt, ansonsten nicht

Tja, nun stellen sich mir noch zwei Fragen:
1. Funktioniert das überhaupt so?
2. Was haltet ihr davon?

Gruss,

Max

geloescht

Ja, das geht und ist weit verbreitet. "Bounding spheres" werden schon sehr lange zur Beschleunigung von ray tracing benutzt. Man kann auch nahe beieinander liegende bounding spheres mit einer weiteren Kugel umgeben und rekursiv so weiter machen. Dadurch entsteht dann eine Hierarchie aus bounding spheres. Persönlich finde ich sind Kugeln relativ ungünstige Objekte fürs bounding. kd-Trees sind einer Hierarchie aus Kugeln fast immer überlegen. Aber für einen einfachen ray tracer sind sie sicher besser als kein bounding.
Such einfach mal nach den Begriffen, die ich benutzt haben. Du wirst mit Tonnen von Material überschüttet werden (meist auf Englisch).
geloescht

blub* 0

Ok, dann werde ich mir wohl mal kd-Trees ansehen, danke dir.

*rant*

Abent^^

Ich habe genau das gemacht, allerdings flexibler, so dass man theoretisch beliebige Bounding Volumes - oder eigentlich müssen es noch nicht einmal Volumes sein - benutzen kann (allerdings war ich dann aber für andere Volumes als Kugeln zu faul :D). In manchen Situationen kannst du damit das Raytracing massiv verschnellern, in anderen hingegen wird es sogar langsamer, wenn du es falsch benutzt. Du musst halt einen Algorithmus finden, welcher dir die Einteilung einermassen sinnvoll vornimmt. Ansonsten aber kann ich es dir nur empfehlen

blub² schrieb:

Ok, dann werde ich mir wohl mal kd-Trees ansehen, danke dir.

Wenn du noch neu dabei bist, dann würde ich zuerst mal mit Bounding Spheres arbeiten. kd-Trees sind IMHO schon relativ komplex zu verstehen, gestalte lieber deine Architektur flexibel und fang mit den einfacheren Dingen an. Später kannst du das dann immer noch einbauen.

MfG

rapso

bounding boxen sind relativ nah am objekt (meistens jedenfalls) und haben noch einen relativ schnellen schnittest, sie lassen sich im gegensatz zu kugeln auch recht einfach erstellen (min und max in x y und z).

geloescht

Ich muss zugeben, dass einen _guten_ kd-tree zu erstellen ziemlich schwierig ist. Ihn zu durchlaufen ist meines Erachtens extrem elegant. Das gilt aber für alle hierarchischen Bounding-Systeme.
Für den Anfang ist es wahrscheinlich schonmal gut einfach für jedes Objekt ein bounding volume zu erstellen, Quader oder Kugel. Wobei ich den Schnittest für einen Quader relativ ätzend finde - zu viele ifs

-Foo-

Ein Mittelding wäre ein großes Gitter mit vllt 100x100x100 Kästchen. Dann sortierst alle dreiecke in alle Gitter-Quader ein, die von ihnen geschnitten werden. Nun musst du nur noch den ersten Gitter-Quader suchen, der vom Strahl getroffen wird. Von dort aus kannste dann ganz simpel durch das Gitter iterieren und musst nun nur die objekte in den durchwanderten Gitter-Quadern testen. Aber wenn du einen Punkt gefunden hast, musst du noch sicherstellen, dass er im Quader ist.
Das ganze ist denke ich einfacher zu implementieren als ein Kd-Tree, fand ich jedenfalls. Fällt auch unter die Kategorie spatial subdivide.
Ich hab das für meinen Raytracer benutzt : http://keller-delirium.de/~olli/mini-1.png

rapso

das wird sehr ineffizient wenn man grosse polys hat und diese dann in zig cellen einsortiert, hab so einen echtzeit raytracer gemacht, lief gut bis die grossen polys kamen
ne id oder sowas pro triangle kann man spaetestens vergessen wenn man mehrere threads laufen hat.

blub* 0

// blub
kann gelöscht werden

*rant*

$EDIT$ : Dieser Beitrag ist nicht mehr relevant, da der Vorposter seinen gelöscht hat

Hmmm sind denn die Normalvektoren auf Einheitslänge gebracht? Ich habe hier getNormal im Auge. Bei mir sieht das für die Kugel so aus:

inline vector<> sphere<>::normal_at(const vector<> &intersection) const
            {
                return vector<>::normalize(inv_rad * (intersection - position()));
            }

Ignorier bitte mal diese Default Templates

$EDIT$ :

// blub
kann gelöscht werden

Nun, da war er schneller...

MfG

blub* 0

Hmm... da lag der Fehler nicht, der Algorithmus ist auch genau gleich.

radius der Kugel * (Schnittpunkt - position der Kugel)

Naja, jetzt siehts immerhin so aus als würde es zumindest im Ansatz funktionieren aber mein Bild... naja... seht selbst:
http://img18.imageshack.us/img18/3790/testgae.jpg

Poste ich den Code halt doch nochmal :P:

if(foundObject != scene.getObjectsEnd())
    {
        Scene::LightIter lightIter = scene.getLightsBegin();

        Ray lightRay;
        lightRay.setOrigin(ray.getOrigin() + (ray.getDirection().getNormal() * distance));
        Vector3 primitiveNormal = (*foundObject)->getNormal(lightRay.getOrigin());

        while(lightIter != scene.getLightsEnd())
        {
            lightRay.setDirection(((*lightIter)->getPosition() - lightRay.getOrigin()));

            float dotProduct = (primitiveNormal * lightRay.getDirection().getNormal());
            if(dotProduct > 0) color += (*lightIter)->getColor() * (*foundObject)->getColor() * (*foundObject)->getMaterial().getDiffuse() * dotProduct;

            ++lightIter;
        }
    }

Naja, eventuell weiß ja jemand Rat, Danke schonmal & Gruss,

Max

#edit2: So, nochmal aktuellerer Code in dem ein paar Bugs schonmal raus sind. Irgendwo schleicht sich noch ein Fehler rum. Das Bild ist auch nochmal neu.