Um ein paar neue Erfahrungen zu machen und um mal ein bischen anderen Wind drehen zu lassen, habe ich die letzten 4 Tage ein wenig gebastelt... Genauer: An einem Raytracer. Kugeln und Ebenen sind bislang eingebaut, aber das sollen durchaus noch mehr Objekte werden. Beleuchtung, Schatten und Reflexionen sind auch schon voll im Gange. Texturen in Form von Schachbrettern sind noch eher extrem basic und müssen überarbeitet werden - besonders die Texturkoordinatenerzeugung ist im wesentlichen noch nicht existent.

Momentane TODO-Liste:
* Einige Funktionen abstrahieren und verschönern
* einige seltsame Rechenungenauigkeiten genauer untersuchen
* Texturkoordinaten bestimmen, Bilder und Funktionen ermöglichen
* Anti-Alias Funktionalität
* Einige mehr Objekte ermöglichen.. Zylinder, Konus, allg. Quadratics, ...
* CSG Implementieren
* Weiche Schatten implementieren.
* Verteiltes rechnen.

Es ist also für den Anfang noch einiges zu tun. Da der Raytracer aber bereits fleißig traced, wollte ich euch ein erstes Bild nicht vorenthalten.

Heute habe ich mal wieder einige Kleinigkeiten am Raytracer programmiert:
* Einige Funktionen wurden gesäubert und so abstrahiert, so daß sie wiederverwertet werden können.
* Texturkoordinaten können nun für Kugeln berechnet werden
* Quadrics wurden implementiert - im Screen ist ein deformierter Zylinder zu sehen

So und wieder einmal sind ein paar programmierstunden eingegangen. Es hat sich folgendes getan:
* Anti-Aliasing wurde implementiert. Es stehen hierbei eine reihe verschiedener und verschieden schneller varianten zur Verfügung.
* Offene Schnittebenen haben ihren weg in den Code gefunden. Geschlossene werden noch kommen.
In der nächsten Zeit stehen dann ganz besonders auf der Wunschliste: Refraktion und Transparenz - im wesentlichen sollte hierzu bereits alles vorbereitet sein, aber man weis ja nicht, ob sich nicht doch noch irgendwo ein paar Fallen verstecken..

Eigentlich wollte ich mir mit meinem nächsten Post noch etwas zeit lassen - und eigentlich dachte ich, ich hätte ein paar Tage lang keine Zeit zum programmieren... Da hab ich wohl falsch gedacht Jedenfalls kam ich ein wenig dazu. Jedenfalls... Ich habe nicht das implementiert, was ich eigentlich vorhatte (Transparenz und Refraktion). Stattdessen bin ich auf die verrückte Idee gekommen, das Isosurface aus POV-Ray zu klauen (Warum sie so heißen ist mir völlig unklar. Es macht gar keinen Sinn und nur in POV-Ray heißen derartige Gebilde so. Eigentlich sind sie mir nur von POV bekannt). Also, um was handelt es sich:

An POV-Ray kann man im wesentlichen frei wählbare Volumenfunktionen übergeben, welche dann mit äusserstem Rechenaufwandt in ein Bild umgewandelt werden, indem die Nullstellen der Volumenfunktion gesucht wird. Da man aber nichts (man hofft stillschweigend, daß sie stetig, diffbar, halbwegs glatt und nur mäßig oszillieren) übder die Funktionen weiß, sucht man wild drauf los - es gibt im wesentlichen nur die Hau drauf Strategie - Einfach mal gucken, was die Funktion so macht und ablaufen. Das kostet dann massiv rechenzeit, aber man hat ja genug davon - bekommt das World-Community-Grid halt etwas weniger ab (Raytracer sind einfach parallelisierbar - ne Multicore System wäre jetzt nicht verkehrt Naja, dann muss man halt warten, bis das Bild fertig ist)
Das lustige aber ist, daß man in der Wahl der Funktion recht frei ist. Addiert man eine Noise-Funktion drauf, um die Oberfläche hubbelig wirken zu lassen? Warum nicht...

