
Comments and Discussions



I don't know if anyone is interested, but I translated Tolga's excellent code over to simple C. I needed it to dump out some smooth inbetween values for a throttle control system. I used it to save a microcontroller from doing expensive math zillions of times a second by precomputing a lookup table of 1024 points from just 32. Nice smooth curve. Here's the code:
#include <stdio.h>
#include <math.h>
#define ARRAY_SIZE( array ) sizeof( array ) / sizeof( array[0] )
double factorialLookup[33] = {
1.0,
1.0,
2.0,
6.0,
24.0,
120.0,
720.0,
5040.0,
40320.0,
362880.0,
3628800.0,
39916800.0,
479001600.0,
6227020800.0,
87178291200.0,
1307674368000.0,
20922789888000.0,
355687428096000.0,
6402373705728000.0,
121645100408832000.0,
2432902008176640000.0,
51090942171709440000.0,
1124000727777607680000.0,
25852016738884976640000.0,
620448401733239439360000.0,
15511210043330985984000000.0,
403291461126605635584000000.0,
10888869450418352160768000000.0,
304888344611713860501504000000.0,
8841761993739701954543616000000.0,
265252859812191058636308480000000.0,
8222838654177922817725562880000000.0,
263130836933693530167218012160000000.0
};
double factorial( int n ) {
if ( n < 0 ) { printf( "ERROR: n is less than 0\n" ); }
if ( n > 32 ) { printf( "ERROR: n is greater than 32\n" ); }
return factorialLookup[n];
}
double Ni( int n, int i ) {
double ni;
double a1 = factorial( n );
double a2 = factorial( i );
double a3 = factorial( n  i );
ni = a1 / ( a2 * a3 );
return ni;
}
double Bernstein( int n, int i, double t ) {
double basis;
double ti;
double tni;
if ( t == 0.0 && i == 0 ) {
ti = 1.0;
} else {
ti = pow( t, i );
}
if ( n == i && t == 1.0 ) {
tni = 1.0;
} else {
tni = pow( ( 1  t ), ( n  i ) );
}
basis = Ni( n, i ) * ti * tni;
return basis;
}
void Bezier2D( double b[], int bCount, int cpts, double p[] ) {
int npts = bCount / 2;
int icount, jcount;
double step, t;
icount = 0;
t = 0;
step = (double)1.0 / ( cpts  1 );
for ( int i1 = 0; i1 != cpts; i1++ ) {
if ((1.0  t) < 5e6) {
t = 1.0;
}
jcount = 0;
p[icount] = 0.0;
p[icount + 1] = 0.0;
for ( int i = 0; i != npts; i++ ) {
double basis = Bernstein(npts  1, i, t);
p[icount] += basis * b[jcount];
p[icount + 1] += basis * b[jcount + 1];
jcount = jcount +2;
}
icount += 2;
t += step;
}
}
int main( int argc, const char * argv[] ) {
double outputs[2048];
double inputs[66] = {
0, 0.0,
32, 9.0,
64, 16.0,
96, 22.0,
128, 28.0,
160, 0.0,
192, 41.0,
224, 46.0,
256, 50.0,
288, 56.0,
320, 59.0,
352, 60.0,
384, 61.0,
416, 62.0,
448, 63.0,
480, 63.0,
512, 64.0,
544, 64.0,
576, 65.0,
608, 65.0,
640, 66.0,
672, 67.0,
704, 69.0,
736, 71.0,
768, 75.0,
800, 82.0,
832, 87.0,
864, 92.0,
896, 98.0,
928, 105.0,
960, 111.0,
992, 119.0,
1023, 128.0
};
Bezier2D( inputs, ARRAY_SIZE( inputs ), 1024, outputs );
for ( int x = 0; x < 2048; x += 2 ) {
printf( "%li\t%li\n", (long)outputs[x], (long)outputs[x+1] );
}
return 0;
}

Andy
http://StuffAndyMakes.com
@StuffAndyMakes






Of course, after a little more time thinking through what I was doing AND with the realization that the 8bit AVR microcontroller I'm using only has 8K of SRAM to work with, I've tuned the curve down to just 4 points and I get amazing and perfect data:
float inputs[8] = {
1, minPower,
(1024/4), maxPower,
(1024/4)*3, minPower,
1023, maxPower
};
My curve has X values from 0 to 1023 (the analog joystick axes values coming into the microcontroller) and Y values from 0 to 127 (the possible command byte values to the motors). There are two motors, each with its own set of bytes (motor A gets 1 to 127 and motor B gets 128 to 255). Again, for optimization, only one curve is generated (the one for motor A) and the other motor's command is the motor A value with 127 added. So, as the stick is moved, the firmware maps the stick's analog value (0 to 1023) to data in the curve (0 to 127) and depending on the axis, the motor command value is passed to the motor untouched (motor A) or has 127 added to and then passed to the motor (motor B).
Here is the curve deisgn:
Office Chairiot Mark II Throttle Response Curve (Advanced)
The smooth area through the middle of the curve is to allow wiggle and sloppy stick movement while the vehicle is "parked" or idle. All of the three starter curves have that same smooth center:
Office Chairiot Mark II Throttle Response Curve (Regular)
Office Chairiot Mark II Throttle Response Curve (Kiddie/Safe)
Your code has been a TREMENDOUS help in making my code and memory usage more efficient. Thank you so much!





