Dual Contouring - Finden des Feature-Punkts, Normalen aus

9

Ich folge diesem Tutorial, um Dual Contouring zu implementieren: http://www.sandboxie.com/misc/isosurf/isosurfaces.html

Meine Datenquelle ist ein Raster 16x16x16; Ich durchquere dieses Gitter von unten nach oben, von links nach rechts, von nah nach fern.

Für jeden Index meines Rasters erstelle ich eine Würfelstruktur:

public Cube(int x, int y, int z, Func<int, int, int, IsoData> d, float isoLevel) {
            this.pos = new Vector3(x,y,z);
            //only create vertices need for edges
            Vector3[] v = new Vector3[4];
            v[0] = new Vector3 (x + 1, y + 1, z);
            v[1] = new Vector3 (x + 1, y, z + 1);
            v[2] = new Vector3 (x + 1, y + 1, z + 1);
            v[3] = new Vector3 (x, y + 1, z + 1);
            //create edges from vertices
            this.edges = new Edge[3];
            edges[0] = new Edge (v[1], v[2], d, isoLevel);
            edges[1] = new Edge (v[2], v[3], d, isoLevel);
            edges[2] = new Edge (v[0], v[2], d, isoLevel);
        }

Aufgrund der Art und Weise, wie ich das Gitter durchquere, muss ich nur 4 Eckpunkte und 3 Kanten betrachten. In diesem Bild entsprechen die Eckpunkte 2, 5, 6, 7 meinen Eckpunkten 0, 1, 2, 3 und die Kanten 5, 6, 10 meinen Kanten 0, 1, 2. Gitterwürfel

Eine Kante sieht so aus:

    public Edge(Vector3 p0, Vector3 p1, Func<int, int, int, IsoData> d, float isoLevel) {
        //get density values for edge vertices, save in vector , d = density function, data.z = isolevel 
        this.data = new Vector3(d ((int)p0.x, (int)p0.y, (int)p0.z).Value, d ((int)p1.x, (int)p1.y, (int)p1.z).Value, isoLevel);
        //get intersection point
        this.mid = LerpByDensity(p0,p1,data);
        //calculate normals by gradient of surface
        Vector3 n0 = new Vector3(d((int)(p0.x+1),   (int)p0.y,      (int)p0.z       ).Value - data.x,
                                 d((int)p0.x,       (int)(p0.y+1),  (int)p0.z       ).Value - data.x,
                                 d((int)p0.x,       (int)p0.y,      (int)(p0.z+1)   ).Value - data.x);

        Vector3 n1 = new Vector3(d((int)(p1.x+1),   (int)p1.y,      (int)p1.z       ).Value - data.y,
                                 d((int)p1.x,       (int)(p1.y+1),  (int)p1.z       ).Value - data.y,
                                 d((int)p1.x,       (int)p1.y,      (int)(p1.z+1)   ).Value - data.y);
        //calculate normal by averaging normal of edge vertices
        this.normal = LerpByDensity(n0,n1,data);
    }

Ich überprüfe dann alle Kanten auf einen Vorzeichenwechsel. Wenn es einen gibt, finde ich die umgebenden Würfel und erhalte den Merkmalspunkt dieser Würfel.

Wenn ich den Feature-Punkt auf die Würfelmitte setze, bekomme ich den blockigen Minecraft-Look. Aber das will ich nicht.

Um den Feature-Punkt zu finden, wollte ich es wie in diesem Beitrag tun: /gamedev//a/83757/49583

Grundsätzlich starten Sie den Scheitelpunkt in der Mitte der Zelle. Dann mitteln Sie alle vom Scheitelpunkt genommenen Vektoren zu jeder Ebene und verschieben den Scheitelpunkt entlang dieser Resultierenden. Wiederholen Sie diesen Schritt eine festgelegte Anzahl von Malen. Ich fand, dass sich eine Verschiebung von ~ 70% entlang der Resultierenden in der geringsten Anzahl von Iterationen stabilisieren würde.

Also habe ich eine Flugzeugklasse bekommen:

private class Plane {

        public Vector3 normal;
        public float distance;

        public Plane(Vector3 point, Vector3 normal) {
            this.normal = Vector3.Normalize(normal);
            this.distance = -Vector3.Dot(normal,point);
        }

        public float Distance(Vector3 point) {
            return Vector3.Dot(this.normal, point) + this.distance;
        }

        public Vector3 ShortestDistanceVector(Vector3 point) {
            return this.normal * Distance(point);
        }
 }

