bezier curves

jiri · Post by **jiri** » Feb 28, 2006 22:37

3 and 4 point bezier curves using bresenham type algorithm. These are typically less accurate, but 40 to 50% faster than their floating point equivalents. A couple of simple demos, too.

Code: Select all

' bezier.bi
' jiri babor
' j.babor@gmail.com
' homepages.paradise.net.nz/jbabor
' 2006-02-28

declare sub bezier3(x1,y1,x2,y2,x3,y3,col,n=0, byval buffer as any ptr = 0)
declare sub bezier4(x1,y1,x2,y2,x3,y3,x4,y4,col,n=0, byval buffer as any ptr = 0)

sub bezier3(x1, y1, x2, y2, x3, y3, col, n=0, byval buffer as any ptr = 0)
    ' draw 3 point Bezier curve using bresenham type algorithm                                                       
    ' n is number of calculated curve points                                          
    ' if n=0 then number will be estimated from length of lines through control points
    ' x1,y1 and x3,y3 are curve end points, x2,y2 is control point

    if n=0 then
        n = int(1.6 * (sqr((x2-x)*(x2-x) + (y2-y)*(y2-y)) + sqr((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2))))
    end if
    
    if (buffer) then
        pset buffer, (x1, y1), col      ' starting point
        pset buffer, (x3, y3), col      ' end point
    else    
        pset (x1, y1), col              ' starting point
        pset (x3, y3), col              ' end point
    end if

    nn = n * n
    ex = int(nn/2)                      ' x cumulative deviation
    ey = ex                             ' y cumulative deviation

    x = x1  
    y = y1
    
    a1 = 2 * (x - 2 * x2 + x3)
    a2 = 2 * (y - 2 * y2 + y3)
    b1 = 2 * n * (x2 - x)
    b2 = 2 * n * (y2 - y)
    flag = 0                            ' new pixel flag
    for i = 1 to n-1 
        dx = a1 * i + b1
        ex += dx
        while ex > nn 
            x += 1
            ex -= nn
            flag = 1
        wend
        while ex <= 0 
            x -= 1
            ex += nn
            flag = 1
        wend

        dy = a2 * i + b2
        ey += dy
        while ey > nn 
            y += 1
            ey -= nn
            flag = 1
        wend
        while ey <= 0 
            y -= 1
            ey += nn
            flag = 1
        wend
        if flag then                    ' new pixel location
            if (buffer) then
                pset buffer, (x, y), col
            else                
                pset(x, y), col
            end if
            flag = 0
        end if
    next
end sub


