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

Zitat von 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]

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...

Zitat von Daniel Toplak

Eigentlich nicht, die Meshes sind Konkret LEGO-Teile also können die verschiedensten Formen haben und auch Borungen usw...

Das widerspricht sich doch nicht? Ein Polyeder darf auch konkav sein…

Das widerspricht sich doch nicht? Ein Polyeder darf auch konkav sein…

Hm sorry, wie gesagt bin nicht so der Matheguru.
Im CAD-Bereich würde man die Meshes als Solid bezeichnen also als geschlossene Volumenkörper.
Stell dir einfach einen Legostein als Mesh vor

Wenn du normalen berechen wilst von nem dreick nutzt dier vieleicht diese teil meines progs


werte[0].x=-1.0f;
werte[0].y=-1.0f;
werte[0].z=0.0f;
//werte[0].color=0xFF0000FF;
werte[0].tx=0.0f;
werte[0].ty=1.0f;

werte[1].x=0.0f;
werte[1].y=1.0f;
werte[1].z=0.0f;
//werte[1].color=0xFFFF0000;
werte[1].tx=0.5f;
werte[1].ty=0.0f;

werte[2].x=1.0f;
werte[2].y=-1.0f;
werte[2].z=0.0f;
//werte[2].color=0xFF00FF00;
werte[2].tx=1.0f;
werte[2].ty=1.0f;



//normale berechnen
zw1.x=werte[1].x-werte[0].x;
zw1.y=werte[1].y-werte[0].y;
zw1.z=werte[1].z-werte[0].z;

zw2.x=werte[2].x-werte[0].x;
zw2.y=werte[2].y-werte[0].y;
zw2.z=werte[2].z-werte[0].z;

//normalizieren
D3DXVec3Cross(&end,&zw1,&zw2);
D3DXVec3Normalize(&end,&end);

werte[0].nx=end.x;
werte[0].ny=end.y;
werte[0].nz=end.z;

werte[1].nx=end.x;
werte[1].ny=end.y;
werte[1].nz=end.z;

werte[2].nx=end.x;
werte[2].ny=end.y;
werte[2].nz=end.z;

als erstes gebe ich ein dreick alle punkte an und daraus berechne ich mir die normalen und standartiesiere sie mir.

wenn dir das net hilfz gug dir mal das prog
plus 14 an ist eine Mathe samlung und super erklärt hoffe konnte helfen

geh alle flächen durch. Geh davon aus, dass die erste fläche die du anguckst richtig ist. Danach betrachte jeweils nur flächen, die an schon bestimmte flächen angrenzen. nun wende die normale der aktuellen fläche so, dass sie auf die gleiche seite zeigt wie die eines bereits bestimmten, anliegenden triangels (indem du einfach die beiden vertices, welche sich die triangel teilen, in entgegengesetzter umlaufrichtung abläufst als bei dem schon bestimmten triangel). So hast du am Schluss alle normalen gleichgerichtet und kannst sie allenfalls noch allesammt swappen, falls sie in die falsche richtung schauen.

Aber vorsicht - gerade im gamebereich hat man selten geschlossene, saubere oberflächen. Die sind meistens irgendwo offen und es kann auch vorkommen dass eine 'edge' von mehr als zwei polygonen verwendet wird etc.

Warum hast du überhaupt zerschossene Ausgangsdaten?