I intend to use your BezierCurve class to adjust the volume levels coming out of my electronic piano keyboard. I recently bought a nice keyboard but some notes are louder or softer than the rest. I'm going to write an application that applies custom velocity curves to the offending notes.
Thanks
Todd Piltingsrud





Todd,
This is an exciting application, let me know if you got any results.
Bests,





many thanks for the detailed description and the useful advice





why only 32 points? i don't understand. I have a list of point and I have an error in factorial can You help me?





Because:
I have a very simple factorial computation routine and 32 is already as much as I can compute as an int value. Since this code is only a demonstration, I have not bothered to go beyond that. Normally, there are smarter ways.
Cheers,





First of all this is great work!
The limitation of 32 can be easily removed. The issue is in the calculation of Bernstein basis, you used the formula with all the big numbers. If you canculate the basis succsseively, say
B(i+1) = B(i)*t*(ni)/[(1t)*(i+1)]
Then you can bypass all the factorial parts (remove the table, Ni).
Chengyou





Thank you Chengyou,
This is a design choice to speed up the calculations. As you mentioned there are many ways to get rid of such limitation. I think the best way would be to compute those coefficients by a table lookup to 32 and then compute the rest with a recursive formula, like the on you put.






Good work! I just wrote an article on codeproject and used your work. Of course I referenced to you (in code and in the article). You can find it here: Bezier curve for the Microsoft Web Chart control[^]
____________________________________________________________________
Never underestimate the power of stupid people in large groups.





Thanks Rainer, it's great to see such good use of it. Nice idea.
Tolga





Hi,
I found an interesting easy solution to solve Beziercurves: http://www.cubic.org/docs/bezier.htm[^]
Regards, Rainer
____________________________________________________________________
Never underestimate the power of stupid people in large groups.





Makalenizi çok beğendim.
Saygılarımla,
Erol Esen
Eroldynamic





Tesekkur ederim.
Saygılarımla,
Tolga





i'm trying to use the algorithm to generate curvy paths that i will move characters on these paths, but the problem is that this algorithm don't give a smooth curve, how can i fix that ?





Well, to my opinion, it clearly generates smooth curves... It doesn't even pass through the control points, like catmull rom splines do.
How smooth do you want?
Also, one quick idea that I can think of is to reduce the amount of control points. The less control points you have, the smoother the curve will look like.





This is driving me nuts  I can't figure out how to draw filled antialiased Béziers in C#/GDI+. GDI+ offers nonfilled Béziers, and also offers other kinds of filled curves, but not filled Béziers. And I think I can forget about antialiasing. So I'll probably have to roll my own Bézier drawing component. Google isn't helping me here. Anyone have any suggestions to offer? Nice article btw c





I am faced with the same problem. The solution ought to be to create the boundary with nonfilled Beziers, choose any point inside the boundary and use FloodFill. I find this sometimes fails because the Bezier functions in my (admittedly old) Microsoft GDI library sometimes leak. That is, they sometimes create lines with a gap through which FloodFill leaks to the exterior. To solve this I have written my own Bezier function which I am sure doesn't leak. I have experimented with different versions. My fastest version uses fixed point arithmetic and a buffer to hold all the points and then Polyline to draw them. It is only slightly (less than 20%) slower than the library version. Using LineTo for each point to avoid the buffer is many times slower. Using floating point instead of fixed point doubles the time but avoids a possible arithmetic overflow problem with too many segments. This limits my simplest version with a 1024 bit screen to 64 segments and a slightly more complex version to 1024 segments. Many suggest that 32 segments is enough anyway. Incidentally I set a maximum number of segments but unlike other code I have seen I use a recursive binary chop to save time by avoiding calculating and drawing zero length segments in small curves and avoiding calculating and drawing successive segments in a straight line in large curves.





Hello Burisch,
We are now some 6 month further after your cry for help.
If you still need some hints:
I recently needed a Bézier that should exactly fit into a gap in an existing multipoint graph.
Birdal's code, although very good and helpfull, didn't do that job and always left a hole at the end of the Bézier where it should, but didn't, connect to the other end of the gap in the existing graph.
The solution was found in a small change in the code:
change:
// step = (double)1.0 / (cpts  1);
into:
step = (double)1.0 / cpts;
Just the problem of trees and inbetween's.
Till sofar the simple approach.
A far more sophisticated solution to your antialiasing problem you might find in:
"Interpolation with Bezier Curves. A very simple method of smoothing polygons"
which is to be found in http://www.antigrain.com/agg2.5.zip
Good luck,
jvd





Very useful; well explained; nicely simplified.






Thanks for a great article!
Sorry but could you possibly supply the "Bernstein polynomials" function you are using as well? I've looked around for a way to do this but my math is quite rusty and I can't get it to work without it. If you don't have it, maybe a simple description of what I should code to get the same effect? (without the formula as that is all greek to me)
Thanks!





He can't because he's not really using them. He's faked the article and ripped off some code from gamedev.







General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

First Posted  14 Apr 2008 
Views  159,128 
Downloads  7,733 
Bookmarked  86 times 

