Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!
-
dot schrieb:
Und was ist mit Polygonen deren Normale eine y-Koordinate von 0 hat?
Das wiederum kann nicht vorkommen, da die Eingabepolygone zwingend in der XZ-Ebene berechnet werden. Darum kanns ja keine Normale mit y-Komponente = 0 geben.
-
volkard schrieb:
PatrickWG schrieb:
Tatsächlich habe ich aktuell einen Testcase, bei dem in der ursprünglichen und gedrehten Reihenfolge die gleiche Normale ensteht...
Zeig mal, das überrascht mich ein wenig.
Nicht schön, aber hier die Vertices aus meinem Testprogramm:
List<Vertex3d> mVertices = new ArrayList<Vertex3d>(); mVertices.add(new Vertex3d(200.0f, 958.0f, 85.734924f)); mVertices.add(new Vertex3d(246.23288f, 958.0f, 73.34686f)); mVertices.add(new Vertex3d(285.80142f, 958.0f, 73.34686f)); mVertices.add(new Vertex3d(285.80142f, 958.0f, 57.050827f)); mVertices.add(new Vertex3d(290.64044f, 958.0f, 52.211823f)); mVertices.add(new Vertex3d(331.654f, 958.0f, 52.211823f)); mVertices.add(new Vertex3d(331.654f, 958.0f, 11.198273f)); mVertices.add(new Vertex3d(335.14105f, 958.0f, 7.711212f)); mVertices.add(new Vertex3d(356.04742f, 958.0f, -70.3125f)); mVertices.add(new Vertex3d(335.14105f, 958.0f, -148.33621f)); mVertices.add(new Vertex3d(278.0237f, 958.0f, -205.45354f)); mVertices.add(new Vertex3d(200.0f, 958.0f, -226.35992f)); mVertices.add(new Vertex3d(121.97629f, 958.0f, -205.45354f)); mVertices.add(new Vertex3d(64.85896f, 958.0f, -148.33621f)); mVertices.add(new Vertex3d(43.952576f, 958.0f, -70.3125f)); mVertices.add(new Vertex3d(64.85896f, 958.0f, 7.711212f)); mVertices.add(new Vertex3d(85.34248f, 958.0f, 28.194733f)); mVertices.add(new Vertex3d(85.34248f, 958.0f, 34.494637f)); mVertices.add(new Vertex3d(91.64239f, 958.0f, 34.494637f)); mVertices.add(new Vertex3d(114.198586f, 958.0f, 57.050827f)); mVertices.add(new Vertex3d(114.198586f, 958.0f, 73.34686f)); mVertices.add(new Vertex3d(153.76712f, 958.0f, 73.34686f));Normalenberechnung nimmt die ersten 3 Vertices, berechnet Vektoren von 0 auf 1 und von 1 auf 2 und bildet das Kreuzprodukt (das hier beschriebene Polygon ist konkav).
Bei meinen Berechnungen kommt immer eine Normale von (0, -1, 0), egal, ob ich die Vertices vorher noch mal in umgekehrter Reihenfolge in eine andere Liste kopiere oder nicht...
-
Ok, dann frag ich mich aber was überhaupt das Problem mit der Normale ist. Deine Vertices liegen in einer Ebene die du kennst und du kennst auch die Richtung in die du extrudieren willst. Warum musst du diese Richtung jetzt mit irgendwelchen Kreuzprodukten berechnen wenn du sie sowieso schon kennst!?
-
dot schrieb:
Ok, dann frag ich mich aber was überhaupt das Problem mit der Normale ist. Deine Vertices liegen in einer Ebene die du kennst und du kennst auch die Richtung in die du extrudieren willst. Warum musst du diese Richtung jetzt mit irgendwelchen Kreuzprodukten berechnen wenn du sie sowieso schon kennst!?
Na ja, ich will mich für weitere Berechnungen (unabhängig von der Extrusion) darauf verlassen können, dass die Vertexorder bei einer Ebenenberechnung zu konstanten Ausrichtungen führt. Die Extrusion ist nur ein Rechenschritt, der davon abhängt. Darum will ich vermeiden, einfach immer hart eine Ausrichtung zu coden (klassisch: wenn ich mich irgendwann entscheide, dass die andere Ausrichtung doch die schönere ist, dann steh ich da und kann es an x Punkten verändern). Darum soll die Ausrichtung aus der Berechnung hervorgehen. Die Extrusion ist dabei aber der erste Berechnungsschritt, an dem das eine Rolle spielt (darum das Beispiel).
-
Es sind aber beide Möglichkeiten absolut gleichwertig. Kannst du dem Benutzer nicht einfach einen Button geben mit dem er die Reihenfolge umdrehen kann wenn ers lieber anders rum hätte!?
-
Einen Nutzer gibts nicht (und auch noch kein GUI), in weiteren Ausbaustufen soll das mehrere 1000 oder 10000 Mal vorkommen, da würd mich jeder Nutzer zum Teufel jagen, wenn er da 10000 Mal nen Button drücken muss...
-
Dann musst du dir eine Heuristik überlegen nach der du die Richtung festlegst. Wenn du nur einen Haufen Punkte hast ist es mathematisch nicht eindeutig, daran gibts nix zu rütteln.
-
dot schrieb:
Dann musst du dir eine Heuristik überlegen nach der du die Richtung bestimmst. Es ist mathematisch nicht eindeutig, daran gibts leider nix zu rütteln.
Das hatte ich befürchtet, dann wirds wohl doch Brute-Force, so lange die Reihenfolge ändern, bis irgendwann die korrekte Ausrichtung herauskommt. So muss ichs dann wenigstens nur an einer Stelle ändern, wenn ich mich irgendwann mal umentscheiden sollte...
-
PatrickWG schrieb:
Das hatte ich befürchtet, dann wirds wohl doch Brute-Force, so lange die Reihenfolge ändern, bis irgendwann die korrekte Ausrichtung herauskommt.
Wenn du weißt was die korrekte Ausrichtung sein soll dann kannst du sie ja so sortieren dass das rauskommt. Aber das Problem ist doch dass du ja offenbar nicht weißt was die korrekte Ausrichtung sein soll!? Zumindest konntest du bisher noch nicht beschreiben was für die dich "korrekte Ausrichtung" wäre und solange du nicht beschreiben kannst was du willst wirds schwer einen Algorithmus zu finden der tut was du willst...
-
PatrickWG schrieb:
(das hier beschriebene Polygon ist konkav).
Konkav ist schlecht. Diese Kreuzprodukte gehen nur bei konvexen Polynomen alle in die selbe Richtung. Fertig. (Mal welche genommen, die keine Kreuzungen haben.)
PatrickWG schrieb:
Normalenberechnung nimmt die ersten 3 Vertices, berechnet Vektoren von 0 auf 1 und von 1 auf 2 und bildet das Kreuzprodukt
Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt. Nämlich
a b c d e f g h i j
und winkel(a,b,c) ist dumm
machste
d e f g h i j a b c
denn du darfst im kreis ja woanders anfangen
und dann
c b a j i h g f e d
und siehe da, der winkel (c,b,a) ist nicht mehr dumm.
-
dot schrieb:
PatrickWG schrieb:
Das hatte ich befürchtet, dann wirds wohl doch Brute-Force, so lange die Reihenfolge ändern, bis irgendwann die korrekte Ausrichtung herauskommt.
Wenn du weißt was die korrekte Ausrichtung sein soll dann kannst du sie ja so sortieren dass das rauskommt. Aber das Problem ist doch dass du das ja offenbar nicht weißt was die korrekte Ausrichtung sein soll!?
Doch, ich weiß ja, dass ich eine Normale in Richtung der positiven y-Achse herausbekommen will. Den Ansatz, einfach so lange die Reihenfolge zu ändern, bis das Ergebnis rauskommt, was ich haben will, hab ich ja in der Hinterhand. Ich dachte aber, dass es vielleicht ein etwas eleganteres Verfahren gibt, das genau dieses "ich leg fest was rauskommt und rechne so lange, bis es rauskommt"-Vorgehen vermeidet. Aber dann muss es eben so sein...
-
volkard schrieb:
Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt.
Exakt. Wenn ihm +y ausreicht was ja offenbar dann doch nicht der Fall was...
-
volkard schrieb:
Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt. Nämlich
a b c d e f g h i j
und winkel(a,b,c) ist dumm
machste
d e f g h i j a b c
denn du darfst im kreis ja woanders anfangen
und dann
c b a j i h g f e d
und siehe da, der winkel (c,b,a) ist nicht mehr dumm.Das läuft ja im Prinzip auf meinen Trial-And-Error-Ansatz hinaus, bei dem ich immer den Startpunkt und die Reihenfolge variiere, bis rauskommt, was ich haben will.
-
dot schrieb:
volkard schrieb:
Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt.
Exakt. Wenn ihm +y ausreicht was ja offenbar dann doch nicht der Fall was...
Dann soll er endlich mal sagen, was seine Ausgangsdaten sind, zum Beispiel ob es Polygone oder Punktmengen (die ganz im Gegensatz zu Polygonen umsortiert werden dürfen) sind, und was das Ergebnis sein soll.
Bis er das geschafft hat, halte ich mich raus.
-
Warum überhaupt das rumprobieren. Bestimm einfach die Normale und wenn sie dir nicht passt extrudier in die andre Richtung!?
-
volkard schrieb:
dot schrieb:
volkard schrieb:
Und das ist immer so und soll immer so bleiben? Dann kannste Dir schon eine Sache ausdenken, daß dieses Kreuzprodukt immer nach +y zeigt.
Exakt. Wenn ihm +y ausreicht was ja offenbar dann doch nicht der Fall was...
Dann soll er endlich mal sagen, was seine Ausgangsdaten sind, zum Beispiel ob es Polygone oder Punktmengen (die ganz im Gegensatz zu Polygonen umsortiert werden dürfen) sind, und was das Ergebnis sein soll.
Bis er das geschafft hat, halte ich mich raus.Entschuldige bitte, aber das tue ich die ganze Zeit!
1. Ich habe nie von einer Punktewolke gesprochen. Es ist die ganze Zeit die Rede von einem Polygon, das sowohl konkav als auch konvex sein soll.
2. Ich habe inzwischen mindestens 4 Mal geschrieben, dass ich eine Normale in Richtung der positiven y-Achse haben will.
-
dot schrieb:
Warum überhaupt das rumprobieren. Bestimm einfach die Normale und wenn sie dir nicht passt extrudier in die andre Richtung!?
Das wiederum habe ich ebenfalls vor 4 oder 5 Posts geschrieben. Aber ich schreibs auch gerne noch mal, um mir nicht vorwerfen zu lassen, ich würde nicht sagen, was ich will.
1. Die Extrusion ist nur der erste Schritt einer Folge von Berechnungen, die auf die Normale aufbauen. Ich habe diese herausgezogen, da man sich unter "Extrusion" leichter etwas vorstellen kann.
2. In den nachfolgenden Berechnungen will ich mich darauf verlassen können, dass die Vertexorder derart gewählt ist, dass die Normalen so ausgerichtet sind, wie ich es will (ALSO: positive y-Achse). Da ich das aber nicht in jeder Berechnung hart coden will, will ich einmal die Vertexorder derart anpassen, dass sie in den nachfolgenden Berechnungen passt.
-
PatrickWG schrieb:
Das läuft ja im Prinzip auf meinen Trial-And-Error-Ansatz hinaus, bei dem ich immer den Startpunkt und die Reihenfolge variiere, bis rauskommt, was ich haben will.
Nur daß ich sicher nach dem ersten Test ankomme.
PatrickWG schrieb:
Habe es mit Sortierung zunächst nach y- dann nach x-Werten probiert,
Und es ist mit O(n) auch schneller als Sortieren mit O(n*log(n)). Und zufälliges Probieren ist so ungewiß. Würde aber auch funktionieren und recht schnell sein.
Es schien immer, daß Du meim Trial&Error eine zufällige Reihenfolge erzeugst und die testest. Daher die Punktmenge, die auf einmal eine Wolke ist. In Punktwolke steckt für mich schon wieder viel mehr Struktur als in Punktmenge. Und Reihenfolge und Umlaufsinn sind eben auch viel unterschiedlich. Das verwirrt mich.
-
volkard schrieb:
PatrickWG schrieb:
Das läuft ja im Prinzip auf meinen Trial-And-Error-Ansatz hinaus, bei dem ich immer den Startpunkt und die Reihenfolge variiere, bis rauskommt, was ich haben will.
Nur daß ich sicher nach dem ersten Test ankomme.
PatrickWG schrieb:
Habe es mit Sortierung zunächst nach y- dann nach x-Werten probiert,
Und es ist mit O(n) auch schneller als Sortieren mit O(n*log(n)). Und zufälliges Probieren ist so ungewiß. Würde aber auch funktionieren und recht schnell sein.
Es schien immer, daß Du meim Trial&Error eine zufällige Reihenfolge erzeugst und die testest. Daher die Punktmenge, die auf einmal eine Wolke ist. In Punktwolke steckt für mich schon wieder viel mehr Struktur als in Punktmenge. Und Reihenfolge und Umlaufsinn sind eben auch viel unterschiedlich. Das verwirrt mich.
Ok, ich verstehe deine Verwirrung. Ich wollte eben nicht die Reihenfolge der Vertices variieren (dann würde ich ja neue Polygone bauen), sondern nur das Startvertex von dem ausgehend ich die aufspannenden Vektoren berechne. Der Sortierungsansatz war drauf ausgerichtet, ein Vertex zu bekommen, das auf der konvexen Hülle liegt (eben um das Problem konkaver Polygone rauszubrechen). Dadurch erhoffte ich mir aufspannende Vektoren, die zu der Zielnormalen in y-Achsen-Richtung führen. Das war aber leider zu kurz gedacht und nicht von Erfolg gekrönt. Die konvexe Hülle war eben nur ein Zwischenschritt, das eigentliche Polygon muss natürlich unverändert bleiben. Aber wie du ja richtig schriebst, ist es egal, welchen Startpunkt ich als Ausgangspunkt für die Bestimmung der aufspannenden Vektoren verwende, an der Reihenfolge der eigentlichen Vertices ändert sich nichts (damit das Polygon erhalten bleibt).
Hoffe, das ist jetzt was klarer geworden?
-
PatrickWG schrieb:
Hoffe, das ist jetzt was klarer geworden?
Ich glaube, ja.
Vielleicht habe ich mich auch zu unklar ausgedrückt.
vector<Punkt> v;
//irgendwie die Punkte besorgen//Beispiel: a b c d e f g h i j
if(kreuzprodukt(b-a,c-b).y)>0)//wenn winkel gut ist
return;//winkel(a,b,c) ist dumm, denn wir haben nicht returnt
swap(v[0],v[2])
//c b a d e f g h i j
for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts)
swap(v[links],v[rechts]);
//c b a j i h g f e dDie neue Reihenfolge ist nicht geraten, sondern wird durch genau die drei Zeilen Code
swap(v[0],v[2]); for(size_t links=3,rechts=v.size()-1);links<rechts;++links,--rechts) swap(v[links],v[rechts]);zielsicher erzeugt.
Vielleicht gibt es noch günstigere Methoden, eine gute Reihenfolge zielsicher zu erzeugen. Aber nicht immer. Ein konvexes Polygon, daas dfalschrum ist, muß eben komplett umgedreht werden. Und es ist auch so schon recht schnell, unter anderem braucht nur ein einziges Kreuzprodukt berechnet zu werden.
