Dual Contouring - Menemukan titik fitur, normalnya nonaktif

Saya mengikuti tutorial ini untuk menerapkan Dual Contouring http://www.sandboxie.com/misc/isosurf/isosurfaces.html

Sumber data saya adalah kotak 16x16x16; Saya melintasi kotak ini dari bawah ke atas, kiri ke kanan, dekat jauh.

Untuk setiap indeks kisi saya, saya membuat struktur kubus:

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);
        }

Karena cara saya melintasi grid, saya hanya perlu melihat 4 simpul dan 3 ujung. Dalam gambar ini, simpul 2, 5, 6, 7 sesuai dengan simpul saya 0, 1, 2, 3, dan tepi 5, 6, 10 sesuai dengan tepi saya 0, 1, 2.

Tepi terlihat seperti ini:

    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);
    }

Saya kemudian memeriksa semua tepi untuk perubahan tanda, jika ada saya menemukan kubus sekitarnya dan mendapatkan titik fitur kubus tersebut.

Sekarang berfungsi jika saya mengatur titik fitur ke pusat kubus, saya kemudian mendapatkan tampilan minecraft gumpal. Tapi bukan itu yang saya inginkan.

Untuk menemukan titik fitur, saya ingin melakukannya seperti dalam posting ini: https://gamedev.stackexchange.com/a/83757/49583

Pada dasarnya, Anda memulai simpul di tengah sel. Kemudian Anda rata-rata semua vektor yang diambil dari titik ke setiap bidang dan pindahkan titik di sepanjang yang dihasilkan, dan ulangi langkah ini beberapa kali tetap. Saya menemukan memindahkannya ~ 70% di sepanjang hasilnya akan stabil dalam jumlah iterasi paling sedikit.

Jadi saya mendapat kelas Pesawat:

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);
        }
 }

dan fungsi untuk mendapatkan titik fitur, di mana saya membuat 3 pesawat, satu untuk setiap tepi dan rata-rata jarak ke pusat:

 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;
            }
        }

Tapi itu tidak berhasil, simpul ada di semua tempat. Di mana letak kesalahannya? Bisakah saya benar-benar menghitung tepi normal dengan rata-rata simpul normal tepi? Saya tidak bisa mendapatkan kepadatan di titik tengah tepi, karena saya hanya memiliki kisi integer sebagai sumber data ...

Sunting: Saya juga menemukan di sini http://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html bahwa saya dapat menggunakan matriks untuk menghitung persimpangan 3 pesawat, setidaknya begitulah cara saya memahaminya, jadi Saya membuat metode ini

 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;
        }

yang dengan data ini

        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);

menghitung persimpangan di (2.0, 2.0, 2.0), jadi saya menganggap itu berfungsi dengan benar. Namun, bukan simpul yang benar. Saya benar-benar berpikir itu adalah kebiasaan saya.

Pertama-tama normals Anda harus benar-benar baik jika mereka dihitung melalui perbedaan forward / backward / central. Masalahnya adalah, bahwa Anda memindahkan titik tengah Anda ke arah yang salah di fungsi FeaturePoint Anda yang mengakibatkan semakin jauh dari minimum.

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;

Ini terjadi karena kode Anda tidak bertemu titik dan karenanya melompat keluar dari kotak voxel Anda. Saya tidak tahu apakah kode dari Dapatkah seseorang menjelaskan pembentukan ganda? dimaksudkan untuk menggunakan pendekatan proyeksi di mana titik diproyeksikan ke pesawat melalui:

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

tetapi metode yang sama. Jika Anda menulis ulang proyeksi ke dalam kode asli Anda, ini menghasilkan:

    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;

yang dapat ditulis ulang untuk:

    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;

dan karena itu menghasilkan kode pertama. Dengan memproyeksikan titik pada tiga pesawat non planar, perlahan-lahan konvergen menuju minimum karena Anda meminimalkan jarak dari setiap pesawat ke titik Anda seperti yang ditunjukkan dalam gambar.

Titik merah menunjukkan titik fitur, garis biru normal dan titik ungu titik diproyeksikan di pesawat. Anda juga tidak perlu menggunakan faktor 0.7 karena itu akan bertemu lebih cepat tanpa itu. Jika Anda menggunakan metode ini berhati-hatilah, bahwa algoritme mungkin tidak berfungsi jika Anda memiliki pesawat yang tidak berpotongan.