Radiosity - Die Lichtenergie gerät bei zu geringen Abstand aus dem Ruder

XMAMan

Ich muss mich doch nochmal zu dem Thema zu Wort melden^^

Das Problem lag doch nicht an den Normalen. Ich habe mit Blender hier und da einzelnen Flächen mal so und mal so gedreht mit der Hoffnung, dass nun endlich der Blender-Exporter eine Datei erzeugt, wo alle Normalen nach außen zeigen. Dadurch ist es mir dann durch Zufall gelungen genau die beiden Patches, welche ein ganz geringen Abstand zueinander haben so zu drehen, dass sie voneinander wegzeigen.

Aber...

camper hatte ganz am Anfang der Diskusion noch ein wichtigen Punkt genannt, welchen ich nun nochmal aufgegriffen habe. Er sagte, dass wenn ich zwei große Flächen nah zueinander stelle, dann ist die Formel der Geometryterm-Berechnung von den Patchmittelpunkten zu ungenau. Er hatte recht damit.

Ich habe das jetzt so gemacht, dass wenn das Verhältnis zwischen Patch-Oberfläche zu Patch-Quadratdistanz einen bestimmten (Fehler)Wert überschreitet, dann verwende ich für die FormFaktor-Berechnung eine genauere Lösung. Da ich nicht genau wußte, wie man das Integral auf dem Papier lößt, habe ich es numerisch per Monte CarloIntegration gelößt. Es funktioniert sehr gut und das Bild sieht mit dieser Funktion nun so aus:

https://picload.org/view/rwgwolgw/ausgabe3.png.html

private void AddAllViewFaktorsWithSolidAngle(IPatch patch, Random rand)
{
    foreach (var otherPatch in this.patches)
    {
        if (patch == otherPatch) continue; //Keine Beleuchtung mit sich selbst
        if (otherPatch.IsLightSource) continue; //Lichtquellen dürfen nicht  beleuchtet werden

        float distanceSqrt = (patch.CenterOfGravity - otherPatch.CenterOfGravity).QuadratBetrag();
        //if (distanceSqrt <= 0.01f) continue; //Wenn der Abstand zwischen zwei Objekten zu gering ist, dann erhält man ein hohen ViewFaktor (Zahl >> 10), was dann dazu führt, dass mit jeden Beleuchtungsstep die Lichtenergie immer mehr wird
        Ray ray = new Ray(patch.CenterOfGravity, Vektor.Normiere(otherPatch.CenterOfGravity - patch.CenterOfGravity));

        float lambda1 = patch.Normale * ray.Direction;
        if (lambda1 <= 0) continue;
        float lambda2 = otherPatch.Normale * (-ray.Direction);
        if (lambda2 <= 0) continue;

        if (patch.IsLightSource && patch.IsInSpotDirection(otherPatch.CenterOfGravity) == false) continue; //Der andere liegt außerhalb meiens Spotcutoff

        int index1 = this.patches.IndexOf(patch);
        int index2 = this.patches.IndexOf(otherPatch);

        if (this.visibleMatrix[index1, index2] == VisibleValue.NotVisible) continue;
        if (this.visibleMatrix[index1, index2] == VisibleValue.NotSet)
        {
            var point = this.intersectionFinder.GetIntersectionPoint(ray, patch, 0);
            VisibleValue visibleTest = VisibleValue.Visible;
            if (point == null || point.IntersectedObject != otherPatch) visibleTest = VisibleValue.NotVisible;  //Sichtbarkeitstest

            this.visibleMatrix[index1, index2] = visibleTest;
            this.visibleMatrix[index2, index1] = visibleTest;

            if (visibleTest == VisibleValue.NotVisible) continue;

            //float lambda2 = point.Normale * (-ray.Direction);
            //if (lambda2 <= 0) continue;
        }

        float geometryTerm = lambda1 * lambda2 / distanceSqrt;

        float viewFactor = 1; //Diese Zahl soll später mal mit ein Rasterizer berechnet werden

        float formFaktorErrorValue = (patch.SurvaceArea + otherPatch.SurvaceArea) / distanceSqrt;

        float formFaktor;
        if (formFaktorErrorValue > 10) //Die 10 hängt von der Anzahl der Beleuchtungsschritte und der MaxSurfaceAreaPerPatch ab. Um so mehr Beleuchtungsschritte oder um so größer die MaxSurfaceAreaPerPatch ist, um so kleiner muss diese Zahl hier sein
        {
            formFaktor = GetFormfaktor(patch, otherPatch, rand); //Berechnet den Formfaktor genau, wenn eine Näherungslösung zu ungenau wird
        }
        else
        {
            formFaktor = geometryTerm * viewFactor * patch.SurvaceArea * otherPatch.SurvaceArea; //Das ist nur eine Näherungslösung
        }

        patch.AddViewFaktor(new ViewFaktor() { Patch = otherPatch, FormFaktor = formFaktor });
    }
}

