Visualisierung des Lane-Riesenfeld-Algorithmus

Ok, ich lese immer wieder Artikel darüber und keiner von ihnen hat Bilder. Der Spur-Riesenfeld-Algorithmus bietet eine Möglichkeit, Punktmengen mit B-Spline-Konvertierung zu unterteilen.

Die Frage ist einfach WIE? Wenn Sie mir eine Reihe von Bildern mit der Erklärung geben können, ist dies die beste Erklärung, mehr als die Mathematik.

Der erste Schritt (dh das Duplizieren der ursprünglichen Scheitelpunkte) scheint klar genug zu sein, aber ich verstehe nicht vollständig, wie die Mittelwertbildung im Mittelpunkt funktioniert.

Derzeit produziert mein sehr, sehr schlechtes Verständnis Folgendes:

Beginnend mit den folgenden 4 Punkten

Wir duplizieren jeden Punkt (gekennzeichnet durch den grauen Bereich)

Wir nehmen alle ungeraden Punkte in unserem neuen Satz und verschieben sie in die Mitte der Linie, die zwei aufeinanderfolgende Punkte verbindet:

Was mache ich jetzt? Von hier an bin ich einfach völlig verloren

Der Lane-Riesenfeld-Algorithmus unterteilt das Steuerpolygon eines B-Splines, um ein neues Steuerpolygon mit demselben Grenzwert-Spline zu erstellen. Es besteht aus zwei Schritten: Erstens werden alle Kontrollpunkte dupliziert$P_i$ in $P^\prime_{2i}$ und $P^\prime_{2i+1}$;; Verschieben Sie dann jeden Punkt zum Mittelpunkt zwischen ihm und dem nächsten Punkt$P^\prime_i \rightarrow \frac{1}{2} P^\prime_i + \frac{1}{2}P^\prime_{i+1}$. Diese Schritte sind in der Abbildung dargestellt:

Links befindet sich ein anfängliches Steuerpolygon. In der Mitte habe ich die Eckpunkte dupliziert. Rechts haben sich die Scheitelpunkte auf halbem Weg zum nächsten Scheitelpunkt bewegt. Beachten Sie, dass sich im ersten Bewegungsschritt nur die Hälfte der Eckpunkte bewegt: Dies liegt daran$P^\prime_{2i} = P^\prime_{2i+1},$ aber $P^\prime_{2i+1} \neq P^\prime_{2i+2}.$ Diese acht Eckpunkte sind ein verfeinertes Steuerpolygon für den linearen B-Spline, der durch die ersten vier Eckpunkte definiert wird.

Jetzt können wir einen zweiten Bewegungsschritt ausführen (ohne eine weitere Verdoppelung):

Links haben wir jeden Scheitelpunkt auf den Mittelpunkt zwischen ihm und seinem Nachbarn verschoben. Beachten Sie, dass sich diesmal alle Scheitelpunkte bewegen (da sich keine an derselben Position befinden). Rechts haben wir das Polygon mit diesen acht Eckpunkten gezeichnet. Dies ist ein verfeinertes Steuerpolygon für den quadratischen B-Spline, der durch die ersten vier Eckpunkte definiert wird. Sie können dies auch als das gleiche Polygon erkennen, das Sie durch Chaikin-Eckenschneiden erhalten, wodurch Sie auch den quadratischen B-Spline erhalten.

Jetzt können wir weitere Schritte zum Duplizieren, Verschieben und Verschieben ausführen, um das Polygon weiter zu verfeinern und damit die quadratische B-Spline-Kurve näher zu approximieren:

Hier ist eine Animation dieses Prozesses:

Wenn wir stattdessen einen dritten Bewegungsschritt ohne einen Duplikationsschritt ausführen (dh eine Duplizierung gefolgt von drei aufeinanderfolgenden Bewegungen), erhalten wir ein verfeinertes Steuerpolygon für den kubischen B-Spline, der durch die ersten vier Eckpunkte definiert wird:

Eine Animation dieses Prozesses:

Im Allgemeinen tun $k$ Bewegungsschritte nach jedem Duplikat geben uns das verfeinerte Polygon für das $C^k$ B-Spline.

BEARBEITEN : Animationen hinzugefügt.