Klar... Jetzt könnte ich euch die Bilder vorenthalten oder euch nur erzählen, daß ich das gemacht hab und nirgends steht eine Zeile code... Ein paar kleine Bilder können ja nicht schaden Als Funktionen kamen ein paar einfache aus den POV-Ray Tutorias zum Einsatz - da weis man noch am ehesten, ob das, was man da programmiert hat, auch Sinn macht und ob das Ergebnis passt.


Verbunden werden beide Funktionen je nach Bild durch min(f1,f2), max(f1,f2), max(f1,-f2) . Das Rendern dauert erwartungsgemäß lange. Mit 5:1 Anti-Alias brauchten die Bilder in obiger Reihenfolge bei einer 800x600 Auflösung: 4:00min, 1:07min, 2:24min. Allerdings wurde die komplette Szene von oben gerendert, wobei die Quadrik durch die Isosurfaces ersetzt wurden. Hier die wesentlichen Ausschnitte:

Dumdidum... Das wichtigste Bild vorenthalten

Soso.. Schon wieder hat der Nico was Ich hab mich an einen Hype erinnert, der mal vor einiger Zeit um das Thema High Dynamic Range Rendering ausgebrochen ist. Spaßeshalber habe ich einmal die Helligkeit einer der Lampen in meiner Raytracer Scene nach oben gejagd, um zu sehen, was passiert... Ein gleißend heller überbelichteter Klecks Das ist natürlich sehr schade. Jedenfalls bin ich gestern in die Uni-Bibliothek gegangen und hab mir ein wenig Information zu Tone Correction reingezogen. Ein sehr interessantes Thema muss ich sagen. Ich dann gleich ein paar interessante Formeln abgeschrieben, um sie einzusetzen. Das Ergebnis dürft ihr jetzt bestaunen. Das Urspungsbild ist das mit dem hellen Klecks. Ein normiertes ist dabei (im wesentlichen unbrauchbar) und 2 die mit je einem Tone Correction Verfahren nachgebessert wurden. Man bekommt so erstaunlich viele Details zurück, ohne daß anderswo die Details übermäßig leiden. Vielleicht wäre eine Scene mit innen und Außenbereich effektvoller gewesen, aber man kann halt nicht alles haben und zum ausprobieren langt meine einfache Szene, wenn der Effekt dann auch statt "ui klasse" eher ein "aha... interessant" ist und man ihn ohne jeden Stress bereits durch anpassen der Lichtquellen erreicht hätte
Viel vergnügen.

Habe mal wieder für ein paar Kleinigkeiten an meinem Raytracer Zeit gehabt. Was ist passiert?
- Die numerische Stabilität einiger Rechnungen wurde durch geschickte Wahl der Rechenwege Teilweise deutlich erhöht
- Sehr einfaches Stochastisches Anti-Alias hat die einfache grid basierte Anti-Alias Funktionalität ersetzt. Noch hochwertigere Algorithmen dazu - insbesondere objektrand betreffende Funktionen - sind in Planung.
- Ein einfacher Bloom Effekt zum "überstrahlen" der Bilder ist hinzugekommen.
- "Normale" Zylinder haben ihren Weg in die verwendbare Geometrie gefunden.
- Die offenen Schnittebenen hatten, wie sich herausgestellt hatte, noch einen Schlag weg. Das wurde korrigiert. Dafür haben sie jetzt einen anderen in die andere Richtung. Bei Gelegenheit werde ich diesen Bug noch einmal genauer untersuchen.

