## Bezier Curves On The NXT

Bezier Curve Speed Test for a 4th Degree Bezier Curve. At a resolution of 50, each new render takes 286.5 ms, or about a third of a second.

As some of you from NXTasy may remember, I was working on a Bezier Curve implementation for the NXT in NXC. (I was also competing with Spiller for rendering speed; his code is in BezierCurve.zip\BezierComparison\Bezier_curves2\Bézier_curves2.nxc) I’ve managed to render the curve in the picture above in 286.5 ms. And that’s a 4th degree curve (3 control points and 2 end points) with 52 different points along the curve calculated and interpolated to give a “high resolution” output.

To do this, I added a bunch of my own optimizations and tried to avoid floating-point operations where possible. Then, using Spiller’s idea that:

$\mathbf{B}(t) = \displaystyle\sum_{i=0}^n {n\choose i}(1-t)^{n-i}t^i\mathbf{P}_i$

Can be converted to:

$\displaystyle \mathbf{C}_i = {n\choose i} \mathbf{P}_i \\ \mathbf{B}(t) = \displaystyle\sum_{i=0}^n (1-t)^{n-i}t^i \mathbf{C}_i$

I was able to speed up my drawing routines by up to 200%! (On the GeneralBezierCurve2DOut() drawing routine.)

NOTE: $n$ is the degree of the curve. $\mathbf{B}(t)$ is the Bezier Curve parametric function. $\mathbf{P}$ represent the control points. $\mathbf{C}$ and $i$ are temporary variables.
NOTE 2: Math geeks, sorry about the “while” notation. If you have any ideas in which I can use pure mathematical notation without resorting to C, please notify me by leaving a comment.

As well as the demos, I’ve included an entire library (BezierCurve.zip\BezierCurve\v0_3\BezierCurve_v0_3.h.nxc). It can:

• Draw curves on the screen using BezierCurve2DOut().
• Draw different shapes using the ShapeType parameter! For example, you can interpolate the points using Lines, make the curve thicker by using [Filled/Clear/etc] Circles/Ellipses, or make “calligraphy” effects using [Filled/Clear/etc] Rectangles.
• Determine the length of the Bezier curve using GeneralBezierCurve2D_Length_LocationType().
• Draw/connect points in an array onto the screen using LocationType_PointsOut(). (And specify the shape too, of course.)
• Pre-calculate Bezier curves and store their values in an array to increase program performance using BezierCurve2D_GetPoints_LocationType().
• And more!

It is possible that it requires the Enhanced NBC/NXC firmware. That is available here. [LINK]

Here’s a video of the demo/speed test programs in action:

~ by muntoo on January 13, 2011.

### 5 Responses to “Bezier Curves On The NXT”

1. Ahh, I remember this : P
Have you made a new version or is this the same one as the one in that topic on NXTasy.org?
I don’t think I released the last version of my program which used some interesting features of the FW not available in NXC (thus it was almost completely written in NBC). The interesting aspect of that program is that you can change the resolution from 50 and up to 200 almost without seeing any performance drops. (I had only made a 4CP version though.)
Well, but it seems to be broken now (like NXT RPG) of unknown reasons… I should try to get a half year old compiler + FW and see it that makes any difference…

Well, back to watching Lolis and Railguns.

• That’s the new version up there. The one I posted on NXTasy a long time ago was v0.1, I think. My new program features new functions which output the points, so you can interpolate them later. So, if you’re going to use the same Bezier Curve over and over, it saves having to calculate them again and again.

Currently, I’m working on a Bezier Curve Following robot… I’ve planned it out [almost], and I just need to implement it.

• Good idea, I will implement that in my version too when I have the time to finish it. (Since I store the result in a DrawPolygonType struct it already have an array of LocationType with the points, so adding it can’t be much easier and it will not produce any overhead.)

I’m looking forward to seeing how your robot turns out, it sounds quite interesting.

2. […] 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 […]

3. […] 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 […]