Hi!

Ich hatte vor einiger Zeit vor, einen kleinen Raytracer zu schreiben. Ich habe mich nun weiter dazu informiert (und auch in Sachen Vektorrechnung) und wollte loslegen. Ich frage mich aber schon die ganze Zeit und habe auch noch keine Antwort darauf gefunden, wie man den Schnitttest für komplexere Modelle macht, die sich nicht einfach aus geometrischen Grundformen zusammensetzen lassen. Mein erster Gedanke war es, das Modell in kleinere Ebenen zu unterteilen, aber das wäre wohl irgendwie am Sinn des Raytracings vorbei. Außerdem ist das mein kleiner Privatrechner, dem ich nicht elendlange Rechenzeiten zumuten will und auch nicht mehrere MB Plattenspeicher. Ich will ja nicht hochrealistische Bilder mit realistischen Szenen erzeugen (für die ja mehrere GB bzw. TBs durchaus realistisch wären), sondern es sollen einfache Szenen sein, die eben nur nicht gerastert aussehen sollen. (Hintergrund: eine Art 3d-Funktionsplotter). Nur wie stelle ich das am besten an?

Möglicherweise hat jemand ja sowas schonmal gemacht oder kennt sich in Computergrafik gut aus.

Für bekannte Objekte wie Kugeln oder Zylinder gibt es diverse Algorithmen, um diese zu testen. Komplexere Objekte wird man in der Regeln immer in (viele) Dreiecke zerlegen und diese testen.
Das tolle an Dreiecken ist, dass es hierzu relativ schnelle Algorithmen gibt und man das Objekt in Teilobjekte zerlegen kann, was das Rendern nochmals beschleunigt (Stichwort Octrees).

Ein schneller Algorithmus um Dreiecke zu testen, findet sich in diesem Paper:
Fast, Minimum Storage Ray/Triangle Intersection

Allerdings frage ich mich, wie du darauf kommst, dass man für Raytracing viel Festplattenspeicher braucht. Du brauchst nur so viel, wie dein Bild am Ende groß ist, im Zweifelsfall (BMP) sind das c.a. Breite(px)*Höhe(px)*3 Byte + Header.

Ich habs allerdings so gemacht, dass ich das Bild erst einmal rendere, eine Kantenerkennung drauf anwende und dann die Kanten noch einmal genauer rendere, um ein schönes Ergebnis in kurzer Zeit zu erreichen, die Ergebnisse wurden dann auf der Festplatte zwischengespeichert.

Die Szene ist nicht besonders hübsch, aber ich hab sie aus Reproduzierbarkeitsgründen so gemacht, um meine Kantenerkennung testen zu können (die noch Verbesserungs-bedürftig ist). Für schönere Ergebnisse würde man das komplette Bild einfach genauer rendern, was aber auch deutlich länger dauert.

F34r0fTh3D4rk hat folgendes geschrieben :

Allerdings frage ich mich, wie du darauf kommst, dass man für Raytracing viel Festplattenspeicher braucht. Du brauchst nur so viel, wie dein Bild am Ende groß ist, im Zweifelsfall (BMP) sind das c.a. Breite(px)*Höhe(px)*3 Byte + Header.

Ich bezog mich dabei nicht auf das gerenderte Bild, sondern auf die Szene selbst. Ich hatte übrigens schonmal die Idee, für jeden (Raum)bildpunkt abzuspeichern, ob er "solide" ist und welche Farbe er hat. 3Byte * Höhe * Breite * Tiefe waren da schon für mich astronomische Werte.

Wenn ich nun einen Plot von einer Größe 200px * 200px hätte, wären das zumindest ~200*200*2 = 80.000 Dreiecke. Ist eigentlich immernoch ganz schön viel. Zumindest zu viel, um einigermaßen interaktiv damit arbeiten zu können. Gibt es da nicht was einfacheres? Bilde mir ein, schonmal was davon gehört zu haben, dass es einen NURBS-Schnittpunkttest gibt?

Jakob_Ullmann hat folgendes geschrieben :

(Hintergrund: eine Art 3d-Funktionsplotter)

Wenn du eine durch eine Gleichung definierte Oberfläche, dafür aber keine direkte Methode zur Schnittpunktberechnung hast, müssen eben die bekannten Näherungsverfahren ran . Ich habe mal einen sehr einfachen Raytracer mithilfe der Bisektion gebaut. "Interaktives Arbeiten" dürfte damit aber ebenfalls kaum möglich sein.

"Bisektion" ist dann doch vergleichbar mit den Octrees, wenn ich das richtig verstanden habe. Aber zu nähern, wäre auf jeden Fall eine gute Option.

Dank euch für die Antworten!

Beide teilen in gewisser Weise den Raum auf, aber ich bin mir nicht sicher, was ein Octree bei einer einzigen kontinuierlichen Oberfläche helfen sollte. Außer du teilst diese eben in diskrete Elemente wie Dreiecke auf, dann kann ein im Voraus konstruierter Octree schon sinnvoll sein.
Bei meinem Raytracer habe ich aber überhaupt keine Struktur im Voraus aufgebaut, sondern hatte lediglich eine Funktion der Oberfläche f. Dann muss für jeden Strahl mit einer Funktion r (in Parameterform) nur noch f(r(t)) = 0 gelöst werden - eben durch Bisektion oder andere Verfahren. Definitiv das direkteste und am schnellsten implementierte Verfahren .

Ah, dann hatte ich dich erst falsch verstanden. Das ist echt eine Super-Idee! Danke!