Vertex normals und face normals

[liquid]

N'abend,

ich bin (mal wieder) ein wenig konfus, und zwar über das Thema Vertex Normalen. Diese berechnen sich ja aus den Ebenen (Face) Normalen der an diesen Punkt (Vertex) angrezenden Flächen.
Nun, die Berechnung der Face Normals ist ja kein Problem und die der Vertex normals auch nicht, aber ich frage mich irgendwie, warum das jeder anders macht?

Ich hab nämlich letztens das MD2 Tutorial von GameTutorials gezogen und da machen die folgendes. Die berechnen auch die face normals, allerdings machen die nach dem Kreuzprodukt keine Normalisierung mehr. Das sind dann quasi unnormalisierte Pseudo-Normalen.

Um auf die Vertex Normale zu kommen, addieren die jetzt die ganzen face normals, teilen die dann durch die Anzahl der face normals, normalisieren sie und speichern sie dann ab.

Ist das nicht ein bischen komisch? Ich mein jetzt das Teilen durch die Anzahl. Die führen da ja nur eine Skalierung des Vektors durch und nix anderes. Aber warum machen die das, wenn sie den Vektor sowieso danach normalisieren und damit auf Länge 1 bringen? Sehr merkwürdig finde ich das doch?

Und deshalb meine Frage, wie man die vertex normals denn jetzt genau baut? Nimmt man wirklich unnormalisierte face normals, addiert sie und normalisiert sie dann. Oder nimmt man schon normalisierte face normals, addiert sie und schickt sie dann nochmal durch die Normalisierung. Reichlich konfus... *g*

cya
liquid

[Xmas]

Originally posted by liquid
N'abend,

ich bin (mal wieder) ein wenig konfus, und zwar über das Thema Vertex Normalen. Diese berechnen sich ja aus den Ebenen (Face) Normalen der an diesen Punkt (Vertex) angrezenden Flächen.
Nun, die Berechnung der Face Normals ist ja kein Problem und die der Vertex normals auch nicht, aber ich frage mich irgendwie, warum das jeder anders macht?

Ich hab nämlich letztens das MD2 Tutorial von GameTutorials gezogen und da machen die folgendes. Die berechnen auch die face normals, allerdings machen die nach dem Kreuzprodukt keine Normalisierung mehr. Das sind dann quasi unnormalisierte Pseudo-Normalen.

Um auf die Vertex Normale zu kommen, addieren die jetzt die ganzen face normals, teilen die dann durch die Anzahl der face normals, normalisieren sie und speichern sie dann ab.

Ist das nicht ein bischen komisch? Ich mein jetzt das Teilen durch die Anzahl. Die führen da ja nur eine Skalierung des Vektors durch und nix anderes. Aber warum machen die das, wenn sie den Vektor sowieso danach normalisieren und damit auf Länge 1 bringen? Sehr merkwürdig finde ich das doch?

Und deshalb meine Frage, wie man die vertex normals denn jetzt genau baut? Nimmt man wirklich unnormalisierte face normals, addiert sie und normalisiert sie dann. Oder nimmt man schon normalisierte face normals, addiert sie und schickt sie dann nochmal durch die Normalisierung. Reichlich konfus... *g*

cya
liquid
Das Teilen durch die Anzahl ist in diesem Fall wirklich idiotisch und bringt überhaupt nichts.

Vertex Normals sind keine mathematisch korrekte Sache. Es gibt hier keinen "richtigen" Weg. IMO ist es aber das beste, normalisierte Face Normals zu addieren und das Ergebnis wieder zu normalisieren.

[liquid]

