You are not logged in or registered. Please login or register to use the full functionality of this board...
SIGN IN Join Our Community For FREE


Comparison of 3 Bezier drawing algos
06-02-2017, 01:26 PM (This post was last modified: 06-02-2017 01:27 PM by Andy_A.)
Post: #1
 (Print Post)
Comparison of 3 Bezier drawing algos
I needed to draw a bunch of cubic Bezier curves, so I did some research and found these algos which I turned into functions.

The naive approach is this: B(t) = (1-t)^3 * p0 + 3 * (1-t)^2 * t * p1 + 3 * (1-t) * t^2 * p2 + t^3 * p3

The naive approach is fine if you're only drawing a few Beziers at time.

When you need a lot of Beziers, these functions are designed to outperform the naive approach.


Code Snippet: [Select]
AppTitle "Comparison of Three Bezier Curve Drawing Functions"
Graphics 900, 600, 0, 2
SetBuffer BackBuffer()
SeedRnd MilliSecs()

Dim x(2,3), y(2,3)
Local i%, iterations%, numPnts%, st0%, st1%, st2%, et0%, et1%, et2%, iter$

;gen 4 random control points for the Bezier, store values + offsets in an array
For i = 0 To 3
    x(0, i) = Rand(0,299)    ;points in left third of screen
    y(0, i) = Rand(100,599)
    x(1, i) = x(0, i) + 300    ;points in middle third of screen
    y(1, i) = y(0, i)
    x(2, i) = x(0, i) + 600    ;points in right third of screen
    y(2, i) = y(0, i)
Next

;Draw control point and tangents
For i = 0 To 3
    Color 60,60,60
    If i < 3 Then
        Line( x(0,i),y(0,i),x(0,i+1),y(0,i+1) )
        Line( x(1,i),y(1,i),x(1,i+1),y(1,i+1) )
        Line( x(2,i),y(2,i),x(2,i+1),y(2,i+1) )
    End If
    Color 255,0,0
    Oval x(0,i)-2, y(0,i)-2,5,5,True
    Oval x(1,i)-2, y(1,i)-2,5,5,True
    Oval x(2,i)-2, y(2,i)-2,5,5,True
Next
Color 255,255,255
Flip
    

iterations = 5000 ;number of iterations to perform for each Bezier drawing function

numPnts = 100 ;number of points calculated to draw Bezier curve

;Regular Beziers
LockBuffer()
st0 = MilliSecs()
For i = 1 To iterations
    bezier( x(0,0), y(0,0), x(0,1), y(0,1), x(0,2),y(0,2), x(0,3), y(0,3), numPnts)
Next
UnlockBuffer()
Flip
et0 = MilliSecs()-st0

;Re-factored Beziers
LockBuffer()
st1 = MilliSecs()
For i = 1 To iterations
    mBezier( x(1,0), y(1,0), x(1,1), y(1,1), x(1,2),y(1,2), x(1,3), y(1,3), numPnts)
Next
UnlockBuffer()
Flip
et1 = MilliSecs()-st1

;Forward Differencing Beziers
LockBuffer()
st2 = MilliSecs()
For i = 1 To iterations
    fwdDiff( x(2,0), y(2,0), x(2,1), y(2,1), x(2,2),y(2,2), x(2,3), y(2,3), numPnts)
Next
UnlockBuffer()
Flip
et2 = MilliSecs()-st2

iter = Str(iterations)

Text 5, 0, iter+" Regular Bezier function calls, elapsed time:              "+et0+"ms  ("+(Float(iterations)/Float(et0)*1000.)+" Beziers/sec)"
Text 5,15, iter+" Moshplant Bezier function calls, elapsed time:            "+et1+"ms  ("+(Float(iterations)/Float(et1)*1000.)+" Beziers/sec)"
Text 5,30, iter+" Forward differencing Bezier function calls, elapsed time: "+et2+"ms  ("+(Float(iterations)/Float(et2)*1000.)+" Beziers/sec)"

WaitMouse()
End
    
Function bezier (x0%,y0%, x1%,y1%, x2%,y2%, x3%,y3%, segs%=24)
;Source:   http://www.wikipedia.org/wiki/Bezier_curve
;The parametric form of the curve is:
;P(t) = A(1 - t)3 + 3Bt(1 - t)2 + 3Ct2(1 - t) + Dt3    Where 0.0 <= t <= 1.0

    Local xt#, xp#, xi#, xp2#, xi2#, t1#, t2#, t3#, t4#
    Local tmpX1%, tmpY1%, tmpX2%, tmpY2%

    xt = 1.0 / Float(segs)    ;segs = number of line segments defining Bezier curve
    xp = 1.0 - xi

    tmpX1 = x0
    tmpY1 = y0
    While xi < 1.0-xt
        xi = xi + xt
        xp = 1.0 - xi
        
        xp2 = xp * xp
        xi2 = xi * xi

        t1 = xp2 * xp
        t2 = xp2 * xi * 3.0
        t3 = xi2 * xp * 3.0
        t4 = xi2 * xi

        tmpX2 = (t1 * x0) + (t2 * x1) + (t3 * x2) + (t4 * x3)
        tmpY2 = (t1 * y0) + (t2 * y1) + (t3 * y2) + (t4 * y3)
        Line tmpX1, tmpY1, tmpX2, tmpY2

        tmpX1 = tmpX2
        tmpY1 = tmpY2
    Wend
End Function


