Der beste Weg, um Scheitelpunktnormalen aus der Liste eines Dreiecks zu berechnen

8

Hallo, ich bin ein absoluter Neuling in der Computergraphik. Tut mir leid, wenn es eine dumme Antwort ist. Ich versuche, eine einfache 3D-Engine von Grund auf neu zu erstellen, eher für Bildungszwecke als für den realen Gebrauch.

im Moment berechne ich nur Gesichtsnormalen. auf diese Weise:

Ich habe ein Oberflächenobjekt mit in der Liste eines Dreiecks. Ich berechne Normalen innerhalb der Triangle-Klasse auf folgende Weise:

triangle.computeFaceNormals() {
    Vec3D u = v1.sub(v3)
    Vec3D v = v1.sub(v2)
    Vec3D normal = Vec3D.cross(u,v)
    normal.normalized()
    this.n1 = this.n2 = this.n3 = normal
}

und beim Bauen von Oberflächen:

t = new Triangle(v1,v2,v3)
t.computeFaceNormals()
surface.addTriangle(t)

und ich denke, das ist der beste Weg, das zu tun ... nicht wahr?

jetzt .. das funktioniert, ok. aber leicht ist es nicht geglättet. Ich versuche auch Vertex-Normalen zu berechnen. (Ich teste meinen Motor mit tubolaren Oberflächen, so dass ich fast den gesamten Scheitelpunkt mit mehr als einem Dreieck geteilt habe.)

Ich habe diesen einfachen Algorithmus gefunden: Flipcode Vertex normal aber .. hei dieser Algorithmus hat .. exponentielle Komplexität? (Wenn mein Gedächtnis meinen Informatik-Hintergrund nicht verfehlt ..) (Übrigens .. es hat 3 verschachtelte Schleifen .. Ich denke nicht, dass es der beste Weg ist, dies zu tun ..)

irgendein Vorschlag?

nkint
quelle
Welche Sprache ist das? Es sieht für mich so aus, als wäre tes das Ergebnis von computeFaceNormals(was nichts zurückgibt), kein Dreieck.
es ist pseudocode :) du hast recht in echtem code ich habe auch "return this", sorry ich habe bearbeitet!
Nkint

Antworten:

6

"Best" ist ziemlich subjektiv - es geht darum, das, was Sie brauchen, aus dem Algorithmus gegen die Eingaben, die Laufzeitkomplexität und andere Eigenschaften abzuwägen.

Das heißt, sowohl Ihr Ansatz als auch der verknüpfte FlipCode-Ansatz sind vernünftig, um brauchbare Ergebnisse zu erzielen (Sie könnten ganz einfach Ihre "Gesichtsnormalen" auf jeden Scheitelpunkt kopieren, wenn Sie keine tatsächlichen Scheitelpunktinstanzen zwischen Dreiecken teilen, was mir unklar ist auf von Ihrem Code). Andere Techniken umfassen das Gewichten des Beitrags jeder Gesichtsnormalen mit der Größe des Winkels, der mit jeder vom Scheitelpunkt geteilten Fläche gebildet wird.

Sie haben insofern Recht, als der FlipCode-Ansatz wie geschrieben suboptimal erscheint, aber er könnte nur schlecht spezifiziert sein: Es ist ein wenig unklar, ob er beabsichtigt, die zweite Schleife alle zu durchlaufen oder nicht Flächen im Modell , im Vergleich zu den wenigen Flächen, die die teilen Scheitelpunkt in Frage. Wenn Sie über die Adjazenzinformationen verfügen, um den Suchraum der zweiten Schleife zu verringern, ist dies weniger problematisch. Natürlich haben Sie diese Adjazenzinformationen möglicherweise nicht - das meine ich damit, dass ich überlege, welche Eingaben Sie für Ihren Algorithmus zur Verfügung haben.

Wenn Sie nicht nur das Gesicht normal in die Scheitelpunkte kopieren möchten oder Scheitelpunkte freigeben und diese nicht teilen möchten, können Sie:

foreach vertex:
   set vertex normal to (0,0,0)

foreach triangle:
   foreach vertex on that triangle:
      set vertex normal = normalize( vertex normal + face normal )

Dies setzt voraus, dass jedes Dreieck tatsächlich auf jeden Scheitelpunkt verweist, anstatt eine Kopie davon zu speichern. Ich weiß nicht, welche Sprache Sie verwenden, daher weiß ich nicht, ob dies der Fall ist oder nicht.


