G
Hallo,
für einen Raytracer (3D-Renderer, der die Ausbreitung des Lichts an geradlinigen Strahlen entlang simuliert) möchte ich CSG (Constructive Solid Geometry) verallgemeinern. Dazu trenne ich Körper, d.h. die Form eines Gegenstands, und Material, d.h. wie der Gegenstand aussieht. Nun möchte ich Regeln formulieren in der Form "wenn Punkt innerhalb von Körper X (bzw. andere Aussage über Punkte in Körpern), dann Punkt innerhalb von Material A". Neuere Regeln sollen alte Regeln überschreiben. Wenn ich nun einen Strahl zurückverfolge sehe ich für jeden Abschnitt, den der Strahl zwischen zwei Schnittpunkten mit Körpern in der Szene zurücklegt, nach, durch welches Material der Strahl geht. So weit so gut.
Ich brauche zum einen eine Datenstruktur über die ich schnell nachschauen kann, in welchem Material sich der Strahl bewegt, wenn er sich in bestimmten Körpern bewegt (also in die andere Richtung, in der die Regeln formuliert sind).
Außerdem muss ich die Regeln umformen so dass neuere Regeln alte überschreiben oder alternativ Widersprüche zu einem Fehler führen.
Ein Beispiel im zweidimensionalen Raum damit die Sache klarer wird:
Drei Formen, zwei Kreise(-inhalte) X und Y und eine Gerade (bzw. alles was auf der rechten Seite der Geraden liegt) Z.
Die Kreise überschneiden sich teilweise, die Gerade geht durch die Schnittpunkte der beiden Kreise.
Wenn ich nun die Regeln aufstelle: (A und B zwei Materialien, O ein nich sichtbares Material [Vakuum])
XYZ -> A (wenn in Kreis X und Kreis Y und auf rechter Seite von Z, dann in Material A)
XY(¬Z) -> B (wenn in Kreis X und Kreis Y und auf linker Seite von Z, dann Material
(¬A)^(¬B) -> O (ansonsten das Nicht-Material)
Dann hätte ich eine Art Linse die in der Mitte geteilt ist. Falls man sich das nicht vorstellen kann (verständlich) dann kann ich auch noch ein Bild produzieren.
Mir ist nun unklar wie ich solche Regeln verarbeiten und speichern kann. Eine Tabelle wäre schnell, aber gigantisch (2^Anzahl der Körper??). Die Regeln einfach so zu speichern und der Reihe nach abzuarbeiten (also Wahrheitswert überprüfen, speichern, nächste Regel usw.) wäre einfach, aber langsam.
Ich will das machen, weil der herkömmliche Objekt/CSG-Ansatz widersprüchlich (wie kann sich ein Punkt gleichzeitig in zwei Objekten befinden?) und problematisch (coincident surfaces ist ein Problem, das bedeutet, dass zwei Oberflächen sich genau an der selben Stelle befinden und deswegen zu Artefakten wegen der Ungenauigkeit von Gleitkommazahlen führen) ist. Außerdem wäre es nicht nötig, mehr Strahl-Körper-Schnittpunkte zu berechnen als nötig.
Vielleicht kann mir einer einen Hinweis geben, wie man logische Regeln effizient speichert, umformt und ausliest. Ich verwende C++.
geloescht