Performance Problem



  • Hi,

    wie ihr wisst, habe ich mir einen eigenen OBJ-Loader gebaut. Klappt auch alles uper jetzt. Aber es gibt ein Performance Problem bei der Normalenberechnung. Ich versuche die Normale von jeder Vertex zu berechnen, um die Normalen zu glätten. Klappt auch alles gut, nur brauch ich für ein Model mit gerade mal 17k Faces ungefähr 4-5 Minuten. Blender kann auch die Normalen berechnen, indem man auf den "Set Smooth"-Button klickt. Das geschieht aber im Bruchteil einer Sekunde. Wie macht Blender das, bzw. was mach ich schlecht/falsch?
    Hier ist die Methode, ich denke es erklärt sich von selbst.

    void model::generate_normals() {
            // Generate normals for each face
            for (register unsigned int i = 0; i < faces.size(); ++i) {
                vec3d a = faces.at(i).vertices.at(1).pos - faces.at(i).vertices.at(0).pos;
                vec3d b = faces.at(i).vertices.at(2).pos - faces.at(i).vertices.at(0).pos;
    
                faces.at(i).normal = a.cross(b);
                faces.at(i).normal.normalize();
            }
    
            // Generate normals for each vertex
            for (register unsigned int i = 0; i < faces.size(); ++i) { // For each face
                for (register unsigned int j = 0; j < faces.at(i).vertices.size(); ++j) { // For each vertice in that face
    
                    std::cout << "Generating normals for vertex " << j << " of " << faces.at(i).vertices.size() << " owned by face " << i << " of " << faces.size() << "." << std::endl;
    
                    // Locals
                    vec3d normal;
                    unsigned int count = 0;
    
                    for (register unsigned int k = 0; k < faces.size(); ++k) { // For each face
                        for (register unsigned int l = 0; l < faces.at(k).vertices.size(); ++l) { // For each vertice in that face
                            if (faces.at(k).vertices.at(l).pos == faces.at(i).vertices.at(j).pos) {
                                normal += faces.at(k).normal;
                                ++count;
                            }
                        }
                    }
    
                    normal /= static_cast<double>(count);
                    faces.at(i).vertices.at(j).normal = normal;
                }
            }
        }
    

    Danke schonmal

    EDIT: Ein kleiner Denkanstoß: Erst generiere ich die Normalen für jedes Face. Dann suche ich für jeden Vertex jedes Face, der auch dieses Vertex beinhaltet. Am Ende wird der Durchschnitt der Normale der Faces, die um dieses Vertex liegen, gebildet.



  • Mal so als Denkanstoß: du solltest nicht für jedes vertex die normale Berechnen, sondern mit jedem Face die Normalen seiner Vertices updaten.

    Als Pseudocode in etwa so:

    vec3d normalen[anzahl_vertices];
    int num[anzahl_vertices];
    
    für(alle faces f)
        für(alle vertices v von f)
            normalen[v.id]+=f.normal;
            num[v.id]++;
    
    für alle i=1...anzahl_vertices
        normalen[i]/=num[i];
    

    mans ieht sofort, dass du dir auf diese Weise die 2 inneren Schleifen sparst und damit mindestens 3*anzahl_faces schneller bist. Also Faktor 51000 in deinem Beispiel. Dafür brauchte halt die Arrays und die vertex id.

    achja, register als keyword ist völlig unnötig. alle Compiler ignorieren es, da sie im Zweifelsfall besser wissen, wie sie guten Code erzeugen können.



  • Das würde auch gehen und sogar um einiges besser Funktionieren. Das Problem ist nur, dass ich dir Vertices in den Faces speichere. Also gibt es keine v.id. Muss ich da umdenken und die Daten anders strukturieren?



  • Anmerkungen:

    Du könntest dich auch einfach an der Struktur des OBJ-Formates1 orientieren. Hier werden vertices, normals und texture coordinates zunächst definiert und via indices auf diese zugegriffen.

    Es ergeben sich somit drei Sequenzen, welche sich via std::vector sehr gut abbilden ließen:

    std::vector< Vector3f > vertices;
    std::vector< Vector3f > normals;
    std::vector< Vector2f > textureCoords;
    

    Deine faces sollten daher keine vertices als Objekte speichern, sondern lediglich Verweise in Form von indices.

    Weiterer Punkte:

    • Das OBJ-Format kann auch Normalen speichern. So könnte man die Normalen-Berechnung weiterhin von z. B. Blender erledigen lassen.
    • std::vector::at( ... )2 führt eine Bereichsprüfung durch und wirft beim Überschreiten eine exception. Wenn du sicher sein kannst, den Bereich nicht zu überschreiten, verwende std::vector::operator[]( ... )3.
    • Ausgaben auf der Konsole verlangsamen die Verarbeitung um ein Vielfaches. Aber du verwendest die Ausgabe ja ohnehin nur zum Debuggen.

    Grüße ... bwbg

    [1]: http://www.martinreddy.net/gfx/3d/OBJ.spec
    [2]: http://www.cplusplus.com/reference/stl/vector/at/
    [3]: http://www.cplusplus.com/reference/stl/vector/operator[]/



  • Razoron schrieb:

    [cpp}faces.at(i).normal = a.cross(b);
    faces.at(i).normal.normalize();[/cpp]

    das kreuzprodukt sollte nicht lange zu berechnen dauern da es ja nur ein paar multiplikationen und subtraktionen sind

    aber das normalisieren?!?
    da müsste eine wurzel gezogen werden, dann der kehrwert gebildet werden und dieser mit allen vektor elementen multipliziert werden

    unter umständen dauert eben diese wurzel sehr lange
    da könntest du mal gucke



  • Nur, dass wir nicht an der falschen Stelle suchen: Versuch Mal cout rauszunehmen.



  • Das Hauptproblem wird, wie von otze schon erkannt an der Suche nach Faces zu einem Vertex liegen. Für jedes Vertex rennst du alle anderen jedes mal wieder durch.

    Razoron schrieb:

    Das würde auch gehen und sogar um einiges besser Funktionieren. Das Problem ist nur, dass ich dir Vertices in den Faces speichere. Also gibt es keine v.id. Muss ich da umdenken und die Daten anders strukturieren?

    Wenn du es nicht umstellen möchtest und nicht die Lösung von otze umsetzen kannst (die sicher die effizientere ist) kannst du die Normalen während des Durchlaufs statt in einem vector oder array in einer map speichern.

    std::(unordered_)map<vertex*, vec3d> normalen;
    
    für(alle faces f)
        für(alle vertices v in f)
            normalen[&v] += f.normal;
    ...
    

    edit:
    in deiner derzeitigen Implementierung muss es wahrscheinlich eher heißen:

    std::map<vec3d /*vertex.pos*/, vec3d /*normal*/> normalen;
    


  • Okay, danke für eure vielen guten Räte, ich hab das jetzt mal nach otze umgebaut. Allerdings hab ich jetzt noch ein anderes Problem, das werde ich dann aber wohl in ein anderes Forum posten.


Anmelden zum Antworten