Bézier, oder: Wie bringe ich jemanden locker um die Ecke

Ein Objekt oder ein Sprite von A nach B zu bewegen, sollte die meisten von uns nicht vor sonderlich große Herausforderungen stellen. Ein Objekt von A nach B über C und D zu bewegen ist schon ein klein wenig schwieriger, aber auch problemlos zu schaffen. Und an dieser Stelle beginnt es auch schon interessant zu werden. Das Objekt bewegt sich allenfalls wie die von Kraftwerk besungenen Roboter aus einer Zeit, in der Prozessoren noch deutlich weniger als 100Mhz hatten. Eckig und unsanft ist das Stichwort und das möchte ich mit diesem kleinen Grundlagenartikel ändern.

Ich möchte in diesem Beitrag nicht auf die graue, mathematische Theorie einer Bézier-Kurve eingehen, da dies für die meisten von uns auch eher uninteressant sein dürfte. Diese Erklärung laut Wikipedia sollte ausreichen:

Die Bézierkurve ist in der numerischen Mathematik eine parametrisch modellierte Kurve, die ein wichtiges Werkzeug für Vektorgrafiken darstellt.

Also eine Kurve, deren Definition sehr, sehr kompliziert klingt und die es sicherlich auch ist. Citröen hat diese „Erfindung“ in den 60er fast 10 Jahre lang geheim gehalten um anderen keinen Wettbewerbsvorteil zu verschaffen. Jedenfalls ist im Wiki-Artikel ausführlich beschrieben, wie solche Kurven funktionieren und auch einiges über deren Herleitung zu erfahren. Für uns ist dies recht uninteressant, denn wir wollen nur mit den Kurven arbeiten…

Kurven sind natürlich bestens geeignet, um etwas weich zu bewegen, vor allem wenn das Ziel ist, eine eckige Bewegung zu vermeiden. Im weiteren Verlauf werden wir exakt dies lernen. Im folgenden Bild habe ich versucht dies ein wenig zu verdeutlichen. Im linken Bereich ist ein eckiger Pfad, der nicht sonderlich natürlich aussieht, wenn wir ein Sprite an diesem Pfad entlang bewegen würden. Auf der rechten Seite sehen wir ein Beispiel für eine Bézier-Kurve, die bereits viel natürlicher und vor allem weicher aussieht.

Beide Pfade wurden durch 4 Kontrollpunkte definiert. Bei der Bézier-Kurve sieht man jedoch, dass lediglich der erste und der letzte Punkte auf der Kurve liegen und die anderen beiden nicht. Dies wird im folgenden Bild noch etwas deutlicher. Dieses Bild werde ich im weiteren Verlauf für alle Erklärungen verwenden.

P0 ist also der Startpunkt unserer Kurve und P3 ist der Endpunkt. P1 und P2 sind die beiden Kontrollpunkte mit denen wir die Krümmung und den Verlauf beeinflussen können.

Um nun den Verlauf der Kurve zu berechnen, benötigen wir folgende Formel:

P(t) = (1-t)^3P0 + 3(1-t)^2tP1 + 3(1-t)t^2P2 + t^3P3

Die neu aufgetauchte Variable t legt die Position auf der Kurve fest, die wir berechnen möchten. t = 0.0 ist dabei P0, also der Startpunkt und t = 1.0 ist der Endpunkt P3. Lassen wir also die Variable t in einer Schleife von 0 bis 1 laufen, so erhalten wir für jeden Zwischenschritt einen Punkt, der exakt auf der Kurve liegt. In Code gegossen sieht das ungefähr so aus:

        public Vector2 GetPoint(float t)
        {
            float cx = 3.0f * (P1.X - P0.X);
            float cy = 3.0f * (P1.Y - P0.Y);
            float bx = 3.0f * (P2.X - P1.X) - cx;
            float by = 3.0f * (P2.Y - P1.Y) - cy;
            float ax = P3.X - P0.X - cx - bx;
            float ay = P3.Y - P0.Y - cy - by;
            float s = t * t;
            float c = t * s;
            float rX = (ax * c) + (bx * s) + (cx * t) + P0.X;
            float rY = (ay * c) + (by * s) + (cy * t) + P0.Y;

            return new Vector2(rX, rY);
        }

Das Gleiche funktioniert auch für den 3D-Fall indem man schlicht und einfach die Z-Koordinate auf die gleiche Art und Weise berechnet wie die beiden anderen Koordinaten.

