Feb 16 2011

## Bezier v2.4.0

Category: Lego,Mindstorms,NXC,Programs,SoftwareSpiller @ 00:31

\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:

$B(t)=\sum_{i=0}^n{n\choose i}(1-t)^{n-i}t^iP_i$

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:

$C_i={n\choose i}P_i$

$B(t)=\sum_{i=0}^n(1-t)^{n-i}t^iC_i$

### Implementation v2.+

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:

$(1-t)^{n-0}t^0=(1-t)^n$

We will only need to calculate $(1-t)^n$, so lets try finding the difference between the first iteration and the next:

$(1-t)^{n-1}t^{0+1}$

$\frac{(1-t)^n}{(1-t)^1}t^0t^1$

We can therefore get to the next iteration by multiplying $\frac{t}{1-t}$ into $(1-t)^n$ 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 $(1-t)^n$ 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.)

Bezier v2.4.0

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…

Feb 09 2011

## How to implement OO programs on the standard NXT firmware

Category: Lego,Mindstorms,NXC,SoftwareSpiller @ 23:39

OOP is not at this time supported in NXC. Even though the memory management in the standard firmware might be limiting it is still possible to achieve a simple OOP implementation fairly easily. It will however be a bit inefficient memory wise and you will have the standard issues with tread-safety.

However actually testing my hypothesis in the large scale turned out to be cumbersome and thus I didn’t… If you notice anything that wouldn’t work out, something I forgot to consider or anything, please leave a comment : )

## Object representation

The base for every object is a data structure containing all non-static variables. Lets consider a class like this:

class monster{
public:
static const unsigned char LEVEL_EASY = 0;
static const unsigned char LEVEL_MEDIUM = 1;
static const unsigned char LEVEL_HARD = 2;

protected:
unsigned char level;
unsigned int hp;
unsigned int max_hp;
unsigned char attack[];

public:
monster();
~monster(){
//The destructor could reset large arrays
ArrayInit( attack, 0, 0 );
}

unsigned char difficulty() const{ return level; }
float life() const{ return (float)hp/max_hp; }

void receive_damage( unsigned char power, unsigned char attacker_level );
void attack( monster opponent, unsigned char attack_id );
};

It would end up to something like this in NXC code:

const byte monster::LEVEL_EASY = 0;  //Yes, I know you can't do it like this in NXC...
const byte monster::LEVEL_MEDIUM = 1;
const byte monster::LEVEL_HARD = 2;
struct monster{
byte level;
unsigned int hp;
unsigned int max_hp;
byte attack[];
};
monster monster_paratemp;

The static variables are in global scope and the struct contains the other variables, nothing special here. Then an instantiation of the object is created, this will serve as a temporary object for function calls explained below.

## Functions

At the NBC level, all variables are global and every reference to a variable is static and can’t be changed. Dynamic memory (other than arrays which content is dynamic) and pointers aren’t supported. This means that functions operate on a fixed set of variables and that all parameters must be passed by copying. If you want to pass a parameter by reference it is actually passed by copying and then copied back once the function returns.

This is problematic since in order to share the same function for multiple instances of the object we will need to tell the function which object to act upon, in short we need to pass the object by either reference or constant reference.

object.life(); //The way we want to call it in code
life( object ); //The way it would be implemented behind the scenes

NXC currently makes a copy for each function however this isn’t optimal if we have many functions in the object. Even if we have a lot of free memory and doesn’t care about wasting some, it will have a rather negative effect on the file size of the .rxe file due to the way variables are declared.

To avoid making this effect to large, I suggest sharing a single object for all functions. It could also optimize repeated function calls in some cases as you could leave the copy in the function copy instead of copying it back and forth. (It will cause longer delays if you need to protect it with a mutex though.) This is the reason for the monster_paratemp variable in the example.

(It would be nice to see this form for optimization for general functions, though it would be a lot more complicated since you need to take treading and sub-functions into consideration…)

If there is only one instance of the class, then the functions should of course operate on the object directly instead of using a copy. Inline functions should do the same. And if  the class only contains inline or static functions, a copy shouldn’t be needed at all.

## Inheritance

Here is an example where the monster class is inherited:

class magic_monster: public monster{
private:
unsigned int sp;
unsigned int max_sp;

public:
magic_monster(): monster(){
ArrayBuild( attack, attack, 45, 30 );
}
~magic_monster(){
ArrayInit( attack, 0, 0 );
}
float magic_power() const{ return (float)sp/max_sp; }
void attack( monster opponent, unsigned char attack_id );	//The attack might be magic
};

The NXC struct:

struct magic_monster{
monster parent_monster;
unsigned int sp;
unsigned int max_sp;
};
magic_monster magic_monster_paratemp;

Instead of copying the monster struct and then add the extra variables, the struct is included as a sub-element. The reason is that this makes it a lot easier to call the functions defined in the inherited class. To call those, you simply copy parent_monster into monster_paratemp, call the function and then copy monster_paratemp back into parent_monster if necessary.

Multi-inheritance should also be easily possible this way, but I have never used it before so I don’t know if there are any special considerations to take…

## Virtual functions

Unfortunately there is no way to properly implement virtual functions at runtime. It must be done completely at compile-time to work. (Well, fairly simple virtual functions could work, but the implementation would be inefficient and nowhere close to being sufficient.)

However because pointers aren’t supported, the cases where you need to save it in a parent class (and therefore having to rely on runtime detection) are rather few. There are only two cases I can think of. First one being function calls which accepts an object. And second one being the use of virtual functions directly in the base class, it would always use its own implementation (if available).

I think that we should depend on compile-time virtual functions, accept the changed functionality in the cases where it can’t be detected, but try to warn the programmer about issue. (Perhaps a custom keyword could be added to turn off the warning to show to compiler that you understand the issue?)

## Functions accepting an object of the same class

One issue that appeared of using a single copy for the object parameter is apparent in the following example:

void monster::attack( monster opponent, unsigned char attack_id ){
}
monster dragon, ogre;
dragon.attack( ogre, 2 );

If we try to add how the temporary object is used together with the function calls it looks like this:

monster_paratemp = dragon;
attack( ogre, 2 );
monster_paratemp = ogre;
ogre = monster_paratemp;
dragon = monster_paratemp;

Notice how dragon now is equal to ogre because it hijacked the temporary variable. Also note how the parameters send to the receive_damage function are actually holding ogre‘s values. (This might not always be the case though, depending on which order the parameters are copied.)

In order to make this work, we would need to copy the currently active object into another temporary object, move ogre into monster_paratemp like normal, call the function and then revert the whole process.

Hells begins once we start seeing stuff like this:

void monster::chained_attack( monster chained_monster, monster opponent, byte attack_id ){
chained_monster.attack( opponent, attack_id );
}

## Conclusion

It seems to me that OOP could very well work out just fine on the NXT using the standard firmware. It might not be exactly like C++, but considering the platform I would say it is quite satisfying.
In my opinion OO is a great way to program and I would love to see it in NXC. (I do realize that it will be quite some work to get it to parse C++ properly, but a man must dream. (Or make his own compiler))

I have only programmed OO for half a year though, so I’m sure  there are a lot of features that I don’t know and therefore haven’t considered how to (if possible) to implement.