Author Topic: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic  (Read 13330 times)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1579
  • Particle Hawk
    • View Profile
I think i found a bug with GLBasic math processing....but i cant prove it.
Perhaps its a flaw in Beziers Formula, although I highly doubt this is the case.
The 1st 2nd and 3rd degree formulas, which are simply subsequent increments in the math, all work great.
But when i try to increment the formula to the 4th degree, something very wrong happens.
When i set all the control masses to be parallel, the curve should be perfectly flat.
However, the result is unexpected....the flat curve, is arc shaped!

If anyone is feeling up for some math, i would really appreciate it if you can review and fix this code.
The correct result here should be a flat line, the blue line and the grey line should match each other.
Here is a working sample of the 4th degree..this i cant solve any further:

Code: GLBasic [Select]
//! --------------------------------- //
//! Project: Bezier Curve - problem with quartic curve.
       
        SYSTEMPOINTER TRUE
        LIMITFPS 60000
       
        GLOBAL mb1,mb2
        Grey = RGB( 128 , 128 , 128 )
        Lime = RGB( 0 , 255 , 0 )
        Red  = RGB( 255 , 0 , 0 )
        Blue = RGB(0,0,255)
        White= RGB(255,255,255)
       
        // start point
        Px0 = 100
        Py0 = 400
       
        // control point
        Px1 = 200
        Py1 = 400
       
        // control point
        Px2 = 300
        Py2 = 400
       
        // control point
        Px3 = 400
        Py3 = 400
       
        // end point
        Px4 = 500
        Py4 = 400

       
        //total num of points from start to end of the bezier
        NumPointsOnCurve=5

       

// -------------------------------------------------- //
MAIN:
WHILE TRUE
       
        MOUSESTATE Px2,Py2,mb1,mb2 //change the second control point position with mouse
       
        //Draw imaginary control lines:
        DRAWLINE Px0 , Py0 , Px1 , Py1 , Grey
        DRAWLINE Px1 , Py1 , Px2 , Py2 , Grey
        DRAWLINE Px2 , Py2 , Px3 , Py3 , Grey
        DRAWLINE Px3 , Py3 , Px4 , Py4 , Grey
        PRINT "C0",Px0,Py0+20
        PRINT "C1",Px1,Py1+20
        PRINT "C2",Px2,Py2+20
        PRINT "C3",Px3,Py3+20
        PRINT "C4",Px4,Py4+20
       
//Quartic Bezier Curve:
       
        QuarticBezier2d( Px0,Py0 , Px1,Py1 , Px2,Py2, Px3,Py3, Px4,Py4, NumPointsOnCurve )//    calculate the points
       
        FOR PointIndex = 0 TO NumPointsOnCurve - 2 //    Use the bezier point array TO draw the curve: -2 because we call last one in loop(B2)
                B1x = QuarticBezierArray2d[ PointIndex ][ 0 ] //line segment, start x
                B1y = QuarticBezierArray2d[ PointIndex ][ 1 ] //line segment, start y
                B2x = QuarticBezierArray2d[ PointIndex + 1 ][ 0 ] //line segment, end x
                B2y = QuarticBezierArray2d[ PointIndex + 1 ][ 1 ] //line segment, end y
                DRAWLINE B1x , B1y , B2x , B2y , Blue
        NEXT
       
        FPS( 500 , 10 , TRUE )
        SHOWSCREEN
       
WEND
       
       

       
FUNCTION QuarticBezier2d: P0x , P0y , P1x , P1y , P2x , P2y , P3x , P3y , P4x , P4y , NumPoints
        DIM QuarticBezierArray2d[ NumPoints ][ 2 ]
       
        Segment = 1.0 / ( NumPoints - 1.0 )
        Point = 0
       
        //first vector
        QuarticBezierArray2d[ Point ][ 0 ] = P0x
        QuarticBezierArray2d[ Point ][ 1 ] = P0y
       
        //middle vectors
        FOR t0 = Segment TO 1.0 STEP Segment
               
                t1 = 1.0 - t0
                t2 = POW( t1 , 2 )
                t3 = POW( t1 , 3 )
                t4 = POW( t1 , 4 )
               
                s1 = t0 * 1.0
                s2 = POW( s1 , 2 )
                s3 = POW( s1 , 3 )
                s4 = POW( s1 , 4 )
       
                B0 = t4 * P0x
                B1 = 4.0 * t3 * s1 * P1x
                B2 = 4.0 * t2 * s2 * P2x
                B3 = 4.0 * t1 * s3 * P3x
                B4 = s4 * P4x
                X  = B0 + B1 + B2 + B3 + B4
               
                B0 = t4 * P0y
                B1 = 4.0 * t3 * s1 * P1y
                B2 = 4.0 * t2 * s2 * P2y
                B3 = 4.0 * t1 * s3 * P3y
                B4 = s4 * P4y
                Y  = B0 + B1 + B2 + B3 + B4
       
                Point = Point + 1
                QuarticBezierArray2d[ Point ][ 0 ] = X
                QuarticBezierArray2d[ Point ][ 1 ] = Y
       
        NEXT
       
        //last vector
        QuarticBezierArray2d[ NumPoints - 1 ][ 0 ] = P4x
        QuarticBezierArray2d[ NumPoints - 1 ][ 1 ] = P4y
       
        RETURN 1
       
