Visualisierung des Lane-Riesenfeld-Algorithmus

7

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

Geben Sie hier die Bildbeschreibung ein

Wir duplizieren jeden Punkt (gekennzeichnet durch den grauen Bereich)

Geben Sie hier die Bildbeschreibung ein

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

Geben Sie hier die Bildbeschreibung ein

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

Makogan
quelle

Antworten:

15

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 dupliziertP.ich in P.2ich' und P.2ich+1';; Verschieben Sie dann jeden Punkt zum Mittelpunkt zwischen ihm und dem nächsten PunktP.ich'12P.ich'+12P.ich+1'. Diese Schritte sind in der Abbildung dargestellt:

Eine Vervielfältigung und ein Bewegungsschritt

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 daranP.2ich'=P.2ich+1', aber P.2ich+1'P.2ich+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):

Zweiter Bewegungsschritt und neues Polygon

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:

Weitere Verfeinerungen des quadratischen B-Spline-Steuerpolygons

Hier ist eine Animation dieses Prozesses:

Animation des LR-Algorithmus zur Erzeugung eines quadratischen B-Spline

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:

Kubische B-Spline-Verfeinerung durch Dup-Move-Move-Move-Schritte

Eine Animation dieses Prozesses:

Animation des LR-Algorithmus zur Erzeugung eines kubischen B-Spline

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

BEARBEITEN : Animationen hinzugefügt.

Gilgamec
quelle
Obwohl dies eine klare Antwort ist, würde ich den Prozess gerne animiert sehen. Aber hey, wir sind Grafikprogrammierer, die nicht zu schwer sein sollten. Ich werde es morgen versuchen.
Jojaja
1
Mit welcher Software haben Sie dies gezeichnet / generiert?
Makogan
@Makogan Vielleicht möchten Sie in diesem Beitrag nach Ideen zum Zeichnen suchen . Obwohl die Wahl sehr persönlich ist.
Jojaja
1
@ Makogan Ich habe die Diagramme in Asymptote erstellt , was Open Source ist.
Gilgamec
1
@joojaa Ich habe Animationen der quadratischen und kubischen B-Spline-Erzeugung hinzugefügt.
Gilgamec