Nun ist wieder ein wenig passiert. Endlich hat Transparenz + Refraktion einzug gefunden. Für die Transparenz fehlen jetzt noch Dielektrik-Eigenschaften (korrekte Anpassung der Brechungswinkel, wenn ein Mediumsübergang stattfindet). Inzwischen ist auch der Bug entdeckt worden, der verhindert hat, daß die offenen Schnittebenen nicht funktionieren - ein klitzekleiner Fehler, der dann auch bei der Transparenz böse zugeschlagen hat und für etwas Verwirrung sorgte. Jedenfalls ist das Problem jetzt beseitigt und auch in den aktuellen Bildern gibts deshalb angeschnittene Kugeln zu sehen. Und weil der Bloom einfach interessant ist, gibts heute den Bloom zusätzlich zum normalen Bild.
Für die Interessierten: Das Bild wurde mit 16:1 stochastischem AA gerendert, hat eine Auflösung von 600x450 und benötigte 2:32 min zur Berechnung. Das macht etwa 1776*16~28421 berechnete Pixel pro Sekunde.

So.. nocheinmal sind ein paar Zeilen Code enstanden. Was also ist hinzugekommen:
- Monte Carlo Anti-Alias
- Vereinfachtes Monte-Carlo AA
- Statistiken (zum aktuellen Bild hab ich eine hinzugegeben)
- Nichtperfekte Spiegelungen. Man beachte im Bild die blaue Kugel und die alles tragende Ebene.
- Bewegungsverwischen

Ein paar Worte möchte ich zum vereinfachten Monte Carlo AA sagen, da mir dieser besonders spannend erscheint und recht flott zu Werke geht. Was also macht dieser? Er rendert jedes Pixel durch zusammensetzen einer bestimmten Anzahl zufällig losgeworfener Strahlen. Stellt er fest, daß diese Strahlen sehr stark abweichende Farbwerte zurückbrachten, so wirft er weitere Strahlen in die Szene (wieder von einer bestimmten Anzahl) und verrechnet diese - sprich: An Objektkanten rechnet er besonders genau, falls er eine solche erkannt hat.

Statistiken für das Bild mit der Bewegung und den verwaschenen Spiegelungen. Anti Alias: (Vereinfachter MC 5+11)


Statistiken für das statische Bild (ohne Bewegung und ohne Verwischen von Spiegelungen). Anti Alias: (Vereinfachter MC 5+11)

Anmerkung zu den Statistiken:
"Avg. stoch. per i. pixel" steht für die durchschnittliche Zahl der strahlen, die für jeden Pixel des Bildes gestartet wurden. DIe variante mit den "rays" im Namen ganz entsprechend.

Nachdem Objekt-Blurring und Bewegungsunschärfe scheinbar kein großes Interesse hervorgerufen hat, versuche ich es wieder mit etwas neuem Diesmal hat die Constructive Solid Geometry das Licht der Welt erblickt. Es gibt nun die Möglichkeit, Objekte zu vereinigen und miteinander zu schneiden. Das ganze wird auf jedem berechneten Strahl auf Intervallbasis gemacht - wird also ein Objekt als CSG Objekt angewendet, so sollte es solide sein, sonst gibt es schnell ein lustiges durcheinander. Jedenfalls werden alle Schnitte mit einem Strahl in Intervalle Zerlegt (das klappt recht einfach, da die Objekte sowieso beim schneiden mit dem Strahl immer angeben, ob der Strahl sie nun nach innen oder nach aussen durchstossen hat und somit die Intervalle schnell zu identifizieren sind). Die Mengenoperationen auf den Intervallen sind jedoch denkbar einfach und CSG ist weniger kompliziert als ich anfangs befürchtet habe. Wie man Intervalle miteinander schneidet kann sich jeder mit einem Blatt Papier sehr leicht selbst überlegen, ich denke also nicht, daß man da viel zu sagen muss.
Eingebaut sind bislang Vereinigung und Differenz. Schnitt ist zwar im Gegensatz zu Differenz eine eher einfache Operation, dazu bin ich jedoch noch nicht gekommen. Meinen CSG-Code will ich jedoch noch ein wenig umstrukturieren, da man um CSG auf beliebigen Objekten anwenden zu können, momentan noch 1-Methodige CSG-Hüllenobjekte benötigt, die die Objektschnitte in Intervalle zerlegen. Ich plane dies in das Basisobjekt umzulegen um dadurch diese seltsame Konstruktion wieder loszuwerden.
Zusätzlich sind noch eine Box hinzugekommen und es wurde ein Bug betreffend der normalen des Zylinders entfernt, der aber nur dann sichtbar wurde wenn man den Zylinder von der falschen seite Betrachtet - die glatte Unterseite erschient dann gebogen - ein etwas seltsamer Effekt, wenn er nicht erwünscht ist