//Berechnet numerisch das Doppelintegral, wo über alle alle Punkte aus Patch1 und Patch2 gegangen wird, und jeweils der GeometryTerm für dA1 udn dA2 berechnet wird
//Der FormFaktor, welcher hier beschrieben ist: https://de.wikipedia.org/wiki/Radiosity_(Computergrafik) enthält noch zusätzlich den VisibleTerm und / PI (Brdf)
//Brdf gehört für mich nicht zu diesen Term, da er sich nicht direkt auf die Strecke zwischen zwei Patches bezieht sondern auf ein Patch (Pfadumknickpunkt)
//VisibleTerm lasse ich aus Performancegründen weg
private float GetFormfaktor(IPatch patch1, IPatch patch2, Random rand)
{
    int sampleCount = 100;
    float geometryTermSum = 0;
    for (int i = 0; i < sampleCount; i++)
    {
        var point1 = patch1.GetRandomPointOnSurvace(rand);
        var point2 = patch2.GetRandomPointOnSurvace(rand);

        Vektor direction = point2.Position - point1.Position;
        float sqrtLength = direction.QuadratBetrag();
        direction /= (float)Math.Sqrt(sqrtLength);
        float lambda1 = patch1.Normale * direction;
        float lambda2 = patch2.Normale * (-direction);

        float geometryTermEstimation = lambda1 * lambda2 / sqrtLength * patch1.SurvaceArea * patch2.SurvaceArea;
        geometryTermSum += geometryTermEstimation;
    }

    return geometryTermSum / sampleCount;
}

Das Problem mit Blender habe ich jetzt noch nicht lösen können. Ich habe gestern die neuste Blenderversion installiert und der Wavefront(obj)-Exporter erzeugt weiterhin falsche Normalen. Das komische ist, dass er es nur für manche Objekte falsch macht. Die Lampen sind ok. Der Tisch oder der Schrank nicht. Dort muss ich die Normalen nach Innen zeigen lassen, damit sie im Export nach außen zeigen.

Ich werde versuchen mithilfe von ein globalen Beleuchtungsalgorithmus mir die 'wahren' Normalenrichtungen bestimmen zu lassen, um somit die fehlerhafte OBJ-Datei zu korrigieren.

rapso

Haette nicht gedacht, dass deine patches schon zu gross sind, aber da hatte camper ein gutes gespuer.

Wenn du soeinen fehler hast, ist eine andere integration nicht immer die beste loesung, da die patches dann weiterhin zu gross sind, du somit einem "mittelwert" hast, statt eine varianz ueber das ganze patch (du sendest also vielleicht weiterhin nicht die richtige menge energie an andere patches). Es ist deswegen gaengig die patches adaptiv zu tesselieren.

http://www.cs.utah.edu/~schmelze/radiosity/hw2/meshl1_lo.jpg

nicht nur wegen distanz, sondern auch bei varianz:
https://classes.soe.ucsc.edu/cmps161/Winter04/projects/aames/images/screen4.jpg

XMAMan

rapso schrieb:

Wenn du soeinen fehler hast, ist eine andere integration nicht immer die beste loesung, da die patches dann weiterhin zu gross sind, du somit einem "mittelwert" hast, statt eine varianz ueber das ganze patch (du sendest also vielleicht weiterhin nicht die richtige menge energie an andere patches).

Dieser Mittelwert konvergiert doch aber gegen den perfekten FormFaktor-Wert. Ich verwende hier jetzt zwar nur 100 Samples, aber um so höher die Zahl ist, um so mehr müsste es doch passen.

Um das Integral zu berechnen, nutze ich folgende Formel:

⟨FN⟩=1N∑i=0N−1f(Xi)pdf(Xi).