Ich hab mal ein wenig gesucht und du hattest recht Xmas. Es gibt da keine richtige Methode. Ich quote mal von dieser Page (http://research.microsoft.com/~hollasch/cgindex/geometry/surfnorm.html)

Recall the assumptions: you are given a shared vertex, and its neighbors in a polygonal (triangular) mesh. The problem is to estimate the surface normal at the shared vertex. Here are the methods submitted in response to my query, in roughly the order received:

Method 0: `weight-by-area'
Add up the normals of each polygon sharing a vertex, then normalize. While it was unstated by the people who submitted this method, it was clear that the `normals of each polygon' have magnitudes which are proportional to their areas (in some sense). If the `polygons' are triangles, then these `weighted normals' are simply computed as the cross-products of the successive vectors formed by the shared vertex and it's neighbors. Re-arrange terms, optimize the code, and you get the formula presented in many texts. A possible problem with this method is that the result is independent of the location of the shared vertex. A major advantage is that it can be made to run very fast.

Method 1: `weight-uniformly'
Add up normalized face normals, then normalize. This is more expensive, unless you already compute and store (normalized) face normals for each polygon (triangle). It is reported to work a bit better than `weight-by-area'.

Method 2: `least squares'
Fit a plane to all of the vertices. Variation: fit the plane to all of the vertices *except* the shared vertex.

Method 3: `eigenvalues'
Compute moments, form a scatter matrix, and extract eigenvalues and eigenvectors. The eigenvector corresponding to the smallest eigenvalue is the (unnormalized) surface normal. Variations as above - either with or without the shared vertex.

Method 4: `independent derivatives'
Intended only for dense meshes - use 2 independent directional derivative estimators.

Method 5: `weight-by-angle'
Compute normalized face normals for the neighboring polygons, and weight each normal by the angle formed at the shared vertex.

Method 6: `weight-by-inverse-area'
As above, but weight the normals by inverse area. This method appears to have been independently invented by myself and Andrew Glassner, circa 1985. I am particularly interested in pointers to published literature which discusses this method. The idea here is that small triangles have all of their vertices close to the shared vertex, and "know" more about the local surface normal than the far-off vertices forming large triangles. It turns out (see the forthcoming paper) that this is also relatively easy to compute.

Thanks to all. (very) preliminary results indicate that `weight-by-area' is the most accurate method. But, this is very preliminary (i.e., see the forthcoming paper).

If there are any other methods out there that were `too obvious to mention', I'd still like to hear about them.

Also wenn ich das mal als Fakten hinnehme, dann heißt es doch, dass ich doch die unnormalisierte Pseudo-Normalen Methode anwenden sollte, oder?

cya
liquid

[Einfachkrank]

Ehm, ich peil das hier gerade net so ganz :D
Wie geht man den mit Vertex Normals um? Sehen die dann besser aus als die ganz normalen Surface Normals? Wie werden die denn z.B. unter OpenGL benutzt?

[Demirug]

Sowas wie Sufrace Normals kenne 3d Karten ja nicht. Normals werden daher immer per Vertex übergeben. Benötigt werden diese in der einen oder anderen Form für dynamische Lichtmodele. Beim HT&L also für den Lichtteil und wenn man Vertexshader benutzt stellen die Normalen einfach ein zusätzlichen Inputregister dar mit dem man machen kann was man will.

[zeckensack]

Einfachkrank,
oben face normals,
unten vertex normals ...

[liquid]

@zeckensack: Wie würdest du es denn machen?

cya
liquid

[zeckensack]

'weight uniformly'

Aber mit dem Zusatz, daß harte Kanten auch harte Kanten bleiben. Wenn der Winkel zwischen zwei benachbarten Dreiecken über einem gewissen Schwellwert liegt, dann würde ich die entsprechenden Vertices verdoppeln und weist jeweils jeder Kopie die 'face normal' zu.
30° sind ein ganz guter Wert für den Anfang, man sollte aber rumprobieren, was am besten paßt.

[Einfachkrank]

ach, ist das nicht dasselbe wie bei Direct3D das Guard-Shading oder so ähnlich?
Und in OpenGL muss ich dafür statt vor einer Fläche eben vor jedem Vertex einen Normal angeben, der den Durchschnitt aller Surface Normals der anliegenden Flächen ist ? Hab ich das so richtig verstanden?

MFG Einfachkrank

[Kant]

Originally posted by Einfachkrank
ach, ist das nicht dasselbe wie bei Direct3D das Guard-Shading oder so ähnlich?
Und in OpenGL muss ich dafür statt vor einer Fläche eben vor jedem Vertex einen Normal angeben, der den Durchschnitt aller Surface Normals der anliegenden Flächen ist ? Hab ich das so richtig verstanden?

MFG Einfachkrank

Für normales Flat-Shading (Face-Normal) reicht es diese in OpenGL einmal anzugeben.
glNormal2f(...)
glVertex3f(...)
glVertex3f(...)
glVertex3f(...)
Damit hat man ein Face, was nur eine Normal hat.

Wenn du für jede Vertex eine eigene Normal definierst, wird diese beim Rendern im Face interpoliert, was ?Gourard? Shading entspricht.

Edit :
Bzw wird bei Gourard die Beleuchtung pro Vertex ermittelt, und dann diese interpoliert. Das interpolieren der normalen wäre phong-shading.

[Einfachkrank]

@Kant
Ja, genau das meinte ich :)

Gut, das normale Flat Shading habe ich ja bisher immer genutzt, aber ich denke es wäre auch mal interessant mit Vertex Normals zu experimentieren :)
Also kannst du mir das vielleicht noch en bisschen genauer erklären, wie das mit dem Interpolieren geht? Und ich hätte da noch ne allgemeine Frage, bezüglich Vektoren :) Wenn ich einen Vektor normalisiere, dann wird er doch quasi "auf die Länge 1 gekürzt", oder? Korrigiert mich, wenn ich falsch liege - aber wo zu macht man das genau?

[liquid]

Originally posted by Einfachkrank
Gut, das normale Flat Shading habe ich ja bisher immer genutzt, aber ich denke es wäre auch mal interessant mit Vertex Normals zu experimentieren :)
Also kannst du mir das vielleicht noch en bisschen genauer erklären, wie das mit dem Interpolieren geht? Und ich hätte da noch ne allgemeine Frage, bezüglich Vektoren :) Wenn ich einen Vektor normalisiere, dann wird er doch quasi "auf die Länge 1 gekürzt", oder? Korrigiert mich, wenn ich falsch liege - aber wo zu macht man das genau?
Du kannst verschieden interpolieren. Die einfachste Möglichkeit ist natürlich lineare Interpolation. Bei dieser Interpolation hast du gewissermaßen zwei Keyframes zwischen denen du interpolierst und einen Prozent-Wert (von 0.0 bis 1.0) der angibt, wie viel interpoliert wird (ich nennen das immer step-value).
v(t) = v(0) + t * (v(1) - v(0))
Wobei v(0) der erste Keyframe ist, v(1) der zweite KF und t das step-value.

Dann gibt es noch verschiedene andere Arten von Vektorinterpolation. Quadratisch, Biquadratisch, Kubisch, Bikubisch, Spline, etc.
Da musste selber mal Google quälen, wenn du genaueres dazu wissen willst.
Für Normalen gibt es auch noch besondere Interpolationsverfahren, aber "erstmal" reicht wohl lineare Interpolation.

Zur Vektornormalisierung. Einen Vektor normalisiert du, indem du ihn durch seine Länge teilst. Länge ist ja die Quadratwurzel des inneren Vektorproduktes (x*x + y*y + z*z). Wenn das 1 ist oder die Wurzel 1 ist (kommt aufs selbe raus), dann ist der Vektor "normal" und braucht nicht normalisiert werden. Wenn dem nicht so sein sollte, dann bildeste die Länge und teilst den Vektor dadurch.

cya
liquid

EDIT: Catmull-Rom Interpolation ist auch ganz nett, dazu gibts auch ne' Menge Informationen. Oder Kochanek-Bartels Splines aka TCB-Splines, da hat man mehr Kontrolle über den Interpolationsverlauf.

[Einfachkrank]

Ach, sche*** ich habs mal wieder verplant :)
Interpolisation kenn ich doch! Ist doch gut um irgendwas zu animieren, zumindest kenn ich den Begriff von Dateiformaten wie das MD2...
Aber wie berechne ich jetzt noch mal genau den Vertex Normal Vektor, zwischen mehreren Flächen?

[liquid]

Steht da doch schon, was es alles für Methoden gibt! ;)

cya
liquid

[Kant]

@Einfachkrank

Es ist deswegen sinnvoll einen normalen Vector zu "normalisieren" (also auf Laenge 1 zu bringen), da er so direkt für die meist folgende Lichtberechnung verwendet werden kann. Egal ob man jetzt das Standard-OpenGL Licht verwendet , oder selbst eine eigene Berechnung im Pixel/Vertex Shader durchführt.

Zu dem erzeugen von Vertex-Normalen aus gegebenen Faces sind ja schon so ziemlich alle Methoden genannt worden. Das prinzipielle Vorgehen ist dabei immer gleich.
Als Pseudo-Code was in der Art,
for (Vert=0;Vert<Verts;Vert++) {
vnormal=(0,0,0);
for (Face=0;Face<Faces;Face++) {
if (Vert Vertex von Face ) {
// Weitere Tests ?
vnormal+=facenormal;
}
}
normalisiere(vnormal);
}
Wobei sich die verschiedenen Methoden durch untersch. Tests / Gewichtungen bei der Addition der facenormal unterscheiden.
Nebenbei bemerkt wäre dieser Pseudo-Code bei größeren Modellen brechend lahm :)

[Einfachkrank]

Nur noch mal um Sicher zu gehen. Den Vektor normalisiere ich doch in dem ich erst seine Länge ermittle und dann jeden Richtungswert(x,y,z) durch diese teile, oder?