Also noch zwei CSG Differenz Objekte, als Beweis im Bild: Links eine Kugel, aus die ein Zylinder herausgeschnitten wurde. Rechts eine Kugel, in der innen ein Zylinder herausgeschnitten wurde und diesem Objekt wurde danach wiederum links eine Box weggeschnitten, damit man auch sehen kann, daß die Kugel innen teilweise hohl ist.

Heute habe ich ein paar hübsche, bunte und verschiedenfarbige Bonbons auf meinen Schreibtisch gelegt und diese mit einem Weitwinkelobjektiv abfotografiert.... Jedenfalls war das das, was ich als erstes gedacht habe, als mein Raytracer nach 7:21min mit einem Bild fertig war (eigentlich hab ich es schon vorher einmal gesehen: nach etwa 30 Sekunden, jedoch ohne AA): Eine Reihe verschieden parametrisierter Superellipsoiden - numerisch gelöst, weswegen es ein wenig gedauert hat. Ein bischen Sorgen bereitet mir noch die Rechenungenauigkeit, weshalb Schatten und Spiegelungen erst noch auf der Wartebank sind, aber das Bild ist dennoch höchst interessant. Was also sind Superellipsoiden? Man sucht die Nullstellen der Folgenden Funktion:

mit den Parametern e,n nicht zu groß und nicht zu klein.
Numerisch gelöst wird, indem man den Elipsoiden durch 9 Ebenen zerteilt und auf den Teilintervallen von Strahl/Ebenenschnittpunkt zu Strahl/Ebenenschnittpunkt sucht man dann per Bisektion oder Newton-Verfahren nach den Nullstellen.

Wenn man das halbwegs richtig macht, bekommt man Objekte wie im Bild unten. Ausserdem hab ich euch noch ein kleines CSG-Schmankerl beigelegt. Inspiriert von der CSG-Seite auf Wikipedia, habe ich das Objekt dort nachgebaut. Hat ganz gut geklappt. Das ist dann übrigens gleichbedeutetnd damit, daß der Raytracer nun auch Objekte miteinander schneiden kann - die CSG-Implementation jetzt also im wesentlichen fertig ist.

edit: Das Problem mit den Schatten udn Reflexionen wurde gelöst. Ein kleiner Trick mit mindesttoleranzen beim Start auf der Elipsoidoberfläche und schon klappts wunderbar.

Besonders viele Antworten gebt ihr ja leider nicht auf meinen schönen Raytracer... Naja, kommt vielleicht noch oder wieder.... Jedenfalls möchte ich euch weiterhin etwas kleinschrittig auf dem laufenden halten. Zu Testzwecken wurden ein paar weitere Raytracer aus der Basis-Tracerklasse abgeleitet: Ein Tiefentracer und ein Normalentracer (siehe Bild). Zusärtlich haben die Superellipsoiden jetzt auch die Möglichkeit bekommen, als CSG verwendet zu werden. Ich werde mich bemühen, selbiges auch für die Isosurfaces zu implementieren (bedeutet: Neue Klasse: Numerical-Solvers in der die Gemeinsamen Operationen zusammengeflickt werden können und so massiv redundadnder Code vermieden wird.)

Diesmal sind ein paar unsichtbare Änderungen eingegangen. Es hat sich folgendes getan:
Die Szene wird nun per Octree in Teile zerlegt, so daß ein schnellerer Test möglich ist, der überprüft, ob ein Strahl ein Objekt überhaupt treffen kann. In einer deutlich aufgefüllten Szenerie mit massiver Reflexion, wobei aber die meisten Objekte im sichtbaren Bereich liegen und auch teilweise sichtbar sind, hat sich dabei folgender Schub ergeben:
Brute-Force: Alles abtesten: 2:53
Subdivision bis max. Rekursion 5. Unendlichdimensionierte (und sich bewegende) Objekte zuletzt: 2:05
Subdivision bis max. Rekursion 5. Unendlichdimensionierte (und sich bewegende) Objekte zuerst: 1:58