Jedes Sample berechnet den GeometryTerm zwischen den Differentialflächen dA1 und dA2. Die Wahrscheinlichkeitsdichte (Pdf A), dass ich einen von diesen Punkten generiere ist 1 / SurfaceArea. Wenn ich dann den GeometryTerm mit der PdfA diffidiere, dann ist dass das gleich wie die Multiplikation mit Patch-SurfaceArea.

Die Formel sieht jetzt erstmal genau so aus wie die Näherungsformel oben, aber es sind zweich verschiedene Sachen.

Hier wird ein bisschen auf das Thema eingegangen, wenn du es näher wissen willst:

http://www.scratchapixel.com/lessons/3d-basic-rendering/global-illumination-path-tracing

http://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/monte-carlo-integration?url=mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/monte-carlo-integration

Die Idee mit den adaptivren anpassen der Patchgröße habe ich woanders auch schon gesehen. Die Sache ist, ich will jetzt nicht mit Radiosity versuchen gegen mein Pathtracer oder andere Distributet Raytracing-Algorithmen anzukommen. Dafür ist Radiosity einfach zu schlecht. Mir ging es eher darum die Basis-Variante zu machen und zu akzeptieren, dass ich mir der begrenzten Patch-Größe eben auch nur so Mindcraft-Mäßige Bilder erzeugen kann. Ich find das so ok.

Bildfehler aufgrund von falschen Formfaktoren sind nicht ok. Pixeliges außsehen aufgrund der Patches ist ok.

rapso

XMAMan schrieb:

rapso schrieb:

Wenn du soeinen fehler hast, ist eine andere integration nicht immer die beste loesung, da die patches dann weiterhin zu gross sind, du somit einem "mittelwert" hast, statt eine varianz ueber das ganze patch (du sendest also vielleicht weiterhin nicht die richtige menge energie an andere patches).

Dieser Mittelwert konvergiert doch aber gegen den perfekten FormFaktor-Wert. Ich verwende hier jetzt zwar nur 100 Samples, aber um so höher die Zahl ist, um so mehr müsste es doch passen.

es konvergiert gegen den durchschnittswert, nicht gegen den perfekten wert, denn diesen einen wert gibt es eventuell nicht. Wenn z.b. 50% vom Patch direktes licht bekommt, 50% im schatten wird, wird das patch "grau".
Was erstmal "ok" klingt, du musst aber beachten, dass das patch wieder benutzt wird um fuer andere patches die energie einzuschaetzen, wenn also in einem bereich wo 100% reflektiert werden sollte nur 50% der energie weitergetragen wird, im schattenbereich wo 0% reflektiert werden sollte auch 50% weitergetragen wird, bekommst du eine falsche ausleuchtung.

Die tesselierung wird also nicht (nur) dem eigentlichen patch "zuliebe", sondern all den verbundenen patches "zuliebe" gemacht.

Die Sache ist, ich will jetzt nicht mit Radiosity versuchen gegen mein Pathtracer oder andere Distributet Raytracing-Algorithmen anzukommen. Dafür ist Radiosity einfach zu schlecht. Mir ging es eher darum die Basis-Variante zu machen und zu akzeptieren, dass ich mir der begrenzten Patch-Größe eben auch nur so Mindcraft-Mäßige Bilder erzeugen kann. Ich find das so ok.

Bildfehler aufgrund von falschen Formfaktoren sind nicht ok. Pixeliges außsehen aufgrund der Patches ist ok.

Radiosity wird, bzw wurde oft verwendet um daraus das eigentlich nuetzliche zu errechnen. Du kannst z.B. eine lightmap erstellen (indem du die patches direkt einzeichnest, oder eine art "final gathering" per texel in die radiosity patche traced). Das kannst du abspeichern und hast relativ echt beleuchtete echtzeit szenen.

Du kennst sicher:
http://i39.tinypic.com/11sgq39.jpg
https://image.slidesharecdn.com/henrikgdc09-compat-100210170437-phpapp01/95/the-unique-lighting-of-mirrors-edge-41-728.jpg?cb=1265822373
http://imgur.com/oN5kPe3

oder:
https://zigguratvertigodotcom.files.wordpress.com/2015/11/giunity.png

XMAMan

Hättest du ein Paper / Internetlink den ich durcharbeiten kann, um das Radiosity so umzubauen, dass ich damit härtere Schattenkanten hinbekomme? Also dieses Unterteilen der Patches im Abhängigkeit vom Irradiance-Gradienten?

