Wie funktioniert der Simple Stupid Funnel Algorithmus?

14

Ich bin mir nicht sicher, wie die Erkennung des Trichters funktioniert, wenn ich mit dem auf Digesting Duck gezeigten Trichteralgorithmus arbeite.

Kann mir jemand die Methode klar erklären oder eine alternative Methode zur Erkennung des Trichters vorschlagen und ob sich die Trichterseiten überlappen?

Rolfcore
quelle

Antworten:

18

Der Algorithmus beginnt mit einem zuvor gefundenen Pfad, in diesem Fall einer Liste von Dreiecken:

Pfad

Der Code am unteren Rand von Mikkos Blogbeitrag erstellt das Portals-Array, das eine Liste von Liniensegmenten darstellt, die die Liniensegmente zwischen den Polygonen des Pfades darstellen. Dies sind die "Portale", durch die der geglättete Pfad verlaufen muss (oder die Polygonkanten von "Verfolgen wir die Polygonkantenmittelpunkte"). Beachten Sie, dass die Portalliste mit degenerierten Liniensegmenten an den Start- und Zielpunkten beginnt und endet.

Diese Portalliste wird in seinen Bildern als gelb gepunktete Liniensegmente dargestellt.

Portale

Der Algorithmus beginnt mit einem breiten Trichter und fährt fort, indem die Trichterseiten iterativ entlang der Portalseitenpunkte (den Endpunkten der Liniensegmente) nach vorne bewegt werden, solange dies den Trichter festzieht (AD).

Algorithmus

Dies bedeutet, dass bei jeder Vorwärtsbewegung die Trichterkanten nach innen verschoben werden sollten. Dies kann anhand des Kreuzprodukts der Vektoren überprüft werden, die die alte Seite und die potenzielle neue Seite darstellen ( P × Q im Bild unten; siehe auch triarea2Mikkos Code). Wenn eine Bewegung nach vorne für eine Seite den Trichter nicht straffen würde, aktualisieren wir diese Seite nicht für die aktuelle Iteration der Portale (E).

nach innen bewegen

Der andere Fall, der behandelt werden muss, ist, wenn der Trichter zu einem Liniensegment ausartet. Um dies zu berücksichtigen, prüft der Algorithmus, ob sich eine der Seiten auf der "falschen" Seite befindet, indem er das Kreuzprodukt erneut verwendet, diesmal mit den Vektoren, die von der Trichterspitze und den Endpunkten der rechten und linken Seite erzeugt werden ( R × S in das Bild unten).

degenerierter Trichter

Ist dies der Fall, wird der Vektor von der Trichterspitze und dem korrekten seitlichen Endpunkt zum geglätteten Pfad ( R in der Abbildung oben) hinzugefügt und der Algorithmus mit seinem Endpunkt als neuer Spitze (FG) neu gestartet, sofern nicht Natürlich, wenn es der Zielpunkt ist.

Eric
quelle
2
@Rolfcore Ist die Antwort klar? Wenn nicht, welche Teile müssen verbessert werden?
Eric
Ich denke er hat einfach vergessen die Antwort zu akzeptieren, diese ist sehr gut und sollte seriell hochgestuft werden ^^.
GameDeveloper
Vielleicht ist das, wie ich gehört habe, dass Sie in Zug F nicht sagen, dass Sie nicht von vorne anfangen, da die Möglichkeit besteht, dass eine enge Ecke nach Süden einen engsten Trichter ermöglicht, sodass wir warten müssen, bis die Bot-Seiten tatsächlich ausfallen Test und nicht nur eine. Also machen wir das auf jeden
Fall