Die sich bewegenden sind in Klammern, da es in dieser Szene keine gab, aber der Subdivisions-Algorithmus ist entsprechend so ausgelegt, daß sie sich wie unendliche Objekte verhalten.

Erweitert man die Szene noch um eine weitere große Menge an Objekte, die aber hinter der Kamera liegen und so nur klein in Reflexionen auftauchen, ergibt sich:
Brute Force: 5:05
Subdiv. 5 Unendliche zuerst: 2:17

Der Brute-Force Ansatz geht hier also wie zu erwarten war, sehr deutlich in die Knie. Sind dagegen sehr wenige Objekte im Bild, erzeugt der Subdivisions-Algo einiges an Overhead. Ein Abschalten ist dann möglich, aber bei den dann sowieso recht kurzen Renderzeit meist eh nicht nötig.

Noch eine kleine Anmerkung zur Implementierung: Der Algorithmus arbeitet mit AABBs. Transformierte Objekte werden möglichst platzsparend nach allen Transformationen mit einer AABB umhült. Es werden alle unendlich großen und sich bewegenden Objekte gesondert behandelt. Der Zugriff auf die Objekte, die vom Subdivisionsalgorithmus verwaltet werden, verhält sich nach aussen wie ein Stapel, man kann also nach belieben immer wieder Objekte aus dem nähesten noch nicht abgegangenem Blatt herausnehmen. Sind in der Box keine Objekte mehr, so wird die nächste Box genommen und ggf. bis zu ihren Blättern zerlegt. Zwischenzeitlich kann es passieren, daß bereits bekannt ist, daß eine Intersektion mit dem Strahl nur noch auf einem kleineren Intervall möglich ist. Beim holen der nächsten Box werden dann alle Boxen die sich auf der Liste der noch nicht abgearbeiteten Boxen befinden und zu weit entfernt liegen, herausgeworfen.
Dadurch daß sich der Algorithmus nach aussen wie ein Stack zum herunternehmen verhält, musste am eigentlichen Ray-Tracing Algorithmus nur die Schleife, die durch alle Objekte geht, angepasst werden. Der Brute-Force-Algorithmus wurde dann entsprechend in ein Objekt verwandelt, der sich nach aussen wie der Subdivisions-Algo benutzen lässt, aber einfach alle Objekte der Reihe nach zur Verfügung stellt.

Diesmal gibt es wieder sichtbare Änderungen. Ich hab mich noch ein wenig weiter mit Impliziten Flächen beschäftigt und insebsonders solche betrachtet, die Lipschitzstetige Volumenfunktionen besitzen. Diese lassen sich relativ flott rendern, wobei flott recht relativ ist. Jedenfalls, je kleiner die Lipschitzkonstante ist, d.h. die Maximale Steigung der Funktion, desto schneller arbeitet der Algorithmus (Noch eine Anmerkung: Der Algorithmus ist dann schnell, wenn die L-Konstante klein und die Funktionswerte groß sind. Es bringt allerdings nichts, die L-Konstante durch Division klein zu machen, weil die Funktionswerte so natürlich auch kleiner werden: nichts gewonnen). Die Impliziten Funktionen pakt man dann in etwas, das sich Blobtree net, auf den man Operationen wie verdrehen, biegen, rotieren, strecken, anschmiegen, vereinigen, schnitt, o.ä. anwenden kann. Einige dieser Funktionen verhalten sich jedoch so, daß sie die L-Konstante deutlich vergrößern und die Sache dadurch deutlich langsamer wird. Bislang sind implementiert: Verdrehen, (Rotieren, Strecken sowieso, weil da musste man nur die im Raytracer vorhandenen Funktionen für wiedereinsetzen) und als vordefinierte implizite Objekte Tori und Kugeln. Es gibt also noch viel auszuprobieren. Bislang kann der Algorithmus auch nur mit dem ersten Treffern von aussen zusammen arbeiten, transparenz ist so noch nicht möglich. Die Änderung dazu ist jedoch minimal. Braucht man aber für CSG von aussen alle Schnittpunkte (also wenn man nicht implizite Objekte mit impliziten verwurstet), muss ein anderer Algo zum Einsatz, etwa der der Isosurfaces. Soweit habe ich die Sache aber noch nicht zusammengesetzt.
Als kleines Schmankerl noch ein verdrehter, impliziter Torus:

Eigentlich hatte ich ja vor, noch ein wenig mehr am Blobtree zu arbeiten, bis ich dazu wieder mehr. Dummerweise habe ich dabei ein Bild erzeugt, daß ich einfach interessant fand und euch deshalb auch nicht vorenthalten will, auch wenn es eigentlich früher als geplant ist.
Also erkläre ich zuerst die paar Änderungen:
* Der Raytracer kann jetzt lokale Farben anzeigen: Es ist ja durchaus möglich, daß ein Objekt lokal eine Farbe zugewiesen hat, die sich im Verlaufe des Objektes ändert und nicht konstant bleibt (wir reden hier nicht über Texturen, sondern tatsächlich über lokale Farben. Unter OpenGl kann man das auch mit glColor und SecondaryColor erreichen, selbst wenn Texturing aktiviert ist). Das ist besonders bei Impliziten Manigfaltigkeiten oder Handgemodelten Objekten sehr naheliegend und ist nun möglich und wird durch zusätzlichen Übergabe der lokalen Farbe in die Strahl-Schnitt-Eigenschaften erreicht.
* abgerundete Zylinder sind als Blob-Objekt hinzugekommen
* das Ineinanderblenden von Objekten ist nun möglich. Es stehen eine Reihe Blendoperationen zur Auswahl, die interessanteste ist dabei jedoch Superelliptisches Blending (hat tatsächlich was mit den Superellipsoiden zu tun ).
Die Blendfunktion ist hier: 1- Summe(i, Max(0,1-Fi(x))^n)^(1/n); Was man durchaus mit der Oberen Funktion in Verbindung bringen kann. Hier wird n jedoch integer, positiv und ungerade gewählt. Ein paar weitere Blendingverfahren sind noch in der Warteschleife

Ausserdem wurde ich wieder daran erinnert, warum man Schwarz und Weiß niemals als Hintergrundfarbe bei einem unfertigen Grafikprogramm verwenden sollte: Man übersieht zu leicht Fehler. Ich war doch ein wenig verwirrt, als plötzlich glanzlichter in der Szene auftauchten, wo eigentlich gar keine Objekte hätten sein dürfen - und tatsächlich waren wirklich nur ein paar isolierte Glanzlichter zu sehen

Zum Bild: Es wurden 4 Zylinder Superelliptisch ineinandergeblendet. Diese haben jeweils unterschiedliche Farben und überschneiden sich leicht. Die Farben der Zylinder gehen so leicht in die benachbarten Zylinder über, der Abfall der Intensität ist dabei jedoch exponentiell. Daneben sind die Zylinder auch nach dem Twist zu sehen - was eigentlich das spannendere Bild-Element ist. Das Bild dauerte 17:33 min zum Rendern. Mit deaktiviertem AA dauert der Spaß freundlicherweise nur < 1 Minute, man hat also nicht zwangsweise das Gefühl, daß nichts mehr passiert und kann auch "mal schnell" sehen, ob die neuen Einstellungen und Codezeilen so halbwegs sinnvoll sind. Beschränkt man sich dann auf eine der Darstellungen, also normal oder verdreht, dann geht es noch um einiges flotter und man ist beim Programmieren nicht nur damit beschäftigt, auf die Maschiene zu warten.