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

Algorithmus für Polygonvertexorder mit konstanter Normalenausrichtung gesucht!

  • P

    Hallo zusammen,

    ich habe folgendes Problem. Ich habe eine Menge von Vertices, die ein Polygon (beliebiger Art) beschreiben. Nun möchte ich eine Ebene aus berechnen, die dieses Polygon vollständig enthält. Soweit so gut, kriege natürlich meine Ebene berechnet, indem ich 3 aufeinanderfolgende Vertices nehme, die Vektoren berechne und daraus das Kreuzprodukt bilde. Nun will ich aber durch die Anordnung bzw. Auswahl der Vertices erzwingen, dass ich immer die gleiche Ausrichtung erhalte.

    Beispiel:
    Ich habe eine Menge von Vertices in der XZ-Ebene. Berechne ich daraus eine Ebene, so soll deren Normale immer in Richtung der positiven y-Achse zeigen (was ich momentan bekomme, sind eben teilweise Ausreißer, die in Richtung der negativen y-Achse zeigen).

    Habe es mit Sortierung zunächst nach y- dann nach x-Werten probiert, allerdings hängt das Kreuzprodukt leider eben nicht nur von den Vorzeichen, sondern eben auch von den Absolutbeträgen ab, so dass mir eine solche Sortierung auch keine wirkliche Robustheit erbrachte.

    Vielleicht hat ja jemand von euch eine Idee, wie man das geschickt machen kann?

    Danke schon mal,
    Patrick

    0
  • H

    Ermittle die konvexe Huelle Deiner Punktmenge zB per Graham Scan.

    0

  • Wenn dein Polygon konkav sein kann ist das rein prinzipiell unmöglich da es der Definition von konkav entspricht dass Innenwinkel > 180° auftreten. Wenn dein Polygon immer konvex ist dann nimm einen beliebigen Vertex und sortier die restlichen Vertices nach dem Winkel zwischen einer fixen Richtung und dem Vektor zu diesem ersten Vertex.

    0
  • ?

    Es ist ohne weitere Infos generell unmöglich, die Orientierung eines im R³ liegenden Polygons zu bestimmen (wenn nur dessen unsortierte Eckpunkte bekannt sind). Worum geht's denn genau? wenn du mehrere Polys hast, wäre es möglich, diese mithilfe eines Minimum Spanning Trees zu verbinden und dann über den Minimum Spanning Tree eine konsistente Orientierung zu propagieren.

    Gruss, Jochen

    0
  • P

    Mein Ziel ist die Extrusion dieses polygonalen Grundrisses eben in genau der fixen Richtung des Normalenvektors der Ebene, die das Polygon enthält. Darum ist natürlich die Ausrichtung so entscheidend, da er mir sonst in die falsche Richtung extrudiert. Somit habe ich auch leider nur das eine Polygon zur Verfügung. Wobei ich aber nicht ganz genau verstehe, wie MSTs mir da helfen könnten?

    Vielleicht ist der Graham-Scan-Ansatz ein guter Ausgangspunkt, durch diesen bekomme ich ein garantiert konvexes Polygon. Anschließend nehme ich mir diese Punkte, wähle bsw. die x-Achse als Winkelreferenzgerade und sortiere, wie von dot vorgeschlagen. Wieso gararantiert mir das eine konstante Ausrichtung? Und welches Vertex wäre dann das Startvertex meiner umgestalteten Vertexorder?

    Viele Grüße,
    Patrick

    0

  • Und wie genau ist der Normalvektor dieser Ebene definiert?

    0
  • P

    Ich wähle ein Vertex aus, von dem ich Vektoren auf das Vorgänger- und Nachfolger-Vertex bestimme (die Vektoren spannen die Ebene auf) und von diesen Vektoren das Kreuzprodukt berechne.

    0

  • Gut, dann ist es eben so definiert, wenn das nicht ist was du haben willst musst du dir eine bessere Definition überlegen. Das Problem ist eben dass es nicht eindeutig ist und du offenbar selber nicht weißt was genau du haben willst oder zumindest nicht ausdrücken kannst. Für irgendwas musst du dich aber eben entscheiden. Kannst du nicht einfach voraussetzen dass der Benutzer die Vertices in der Reihenfolge angibt in der er sie haben will!?

    0
  • P

    Das Problem ist, dass die Polygone selber algorithmisch erstellt werden (u.a. auch durch Graham-Scan), somit gibts im eigentlichen Sinne keinen Nutzer, von dem ich eine feste Reihenfolge fordern könnte. Im Prinzip muss ich eben die Ergebnisse vorheriger Berechnungen derart aufbereiten, dass ich eben diese Ausrichtung für die weiteren Berechnungen zusichern kann. Im schlimmsten Fall muss ich eben so lange Anordnungen zufallsbasiert testen, bis ich eine treffe, die meinen Anforderungen entspricht, wenn es aber ein allgemeineres und eleganteres Verfahren gäbe, würde ich mir solche Brute-Force-Attacken gerne sparen.
    Wenn es aber auch aus mathematischer Sicht eben keine Möglichkeit gibt, sowas geschickt zu machen (meine Betrachtungen des Kreuzprodukts legten mir sowas nahe, wollte aber gerne andere Meinungen dazu hören), dann beuge ich mich natürlich, aber wie gesagt, würds gern besser lösen...

    0

  • PatrickWG schrieb:

    Im schlimmsten Fall muss ich eben so lange Anordnungen zufallsbasiert testen, bis ich eine treffe, die meinen Anforderungen entspricht, wenn es aber ein allgemeineres und eleganteres Verfahren gäbe, würde ich mir solche Brute-Force-Attacken gerne sparen.

    Was sind denn deine Anforderungen!? Das Problem ist ja offenbar dass du das nicht wirklich definieren kannst...

    0
  • V

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

    0
  • P

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

    0
  • 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
Anmelden zum Antworten