✔ [C++]Polygonerstellung, CCW-Sortierung von Punkten

[Sp3iky]

Hallo!

Habe hier ein Problem, bei dem mir einfach keine gescheite Lösung einfallen will. Es geht um folgendes:

Ich rendere eine Box bestehend aus 6 Polygonen. Diese Box schneide ich mit der Near Plane, um die Schnittpunkte zu erhalten. Diese Punkte benötige ich, um das durch Clipping entstandene Loch wieder zu schließen, indem ich mir aus den berechneten Schnittpunkten ein neues Polygon bastele.

Die Schnittpunkte habe ich. Mein Problem liegt nun darin sie entgegengesetzt dem Uhrzeigersinn zu sortieren, damit ein zu mir zeigendes Polygon dabei heraus kommt und kein Murks.

Mein bisheriger Ansatz war es, den Mittelpunkt der Schnittpunkte zu berechnen und dann Vektoren von diesem zu den jeweiligen Schnittpunkten zu bilden. Im Anschluss nehme ich mir einen Vektor als "Ursprung" und berechne mir den Winkel zu den anderen Vektoren.
Das Problem hierbei ist aber, dass ich sowohl mit dem Kosinus(Skalarprodukt), als auch mit dem Sinus(Kreuzprodukt) doppelte Werte bekomme, da diese ja periodisch sind und ich somit nur bis 180 Grad Werte bekomme...

Hat jemand eine Idee, wie ich diese Punkte in die richtige Reihenfolge bekomme?

 

[Cromon]

Wie sind denn deine Punkte definiert? Eine Ebene geschnitten mit einer Fläche hat doch im nicht entarteten Fall unendlich viele Schnittpunkte?

 

[Sp3iky]

Um genau zu sein, schneide ich die Polygonkanten mit der Ebene, da ich ja die geclippten Polygone haben möchte und dafür nur die neuen Schnittpunkte brauche.

Ich habe also je nach Lage der Ebene 3-6 Schnittpunkte, welche ich nun so sortieren muss, dass ich daraus in OpenGL ein Polygon definieren kann.

 

[Cromon]

Also grundsätzlich solltest du die worldViewProj-Matrix mal verwenden um alle deine Punkte zu transformieren in die 2-dimensionale Oberfläche. Das ist dann nämlich auch der verlässlliche Ausgangspunkt für die Berechnung des Uhrzeigersinns.

Anschliessend nimmst du als Usprung des Koordinatensystems den Mittelpunkt der x-Achse und y-Achse deines Buffers. Damit kannst du dann alle Punkte katalogisieren in einen der 4 Quadranten und dann da den Winkel über das Skalarprodukt zu einer der beiden Achsen berechnen. Grundsätzlich würde schon eine Unterteilung in nur eine Richtung reichen, da der cosinus, den dir das Skalarprodukt liefert auf [0, pi] bijektiv ist.

 

[Daniel76]

Hab mir dein Problem mal überlegt, eine interessante Aufgabe, aber nicht ganz einfach (für mich zumindest : ).
Ich würde das ganze kantenbasiert lösen, nicht punktbasiert, weil es dafür eine einfachere und fehlersichere Methode gibt.
Anfangsüberlegungen:

* Die Schnittfläche(Schnittpolygon) eines Quaders(Box) hat 3 oder 4 Eckpunkte.

Nehmen wir den nichttrivialen 4-Schnittpunkte-Fall.
Die Schnittpunkte seien gemäß deiner Aufgabenstellung bereits bekannt.
Jetzt betrachte ich das Problem aus der Sicht der Kanten:

* Es gibt 4 Schnittkanten mit je 2 Punkten(Schnittpunkten), also insgesamt 8 Schnittpunkte,
wobei aber jeweils 2 deckungsgleich sind. Kannst du mir soweit folgen?

Jetzt musst du die Kanten nur noch aneinanderfügen, so entsteht ein umlaufender Kantenzug, oder auch Polygon genannt. Schritte:

* Erzeuge neue, leere Kantenliste L
* Du beginnst mit einer beliebigen Kante K

Start:
* Kante K als besucht markieren und in Kantenliste L einfügen
* Wähle einen Punkt P der Kante K
* Finde eine unbesuchte Nachbarkante K2 (sie muss einen zu P deckungsgleichen Punkt besitzen)
* Falls K2 gefunden:
Wechsle zur Nachbarkante mit K = K2, Gehe zu Start

In Liste L steht nun der Kantenzug des gesuchten Polygons.
Nun die Punkte noch auf Uhrzeigersinn testen (z.B. mithilfe des Vektorprodukts der ersten 3 Punkte)
und ggf. die Liste spiegeln. => Fertig

 

[Sp3iky]

So noch eine kurze Rückmeldung.

Danke für die Tipps, besonders an Daniel76. Hat perfekt funktioniert. Hatte die doppelten Punkte schon beim Hinzufügen aussortiert, weshalb ich gar nicht auf die Idee kam, dass ich ja die Kanten betrachten könnte, womit ich dann zusätzliche Informationen zu jedem Punkt habe.

 

[Daniel76]

Schön ^.^ Hätt' nicht gedacht, daß es gleich so funktioniert, aber du hast den Algorithmus bestimmt noch an dein Problem angepasst so dass es wirklich läuft oder?
Die Kernidee war wirklich das ganze Kantenbasiert anzugehen, dann tut man sich wesentlich leichter bei der Lösung.
Hab vergessen zu erwähnen, daß man die Kanten vor dem Einfügen in die Liste ggf. auch noch umdrehen(spiegeln) muss, damit die Eckpunkte wirklich umlaufend aneinander passen.

 

[Sp3iky]

Ich hab die Kanten einfach in Vektoren gespeichert und alle Kanten dann in einem Gesamtvektor. Habe mir eine Kante genommen, diese aus dem Gesamtvektor geschmissen, einen Punkt daraus genommen und nach dem anderen in den restlichen Kanten gesucht (bzw. bei nur einem Punkt auch nach diesem gesucht). Wenn ich den Punkt gefunden hab, wird er meiner Polygonliste hinzugefügt und der andere Punkt der Kante ist der neue Suchvektor. Die Kante wird dann wieder aus dem Gesamtvektor raus geschmissen. Das mache ich so lange, bis dieser leer ist.

Zum Schluss muss ich nur noch das Kreuzprodukt berechnen und die Vorzeichen des entstandenen Richtungsvektors mit der Normalen der Schnittebene vergleichen und gegebenenfalls die Reihenfolge umkehren. Am Ende einfach per GL_POLYGON gezeichnet.

 

[Daniel76]

find ich großartig!
Vielleicht noch als Ergänzung, die Methode ist allgemein und sollte daher nicht nur für Quader, sondern auch für komplexere Polyeder(Körper) funktionieren, solange die Schnittfläche zusammenhängend ist. Der Algorithmus ist auch nicht so optimal von der Laufzeit her, wegen der quadratischen Komplexität (n*n durch die Kantensuche);
Wird z.B. ein Kegel mit einer Mantelfläche aus 100 Facetten geschnitten, kann die Berechnung der Schnittfläche bis zu 5000 Iterationen dauern.
(Sortierungs- und Suchprobleme lassen sich im Grunde immer mit n*log Laufzeit lösen, aber dann häufig auf Kosten der Einfachheit des Verfahrens)