WaBis

walter.bislins.ch

JavaScript: Bezier-Segmente für Spline berechnen

Freitag, 1. Juli 2016 - 19:30 | Autor: wabis | Themen: Programmierung, Mathematik, Download
Auf meiner Blog-Seite Abstrakte Symbole und Schmuckvorlagen generieren werden zufällig Punkte generiert und eine Spline-Kurve durch diese Punkte gezeichnet. Die Spline-Kurve wird aus Bezier-Segmenten zusammengesetzt. Hier wird erklärt, was Splines und Bezier-Kurven sind und wie letztere aus dem Spline berechnet werden. Die enstprechenden JavaScript-Funtionen werden erklärt und zum Download zur Verfügung gestellt.

 Download: Media ComputeSplineCurve.js Info

Splines und Bezier-Kurven

Ein Spline n-ten Grades ist eine Funktion, die stückweise aus Polynomen höchstens n-ten Grades zusammengesetzt ist. Dabei werden an den Stellen, an denen zwei Polynomstücke zusammenstossen (ich nenne sie Stützpunkte), bestimmte Bedingungen gestellt, etwa dass der Spline (n-1)-mal stetig differenzierbar ist. Handelt es sich bei dem Spline um eine stückweise lineare Funktion, so nennt man den Spline linear. Es handelt sich dann um einen Polygonzug. Analog gibt es quadratische, kubische usw. Splines. [1]

Auf dieser Seite verwende ich Splines, die durch quadratische Bezier-Segmente stückweise zusammengesetzt sind. Da es unendlich viele Möglichkeiten von quadratischen Bezier-Segmenten gibt, welche die oben genannten Bedingungen erfüllen, muss eine Methode gefunden werden, eine dieser Möglichkeiten auszuwählen. Dazu dient ein Parameter Tension (Spannung), der steuert, wie fest abgerundet die Spline-Kurve an den Stützpukten ist. Wenn Tension = 0 ist, ist die Kurve an den Stützstellen nicht gerundet, d.h. es entstehen dort Ecken. Der Spline degradiert zu einem gewöhnlichen Polygonzug.

In der folgenden Animation sind die Spline- bzw. Bezier-Stützpunkte als gelbe Kreise und die Bezier-Kontrollpunkte als kleine Rechtecke eingezeichnet. Spiele mit dem grünen Schieberegler Tension und beobachte, wie sich die Kontrollpunkte und damit die Spline-Kurve ändert.

Ein quadratisches Bezier-Segment besteht aus zwei Stützpunkten und für jeden Stützpunkt je einem Kontrollpunkt. Die Kontrollpunkte bestimmen den Verlauf der Kurve zwischen den zwei Stützpunkten. Je zwei benachbarte Bezier-Segmente teilen sich einen Stützpunkt. Dieser gemeinsame Stützpunkt hat daher zwei Kontrollpunkte, je einen für die angrenzenden Bezier-Segmente. Damit die Kurve beim Stützpunkt keine Ecke hat, müssen diese Kontrollpunkte mit dem gemeinsamen Stützpunkt auf einer Linie liegen. Die Richtung dieser Linie hängt in unserem Fall von der Position der angrenzenden Stützpunkte ab.

Der Parameter Tension gibt an, wie weit die Kontrollpunkte auf dieser Linie vom Stützpunkt entfernt sein sollen. Je grösser der Parameterwert, umso weiter entfernt sind die Kontrollpunkte vom Stützpunkt und umso mehr schmiegt sich die Kurve an diesem Stützpunkt an die Linie an. Ein Wert von 0,5 ergibt eine ausgeglichene Kurve. Ein negativer Wert für Tension bewirkt, dass die Kotrollpunkte auf der Linie vertauscht sind. Dadurch macht die Kurve am Stützpunkt eine Schleife.

Die hier vorgestellte Funktion ComputeSplineCurve() nimmt ein Polygon mit Spline-Stützpunkten an und berechnet daraus eine Sequenz von Bezier-Segmenten mit den oben geschilderten Eigenschaften. Mit einem Grafik-Modul oder der HTML-Canvas-Funktionen bezierCurveTo() [2] können diese Bezier-Segmente dann gezeichnet werden.

Berechnung der Bezier Segmente aus dem Spline

Die Funktion ComputeSplineCurve() kann offene und geschlossene Spline-Kurven berechnen. Dies wird durch den Parameter closed gesteuert. Bei einer geschlossenen Spline-Kurve werden der erste und letzte Spline-Stützpunkt ebenfalls durch ein Bezier-Segment verbunden.