sub bezier4(x1, y1, x2, y2, x3, y3, x4, y4, col, n=0, byval buffer as any ptr = 0)
    ' draw 4 point Bezier curve bresenham type algorithm                                                      
    ' n is number of calculated curve points                                          
    ' if n=0 then number will be estimated from length of lines through control points
    ' x1,y1 and x4,y4 are curve end points, x2,y2 and x3,y3 are control points

    if n=0 then
        n = int(1.6 * (sqr((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) + sqr((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2))+_
            sqr((x4-x3)*(x4-x3)+(y4-y3)*(y4-y3))))
    end if
    
    if (buffer) then
        pset buffer, (x1, y1), col      ' starting point
        pset buffer, (x4, y4), col      ' end point
    else    
        pset (x1, y1), col              ' starting point
        pset (x4, y4), col              ' end point
    end if

    pset (x1, y1), col                  ' starting point
    pset (x4, y4), col                  ' end point
    
    dim as longint a1, a2, b1, b2, c1, c2, dx, dy, ex, ey, nn, nnn 
    
    nn = n*n
    nnn = nn*n

    ex = int(nnn/2)                     ' x cumulative deviation
    ey = ex                             ' y cumulative deviation
    x = x1  
    y = y1

    a1 = 3 * (-x + x4) + 9 * (x2 - x3)
    a2 = 3 * (-y + y4) + 9 * (y2 - y3)
    b1 = 6 * n * (x - 2 * x2 + x3)
    b2 = 6 * n * (y - 2 * y2 + y3)
    c1 = 3 * nn * (-x + x2)
    c2 = 3 * nn * (-y + y2)
    flag = 0                            ' new pixel flag
    for i = 1 to n-1 
        ii = i * i
        dx = a1 * ii + b1 * i + c1
        ex += dx
        while ex > nnn 
            x += 1
            ex -= nnn
            flag = 1
        wend
        while ex <= 0 
            x -= 1
            ex += nnn
            flag = 1
        wend

        dy = a2 * ii + b2 * i + c2
        ey += dy
        while ey > nnn 
            y += 1
            ey -= nnn
            flag = 1
        wend
        while ey <= 0 
            y -= 1
            ey += nnn
            flag = 1
        wend
        if flag then                    ' new pixel location
            if (buffer) then
                pset buffer, (x, y), col
            else                
                pset(x, y), col
            end if
            flag = 0
        end if
    next
end sub


' bezier.bas 
' jiri babor
' j.babor@gmail.com
' homepages.paradise.net.nz/jbabor
' 2006-02-27

#include "bezier.bi"

dim as double t 

windowtitle ""
screen 18

col = 1                                 ' initial curve colour

x1 = int(640*rnd(1)) : y1 = int(480*rnd(1))
x2 = int(640*rnd(1)) : y2 = int(480*rnd(1))
x3 = int(640*rnd(1)) : y3 = int(480*rnd(1))
x4 = int(640*rnd(1)) : y4 = int(480*rnd(1))

t = timer
do 
    bezier4 x1,y1, x2,y2, x3,y3, x4,y4, col
    x1 = x4 : y1 = y4
    x2 = x1 + int((x4 - x3)/2)
    y2 = y1 + int((y4 - y3)/2)
    x3 = int(640*rnd(1)) : y3 = int(480*rnd(1))
    x4 = int(640*rnd(1)) : y4 = int(480*rnd(1))
    count += 1
    if (count and 511) = 511 then
        cls
        col += 1
        if col = 16 then col = 1
        windowtitle str(int(count/(timer - t))) & " random curves/s"
    end if
loop until inkey$ <> ""


' bez4demo.bas
' jiri babor
' j.babor@gmail.com
' homepages.paradise.net.nz/jbabor
' 2006-03-01

#include "bezier.bi"

declare sub redraw()

dim shared x(3), y(3)

for i = 0 to 3
    x(i) = int(630*rnd(1)) + 5
    y(i) = int(470*rnd(1)) + 5
next

screen 18',,2
locate 2,3 : print "Grab & drag any coloured point to change the curve!"
locate 3,3 : print "Hit any key to exit..."
redraw()

do 
    getmouse mx,my,,mb
    if mb and 1 then
        for i = 0 to 3
            if x(i)-4 < mx and x(i)+4 > mx and y(i)-4 < my and y(i)+4 > my then
                while mb and 1
                    if x(i) <> mx or y(i) <> my then
                        x(i) = mx
                        y(i) = my
                        'screenset page, not page
                        cls
                        redraw()
                        'page = not page
                    end if 
                    getmouse mx,my,,mb
                wend
                exit for
            end if
        next
    end if
loop until inkey$ <> ""

sub redraw()
    line (x(0),y(0))-(x(1),y(1)), 8
    line (x(2),y(2))-(x(3),y(3)), 8
    bezier4 x(0),y(0), x(1),y(1), x(2),y(2), x(3),y(3), 14
    circle (x(0),y(0)), 3, 12,,,,f      
    circle (x(1),y(1)), 3, 9,,,,f      
    circle (x(2),y(2)), 3, 9,,,,f      
    circle (x(3),y(3)), 3, 12,,,,f      
end sub

D.J.Peters · Post by **D.J.Peters** » Sep 08, 2006 15:07

Not bad but your control point are to far away from the original "Bezier" curve and there is no need to use 2 times the slow SQR() function.

I mean it only as a hint if you will fix your nice Bresenhem Bezier codes.

Joshy

Code: Select all

private Sub _
DrawQCurve3(Byval ax as integer,Byval ay as integer, _ 
            Byval bx as integer,Byval by as integer, _ 
            Byval cx as integer,Byval cy as integer, _ 
            Byval col as integer) 
  
  Dim As Single t,tq,onestep,steps 
  Dim As Integer x1,y1,x2,y2,ax2,ay2,xo,yo,x,y 
  ' steps without any SQR()
  steps =(bx-ax)*(bx-ax)+(by-ay)*(by-ay) 
  steps+=(cx-bx)*(cx-bx)+(cy-by)*(cy-by) 
  ' adjust control point near to the curve
  bx=bx shl 1 - ax shr 1 - cx shr 1
  by=by shl 1 - ay shr 1 - cy shr 1
  If steps>2 Then 
    onestep=1.0/int(steps*0.01)
    bx+=bx:by+=by 
    x1=ax-bx+cx
    y1=ay-by+cy
    x2=bx-ax shl 1 
    y2=by-ay shl 1 
    x=ax:y=ay:t=onestep 
    ' plot every pixel from A to C over B
    While (x<>cx) Or (y<>cy) 
      Pset(x,y),col 
      ' save old position 
      xo=x:yo=y 
      ' plot only on new position 
      While (x=xo) And (y=yo) 
        tq=t*t 
        x=ax + x1*tq + x2*t 
        y=ay + y1*tq + y2*t 
        t+=onestep  
      Wend 
    Wend 
  Else 
    Pset(bx,by),col 
  End If 
End Sub

Sub bezier3(x1, y1, x2, y2, x3, y3, col, n=0, Byval buffer As Any Ptr = 0)
    ' draw 3 point Bezier curve using bresenham type algorithm                                                       
    ' n is number of calculated curve points                                          
    ' if n=0 then number will be estimated from length of lines through control points
    ' x1,y1 and x3,y3 are curve end points, x2,y2 is control point

    If n=0 Then
        n = Int(1.6 * (Sqr((x2-x)*(x2-x) + (y2-y)*(y2-y)) + Sqr((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2))))
    End If
    
    If (buffer) Then
        Pset buffer, (x1, y1), col      ' starting point
        Pset buffer, (x3, y3), col      ' end point
    Else    
        Pset (x1, y1), col              ' starting point
        Pset (x3, y3), col              ' end point
    End If

    nn = n * n
    ex = Int(nn/2)                      ' x cumulative deviation
    ey = ex                             ' y cumulative deviation

    x = x1  
    y = y1
    
    a1 = 2 * (x - 2 * x2 + x3)
    a2 = 2 * (y - 2 * y2 + y3)
    b1 = 2 * n * (x2 - x)
    b2 = 2 * n * (y2 - y)
    flag = 0                            ' new pixel flag
    For i = 1 To n-1 
        dx = a1 * i + b1
        ex += dx
        While ex > nn 
            x += 1
            ex -= nn
            flag = 1
        Wend
        While ex <= 0 
            x -= 1
            ex += nn
            flag = 1
        Wend

        dy = a2 * i + b2
        ey += dy
        While ey > nn 
            y += 1
            ey -= nn
            flag = 1
        Wend
        While ey <= 0 
            y -= 1
            ey += nn
            flag = 1
        Wend
        If flag Then                    ' new pixel location
            If (buffer) Then
                Pset buffer, (x, y), col
            Else                
                Pset(x, y), col
            End If
            flag = 0
        End If
    Next
End Sub

' 
' main
'
dim as integer ax,ay,mx,my,cx,cy,ox,oy
ax=160:ay=220
cx=480:cy=220

screenres 640,480

while inkey=""
  if getmouse(mx,my)=0 and (ox<>mx or oy<>my) then
    ox=mx:oy=my
    screenlock:cls
    ? "white my 'QCurve' and red bresenhem's 'Bezier'"
    line (ax-1,ay-2)-step(4,4), 7,bf
    line (mx-1,my-2)-step(4,4),14,bf
    line (cx-1,cy-2)-step(4,4), 7,bf
    DrawQCurve3(ax,ay,mx,my,cx,cy,15)
    Bezier3(ax,ay,mx,my,cx,cy,4)
    screenunlock
  end if
  sleep 10
wend
end

jiri · Post by **jiri** » Sep 16, 2006 11:46

Thanks, Joshy, for your comments. I am sorry to be so late with my response, I am trying to rein in my vices, programming is just one of many.

Not bad but your control point are to far away from the original "Bezier" curve

My algorithms produce curves very close to the 'classical' 3- and 4-point Bezier curves. The whole point is, surely, to control tangent angles as well as the curvature at the end points of the splines. I am not quite sure how you do that with your 'Q' curve.

there is no need to use 2 times the slow SQR() function

That's quite true, but a typical spline will consist of hundreds, i not thousands, of points with corresponding numbers of floating point calculations, plus the actual plotting of the points. The influence of a couple of square roots is most likely going to be quite negligible.

jiri