Hab kein speziellen paper dazu im kopf, koennte nur das auflisten was google ausspuckt.

ich denke die offensichtlichen methoden sind:
1. wie du es schon gemacht hast, ueber die min-distanz zu gehen, sodass die kantenlaenge * faktor < minDistanz ist. (natuerlich mit einem min-limit, damit bei sich beruehrenden/schneidenden patches es nicht zuweit geht.
2. alternativ koenntest du in der mitte und an den raendern der patches paar samples nehmen und wenn dort die energie zu sehr variiert, unterteilst du das patch.
3. oder evaluierst wie kontrastreich benachbarte patches sind nach einem gather step und unterteilst die, die sehr variieren

XMAMan

Meine Idee wie man das machen könnte war bis jetzt die, dass ich zuerst mit normalen Raytracing und LightSourcesampling das direkte Licht für jeden Punkt, den der Primärstrahl sieht, berechne, um somit zu sehen, wo Schatten/Halbschatten oder keine Schatten sind.

In den Halbschatten unterteile ich dann genauer.

Nachteil von den Verfahren: Ich habe nur für den Kamera-Punkt die Patches genau unerteilt, wo ich halt wärend des Schattenberechnes die Kamera stehen habe. Wenn hinter mir Schatten sind, und ich will nach dem Radiosity mich in der Szene frei bewegen können, dann wäre das schlecht.

Zweite Idee: Ich unterteile die Szene erstmal grob in Patches. Für jedes Patch berechne ich an N zufällig gewählten Punkten die DirectLighting-Berechnung, wie es schon bei Idee 1 gemacht wird nur dass ich hier keine Kamera brauche. Ändert sich die Irradiance über alle N Punkte stark, dann wird das Patch rekursiv erneut so lange unterteil, bis die Änderungsrate zwischen den N Punkten unter ein Schwellwert fällt.

Was hällst du von den Ideen?

rapso

wenn du "zufall" nimmst, wirst du eine streuung haben und die kann deine entscheidungsfindung beeinflussen, ob du patches teilen solltest.
Du kannst eher als 4 subpatches ansehen und zu den zufaellig gewaehlten flaechen tracen, wenn die 4 dann variieren, nimmst du die tesselierung wirklich vor. (da ist auch noch streuung, aber die 4 sub-patches haben wenigstens eine relativ gleiche randomization.)

am ende wirst du wohl 10 versionen ausprobieren muessen bis du weisst, welche, wann gut ist. vermutlich musst du dann 2 oder 3 quellen fuer die entscheidungsfindung nehmen und sie gewichten.

XMAMan

Momentan ist mein Algorithmus so:

Ich suche erst die Patches raus, welche im Halbschatten liegen. Dazu bestimme ich für zufällige Punkte auf dem Patch, wie viel Prozent aller Schattenstrahltests erfolgreich sind. Ist es 0 oder 100%, dann liegt das Objekt nicht im Halbschatten. Ansonsten ja.

Dann berechen ich die Varianz über die Irradiance von diesen Punkten. Ist sie größer als 1, unterteile ich mehr.

Bei den Patches unter dem Stuhl sieht man, dass sie etwas kleiner sind, als z.B. an den Wänden.

https://img1.picload.org/image/rwdcrwwa/ausgabe.png

Das Bild ist etwas besser dadurch aber den Schatten vom Stuhlbein bekomme ich trotzdem noch nicht hin, da auch Bildstellen für weitere Unterteilungen markiert werden, die eigentlich ok aussehen. Ich habe aber nur eine begrenzte Anzahl an Patches, die ich erzeugen kann. Deswegen bleibt dann nicht genug Speicher übrig, um den Stuhlbeinschatten schön darzustellen.

rapso

wie kommt das limit zustande?

XMAMan

Ich muss ja dann für jeden Patch zu jeden anderen Patch die FormFaktor berechne. Wärend er diese Berechnung macht, wächst der Speicher von den Prozess immer weiter an, da es so viele Patche sind. Wenn ich überhaupt keine feinere Unterteilung mache, dann erhalte ich ja schon 10.000 Patche. Untereile ich dann nochmal einige von den Patches auf ein Zentel von ihrer Größe, dann bekomme ich beim FormFaktor-Erstellen eine OutOfMemoryExcepiton.

rapso

das ist natuerlich kein neues Problem, spare matrix

Ein paar tricks sind:
-jede Zeile Runlength encoden (da vieles 0 sein sollte), du arbeitest eh zeile fuer zeile ab. (ich empfehle 1 byte mit 4bit fuer wieviele 0 und 4bit fuer wieviele nicht-null folgen).
-quantifizierung (du suchst pro zeile den maximaln float raus und teilst durch den, legst dann jeden einzelwert als 0-255 oder 0-65525 ab)
-clustering: du merkst dir beim teilen der patches welche zusammengehoeren, wenn du dann dir formfaktoren errechnest (von anderen patches zu dem zerteilten) und die variieren nicht, legst du nur den wert zum haupt-patch ab.

XMAMan

rapso schrieb:

das ist natuerlich kein neues Problem, spare matrix

Ein paar tricks sind:
-jede Zeile Runlength encoden (da vieles 0 sein sollte), du arbeitest eh zeile fuer zeile ab. (ich empfehle 1 byte mit 4bit fuer wieviele 0 und 4bit fuer wieviele nicht-null folgen).
-quantifizierung (du suchst pro zeile den maximaln float raus und teilst durch den, legst dann jeden einzelwert als 0-255 oder 0-65525 ab)
-clustering: du merkst dir beim teilen der patches welche zusammengehoeren, wenn du dann dir formfaktoren errechnest (von anderen patches zu dem zerteilten) und die variieren nicht, legst du nur den wert zum haupt-patch ab.

Also ich speichere die Formfaktoren ja nicht in einer 2D-Matrix sondern jetztes Patch besitzt eine Liste von FormFaktoren:

class Patch
{
 public List<ViewFaktor> ViewFaktors { get; private set; }
}

class ViewFaktor
    {
        public Patch Patch;
        public float FormFaktor;
    }

In dieser Liste werden ja nur die ViewFaktor-Objekte gespeichert, wo der FormFaktor-Wert größer null ist. Ich verstehe jetzt also nicht, inwiefern mir die SpareMatrix-Sache hier weiter helfen kann.

Ich selbst sehe nur eine sinnvolle Lösung: Ich muss die Patches, welche ich weiter untereile weiter einschränken. Momentan sind es noch immer zu viele. Mich interessieren ja nur die Bereiche, wo es Schattenkanten zu sehen gibt.

rapso

Wieviel speicher kostet eine "verbindung" bei dir genau?

XMAMan

C# hat für Datentypen, dass Speicher vom GC verwaltet wird anscheinend kein sizeof-Operator. Wenn ich die Klasse serialisiere, dann erhalte ich 168 Byte. Vermutlich hat er die Patch-Klasse mit serialisiert obwohl sie ein Null-Pointer ist.

long size = 0;
            object o = new ViewFaktor();
            using (System.IO.Stream s = new System.IO.MemoryStream())
            {
                System.Runtime.Serialization.Formatters.Binary.BinaryFormatter formatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter();
                formatter.Serialize(s, o);
                size = s.Length; //->Hier sagt der Debugger 168 
            }

Mein zweiter Weg war über die GC.GetTotalMemmory-Funktion.

long s1 = GC.GetTotalMemory(false);
            ViewFaktor v = new ViewFaktor();
            string s5 = v.GetType().ToString();
            long s2 = GC.GetTotalMemory(false);
            long s3 = s2 - s1; //-> Hier sagt er 0 Byte
            string s4 = s1.ToString() + s2.ToString() + s3.ToString() + v.ToString() + s5;

Dabei kommt 0 Byte raus.

Das heißt meine Klasse brauch so zwischen 0 und 168 Byte^^ Das ist so peinlich, dass C# mit dieser simplen Sache überfordert ist.

Laut meiner Schätzung dürften es 8 Byte sein. Aber zwischen den einzelnen Memberm können noch speicherlöcher sein, so dass die Klasse gut auch doppelt so groß sein kann. Ich weiß es halt nicht genau.

Mit

System.Runtime.InteropServices.Marshal.SizeOf(typeof(ViewFaktor));

habe ich es übrigens auch schon versucht und bekomme da nur eine Execption, da das eine Manged-Class- ist.

vielleicht kannst du eine million verbindungen allokieren, so wie du es normalerweise machst, und die differenz aus vorher/nachher nehmen, notfalls im taskmanager.

mit einer matrix solltest du auf etwa 4-5byte pro verbindung kommen (RLE komprimiert).