ENDFUNCTION
       

       
       
@FUNCTION FPS: X,Y,ShowFpsBOOL  //STABLE FPS!
STATIC TimeBuffer,FrameCount, FPSValue
LOCAL FrameTime
FrameTime=GETTIMER(); TimeBuffer=TimeBuffer+FrameTime; FrameCount=FrameCount+1
IF TimeBuffer>999; TimeBuffer=TimeBuffer-1000; FPSVALUE=FrameCount; FrameCount=0; ENDIF
IF ShowFpsBOOL=TRUE THEN PRINT "FPS="+FPSVALUE,X,Y
RETURN FPSValue
ENDFUNCTION


 
« Last Edit: 2010-Apr-01 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1579
  • Particle Hawk
    • View Profile
Ahh that is a great page!
This is exactly what i needed thank you.
This formula below is the 4th degree curve function.
B(t)=(1-t)4P1 + 4t(1-t)3P2 + 6t2(1-t)2P3 + 4t3(1-t)P4 + t4P5

As for opengl handling it, i dont know how, and I dont have time to study it.

edit:
also, a reason to use this set is for creating lookup tables for arcs etc, for either planar or space coordinates.

Btw i have tested the planar version for quartic 2d array(screenshot below), i will also make it work in a 3d function.
Im going to keep looking around for the quintic formula.


[attachment deleted by admin]
« Last Edit: 2010-Apr-02 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1579
  • Particle Hawk
    • View Profile
realise that this is an extremely funny statement, don't you?  You don't have time to study how OpenGL could be of service, yet you do take the time to re-implement what is there already.  I guess a lot of software came to be that way...  Thank you for putting a smile on my face :)


Heh yeah very funny. Im laughing..on the inside.
Opengl automatically will calculate this formula, for 3 dimensions not less, and that is expensive, resource-wise.
My function set will allow you to choose, 1 2 or 3 dimensional calculation.

Because of the way i will finish this lib, in some cases, it might prove to be faster than opengl.
Additionally to the prexisting lib, I will be building a set for each degree to calculate in 1 dimension.
So, this would be something like this: Linear_Bezier_Curve_1d() ... Quadra... etc

The reasoning for a 1d lib would actually be an advantage, because the amount of calculations will be almost half of what the 2d calls for in resources. I had a few ideas for using bezier in 1d, and it should prove useful to many.
Think about that, 1d, you can have a line across the screen with many segments,
 which would only be affected by the bezier is Y dimension, or X....
This could be VERY handy in making 3d bezier surfaces too...by affecting only the Y dimension.

So the theory is, GLBasic can run a 1 dimensional bezier calculation faster than opengl, simply because opengl automatically calculates 3 dimensions(2 too many).

edit:
i was testing the algorithms, and found you can interpolate through the control points by altering the inputs to the function.
Just update the control point inputs with new positioning info according to tensions and constraints(do a check against the magnitude distance for control handles, versus a fixed vertex array index), before calling the function.

example. if the line is a quadratic, and it is 10 points..
You can check the magnitude distance of the control point, and the 5th index position in the array.
This will be the center point which you are testing, to maintain some sort of automatic movement of the control point.
From here you make a constraint.....for instance, if magnitude of the 5th point is greater than 100 away from the control point, then move the control point input data to be closer to the 5th point.



I was able to create rigid animated lines, and not-so-rigid lines, which makes them act like a spring or a rubber band.
« Last Edit: 2010-Apr-02 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1579
  • Particle Hawk
    • View Profile
Found quintic in some code on the web....here i convert it into general format...i will add quintic now also.

B(t)=(1-t)5P1 + 5t(1-t)4P2 + 10t2(1-t)3P3 + 10t3(1-t)2P4 + 5t4(1-t)P5+ t5P6

Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1579
  • Particle Hawk
    • View Profile
Check out my quintic test, you can download from this message:


[attachment deleted by admin]
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)