GLBasic forum

Codesnippets => Math => Topic started by: Hemlos on 2009-Nov-19

Title: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2009-Nov-19
Bezier Curves Library - 2d and 3d, Linear, Quadratic,  and Cubic
Created By Neil Silver(aks Hemlos), November 18,2009
These math functions are documented on Wikipedia:
http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Usage of this math is up to your imagination.
Really, this functionality gives alot of power.
You can merge this array with other structures of math to create some awesome stuff.
These curvatures can be applied to structures in middle of the line, or anywhere on it.
You can do alot, you could create tradjectories, or paths.
You can use these with polyvectors to make dynamic flexing objects.
If done proper, you could apply these to 3d object creations also.
The sky is the limit here, and i wish i had more time to makes more samples, but i dont.

6 function library:
LinearBezier2d
LinearBezier3d
QuadraticBezier2d
QuadraticBezier3d
CubicBezier2d
CubicBezier3d

Here is the lib with 3 sample projects:
sample1 draws the 2d curves.
sample2 draws a bezier spline
sample3 is a game player and an AI critter following a path




[attachment deleted by admin]
Title: Re: Bezier Curves Library - Linear, Quadratic, and Cubic
Post by: Kitty Hello on 2009-Nov-19
Excellent! I had once need for that but dropped the idea.
Title: Re: Bezier Curves Library - Linear, Quadratic, and Cubic
Post by: bigsofty on 2009-Nov-19
Yes Beziers have multiple uses, well done Hemlos!  :good:
Title: Re: Bezier Curves Library - Linear, Quadratic, and Cubic
Post by: codegit on 2009-Nov-19
Thank you very much. I have played with curves before and this is definitely going into my toolbox.  :good:
Title: Re: Bezier Curves Library - Linear, Quadratic, and Cubic
Post by: Qube on 2009-Nov-19
Nice work, thanks for sharing  :good:
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2009-Nov-22
Np,

The complete library with sample is in the first message of this thread.
I think i covered all the curves needed.

Unless anyone can think of a really good use for a higher order curve, im leaving this lib as is.

Edit:
You might be able to create a Bezier-Bones, cpu-based 3d bone system, with this lib.
Goodluck, enjoy.


Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2009-Nov-23
I updated the library, it has 3 samples now, top of thread.
I included a simple program where a game player follows a path.


[attachment deleted by admin]
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: bigsofty on 2009-Nov-23
Ooh 3D Beziers, nice addition, thanks buddy!  :good:
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2009-Dec-06
Quote from: bigsofty on 2009-Nov-23
Ooh 3D Beziers, nice addition, thanks buddy!  :good:

Yup, you can create curvy paths or lines in 3d space.

I am going to use the 3d quadratic beziers, for homing missles paths, and radar tracking systems for my helicopter HUD.

Also, i was thinking about a 2d vector font system for GLBasic....this should actually be easy to make fonts with...i dont have the time for this now though.
And if youre crafty enough, you could use the 3d beziers for making 3d fonts too.
Vector fonts, like windows font, can be sized, colored, italics, bold, and even line resolution(number of segments, to change font style automatically).
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Ian Price on 2010-Jan-14
Hi Hemlos

Have you removed the link for this library? Is it still available for download?
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Jan-14
Hi Ian,

The link is above the screenshots.

Here is a shortcut to it:

http://www.glbasic.com/forum/index.php?action=dlattach;topic=3839.0;attach=1279
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Ian Price on 2010-Jan-14
D'oh! I missed it, thinking it was the screenshot link!

Cheers :)
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Feb-22
Quote from: Ocean on 2010-Feb-19
Hi Hemlos,

excellent work, I only stumbled across it today.  Thanks for posting it.  Did you ever consider other methods of interpolation?   Longer ago than I care to admit I once dabbled with interpolating cubic and quintic splines, would be nice to have those in GLB as well.

cheers
Ocean

What this lib currently contains for 2d and 3d array structures:
Linear, quadratic, and cubic.


Quintic....i assume this is the form with 2 ends and 3 handles?
Do you need quintic?

I was going to add this, but thought to myself, 'Who in the world would use this?'.
Using quintic only seems to me, to be a daunting task, applying it to something useful.

Please explain to me, what do you mean by 'other methods of interpolation'



Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-01
Interpolating can be done by scanning the array.
This library only contains beziers 2d and 3d array structures, for orders of these degrees:
1st 2nd 3rd (linear, quadratic, cubic, respectively)


Im currently trying to create orders of 4th(quartic) and possibly a 5th(named?) degree.
No guarantees...first test run has not been so good...as im missing something in my formula.
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-01
Knots, handles, control points, are NOT part of the curves.
For 3D animation Bézier curves are often used to define 3D paths as well as 2D curves for keyframe interpolation.
Linear Bézier curves are equivalent to linear interpolation.
Quadratic Bézier curves are quadratic interpolations.
Etc etc..

There are many resources on the internet explaining in great detail how bezier interpolation works.
For further in-depth, examination of this formula set, refer to this link:
http://en.wikipedia.org/wiki/B%C3%A9zier_curve
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-01
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


Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-02
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]
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-02
Quote from: Ocean on 2010-Apr-02
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.
Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-02
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

Title: Re: Bezier Curves Library - 2d and 3d, Linear, Quadratic, and Cubic
Post by: Hemlos on 2010-Apr-09
Check out my quintic test, you can download from this message:


[attachment deleted by admin]