Zunächst wird ein Polygon für die Bezier-Segmente erstellt und mit den Spline-Stützpunkten so gefüllt, dass zwischen je zwei Stützpunkten Platz für die Bezier-Kontrollpunkte ist. Bei einem geschlossenen Spline müssen die ersten beiden Stützpunkte zusätzlich hinten an das Bezier-Polygon angehängt werden. Der erste zusätzliche Stützpunkt wird benötigt, um das Bezier-Segment vom Spline-Ende zum Sline-Anfang zu berechnen. Der zweite zusätzliche Stützpunkt wird für die Berechnung des letzten Kontollpunktes dieses Bezier-Segmentes und des ersten Kontrollpunktes des ersten Bezier-Segmentes benötigt, siehe Berechnung der Kontrolpunkte der Bezier Segmente.

function ComputeSplineCurve( splinePoly, tension, closed ) {

  // splinePoly: CPolygon = { X: array of number, Y: array of number, Size: integer }
  // splinePoly.Size defines the number of valid points in X, Y, ignoring further points.
  //
  // tension: number; curve parameter; 0.5 is a good value
  //
  // closed: boolean; true -> closed spline
  //
  // returns a new CPolygon of sequence: [ P0, C0b, C1a, P1, C1b, C2a, P2, C2b, C3a, P3, ... ]
  // where P0 and P1 are the endpoints and C0b and C1a are control points of the first bezier segment...
  // Note: the returned CPolygon.X.length may be greater than CPolygon.Size! Use only Size Points to draw!

  var splineSize = splinePoly.Size;
  if (splineSize <= 2) return null;

  // make bezier polygon in format: [ P0, C0b, C1a, P1, C1b, C2a, P2, C2b, C3a, P3, ... ]
  
  var bezierPoly = new CPolygon();
  var xSpline = splinePoly.X;
  var ySpline = splinePoly.Y;
  bezierPoly.AddPoint( xSpline[0], ySpline[0] );    // P0
  for (var i = 1; i < splineSize; i++) {
    bezierPoly.AddPoint( 0, 0 );                    // placeholder for C<i-1>b
    bezierPoly.AddPoint( 0, 0 );                    // placeholder for C<i>a
    bezierPoly.AddPoint( xSpline[i], ySpline[i] );  // P<i>
  }

  if (closed) {

    // closed spline: replicate first two points and add them to the end of bezierPoly
    
    bezierPoly.AddPoint( 0, 0 );
    bezierPoly.AddPoint( 0, 0 );
    bezierPoly.AddPoint( xSpline[0], ySpline[0] );
    bezierPoly.AddPoint( 0, 0 );
    bezierPoly.AddPoint( 0, 0 );
    bezierPoly.AddPoint( xSpline[1], ySpline[1] );

  } else {

    // open spline: set first and last bezier control point equal first and last spline point
    
    bezierPoly.X[1] = xSpline[0];
    bezierPoly.Y[1] = ySpline[0];
    var lastCP = bezierPoly.Size - 2;
    var lastSplineP = splineSize - 1;
    bezierPoly.X[lastCP] = xSpline[lastSplineP];
    bezierPoly.Y[lastCP] = ySpline[lastSplineP];

  }

  // compute bezier control points C<i>a and C<i>b for i from 1 to lastPivot
  // [ P0 C0b C1a P1 C1b C2a P2 ... P7 C7b C8a P8 C8b C9a P9 ]
  //               ^----firstPivot              ^----lastPivot
  
  var lastPivot = closed ? splineSize : splineSize - 2;
  ComputeBezierControlPoints( bezierPoly, tension, lastPivot );

  // closed spline: copy control point Cb of second last extra point (P8) to 
  // control point Cb of first point (P0) and cutoff last extra bezier segment
  //       v------------------------------+
  // [ P0 C0b C1a P1 ... P7 C7b C8a P8 | C8b C9a P9 ]
  
  if (closed) {
    var lastCP = bezierPoly.Size - 3;
    bezierPoly.X[1] = bezierPoly.X[lastCP];
    bezierPoly.Y[1] = bezierPoly.Y[lastCP];
    bezierPoly.Size -= 3;
  }

  return bezierPoly;
}

Berechnung der Kontrolpunkte der Bezier Segmente

Die Funktion ComputeBezierControlPunkts() [3] berechnet in einer Schleife für jeden Stützpunkt P<i> die zugehörigen zwei Kontrollpunkte C<i>a und C<i>b. Da der erste und letzte Stützpunkt jeweils nur einen einzigen Nachbar-Stützpunkt haben, können für diese beiden Punkte keine Kontrollpunkte berechnet werden. Diese werden in der übergeordneten Funktion bestimmt.

