Algorithmus zum Berechnen der Normalenvektor-Ausrichtung eines 3D Meshs

Daniel Toplak

Erfahrenes Mitglied
Hi,

hat irgendjemand einen Algorithmus (Sprache ist nebensächlich) zum Berechnen der Normalenvektor-Ausrichtung eines 3D Meshs?
Ich hab das Problem das ich ein Mesh aus Polygonen erstelle und die Normalenvektoren teilweise in die falsche Richtung zeigen, allerdings tritt dieses Problem nur bei einem Teil der Polygone auf und nicht bei allen.
Grund dafür ist das ich beim Erstellen der Polygone nicht weis welche Punktreihenfolge ich verwenden muss, deshalb stimmen per Zufall einige Normalen und andere wiederum nicht.

Deshalb bin ich auf der Suche nach einer zuverlässigen Methode/Algorithmus um am ende alle "falschen" Vektoren einfach "umzukehren".

Ich hoffe jemand kann mir hierzu behilflich sein.
 
Bin nicht der Über-Coder, aber woher soll der Algorithmus wissen, welche Richtung die Richtige ist ?
Man sollte beim Erstellen natürlich an allen Polygonen schon die Nummerierungsrichtung einhalten.

Der einzige - und trotzdem nicht sichere und noch dazu powerfressende - Weg wäre, zu schauen, in welche Richtung die
umliegenden Polygone ( deren Normalen ) schauen.

mfg chmee
 
Bin nicht der Über-Coder, aber woher soll der Algorithmus wissen, welche Richtung die Richtige ist ?
Man sollte beim Erstellen natürlich an allen Polygonen schon die Nummerierungsrichtung einhalten.
Würde ich ja gerne, denn dann wäre das Problem garnicht vorhanden, aber in meinem Fall geht das leider nicht, da die Basisdaten dies nicht hergeben.

Der einzige - und trotzdem nicht sichere und noch dazu powerfressende - Weg wäre, zu schauen, in welche Richtung die
umliegenden Polygone ( deren Normalen ) schauen.
Ja allerdings ist er nicht zuverlässig, denn dann mach ich unter umständen mehr "kaputt" als ganz.
 
Hmm, ist es vielleicht sinnvoll, erstmal etwas zu coden, dass Dir die Polygone wieder richtig macht ? Ist blöd, aber ich denke weiterhin, dass es keinen Algorithmus geben wird, der zuverlässig und schnell ist bei diesem Problem.

Wenn - Wunschdenken ! - das Objekt grundsätzlich konvex ist, könnte man schauen, ob die Normale des Polygons in die gleiche Richtung schaut wie der Vektor von Mitte_Objekt zu Polygon.

mfg chmee
 
Darf ich fragen, warum es so unmöglich scheint, die Daten der Meshs zu ändern ?

mfg chmee
 
Darf ich fragen, warum es so unmöglich scheint, die Daten der Meshs zu ändern ?

mfg chmee
Nein es ist nicht unmöglich, ich hab volle Kontrolle über die Meshdaten, also Vertexe, Faces usw...
Aber die Ausgangsdaten sind fix.
Das Ganze ist für ein Konverterprojekt (siehe meine Signatur) das ich mal weitermachen will und die Basisdaten sind einfache 2D Shapes deren Reihenfolge der Eckpunkte leider nicht korrekt ist. Deshalb hab ich keinen Einfluss auf die Richtung ob links oder rechts herum und somit auch keinen Einfluss auf die Ausrichtung des Normalenvektors selbst.

Deshalb benötige ich eine Möglichkeit die Normalenvektoren, nachdem das Mesh erstellt wurde zu prüfen und ggf. zu korrigieren.

Wo sind die 3D Spiele Programmierer unter euch? :)

Ich hätte auch einen Ansatz einer Vorgehensweise im Kopf, aber da fehlen mir leider ein paar mathematische bzw. geometrische Kenntnisse:

1. Ich nehme den Bestehenden Normalenvektor (falsch oder richtig, spielt keine Rolle)
2. Ich verlängere diesen Vektor um einen definierten Faktor, unendlich ist hier net möglich
:)
3. Und zähle wie oft ein anderes Dreieck im Mesh geschnitten wird.
4. Wenn die Anzahl der Schnitte gerade ist (0, 2, 4, ....) dann ist der Normalenvektor korrekt
5. Wenn die Anzahl der Schnitte ungerade ist (1, 3, 5, ....) dann ist der Normalenvektor
falsch

Aber da gibt es verschiedene Probleme bei dem Ansatz.
1. Ich weiss nicht wie ich das Programmiertechnisch, bzw. in einen Algorithmus bring
2. Was ist wenn der "verlängerte" Vektor eine Kante von 2 Dreiecken schneidet (muss ich dann 1x oder 2x zählen)

So ich hoffe ich hab das jetzt etwas ausführlicher dargestellt.
 
Ja also irgendwie haben die das Problem bei Blender ja auch in den Griff bekommen mit der Funktion "Recalculate Outside". Der Algorithmus hat bei mir noch nie einen Fehler gemacht, er erkennt also was ein Körper ist und was seine Aussenseite. Vielleicht schaust du einfach mal in den Blender Quellcode, da haben sich schon ein paar mehr Leute die Köpfe zerbrochen :)

Eine einfache Idee meinerseits: Ich würde erstmal einen Mechanismus finden, der alle normalen auf eine Seite bringt und mir dann darüber Gedanken machen, was innen und was aussen ist.
 
Sehe ich das richtig, dass die Dreiecke einen Rauminhalt vollständig und überschneidungsfrei abschließen? [edit]Man könnte auch sagen: bilden die Dreiecke ein Polyeder (das Wort wollte mir just nicht einfallen)?[/edit]
 
Zuletzt bearbeitet:
Ja also irgendwie haben die das Problem bei Blender ja auch in den Griff bekommen mit der Funktion "Recalculate Outside". Der Algorithmus hat bei mir noch nie einen Fehler gemacht, er erkennt also was ein Körper ist und was seine Aussenseite. Vielleicht schaust du einfach mal in den Blender Quellcode, da haben sich schon ein paar mehr Leute die Köpfe zerbrochen
Hm gute Idee ich glaub ich werde mir mal den Blender-Source holen und bei 1-5 Tassen Kaffee durchlesen :)
Das wird wohl nicht gerade einfach denn ich kenn den Source nicht und auch den Aufbau nicht und Blender ist auch kein Konsolentaschenrechner :)
Sehe ich das richtig, dass die Dreiecke einen Rauminhalt vollständig und überschneidungsfrei abschließen? [edit]Man könnte auch sagen: bilden die Dreiecke ein Polyeder (das Wort wollte mir just nicht einfallen)?[/edit]
Eigentlich nicht, die Meshes sind Konkret LEGO-Teile also können die verschiedensten Formen haben und auch Borungen usw...
 
Zurück