Vectors. Vectors Everywhere.

Defenderoids, nothing more than a name really. But lets see where that goes… So, last time, we left our little bitmap engine creating a glorified star field, to not especially great effect.

Time to add some pizazz.

Vectors are great, but they are very mathematically intense, especially on a system without functional floating points like the poor old NGPC.

To start with then, we need to think about what constitutes a vector, and how to model that in code in such a way that we can work on it in integer maths.

A vector is, to all intents and purposes, a line. It has an origin, a direction and a length. It could also be represented as a start and end point if we prefer.

But a line isn’t very interesting, and probably not what you or I think about when we imagine vectors. I want shapes. Triangles, Squares, Asteroids, SPACESHIPS. For that, we need a list of Vectors, and a way to join them up.

So, what does that mean in practise? If we think of that as a series of points and each line is a vector from the last point to the next, then we can envisage how we might draw the five lines in sequence from that list like so:

X	Y
0	30
20	20
30	0
40	10
10	0
0	30

So, five vectors, needs six points – as I said, in this case it’s easier to think of the vectors as having fixed start and end points rather than trying to work backwards from a direction and length). Each vector hops from one point to the next in sequence – vector 1 from (0,30) to (20,20), vector 2 from (20,20) to (30,0) right the way through to vector 5 which joins the shape up by going from (10,0) back to (0,30). (remember that our bitmap origin in the NGPC is the Top Left corner, so all points are relative to that. There’s no particular need to join it up I suppose, but it wouldn’t be a very good asteroid if it wasn’t closed now would it?

Luckily, as well as the humble SetPixel() our NGPC C Library contains a handy function to draw a line on a bitmap – DrawLine(). So, enough theory for now – lets see how that works if we inject that into our bitmap code for the above example.

// Create the bitmap
CreateBitmap((u16*)bmpLogo, 144, 112);
CopyBitmap((u16*)bmpLogo, bgTileBase);

// Copy the tiles into the screen RAM
iTile=0;
for (iLoopY=0;iLoopY<14;iLoopY++)
{
	for (iLoopX=0;iLoopX<18;iLoopX++)
	{
		PutTile(SCR_1_PLANE, 0, 1 + iLoopX, 1 + iLoopY, bgTileBase+iTile);
		iTile++;
	}
}

// Draw the lines
DrawLine((u16*)bmpLogo,0,30,20,20,1);
DrawLine((u16*)bmpLogo,20,20,30,40,1);
DrawLine((u16*)bmpLogo,30,40,40,10,1);
DrawLine((u16*)bmpLogo,40,10,10,0,1);
DrawLine((u16*)bmpLogo,10,0,0,30,1);

// Then copy the bitmap back into tile memory...
CopyBitmap((u16*)bmpLogo, bgTileBase);

Voila, our first “vector” object

So far so good, but not very flexible. We need to step back a bit from the DrawLine() functions and define a couple of structures that can represent our shapes.

typedef struct Point
{
	s16 x;
	s16 y;
} POINT;

typedef struct ColourPoint
{
	s16 x;
	s16 y;
	u8 colour;
} COLOURPOINT;

typedef struct VectorObject
{
	POINT Origin;
	POINT Position;
	u8 Points;
	COLOURPOINT VectorList[128];
	u8 Scale;
	s8 RotationAngle;
} VECTOROBJECT;

First, we need a “point” structure – I use two slightly different ones both with and without a colour attribute. I could probably use the COLOURPOINT for both purposes and just ignore the Colour, but I prefer to keep things focused.

The main part of the VECTOROBJECT structure is the list of COLOURPOINTS – I’ve coded this to a maximum of 128 points because we can’t have open ended arrays within a structure. There are then a few additional attributes around this big list of points (as in our example basically) which will be used to define the position of the object within our bitmap, the scale, and the rotation angle – more on that in a minute. As we move on, we’ll extend this to include behavioural attributes for the object such as speed, direction and rotation. Lets look at our example again but this time using the above structure.

// Create the bitmap
CreateBitmap((u16*)bmpLogo, 144, 112);
CopyBitmap((u16*)bmpLogo, bgTileBase);

// Copy the tiles into the screen RAM
iTile=0;
for (iLoopY=0;iLoopY<14;iLoopY++)
{
	for (iLoopX=0;iLoopX<18;iLoopX++)
	{
		PutTile(SCR_1_PLANE, 0, 1 + iLoopX, 1 + iLoopY, bgTileBase+iTile);
		iTile++;
	}
}

myVectorObject.Points=5;
myVectorObject.VectorList[0].x = 0;
myVectorObject.VectorList[0].y = 30;
myVectorObject.VectorList[0].colour = 1;
myVectorObject.VectorList[1].x = 20;
myVectorObject.VectorList[1].y = 20;
myVectorObject.VectorList[1].colour = 1;
myVectorObject.VectorList[2].x = 30;
myVectorObject.VectorList[2].y = 40;
myVectorObject.VectorList[2].colour = 1;
myVectorObject.VectorList[3].x = 40;
myVectorObject.VectorList[3].y = 10;
myVectorObject.VectorList[3].colour = 1;
myVectorObject.VectorList[4].x = 10;
myVectorObject.VectorList[4].y = 0;
myVectorObject.VectorList[4].colour = 1;
myVectorObject.VectorList[5].x = 0;
myVectorObject.VectorList[5].y = 30;
myVectorObject.VectorList[5].colour = 1;

myStartPoint = myVectorObject.VectorList[0];
for (iLoop=1;iLoop<=myVectorObject.Points;iLoop++)
{
	DrawLine((u16*)bmpLogo,(u8)myStartPoint.x,myStartPoint.y,(u8)myVectorObject.VectorList[iLoop].x,(u8)myVectorObject.VectorList[iLoop].y,(u8)myVectorObject.VectorList[iLoop].colour);
	myStartPoint = myVectorObject.VectorList[iLoop];
}

// Then copy the bitmap back into tile memory...
CopyBitmap((u16*)bmpLogo, bgTileBase);

If we run that, then we should get the same shape again – just with more lines of code (and yes, I know that the constructor can be simplified, at the expense of readability). But, crucially, we’ve now abstracted the shape definition away from the drawing – and we can now further abstract that to do more stuff. Remember we had a couple of attributes in the VECTOROBJECT structure for rotation and scale. After all, if they were just going to stay the same size and face in one direction, a sprite would be much easier.

I won’t dwell on the maths too much – there are far better places to go for that if you are interested – I’d recommend Ian Bell’s page “Maths for programmers” – it’s just brilliant. And yes, it is that Ian Bell.

So, the two things we want to do most will be to scale the shape – I won’t dwell on that, as essentially all we have to do is “multiply” the .x and .y coordinates by our scaling factor. For speed reasons, I will always try and use the boolean left and right shift operators for multiplication and division where it makes sense, so multiplying by factors of two.

Rotation is a bit more complex, and needs three things:

• a point of origin, that we are going to rotate our object around
• a rotation angle
• Sine and Cosine functions.

The basic method to rotate a point is simply:

1. Offset the point by the origin
2. Transform the x-coordinate as point.x * Cosine(angle) – point.y * Sine(angle)
3. Transform the y-coordinate as point.x * Sine(angle) + point.y * Cosine(angle)
4. Offset the rotated point back to it’s relative position from the origin

So, putting both of those together, and further abstracting our “drawing” routine into a function gives us:

void DrawVectorObject(u16 * BitmapAddress, VECTOROBJECT VectorObject)
{
	s16 iStartX;
	s16 iStartY;
	s16 iEndX;
	s16 iEndY;
	s16 iTempX;
	s16 iTempY;
	u8 iPoint = 0;
	s8 cSin;
	s8 cCos;
	
	cSin = Sin(VectorObject.RotationAngle);
	cCos = Cos(VectorObject.RotationAngle);

	iStartX = VectorObject.VectorList[0].x;
	iStartY = VectorObject.VectorList[0].y;

	while (iPoint++<VectorObject.Points)
	{

		// Modifier here is to find the centre of rotation
		iStartX = (iStartX*VectorObject.Scale)-VectorObject.Origin.x;
		iStartY = (iStartY*VectorObject.Scale)-VectorObject.Origin.y;

		// rotate point.
		iTempX = ((iStartX * cCos)>>7) - ((iStartY * cSin)>>7);
		iTempY = ((iStartX * cSin)>>7) + ((iStartY * cCos)>>7);

		// translate point back to it's original position:
		// Modify back from the centre of rotation above, and then add the X & Y co-ordinates
		iStartX = (VectorObject.Position.x>>7)+iTempX+VectorObject.Origin.x;
		iStartY = (VectorObject.Position.y>>7)+iTempY+VectorObject.Origin.y;

		iEndX = (VectorObject.VectorList[iPoint].x*VectorObject.Scale)-VectorObject.Origin.x;
		iEndY = (VectorObject.VectorList[iPoint].y*VectorObject.Scale)-VectorObject.Origin.y;

		// rotate point
		iTempX = ((iEndX * cCos)>>7) - ((iEndY * cSin)>>7);
		iTempY = ((iEndX * cSin)>>7) + ((iEndY * cCos)>>7);

		// translate point back:
		iEndX = (VectorObject.Position.x>>7)+iTempX+VectorObject.Origin.x;
			//if (iEndX<0) iEndX=0;
		iEndY = (VectorObject.Position.y>>7)+iTempY+VectorObject.Origin.y;

		// Bounds check to ensure that rotated points are still within the bitmap boundary
		if (iStartX>=0&&iStartY>=0&&iEndX>=0&&iEndY>=0&&iStartX<=BitmapAddress[0]&&iStartY<=BitmapAddress[1]&&iEndX<=BitmapAddress[0]&&iEndY<=BitmapAddress[1])
		{
			DrawLine((u16*)BitmapAddress,(u8)(iStartX),(u8)(iStartY),(u8)(iEndX),(u8)(iEndY),VectorObject.VectorList[iPoint].colour);
		}
		iStartX = VectorObject.VectorList[iPoint].x;
		iStartY = VectorObject.VectorList[iPoint].y;
	}
	
}

We can now call that directly instead of our drawing code:

myVectorObject.Position.x = 0;
myVectorObject.Position.y = 0;
myVectorObject.RotationAngle = 0;
myVectorObject.Scale = 1;

DrawVectorObject((u16*)bmpLogo,myVectorObject);

Which will give us the same shape again, or we can change the scale, position and angle to do something more interesting.

myVectorObject.Points=5;
myVectorObject.VectorList[0].x = 0;
myVectorObject.VectorList[0].y = 3;
myVectorObject.VectorList[0].colour = 1;
myVectorObject.VectorList[1].x = 2;
myVectorObject.VectorList[1].y = 2;
myVectorObject.VectorList[1].colour = 1;
myVectorObject.VectorList[2].x = 3;
myVectorObject.VectorList[2].y = 4;
myVectorObject.VectorList[2].colour = 1;
myVectorObject.VectorList[3].x = 4;
myVectorObject.VectorList[3].y = 1;
myVectorObject.VectorList[3].colour = 1;
myVectorObject.VectorList[4].x = 1;
myVectorObject.VectorList[4].y = 0;
myVectorObject.VectorList[4].colour = 1;
myVectorObject.VectorList[5].x = 0;
myVectorObject.VectorList[5].y = 3;
myVectorObject.VectorList[5].colour = 1;
myVectorObject.Position.x = 2048;
myVectorObject.Position.y = 2048;
myVectorObject.RotationAngle = 16;
myVectorObject.Scale = 6;

DrawVectorObject((u16*)bmpLogo,myVectorObject);

It’s moved! Finally.

There are a couple of things to note here. Firstly, I use a larger scale for the position variables, so that objects can move at different paces, but still move at the right relative speeds.

You’ll also notice that the point definitions of the base object have changed slightly – this is just to make the vector definition as small as possible so that we have more flexibility to scale it up. There is no support here for scaling the object down to make it smaller, but there’s no reason why we couldn’t do that too I suppose.

Secondly, sine() and cosine() as defined in the library are integer values – remember how I mentioned that we don’t have a floating point on the poor old NGPC? So, we need to shift these down by 128 AFTER the multiplication in order to pretend that we’re multiplying by a decimal point. Also, we use a 256 degree circle for the angles – primarily for speed reasons. Everything is better when it’s a power of two.

I’m going to leave this post here, as I think I’ve waffled on plenty well enough about the theory for now. Tune in next time when I might actually start doing something about writing a game…

Advertisement