quelle
Entschuldigung, Englisch ist nicht meine erste Sprache. Vielleicht habe ich auf eine schlechte Weise erklärt, was ich will. Ich habe noch keine Vertex-Normalen! Ich habe meine Antwort ein wenig bearbeitet, hoffe jetzt bin ich klarer
nkint
Es ist okay, ich habe verstanden, dass Sie keine Scheitelpunktnormalen hatten. Der von mir bereitgestellte Pseudocode berechnet sie für Sie, indem Sie zuerst die Normalen jedes Scheitelpunkts auf (0,0,0) setzen und dann die Gesichtsnormalen für jedes Gesicht, das der Scheitelpunkt berührt, aufsummieren (und natürlich erneut normalisieren).
5
Sie sollten Normalen nicht auf diese Weise normalisieren. Sie sollten nach allen Summierungen in einem anderen Foreach normalisieren. Wenn es zum Beispiel 10 Dreiecke mit derselben Normalen gibt, aber die letzte mit unterschiedlichen (Ergebnisnormal sollte fast gleich der Normalen von 10 Dreiecken sein), dann haben Sie dies, wenn Sie das letzte summieren: setze Vertex nromal = normalize (( 1,0,0) + (0,0,1)) und das ist (0,5,0,0,5), was falsch ist. Ich hoffe, dass ich dich nicht verwirrt habe.
Zacharmarz
7

Josh Petrie hat recht. Wenn Sie Scheitelpunktnormalen berechnen möchten, sollten Sie den Dreiecksbeitrag nach Winkel gewichten. Sie können jedoch eine naive Lösung verwenden und einfach alle Normalen von allen Flächen um den Scheitelpunkt summieren.

Sie berechnen also einfach alle Gesichtsnormalen und normalisieren sie. Setzen Sie dann alle Scheitelpunktnormalen auf Null. Fügen Sie dann für jede Fläche (Dreieck) ihre Normalen zu allen Scheitelpunkten hinzu. Normalisieren Sie dann alle Scheitelpunktnormalen. Und es ist geschafft.

Es ist nicht zu richtig, aber es könnte genug sein.

Und Ihre Gesichtsnormalberechnung oben - es ist richtig, aber Sie sollten wissen, welche Seite normale Köpfe. Es könnte nach oben oder unten gehen. Es hängt vom Kreuzprodukt ab - AxB ist nicht dasselbe wie BxA - es gibt Ihnen einen entgegengesetzten Vektor.

zacharmarz
quelle
Guter Punkt in Bezug auf das Kreuzprodukt.
2

Nehmen wir an, wir haben einen Würfel aus 6 Rechtecken. Wir wissen bereits, dass die Scheitelpunktnormale für einen Würfel aufgrund der scharfen Kante nicht die normalisierte Summe der Verbindungsflächen ist. Wenn Sie eine Karte mit dem Scheitelpunktwert und den verschiedenen Scheitelpunktnormalen für einen Würfel erstellen, erhalten Sie 3 Normalen für jeden Scheitelpunkt.

Unter Berücksichtigung des obigen Punktes berechne ich auf diese Weise Scheitelpunktnormalen (ich habe es getestet und verwende es).

class Face{
    uint vert_indices[3];
    vec3 surface_normal;
    vec3 vertex_normal[3];
}

Jede Fläche verfolgt die zu verwendenden Scheitelpunktnormalen, da zwei Flächen einen Scheitelpunkt teilen können. Dies bedeutet nicht, dass die Scheitelpunktnormalen für jede Fläche gleich sind.

Nehmen wir an, wir versuchen beim Rendern von face2, die Scheitelpunktnormalen für vert zu berechnen .

vert wird von face0 , face1 , face2 , face3 und face4 geteilt . Alle oben genannten Flächen sind in der Reihenfolge Nachbarn und face0 und face4 verbinden sich zu einer Schleife.

Die Scheitelpunktnormalen für vert ist die Summe aller mit face2 normalisierten verbundenen Nachbarketten . Die Kette stoppt, wenn der Winkel zwischen zwei benachbarten Flächen mehr als 0,8 Bogenmaß beträgt (Winkel == arccos (crossProduct (faceA.surface_normal, faceB.surface_normal)).

wenn der Winkel zwischen face0 und face1 mehr als 0,8 Radiant und der Winkel zwischen Face3 und face4 mehr als 0,8 Radiant ist als der Scheitelpunkt normal vert beim Rendern face2 ist Normalisieren ( surfnormal1 + surfnormal2 + surfnormal3 ).

Fredrique Samuels
quelle