[Demirug]

Originally posted by Einfachkrank
Nur noch mal um Sicher zu gehen. Den Vektor normalisiere ich doch in dem ich erst seine Länge ermittle und dann jeden Richtungswert(x,y,z) durch diese teile, oder?

Ja und danach muss die Länge dann genau 1 sein.

[liquid]

Ist es eigentlich besser erst zu testen ob die Länge 1 ist und dann zu normalisieren, oder gleich drauf los zu rechnen?? Also ganz ohne Test.
Ich frage weil für die Normalisierung ja erstens eine Quadratwurzel berechnet werden muss und dann noch eine Division durchgeführt werden muss. Und das sind ja beides sehr rechenintensive Aufgaben.

cya
liquid

[Xmas]

Originally posted by liquid
Ist es eigentlich besser erst zu testen ob die Länge 1 ist und dann zu normalisieren, oder gleich drauf los zu rechnen?? Also ganz ohne Test.
Ich frage weil für die Normalisierung ja erstens eine Quadratwurzel berechnet werden muss und dann noch eine Division durchgeführt werden muss. Und das sind ja beides sehr rechenintensive Aufgaben.

cya
liquid
Ds kommt ganz drauf an was für Vektoren normalisiert werden sollen. Wenn das zusammengerechnete Face-Normals sind, dann ist die Wahrscheinlichkeit dass die Summe die Länge 1 hat so verschwindend gering, dass man sich den Test auf Länge 1 besser spart.

[liquid]

Originally posted by Xmas

Ds kommt ganz drauf an was für Vektoren normalisiert werden sollen. Wenn das zusammengerechnete Face-Normals sind, dann ist die Wahrscheinlichkeit dass die Summe die Länge 1 hat so verschwindend gering, dass man sich den Test auf Länge 1 besser spart.

Ich hab hier ein Terrain was aus einem gleichmäßig Vertex-Raster besteht. Sagen wir mal ich berechne jetzt von allen Dreicken des Terrains ein AreaNormal (ich nenne diese Art von Normale mal so, da ihre Länge proportional zur Fläche des Dreiecks ist) und bilde dann im nächsten Schritt an den einzelnen Vertices Vertex-Normalen durch aufsummieren der AreaNormals. Diese V-Normals normalisiere ich dann anschließend. Ist das Verfahren gut, oder sollte ich es lieber so machen?

1. Face-Normals bilden mit Cross-Product und anschließender Normalisierung (dann weiß ich dass alle Face-Normals die Länge 1 haben).
2. Aufsummieren der Face-Normals zur Berechnung der V-Normals
3. Pseudo-Normalisierung durch Division mit der Menge n der aufsummierten Vektoren. Denn die Menge n ist immer bekannt (abhängig von der Position des Vertices im Terrain-Grid) und Division mit einer Konstanten wird ja umgerechnet in Multiplikation mit reziprokem Wert (1/x).

Oder habe ich bei der Sache mit der Division ein Denkfehler drin bzw. hat die Summe S zweier Vektoren A und B mit den Längen a und b auch die Länge a+b ??
Wenn dem so ist, dann spart das wohl ein wenig Rechenzeit und ich würde auch zeckensack's Empfehlung nachkommen das ganze "uniformly" zu weighten.
Spart insofern Rechenzeit, da die Anzahl der V-Normal ja n² ist, wenn eine Seite des Terrain aus n Vertices besteht. F-Normals sind "nur" (n-1)² * 2.
Naja, ich glaub ich optimiere schon wieder zu viel. Was denkt ihr? Bringt es was, oder nicht?
Werde mal den Schnittpunkt der Funktionen (f(n) = n² und g(n) = (n-1)² *2) bestimmen. Mal gucken wann sich das ganze rentiert.

cya
liquid

[zeckensack]

liquid,
Die Generierung der Normalen mußt du normalerweise nicht 'totoptimieren', das ganze kannst du einmal beim Laden machen, und dann ist's gut. Für die Performance 'im laufenden Betrieb' ist's also egal, wie kompliziert dein Verfahren ist.

Das mit dem (N+N+N)/3=N ist bei Vektoren nicht gültig. Bsp:
0 1 1
1 + 0 = 1
0 0 0
Die beiden Summandenvektoren haben Länge 1, der Summenvektor hat aber die Länge Wurzel 2. Teilst du die Summe durch zwei, erhälst du einen Vektor der Länge 0,707uswusf.
Du mußt den Summenvektor schon 'richtig' normalisieren :)