Frage Algorithmus zum Konvertieren von Scheitelpunkten eines dreieckigen Streifens in ein Polygon


Ich habe ein Array mit Scheitelpunkten, die einen dreieckigen Streifen darstellen. Ich muss es in Polygon umwandeln. Es gibt viele Lösungen, um das Umgekehrte zu tun, aber ich habe einen für das obige Problem nicht gefunden. Oder es könnte zu einfach sein und ich kann es einfach nicht sehen. Bitte helfen Sie.

OpenGL = kompatibel, siehe http://en.wikipedia.org/wiki/Triangle_strip

Beispiel: für diesen Streifen http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png Ich brauche Ausgabe A B D F E C oder A C E F D B


9
2017-08-20 14:09


Ursprung


Antworten:


Ich glaube, dass folgendes funktionieren sollte:

Gehe durch die Liste der Scheitelpunkte. Fügen Sie den ersten Punkt zu Ihrem Polygon hinzu. Drücken Sie den zweiten Punkt auf dem Stapel. Fügen Sie den dritten Punkt zum Polygon hinzu. Wechseln Sie abwechselnd zwischen den Punkten auf dem Stapel und fügen Sie sie dem Polygon hinzu, bis Sie das Ende der Liste erreichen. Wenn Sie an das Ende der Liste gelangen, blenden Sie die Punkte des Stapels und fügen Sie sie dem Polygon hinzu.


6
2017-08-20 14:47



alt text

Ich nehme an, dass dein Dreiecks-Streifen immer auf die gleiche Weise verbunden ist (was ich glaube, dass es für OpenGL gilt).

  • Die "unteren" Scheitelpunkte sind immer zwei getrennt: A, C, E, ...
  • Die Spitze" Vertices sind immer zwei voneinander entfernt: B, D, F, ...

Nimm die "untere" Liste und füge die Rückseite der "oberen" Liste an. (ACEFDB für das Beispiel)


Oder, direkter, mit einem nullbasierten Index anstelle von Buchstaben:

// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )

1
2017-08-20 15:00



Es kann eine Abkürzung geben, wenn Ihre Form eine besonders einfache Struktur hat, aber im Allgemeinen denke ich, dass Sie Folgendes tun möchten

  • Erstellen Sie eine Liste von Scheitelpunkten und Kanten aus Ihrer Liste von Dreiecken. Dies beinhaltet die Erkennung gemeinsamer Punkte (hoffentlich sind sie exakte Übereinstimmungen, so dass Sie sie durch Hashing finden können, anstatt eine unscharfe Suche zu benötigen) und geteilte Linien (das ist einfach - ziehen Sie einfach nicht zwei Kanten zwischen ein und demselben Paar gemeinsamer Punkte) .
  • Finde den oberen linken Punkt.
  • Finde die Kante, die so weit oben wie möglich verläuft und in Gegenuhrzeigerrichtung ist.
  • Gehe zum nächsten Eckpunkt.
  • Finde die nächste Kante, die sich auf der vorherigen so weit wie möglich verdoppelt.
  • Machen Sie weiter, bis Sie wieder den oberen linken Punkt treffen.

0
2017-08-20 14:23