\Quite some time ago, way back to the time of nxtasy.org, I was writing a Bézier curve implementation in NXC. Muntoo was also writing one at the time, you can check his out on his blog, here. His implementation is generally more feature rich, like several different drawing modes, while mine is geared towards pure speed.
To start it off, here is a screenshot of the current progress:
The process is two-step, a initiation function which calculates some basic stuff which takes 11 msec, and then the drawing functions. In the screenshot there are 10 cubic curves drawn by the general Bézier algorithm which takes 419 msec in total, so ~42 msec per function call in average. (The first draw with a new amount of control points is a bit slower as some of the calculations are reused.)
Right now there is only a general Bézier algorithm, the one I optimized for cubic curves isn’t working correctly…
Implementation – v1.1.0
The general Bézier formula looks like this:
So to draw a Bézier curve you would start with t=0, calculate the x and y positions, increment t by 1/”desired precision” and recalculate. This process is repeated until t=1. There is a lot of calculation needed for each t value, yet we might be able to do some of the calculation that doesn’t directly involve t beforehand.
We could for example calculate the binomial for each P and store it in C like this:
NXC is compiled into a bytecode format in which math opcodes are polymorphic. If you try to multiply an array with a scalar, the scalar will be multiplied with each of the elements in the array. This is however a lot faster than manually iterating a loop multiplying each element.
So my idea was to take advantage of this by making an array containing each value of t. Instead of iterating a loop, you would simply do the math operations on this array. The array of t values would also only be calculated once in the beginning of the program, instead of each time you need to draw the curve.
So for the Bézier algorithm there would be two arrays, one containing each value of t and another containing each value of 1-t.
However we want to optimize this further. Since we start at i=0, lets consider that case:
We will only need to calculate , so lets try finding the difference between the first iteration and the next:
We can therefore get to the next iteration by multiplying into and into the next iteration by multiplying again:
This fraction can be calculated without knowing n or i, so we can calculate this at the start of the program and reuse it. We will need to calculate each time we get a new n value (but we can keep the array, so if the next curve have same n value, we also reuse this (and when done right, even the binomial)).
However a small loop is still needed to calculate the sum since ArraySum() isn’t polymorphic. Currently there is also a little bit of multiplication in the loop, but I’m working on removing that too.
The major downside with this approach is that if you use high resolutions the arrays become rather large (and they are using float to boot) so memory usage rise quite a bit. (Some temporary arrays are also needed, so it quickly becomes a few KB.)
P.S. I should really have considered reading a tutorial about LaTeX before trying to add all that math which needs to be written in LaTeX…