und eine Funktion, um den Feature-Punkt zu erhalten, an dem ich 3 Ebenen erstelle, eine für jede Kante und den Abstand zur Mitte mitteln:

 public Vector3 FeaturePoint {
            get {
                Vector3 c = Center;
 //                 return c; //minecraft style

                Plane p0 = new Plane(edges[0].mid,edges[0].normal);
                Plane p1 = new Plane(edges[1].mid,edges[1].normal);
                Plane p2 = new Plane(edges[2].mid,edges[2].normal);

                int iterations = 5;
                for(int i = 0; i < iterations; i++) {
                    Vector3 v0 = p0.ShortestDistanceVector(c);
                    Vector3 v1 = p1.ShortestDistanceVector(c);
                    Vector3 v2 = p2.ShortestDistanceVector(c);
                    Vector3 avg = (v0+v1+v2)/3;
                    c += avg * 0.7f;
                }

                return c;
            }
        }

Aber es funktioniert nicht, die Eckpunkte sind überall. Wo ist der Fehler? Kann ich die Kantennormale tatsächlich berechnen, indem ich die Normalen der Kantenscheitelpunkte mittle? Ich kann die Dichte am Randmittelpunkt nicht ermitteln, da ich nur ein ganzzahliges Raster als Datenquelle habe ...

Bearbeiten: Ich habe auch hier http://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html gefunden, dass ich Matrizen verwenden kann, um den Schnittpunkt der 3 Ebenen zu berechnen, zumindest habe ich das so verstanden Ich habe diese Methode erstellt

 public static Vector3 GetIntersection(Plane p0, Plane p1, Plane p2) {              
            Vector3 b = new Vector3(-p0.distance, -p1.distance, -p2.distance);

            Matrix4x4 A = new Matrix4x4 ();
            A.SetRow (0, new Vector4 (p0.normal.x, p0.normal.y, p0.normal.z, 0));
            A.SetRow (1, new Vector4 (p1.normal.x, p1.normal.y, p1.normal.z, 0));
            A.SetRow (2, new Vector4 (p2.normal.x, p2.normal.y, p2.normal.z, 0));
            A.SetRow (3, new Vector4 (0, 0, 0, 1));

            Matrix4x4 Ainv = Matrix4x4.Inverse(A);

            Vector3 result = Ainv * b;
            return result;
        }

welche mit diesen Daten

        Plane p0 = new Plane (new Vector3 (2, 0, 0), new Vector3 (1, 0, 0));
        Plane p1 = new Plane (new Vector3 (0, 2, 0), new Vector3 (0, 1, 0));
        Plane p2 = new Plane (new Vector3 (0, 0, 2), new Vector3 (0, 0, 1));

        Vector3 cq = Plane.GetIntersection (p0, p1, p2);

berechnet einen Schnittpunkt bei (2.0, 2.0, 2.0), also gehe ich davon aus, dass er korrekt funktioniert. Immer noch nicht die richtigen Eckpunkte. Ich denke wirklich, dass es meine Normalen sind.

