4. Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!

Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!

  • V

    PatrickWG schrieb:

    Meine Anforderung ist, dass der Vektor der Ebene immer in Richtung positiver y-Achse zeigt. Polygon in XZ, Normale in Richtung positiver y-Achse.

    Nach dem Graham-Scan zeigen alle Kreuzprodukte aufeinanderfolgender Kantenvektoren in die selbe Richtung, dachte ich. Also alle in positiver y-Richtung oder alle in negativer y-Richtung. Ist das so? Wenn ja, brauchste ja nur im Negativfall den Umlaufsinn zu ändern.

    0
  • P

    volkard schrieb:

    Nach dem Graham-Scan hast Du doch schon gewonnen und die Kanten werden im selben Drehsinn weitergedreht.

    Der Drehsinn reicht leider nicht aus (wobei ich auch nicht verstehe, warum das genau der Fall ist). Würde es nur vom Drehsinn abhängen, so müsste eine Umkehr der Polygonvertexorder ja logischerweise auch zu einer gedrehten Normale führen. Dies ist auch meist der Fall, aber eben nicht immer! Tatsächlich habe ich aktuell einen Testcase, bei dem in der ursprünglichen und gedrehten Reihenfolge die gleiche Normale ensteht...

    0
  • V

    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.

    0

  • Wenn deine Polygone nicht auf konvexe Polygone beschränkt sind ist das unmöglich, das hilft kein Graham Scan und gar nix. Ein konkaves Polygon hat per Definition beide Richtungen da kannst du sortieren wie du willst, es wird immer Stellen geben wo sich die Richtung umkehrt. Und wenn dein Polygon konvex ist brauchst du sowieso keinen Graham Scan...

    PatrickWG schrieb:

    Meine Anforderung ist, dass der Vektor der Ebene immer in Richtung positiver y-Achse zeigt. Polygon in XZ, Normale in Richtung positiver y-Achse.

    Und was ist mit Polygonen deren Normale eine y-Koordinate von 0 hat?

    0
  • P

    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.

    0
  • P

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

    0

  • 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!?

    0
  • P

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

    0

  • 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!?

    0
  • P

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

    0

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

    0
  • P

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

    0

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

    0
  • V

    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.

    0
  • P

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

    0

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

    0
  • P

    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.

    0
  • V

    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.

    0

  • Warum überhaupt das rumprobieren. Bestimm einfach die Normale und wenn sie dir nicht passt extrudier in die andre Richtung!?

    0
  • P

    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.

    0
Anmelden zum Antworten