In Fig 1 sind die ersten drei Stützpunkte P0, P1 und P2 des Splines eingezeichnet. Den mittleren Stützpunkt bezeichne ich als Pivot-Punkt (Pivot = Gelenk). Die für den Pivot-Punkt P1 zu berechnenden Kontrollpunkte C1a und C1b sollen auf die Linie L1 zu liegen kommen. Die Linie L1 soll parallel zur Linie L02 sein, welche durch die Stützpunkte P0 und P2 geht.

Informationen zum BildFig 1
Informationen zum BildFig 2
Informationen zum BildFig 3

Die Abstände der beiden Kontollpunkte zum Punkt P1 sollen proportional zum Abstand der beiden Punkte P0 und P2, sowie proportional zu den Faktoren fa und fb sein. Diese beiden Faktoren werden ihrerseits proportional zu den Abständen der Stützpunkte d01 und d12 und dem Parameter Tension gewählt, siehe Fig 2.

fa = Tension * d01 / (d01 + d12)
fb = Tension * d12 / (d01 + d12)

Die X-Abstände der Kontrollpunkte zum Pivot-Punkt erhalten wir, wenn wir die Seite w des Dreiecks T mit fa respektive fb multiplizieren. Analog erhalten wir die Y-Abstände durch Multiplikation von fa und fb mit der Höhe h des Dreiecks T. Dies gilt, weil die Dreiecke Ta und Tb ähnlich zum Dreieck T sind, d.h. gleiche Winkel und gleiche Orientierung haben, siehe Fig 3.

w = P2[x] - P0[x]
h = P2[y] - P0[y]

Damit lassen sich die Kontrollpunkte einfach berechnen:

C1a[x] = P1[x] - fa * w
C1a[y] = P1[y] - fa * h
C1b[x] = P1[x] + fb * w
C1b[y] = P1[y] + fb * h

Wenn wir die Abstände der Kontrollpunkte so berechnen, skalieren sie mit der Grösse der Spline-Kurve. Da der Abstand der Kontrollpunkte vom Pivot-Punkt ebenfalls proportional zum Parameter Tension ist, kann mit diesem Parameter gesteuert werden, wie stark sich die Kurve an die Linie L1 anschmiegt.

Die Funktion ComputeBezierControlPoints() braucht somit bei jedem Schleifendurchgang je drei Stützpunkte. Der Stützpunkt, für den jeweils die zwei Kontrollpunkte berechnet werden, ist der Pivot-Punkt. Die anderen beiden Stützpunkte nenne ich den linken und rechten Stützpunkt.

Wenn die Funktion fertig ist, sind bis auf den ersten und letzten Kontrollpunkt in poly alle Kontrollpunkte berechnet. Der erste und letzte Kontrollpunkt wird dann von der aufrufenden Funktion ComputeSplineCurve() wiefolgt bestimmt:

  • Bei einem offenen Spline werden die Kontrollpunkt gleich dem benachbarten Stützpunkt gesetzt.
  • Bei einem geschlossenen Spline kann der letzte berechnete Kontrollpunkt an die Stelle des ersten Kontrollpunktes kopiert werden. Das dazu extra erstellte zusätzliche Bezier-Segment kann dann abgeschnitten werden. Das zweitletzte Beszier-Segment verbindet den Endpunkt mit dem Startpunkt des Splines.
function ComputeBezierControlPoints( poly, tension, lastPivot ) {

  // Computes Control Points C<i>a and C<i>b for quadratic Bezier segments.
  // Each pair of Control Points C<i>a, C<i>b is computed from points P<i-1>, P<i>, P<i+1>.
  // P<i> is called a pivot point. i ranges from 1 to <lastPivot> inclusive.
  //
  // poly: CPolygon = { X: array of number, Y: array of number, Size: integer }
  // poly Point Sequence is: 
  // [ P0, (C0b), C1a, P1, C1b, C2a, P2, C2b, C3a, P3, ..., P7 C7b C8a P8 C8b (C9a) C9 ]
  //    first Pivot-----^             ^----second Pivot                 ^----last Pivot
  //
  // Note: Control-Points in () can't be computed by this function.
  //
  // Note: places for control points C<i>a and C<i>b must already exist in poly.
  // lastPivot: index of last pivot point (not poly index but original spline point index).
  //
  // source Rob Spencer, July 2010: http://scaledinnovation.com/analytics/splines/aboutSplines.html
  // adapted by me (Walter Bislin) 2016: http://walter.bislins.ch/ 

  function LengthFor( side1, side2 ) {
    return Math.sqrt( side1 * side1 + side2 * side2 );
  }

  var fa, fb;
  var px = poly.X;
  var py = poly.Y;
  for (var i = 1; i <= lastPivot; i++) {
    var pivot = 3 * i;
    var left  = pivot - 3;
    var right = pivot + 3;
    var ca    = pivot - 1;
    var cb    = pivot + 1;
    var d01 = LengthFor( px[pivot] - px[left], py[pivot] - py[left] );
    var d12 = LengthFor( px[right] - px[pivot], py[right] - py[pivot] );
    var d = d01 + d12;
    if (d > 0) {
      fa = tension * d01 / d;
      fb = tension * d12 / d;
    } else {
      // note: d01 and d12 are also 0, so we are save if we set fa = fb = 0
      fa = 0;
      fb = 0;
    }
    var w = px[right] - px[left];
    var h = py[right] - py[left];
    px[ca] = px[pivot] - fa * w;
    py[ca] = py[pivot] - fa * h;
    px[cb] = px[pivot] + fb * w;
    py[cb] = py[pivot] + fb * h;
  }
}