Das Problem dabei ist, dass diese Art von Kurven relativ schwierig zu kontrollieren ist, insbesondere, wenn man mehrere Kurven dieser Art hintereinander verwenden möchte, um noch mehr Flexibilität zu erlangen. Anders als in meinem Artikel „Spielend Lernen“ vorgeschlagen, macht es an dieser Stelle absolut Sinn einen Editor zu entwickeln, mit dem man Bézier-Kurven und -Pfade schnell und einfach erzeugen kann. Dies ist nicht weiter schwer und schnell erledigt. Ich werde in diesem Artikel nicht darauf eingehen, wie dieser Editor entwickelt wird, da ich mir das für die Folgeartikel „FiniteStateMachine“ und „Game-Editor – ein praktisches Beispiel anhand von Bézier-Pfaden“ aufheben möchte, ich werde trotzdem an dieser Stelle bereits ein paar Tipps geben, falls der ein oder andere jetzt bereits loslaufen möchte und nicht auf die Folgeartikel warten möchte.

Um einen Editor zu entwickeln benötigt man eine Möglichkeit Punkte zu verschieben, neue Punkte zu setzen und Punkte zu löschen. Um einen Pfad zu erzeugen sollte man folgende Regeln beachten:

  • Der Endpunkt P3 ist mit dem Startpunkt P0 des Folgeelements immer Deckungsgleich
  • Der Kontrollpunkt P2 muss mit dem Kontrollpunkt P1 des Folgeelements, sowie dem Endpunkt P3 und dem Starpunkt P0 des Folgeelements auf einer Geraden liegen.
  • Wird der Start- oder Endpunkt bewegt, so müssen die abhängigen Kontrollpunkte um das gleiche Delta bewegt werden.
  • Wird einer der Kontrollpunkte bewegt, so muss Segmentübergreifend sichergestellt sein, dass die anderen Regeln eingehalten werden.

Und schon sind wir am Ende dieses ersten Artikels angelangt. Wie versprochen: Keine Mathematik und damit ist dieses Thema lediglich ein kleines Stückchen Code, dass man immer wieder verwenden kann um weiche Bewegungen zu erzeugen. Wie bereits angedeutet habe ich mindestens zwei weitere Artikel geplant mit dem Ziel zu erläutern, wie man einen einfachen, aber effektiven Editor für Bézier-Pfade bzw. Kurven entwickelt. Im nächsten Artikel werde ich auf ein wenig mehr Theorie eingehen und erklären, was es denn mit „Finite-State-Machines“, also endliche Zustandsautomaten auf sich hat. Diese finden häufig in der Spieleentwicklung Anwendung, sind aber auch extrem gut geeignet, um eine Editoranwendung einfacher und effektiver zu entwickeln. Im abschliessenden Artikel werde ich die FSM, sowie die Kurve aus diesem Artikel zu einem kleinen, aber feinen Editor vervollständingen.

Advertisements

Veröffentlicht am 09.05.2011 in Algorithmen, Grundlagen, XNA und mit , , , , , , getaggt. Setze ein Lesezeichen auf den Permalink. 4 Kommentare.

  1. Netter Blog, gefaellt mir sehr gut. Auch gute Themen.

  2. Schönes Beispiel. Der Vollständigkeit halber möchte ich noch kurz erwähnen, dass es auch eine Variante gibt, um die Krümmung der Linie durch die Kontrollpunkte P1 und P2 zu leiten. In der Tweening-Bibliothek TweenMax für Flash wird das als BezierThrough bezeichnet, allerdings weiß ich nicht, wie die richtige Bezeichnung dieses Verfahrens ist.
    Diese Variante ist in einem grafischen Editor vielleicht nicht so wichtig, ist aber meiner Meinung nach bei manchen Anwendungsfällen, in den die Kurve von Hand programmiert werden muss, etwas komfortabler.

    • Danke sehr 🙂

      Ja, das gibt es tatsächlich auch Kurven, die direkt durch die Punkte gehen. Das Problem ist aber bei diesen Kurven, dass diese schlicht und einfach durch alle Kontrollpunkte und den Start/Endpunkt gehen müssen. Dabei ist aber nicht definiert wie sich die Krümmung verhält bzw. man hat keinerlei direkte Kontrolle darüber. Wenn man die Punkte nah beeinander hat, dann entstehen schnell sehr schmale, aber dafür steile Parabelartige Kurven. Das Problem wird noch deutlich größer, wenn man viele Kontrollpunkte hat…

      Es gibt auch noch Nurbs und B-Splines, die ebenfalls handlich sind.

  1. Pingback: Zustandsautomaten – Finite State Machine (FSM) « "Mit ohne Haare"

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: