Contorno duplo - localizando o ponto de recurso, normal fora

9

Estou seguindo este tutorial para implementar o Dual Contouring http://www.sandboxie.com/misc/isosurf/isosurfaces.html

Minha fonte de dados é uma grade 16x16x16; Atravesso esta grade de baixo para cima, da esquerda para a direita, perto e longe.

Para cada índice da minha grade, eu crio uma estrutura de cubo:

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

Devido a como eu atravesso a grade, só preciso olhar para 4 vértices e 3 arestas. Nesta figura, os vértices 2, 5, 6, 7 correspondem aos meus vértices 0, 1, 2, 3 e as arestas 5, 6, 10 correspondem às minhas arestas 0, 1, 2. Cubo de grade

Uma aresta é assim:

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

Em seguida, verifico todas as arestas para uma mudança de sinal. Se houver, encontro os cubos ao redor e obtenho o ponto de recurso desses cubos.

Agora que funciona se eu definir o ponto de recurso para o centro do cubo, recebo a aparência de bloco minecraft. Mas não é isso que eu quero.

Para encontrar o ponto de recurso, eu queria fazê-lo como neste post: https://gamedev.stackexchange.com/a/83757/49583

Basicamente, você inicia o vértice no centro da célula. Em seguida, você calcula a média de todos os vetores retirados do vértice para cada plano e move o vértice ao longo do resultante e repita essa etapa um número fixo de vezes. Eu achei que movê-lo ~ 70% ao longo do resultante estabilizaria na menor quantidade de iterações.

Então, eu tenho uma aula de avião:

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

e uma função para obter o ponto de recurso, onde eu crio 3 planos, um para cada aresta e calculo a média da distância do centro:

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

Mas não está funcionando, os vértices estão por toda parte. Onde está o erro? Posso realmente calcular a aresta normal calculando a média do normal dos vértices da aresta? Não consigo obter a densidade no ponto médio da borda, pois só tenho uma grade inteira como fonte de dados ...

Edit: Eu também encontrei aqui http://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html que eu posso usar matrizes para calcular a interseção dos 3 planos, pelo menos é assim que eu entendi, então Eu criei esse método

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

que com esses dados

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

calcula uma interseção em (2.0, 2.0, 2.0), então suponho que funcione corretamente. Ainda assim, não os vértices corretos. Eu realmente acho que é o meu normal.

ElDuderino
fonte
O Unity já possui uma Planeestrutura definida ( veja aqui ), que possui os métodos que você definiu (exceto o método vetorial mais curto, que você pode adicionar à Planeestrutura usando métodos de extensão C #). Você pode usar o GetDistanceToPointmétodo em vez do seu Distancemétodo.
Maltak
Obrigado pelo seu comentário, substituí minha implementação pela implementação do Unity e usando esta função private Vector3 shortestDistanceVector (Plano p, ponto Vector3) {return p.GetDistanceToPoint (point) * p.normal; } Também recebo apenas vértices aleatórios. Eu suspeito que meus normais estão totalmente errados. Também adicionei uma edição, na qual tentei um segundo método, talvez você possa dar uma olhada e me dizer o que fiz de errado ali.
ElDuderino
2
Can I actually calculate the edge normal by averaging the normal of the edge vertices?- Posso estar enganado, mas acho que já vi conselhos em outros lugares dizendo para nunca interpolar para obter normais - eles simplesmente não interpolam bem. Calcule por face, é mais seguro. Realmente, você deve primeiro construir um caso de teste mínimo para garantir que seu cálculo de normais esteja correto. Então siga em frente.
Engenheiro de
Mas só obtenho as faces depois de ter as normais, preciso das normais para criar os planos e obter os vértices para as faces deles. E como dito na minha estrutura atual, posso indexar meus dados apenas nos vértices da aresta. Ou sobre quais rostos você está falando?
ElDuderino
@ElDuderino Faces como faces (ou triângulos) de uma malha, mas não sei como você pode obter isso com seus dados. Se você pode gerar triângulos em vez de arestas, o cálculo normal se torna realmente fácil.
EvilTak

Respostas:

1

Antes de tudo, seus normais devem ser totalmente bons se forem calculados através de diferenças de avanço / retrocesso / central. O problema é que você moveu o ponto central para a direção errada na função FeaturePoint, o que resulta em afastar-se do mínimo.

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;

Isso aconteceu porque seu código não converge em relação a um ponto e, portanto, sai da sua caixa de voxel. Não sei se o código de Alguém pode explicar o contorno duplo? foi projetado para usar uma abordagem de projeção em que o ponto é projetado no plano através de:

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

mas é o mesmo método. Se você reescrever a projeção no código original, isso resultará em:

    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;

que pode ser reescrito para:

    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;

e, portanto, resultar no primeiro código. Ao projetar o ponto em três planos não planos, ele converge lentamente para o mínimo, porque você minimiza a distância de cada plano ao seu ponto, como mostra a figura.

Os pontos vermelhos indicam o ponto de destaque, as linhas azuis as normais e o ponto roxo o ponto projetado no plano. Você também não precisa usar o fator 0,7, pois deve convergir mais rapidamente sem ele. Se você usar esse método, cuidado, que o algoritmo pode não estar funcionando se você tiver planos sem interseção.

Tim Rolff
fonte
Ei, incrível para obter uma resposta depois de 2 anos :) Eu nunca encontrei uma solução, então parei este projeto, mas vou revisitá-lo com esse conhecimento e informar como foi. Tenha um +1 até então.
ElDuderino 30/03
Impressionante! Estou feliz por poder ajudá-lo. Deixe-me saber se funciona para você.
Tim Rolff