Function mBezier(x0%,y0%, x1%,y1%, x2%,y2%, x3%,y3%, segs%=24)
    ;Darrel Plant - http://www.moshplant.com/direct-or/bezier/math.html
    ;re-factored Adobe PostScript references
    Local rate#, t#, t2#, t3#, cx#, bx#, ax#, cy#, by#, ay#
    Local oldx%, oldy%, newx#, newy#

    ;segs is the number of line segments used to draw Bezier
    rate = 1.0/Float(segs) :     t = rate
    oldx = x0 : oldy = y0

    ;derive the coefficients
    cx = 3.0*Float(x1-x0)
    bx = 3.0*Float(x2-x1)-cx
    ax = Float(x3-x0)-cx-bx
    
    cy = 3.0*Float(y1-y0)
    by = 3.0*Float(y2-y1)-cy
    ay = Float(y3-y0)-cy-by
    
    ;iterate line segments indicated by rate
    While t<=1.0
        t2 = t*t :     t3 = t2*t
        newx = ax*t3+bx*t2+cx*t+x0
        newy = ay*t3+by*t2+cy*t+y0
        Line oldx, oldy, newx, newy
        oldx = newx :     oldy = newy
        t = t + rate
    Wend
End Function

Function fwdDiff(x0%,y0%, x1%,y1%, x2%,y2%, x3%,y3%, segs% = 24)
    ;Hannu Kankaanpää - https://www.niksula.hut.fi/~hkankaan/Homepages/bezierfast.html
    ;Bezier generated using 'Forward Differencing'
    Local fx#, fdx#, fddx#, fdddx#, fddxPer2#, fdddxPer2#, fdddxPer6#
    Local fy#, fdy#, fddy#, fdddy#, fddyPer2#, fdddyPer2#, fdddyPer6#
    Local t#, temp#
    Local i%, rx%, ry%

    t = 1.0/Float(segs)
    temp =    t * t
    fx = x0
    fdx = 3. * (x1-x0) * t
    fddxPer2 = 3. * (x0 - 2. * x1 + x2) * temp
    fdddxPer2 = 3. * (3. * (x1 - x2) + x3 - x0) * temp * t
    fdddx = fdddxPer2 + fdddxPer2
    fddx = fddxPer2 + fddxPer2
    fdddxPer6 = fdddxPer2/3.

    fy = y0
    fdy = 3. * (y1-y0) * t
    fddyPer2 = 3. * (y0 - 2. * y1 + y2) * temp
    fdddyPer2 = 3. * (3. * (y1 - y2) + y3 - y0) * temp * t
    fdddy = fdddyPer2 + fdddyPer2
    fddy = fddyPer2 + fddyPer2
    fdddyPer6 = fdddyPer2/3.

    rx = x0: ry = y0
    For i = 0 To segs-1
        fx = fx + fdx + fddxPer2 + fdddxPer6
        fdx = fdx + fddx + fdddxPer2
        fddx = fddx + fdddx
        fddxPer2 = fddxPer2 + fdddxPer2
        fy = fy + fdy + fddyPer2 + fdddyPer6
        fdy = fdy + fddy + fdddyPer2
        fddy = fddy + fdddy
        fddyPer2 = fddyPer2 + fdddyPer2
        Line(rx, ry, fx, fy)
        rx = fx: ry = fy
    Next
End Function
Find all posts by this user
Like Post



Forum Jump:


User(s) browsing this thread: 1 Guest(s)




QB64 Member Project - Swirl
QB64 Member Project - RGB Color Wheel
QB64 Member Project - Isolation
QB64 Member Project - 9 Board
QB64 Member Project - Pivet version one
QB64 Member Project - Kings Vallery version two
QB64 Member Project - STxAxTIC 3D World
QB64 Member Project - Martin Fractals version two
QB64 Member Project - Connect Four
QB64 Member Project - Kings Court
QB64 Member Project - OpenGL Triangles
QB64 Member Project - Score 4
QB64 Member Project - Color Rotating Text
QB64 Member Project - Amazon
QB64 Member Project - Othello
QB64 Member Project - Blokus
QB64 Member Project - Bowditch curve
QB64 Member Project - Rotating Background
QB64 Member Project - Pivot version two
QB64 Member Project - Dakapo
QB64 Member Project - Line Thickness
QB64 Member Project - Algeria Weather
QB64 Member Project - Kings Valley verion one
QB64 Member Project - Dreamy Clock
QB64 Member Project - Martin Fractals version three
QB64 Member Project - Rubix's Magic
QB64 Member Project - Input
QB64 Member Project - Spinning Color Wheel
QB64 Member Project - Foursight
QB64 Member Project - Basic Dithering
QB64 Member Project - Kobolts Monopoly
QB64 Member Project - Martin Fractals version one
QB64 Member Project - Exit
QB64 Member Project - Quarto
QB64 Member Project - Inside Moves
QB64 Member Project - MAPTRIANGLE
QB64 Member Project - Touche
QB64 Member Project - ARB Checkers
QB64 Member Project - Full Color LED Sign
QB64 Member Project - Red Scrolling LED Sign
QB64 Member Project - Spiro Roses
QB64 Member Project - Color Triangles
QB64 Member Project - Splatter
QB64 Member Project - Domain
QB64 Member Project - Qubic
QB64 Member Project - Overboard
QB64 Member Project - Point Blank
QB64 Member Project - Sabotage
QB64 Member Project - Martin Fractals version four