Polygon Klasse

Die Klasse CPolgon wird für das Speichern der Spline-Stützpunkte und der Bezier-Segmente verwendet.

function CPolygon() {
  // Note: Arrays X and Y are probably larger then Size. 
  // Use Copy function to optain arrays of size this.Size.
  this.X = [];
  this.Y = [];
  this.Size = 0;
}

CPolygon.prototype.Reset = function() {
  // keep and reuse arrays!
  this.Size = 0;
}

CPolygon.prototype.AddPoint = function( x, y ) {
  // automatic enlarges arrays if array.length <= Size
  this.X[this.Size] = x;
  this.Y[this.Size++] = y;
}

CPolygon.prototype.Copy = function( first, last ) {
  first = (typeof(first) === 'number') ? first : 0;
  last  = (typeof(last)  === 'number') ? last  : this.Size - 1;
  var to = new CPolygon();
  for (var i = first; i <= last; i++) {
    to.AddPoint( this.X[i], this.Y[i] );
  }
  return to;
}

Spline zeichnen

Der folgende Code-Ausschnitt zeigt, wie die Funktion ComputeSplineCurve() angewandt wird. Zur Grafik-Ausgabe verwendet das Beispiel mein JsGraph Modul, welches intern HTML-Canvas-Funktionen wie bezierCurveTo() verwendet.

// Create some random spline points

function RandomSplinePoly() {
  var poly = new CPolygon();
  for (var i = 0; i < 6; i++) {
    poly.AddPoint( Math.random(), Math.random() );
  }
  return poly;
}

// draw gets called automatically from Graph2D Object created below

function Draw( g ) {
  g.SetWindowWH ( 0, 0, 1, 1 );

  var splinePoly = RandomSplinePoly();

  var bezierPoly = ComputeSplineCurve( splinePoly, 0.5, true );

  // draw each bezier segment
  var last = bezierPoly.Size - 1;
  for (var i = 0; i < last; i += 3) {
    g.BezierCurve(
      bezierPoly.X[i],   bezierPoly.Y[i],
      bezierPoly.X[i+1], bezierPoly.Y[i+1],
      bezierPoly.X[i+2], bezierPoly.Y[i+2],
      bezierPoly.X[i+3], bezierPoly.Y[i+3],
      1 // -> draw contour only, no filling
    );
  }
}

// create HTML-Canvas

NewGraph2D( {
  Width: '100%',
  Height: '100%',
  DrawFunc: Draw
} );


Quellen

Spline; Wikipedia
HTML5 Canvas Bezier Curve Tutorial; HTML5 Canvas Tutorials
http://www.html5canvastutorials.com/tutorials/html5-canvas-bezier-curves/
Spline interpolation; Rob Spencer, July 2010
http://scaledinnovation.com/analytics/splines/aboutSplines.html
Dein Kommentar zu diesem Artikel
Name
Email optional; wird nicht angezeigt
Kommentar
  • Name wird bei deinem Kommentar angezeigt.
  • Email ist nur für den Administrator, sie wird nicht angezeigt.
  • Du kannst deine Kommentare eine Zeit lang editieren oder löschen.
  • Du kannst Formatierungen im Kommentar verwenden, z.B: Code, Formeln, usw.
  • Externen Links und Bilder werden nicht angezeigt, bis sie der Admin freischaltet.
More Page Infos / Sitemap
Created Dienstag, 28. Juni 2016
Scroll to Top of Page
Changed Donnerstag, 24. März 2022