ElDuderino
quelle
In Unity ist bereits eine PlaneStruktur definiert ( siehe hier ), in der die von Ihnen angegebenen Methoden bereits definiert sind (mit Ausnahme der kürzesten Vektormethode, die Sie Planemithilfe von C # -Erweiterungsmethoden zur Struktur hinzufügen können). Sie können die GetDistanceToPointMethode anstelle Ihrer DistanceMethode verwenden.
EvilTak
Vielen Dank für Ihren Kommentar. Ich habe meine Implementierung durch die Unity-Implementierung ersetzt und diese Funktion verwendet. Private Vector3 shortestDistanceVector (Ebene p, Vector3-Punkt) {return p.GetDistanceToPoint (Punkt) * p.normal; } Ich bekomme auch nur zufällige Eckpunkte. Ich vermute, meine Normalen sind völlig aus. Ich habe auch eine Bearbeitung hinzugefügt, in der ich eine zweite Methode ausprobiert habe. Vielleicht können Sie sie sich ansehen und mir sagen, was ich dort falsch gemacht habe.
ElDuderino
2
Can I actually calculate the edge normal by averaging the normal of the edge vertices?- Ich kann mich irren, aber ich glaube, ich habe anderswo Ratschläge gesehen, die besagen, niemals zu interpolieren, um Normalen zu erhalten - sie interpolieren einfach nicht gut. Berechnen Sie pro Gesicht, es ist sicherer. Wirklich, Sie sollten zuerst einen minimalen Testfall erstellen, um sicherzustellen, dass Ihre Normalenberechnung korrekt ist. Dann fahren Sie fort.
Ingenieur
Aber ich bekomme die Gesichter erst, nachdem ich die Normalen habe. Ich brauche die Normalen, um die Ebenen zu erstellen und die Eckpunkte für die Gesichter von ihnen zu erhalten. Und wie gesagt mit meiner aktuellen Struktur kann ich meine Daten nur an den Randscheitelpunkten indizieren. Oder über welche Gesichter sprichst du?
ElDuderino
@ElDuderino Gesichter wie Gesichter (oder Dreiecke) eines Netzes, aber ich weiß nicht, wie Sie das aus Ihren Daten erhalten können. Wenn Sie Dreiecke anstelle von Kanten erzeugen können, wird die normale Berechnung sehr einfach.
EvilTak

Antworten:

1

Zuallererst sollten Ihre Normalen völlig in Ordnung sein, wenn sie durch Vorwärts- / Rückwärts- / Zentralunterschiede berechnet werden. Das Problem ist, dass Sie Ihren Mittelpunkt in Ihrer FeaturePoint-Funktion in die falsche Richtung verschoben haben, was dazu führt, dass Sie sich weiter vom Minimum entfernen.

Vector3 c = Center;
Plane p0 = new Plane(edges[0].mid,edges[0].normal);
Plane p1 = new Plane(edges[1].mid,edges[1].normal);
Plane p2 = new Plane(edges[2].mid,edges[2].normal);

int iterations = 5;
for(int i = 0; i < iterations; i++) {
    Vector3 v0 = p0.GetDistanceToPoint(c) * edges[0].normal;
    Vector3 v1 = p1.GetDistanceToPoint(c) * edges[1].normal;
    Vector3 v2 = p2.GetDistanceToPoint(c) * edges[2].normal;
    Vector3 avg = (v0+v1+v2)/3;
    c -= avg * 0.7f; // Error was here!
}
return c;

Dies geschah, weil Ihr Code nicht gegen einen Punkt konvergiert und daher aus Ihrer Voxelbox springt. Ich weiß nicht, ob der Code von Kann jemand die doppelte Konturierung erklären? sollte einen Projektionsansatz verwenden, bei dem der Punkt auf die Ebene projiziert wird durch:

distance = Vector3.Dot(point - origin, normal);
projectedPoint = point - distance * normal;

aber es ist die gleiche Methode. Wenn Sie die Projektion in Ihren ursprünglichen Code umschreiben, führt dies zu:

    Vector3 v0 = c - p0.GetDistanceToPoint(c) * edges[0].normal;
    Vector3 v1 = c - p1.GetDistanceToPoint(c) * edges[1].normal;
    Vector3 v2 = c - p2.GetDistanceToPoint(c) * edges[2].normal;
    c = (v0+v1+v2)/3;

die umgeschrieben werden kann zu:

    Vector3 v0 = p0.GetDistanceToPoint(c) * edges[0].normal;
    Vector3 v1 = p1.GetDistanceToPoint(c) * edges[1].normal;
    Vector3 v2 = p2.GetDistanceToPoint(c) * edges[2].normal;
    c = c - (v0+v1+v2)/3;

und führen daher zum ersten Code. Indem Sie den Punkt auf drei nicht planare Ebenen projizieren, konvergiert er langsam gegen ein Minimum, da Sie den Abstand von jeder Ebene zu Ihrem Punkt minimieren, wie im Bild gezeigt.

Die roten Punkte bezeichnen den Merkmalspunkt, die blauen Linien die Normalen und der violette Punkt den auf die Ebene projizierten Punkt. Sie müssen den Faktor 0,7 auch nicht verwenden, da er ohne ihn schneller konvergieren sollte. Wenn Sie diese Methode verwenden, achten Sie darauf, dass der Algorithmus möglicherweise nicht funktioniert, wenn Sie nicht schneidende Ebenen haben.

Tim Rolff
quelle
Hey, großartig, nach 2 Jahren eine Antwort zu bekommen :) Ich habe nie eine Lösung gefunden, also habe ich dieses Projekt gestoppt, aber ich werde es mit diesem Wissen erneut besuchen und Sie wissen lassen, wie es gelaufen ist. Habe bis dahin eine +1.
ElDuderino
Genial! Ich bin froh, dass ich dir helfen konnte. Lassen Sie mich wissen, ob es für Sie funktioniert.
Tim Rolff