An die Mathematiker: Länge einer Bezierkurve?

[Lebostein]

Hi,

ich benutze für ein Spiel eine Pfadsteuerung, die auf Bezierkurven aufbaut. Ich verwende Bezierkurven mit 4 Punkten (Start- und Endpunkt sowie 2 Stützstellen, siehe hier zum Beispiel: http://www.purearea.net/pb/CodeArchiv/G ... rCurves.pb)
Gibt es eine Möglichkeit, die exakte Länge einer solchen Kurve zu berechnen?

[Froggerprogger]

Hi!
Das wird verflixt kompliziert, wenn Du das Ergebnis wirklich exakt haben willst! Die Mathematik dahinter ist echt böse: Du musst die Länge des Weges des Bezierpolynoms (als parametrisierte Funktion aufgefasst) anhand der Formel

Code: Alles auswählen

t -> integral(abs(F'(t) dt))

in den entsprechenden Grenzen für t auffassen. Das sieht noch fast einfach aus, aber gerade das Parametrisieren macht das Ganze dann enorm unhandlich. Ich habe es gerade versucht durchzurechnen, komme da aber nicht wirklich weiter.

Viel einfacher wäre es, die Länge lediglich zu approximieren. Wenn du Bezierkurven mit nur wenig Punkten nutzt, dann ist die Approximation auch sehr schnell sehr gut.
Also einfach in der Hauptschleife der Bezier-Procedure:

Code: Alles auswählen

  While i.f < 1 
    i+0.05 
    x=((ax*i+bx)*i+cx)*i+x1 
    y=((ay*i+by)*i+cy)*i+y1 
    If i>0: LineXY(oldx,oldy,x,y,color) : EndIf 
    oldx=x 
    oldy=y 
  Wend

anstelle die Linien zu zeichnen die Längen der Linien aufsummieren.
Also sowas:

Code: Alles auswählen

Procedure.f bezierlength(x1,y1,x2,y2,x3,y3,x4,y4,approx.f)  
  Protected length.f, i.f
  oldx=x1 
  oldy=y1 
  cx.f=3*(x2-x1) 
  bx.f=3*(x3-x2)-cx 
  ax.f=x4-x1-cx-bx 
  cy.f=3*(y2-y1) 
  by.f=3*(y3-y2)-cy 
  ay.f=y4-y1-cy-by 
  length = 0.0
  While i.f < 1 
    i+approx
    x=((ax*i+bx)*i+cx)*i+x1 
    y=((ay*i+by)*i+cy)*i+y1 
    If i>0
      length = length + Sqr(Pow(x-oldx, 2) + Pow(y-oldy, 2))
    EndIf
    oldx=x 
    oldy=y 
  Wend
  ProcedureReturn length
EndProcedure 

Aufruf dann mit

Code: Alles auswählen

bezierlength(x1,y1,x2,y2,x3,y3,x4,y4,0.05)

Die 0.05 gibt hier die Approximationsgüte an. Wenn man da dieselbe nutzt, wie für das Zeichnen (0.05), dann hat man auf jedenfall schon eine sehr gute - da pixelgenaue - Näherung.
Die Länge wird hier jetzt in Pixellänge des Gesamtweges zurückgegeben.

Ich denke mal, die Approximation reicht sicherlich für alle möglichen Zwecke aus und dürfte sogar fixer sein, als das Berechnen einer exakten abgefahrenen Riesenformel (wenn man sie denn hätte...).

[Lebostein]

Danke, hab mir fast sowas gedacht, dass es kompliziert sein würde. Dann werd ich wohl doch auf den einfachen und schnellen Weg übergehen, an den ich auch schon gedacht habe. Das mit den einzelnen Kurvenstücken ist sogar noch besser, da ja das Objekt, das später auf der Kurve wandert, eine konstante Geschwindigkeit haben soll und man das ganze so besser steuern kann.

PS: Dann ist sicher auch die Tangente an die Kurve bzw. der Winkel an einem bestimmten Punkt (für die Ausrichtung der Figur) schwer zu berechenen, oder?

[Froggerprogger]

Die Tangentensteigung in Abhängigkeit von i ist nicht schwierig, dafür braucht man nur die Ableitung nach i:

Code: Alles auswählen

x = ((ax*i+bx)*i+cx)*i+x1 
y = ((ay*i+by)*i+cy)*i+y1 

abgeleitet liefert:

difX = cx + i * (bx + ax * i) + i * (bx + 2 * ax * i)
difY = cy + i * (by + ay * i) + i * (by + 2 * ay * i)

Für die exakte Länge müsste man davon nun die Norm bilden (also sqr(difX^2+ difY^2) und das Ergebnis dann in t=0..1 integrieren.

Hier mal der erweiterte Original-code.
Der zeigt nun eine Tangente an, wobei deren Position und die Approximationsgüte der Kurve einstellbar ist:

Code: Alles auswählen

; Bezier-curves
; based on source by Rob, extended functionality by Froggerprogger
; 19.07.05

cw = RGB(255,255,255) 
cr = RGB(255,0,0) 

Procedure bezier(x1,y1,x2,y2,x3,y3,x4,y4, color, smoothness.f, tangentePos.f) 
  ; smoothness in ]0,1] : gives the approximation, typical ~= 0.05
  ; tangentePos in ]0,1[ : gives the point where to draw the tangent

  oldx=x1 
  oldy=y1 
  cx.f=3*(x2-x1) 
  bx.f=3*(x3-x2)-cx 
  ax.f=x4-x1-cx-bx 
  cy.f=3*(y2-y1) 
  by.f=3*(y3-y2)-cy 
  ay.f=y4-y1-cy-by 
  
  tangente = #False
  While i.f < 1.0
    i+smoothness
    x=((ax*i+bx)*i+cx)*i+x1 
    y=((ay*i+by)*i+cy)*i+y1 
    If i>0
      If i < 1.0 - smoothness
        LineXY(oldx,oldy,x,y,color)
        length = length + Sqr(Pow(x-oldx, 2) + Pow(y-oldy, 2))
      Else
        LineXY(oldx,oldy,x4,y4,color)
        length = length + Sqr(Pow(x4-oldx, 2) + Pow(y4-oldy, 2))
        i = 1.0
      EndIf
    EndIf 
    If i>=tangentePos And tangente = #False: 
      difX = cx + i * (bx + ax * i) + i * (bx + 2 * ax * i)
      difY = cy + i * (by + ay * i) + i * (by + 2 * ay * i)
      LineXY(x-difX,y-difY, x+difX, y+difY, RGB(100,100,100)) 
      tangente = #True
    EndIf
    oldx=x 
    oldy=y 
  Wend
  
  FrontColor(255,255,255)
  DrawingMode(1)
  Locate(10,10)
  DrawText("length: " + StrF(length)) 
  Locate(10,30)
  DrawText("tangent-gradient (x/y): " + StrF(difX) +" / " + StrF(difY))
  Locate(10,50)
  DrawText("tangent-position (%): " + StrF(tangentePos * 100) + "  <Up/Down>")
  Locate(10,70)
  DrawText("smoothness: " + StrF(smoothness) + "  <Left/Right>" )
EndProcedure 

InitSprite() 
InitKeyboard() 
InitMouse() 

If OpenScreen(1024,768,32,"Bezier") = 0
  If OpenScreen(1024,768,24,"Bezier") = 0
    If OpenScreen(1024,768,32,"Bezier") = 0
      End
    EndIf
  EndIf
EndIf

MouseLocate(100,100)
x1=100 : y1=100 
x2=924 : y2=100 
x3=100 : y3=668 
x4=924 : y4=668

smoothness.f = 0.05
tangentePos.f = 0.5

key = 1 

Repeat 
  ExamineKeyboard() 
  ExamineMouse() 
  
  ; change points 
  If MouseButton(1) And mousepush=0 ; rotate points: 1-4 
    key = (key % 4) + 1 
    If key=1 : MouseLocate(x1,y1) : EndIf 
    If key=2 : MouseLocate(x2,y2) : EndIf 
    If key=3 : MouseLocate(x3,y3) : EndIf 
    If key=4 : MouseLocate(x4,y4) : EndIf 
  EndIf 
  mousepush=MouseButton(1) 

  StartDrawing(ScreenOutput()) 
  DrawingMode(4) 
  ; draw points
  If key=1 : x1=MouseX() : y1=MouseY() : Circle(x1,y1,5,cr) : Else : Circle(x1,y1,5,cw) : EndIf 
  If key=2 : x2=MouseX() : y2=MouseY() : Circle(x2,y2,5,cr) : Else : Circle(x2,y2,5,cw) : EndIf 
  If key=3 : x3=MouseX() : y3=MouseY() : Circle(x3,y3,5,cr) : Else : Circle(x3,y3,5,cw) : EndIf 
  If key=4 : x4=MouseX() : y4=MouseY() : Circle(x4,y4,5,cr) : Else : Circle(x4,y4,5,cw) : EndIf 
  
  ; draw bezier-curve
  bezier(x1,y1,x2,y2,x3,y3,x4,y4,cw,smoothness,tangentePos)

  StopDrawing() 

  ; handle keyboard-events
  If KeyboardReleased(#PB_Key_Up)
    tangentePos + smoothness
  ElseIf KeyboardReleased(#PB_Key_Down)
    tangentePos - smoothness
  EndIf
  If tangentePos <= smoothness
    tangentePos = smoothness
  ElseIf tangentePos >= 1.0 - smoothness
    tangentePos = 1.0 - smoothness 
  EndIf
  If KeyboardPushed(#PB_Key_Left)
    smoothness - 0.0001
  ElseIf KeyboardPushed(#PB_Key_Right)
    smoothness + 0.0001
  EndIf
  If smoothness <= 0.01
    smoothness = 0.01
  ElseIf smoothness >= 1
    smoothness = 1.0 
  EndIf
  
  FlipBuffers() 
  ClearScreen(0,0,0) 
Until KeyboardPushed(#PB_Key_Escape)

[Lebostein]

Hey cool! Danke!

Ich hab gestern schon ein wenig rumprobiert, die Funktion abzuleiten. Leider bin ich nicht auf die Idee gekommen, beide Komponenten x und y einzeln abzuleiten, ich wollte es mir wahrscheinlich wieder mal unnötig schwer machen....

-> Der Code kann gleich ins Codearchiv wandern @André

[Andre]

-> Der Code kann gleich ins Codearchiv wandern @André

Yep