2D Rendering Without PVR

By BlackAura

The basics

Setting up a video mode

The first thing you should do when doing any kind of graphics programming is set up a video mode. On the Dreamcast, this isn't really that important - KallistiOS will automatically set the video hardware up into 640x480, 16 bit 60Hz mode. However, it's still a good idea to set the video mode manually, in case they change something.

This couldn't really be much simpler - we just need to call the function vid_set_mode, giving it our desired resolution and colour mode, and it'll do the rest:

vid_set_mode(display_mode, pixel_mode);

display_mode can be one of:

display_mode	Width	Height	Refresh rate
DM_320x240	320	240	60Hz, VGA
DM_640x480	640	480	60Hz, VGA
DM_256x256	256	256	60Hz
DM_768x480	768	480	60Hz
DM_768x576	768	576	60Hz
DM_640x480_PAL_IL	640	480	50Hz
DM_256x256_PAL_IL	256	256	50Hz
DM_768x480_PAL_IL	768	480	50Hz
DM_768x576_PAL_IL	768	576	50Hz
DM_800x608	800	608	VGA Only

The 60Hz modes will always be 60Hz, even on a PAL Dreamcast. The 50Hz modes will always be 50Hz, even on an NTSC Dreamcast. While most PAL TVs can display a 60Hz signal, some can not, and virtually no NTSC TVs can display a 50Hz signal. It's usually safe to use the 60Hz modes, but you might want to put in an option to use 50Hz on PAL Dreamcasts for those European gamers with old TVs. I'll go into more detail on that later.

One rather strange omission that is worth taking note of - there is no 320x240 50Hz mode. I don't know why this is, because it's certainly not too difficult to do - it was just never included in KOS. If anyone really needs it, there is a patch to add that mode (DM_320x240_PAL) to KOS 1.2.0, and it should be included in KOS 1.2.1

pixel_mode can be one of:

pixel_mode	Pixel size	Colour format
PM_RGB555	15 bit	0RRRRRGGGGGBBBBB
PM_RGB565	16 bit	RRRRRGGGGGGBBBBB
PM_RGB888	24 bit	RRRRRRRR GGGGGGGG BBBBBBBB

The best mode to use on the Dreamcast is RGB565 - it provides fairly good colour quality, it's significantly faster than 24-bit mode, and it uses less memory. Just trust me on this - it's the best mode to use for pretty much everything that we're going to be doing.

So, to initialise the screen to 640x480 60Hz, in RGB565 colour mode, we'd use the following line:

vid_set_mode(DM_640x480, PM_RGB565);

RGB565 colour mode

In RGB565 mode, the three colour components are packed into two bytes. The upper 5 bits contain the red data, the next 6 contain the green data, and the last 5 contain the blue data. Red and blue range from 0 to 31, and green ranges from 0 to 63. The reason that green is given more space is because the human eye is more sensitive to green.

Colours on a computer are typically represented using three bytes - one each for red, green and blue, ranging from 0 to 255. There's an easy way to convert from this format to the 16-bit RGB565 format that we need - we just use a macro:

#define PACK_PIXEL(r, g, b) ( ((r & 0xF8) << 8) | ((g & 0xFC) << 3) | (b >> 3) )

That macro uses two AND operations to mask out the unnecessary bits of the red and green components, bit shifts the values to get them into the correct place, and ORs them together. For some strange reason, that macro isn't included anywhere in KOS.

Drawing a single pixel

No matter how complex the graphics we're trying to make, no matter how many complex formulae and techniques we're using, no matter how long it's taken to draw our artwork, ALL 2D graphics come down to this - drawing a single pixel. For many things, where we need to plot multiple pixels at once, we can modify this routime to make it faster, but it'll still just be a variation on this. So how exactly do we draw a single pixel?

On the Dreamcast, the image currently being displayed on the screen is stored in an area of video memory called the framebuffer. The pixels are stored in order, from left to right, then from top to bottom, each as a single 16-bit value. So in order to find the location in the framebuffer of a single pixel, we can use this formula:

location = x_coordinate + (y_coordinate * width)

So, assuming a resolution of 640x480, we can do this:

location = x + (y * 640)

Now all we need to know is where the framebuffer is. KOS provides us with a pointer to this location, named vram_s. So all we need to do the get the location in memory of a single pixel on the screen is:

vram_s[x + (y * 640)]

From there, it should be easy to see how to draw a single pixel - we just need to set the value of that location in memory to the colour we want the pixel to be:

vram_s[x + (y * 640)] = PACK_PIXEL(r, g, b);

Clipping

Now that all works fine, until we come across one additional problem - clipping. What happens if we were to try to write to negative X or Y coordinates, or write off the bottom or the right of the screen? We'd be writing either to the wrong part of the screen, or an area of memory that we aren't allowed to write to. We could cause all kinds of problems. So we just don't do it - we have to add some checking to make sure we aren't trying to draw outside the screen:

if((x >= 0) && (x < 640) && (y >= 0) && (y < 480))
	vram_s[x + (y * 640)] = PACK_PIXEL(r, g, b);

Now we have a safe, effective way to draw a single pixel on the screen. Of course, it'd be more convenient as a macro:

#define DRAW_PIXEL(x, y, c) \
	if((x >= 0) && (x < 640) && (y >= 0) && (y < 480)) \
		vram_s[x + (y * 640)] = c;

Now, to draw a single pixel, we can just work out the colour we want to set it to using PACK_PIXEL, and the use DRAW_PIXEL to draw it.

Example

The example program for this tutorial (example1.zip), draws pixels randomly to the screen, using PACK_PIXEL and DRAW_PIXEL. See if you can make it do something more interesting.

Horizontal and vertical lines

Horizontal lines

Drawing pixels is probably getting kinda boring by now, so let's draw something more interesting. As a start, we'll draw a simple horizontal line, which is about the simplest shape you can do. A line is basically a load of pixels, arranged in a line. So they shouldn't be that hard to draw - we just need to draw a load of pixels in a line:

void draw_hline(int x1, int x2, int y, uint16 c)
{
	int cx;

	// Draw the line
	for(cx = x1; cx <= x2; cx++)
		DRAW_PIXEL(cx, y, c);
}

One problem there - what if x2 is smaller than x1? The line won't be drawn. So, if x2 is smaller than x1, we should swap them around:

void draw_hline(int x1, int x2, int y, uint16 c)
{
	int cx;

	// Swap x1 and x2 if necessary
	if(x1 > x2)
	{
		cx = x1;
		x1 = x2;
		x2 = cx;
	}

	// Draw the line
	for(cx = x1; cx <= x2; cx++)
		DRAW_PIXEL(cx, y, c);
}

And that's it... Or is it? The more observant of you may notice that this code is actually very bloated. Remember that DRAW_PIXEL is checking if the pixel is on the screen for every pixel we draw. But, since this is just a horizontal line, we know that if both points are on the screen, the whole line is on the screen. If the line's off the screen entirely, we can just ignore it. If the line is on the screen, we can tell how much of the line is on the screen, and adjust the left and right coordinates appropriately. This is more or less the same thing as the clipping that DRAW_PIXEL does, but we only need to do it for the line, not each pixel:

void draw_hline(int x1, int x2, int y, uint16 c)
{
	int cx;

	// Swap x1 and x2 if necessary
	if(x1 > x2)
	{
		cx = x1;
		x1 = x2;
		x2 = cx;
	}

	// Don't bother if the line's off the screen
	if( (y < 0) || (y > 479) || (x1 > 639) || (x2 < 0) )
		return;

	// Clip the line to the edge of the screen
	if(x1 < 0)
		x1 = 0;
	if(x2 > 639)
		x2 = 639;

	// Draw the line
	for(cx = x1; cx <= x2; cx++)
		vram_s[cx + (y*640)] = c;
}

That's a bit better, but there's still one problem - for each pixel, we're doing y*640, which will be the same for each and every pixel. In face, since we're drawing from left to right, each pixel will be next to the previous pixel. So we can do something like this:

void draw_hline(int x1, int x2, int y, uint16 c)
{
	int cx;
	uint16 *line_buffer;

	// Swap x1 and x2 if necessary
	if(x1 > x2)
	{
		cx = x1;
		x1 = x2;
		x2 = cx;
	}

	// Don't bother if the line's off the screen
	if( (y < 0) || (y > 479) || (x1 > 639) || (x2 < 0) )
		return;

	// Clip the line to the edge of the screen
	if(x1 < 0)
		x1 = 0;
	if(x2 > 639)
		x2 = 639;

	// Set line_buffer to the beginning of the line
	line_buffer = vram_s + x1 + (y * 640);

	// Draw the line
	for(cx = x1; cx <= x2; cx++)
		*line_buffer++ = c;
}

That probably won't make a lot of sense unless you know something about pointers in C - line_buffer is set to the location of the first pixel of the line we're drawing. We then draw the pixel, and increment line_buffer by one pixel, so it now points to the location of the next pixel.

A horizontal line is actually far more useful than it would first appear. A horizontal line is very useful for drawing filled shapes - you just draw a horizontal line from the left-most point of the shape on a given line, to the right-most point of the shape. Then you repeat that for each line. That's how most software rendered 3D games fill polygons.

Vertical lines

These are pretty much exactly the same as horizontal lines. However, we're now drawing down instead of right. Basically, we swap the X and Y coordinates around, and we skip 640 pixels instead of 1 - we jump down one pixel instead of right one pixel:

void draw_vline(int x, int y1, int y2, uint16 c)
{
	int cy;
	uint16 *line_buffer;

	// Swap y1 and y2 if necessary
	if(y1 > y2)
	{
		cy = y1;
		y1 = y2;
		y2 = cy;
	}

	// Don't bother if the line's off the screen
	if( (x < 0) || (x > 639) || (y1 > 479) || (y2 < 0) )
		return;

	// Clip the line to the edge of the screen
	if(y1 < 0)
		y1 = 0;
	if(y2 > 479)
		y2 = 479;

	// Set line_buffer to the beginning of the line
	line_buffer = vram_s + x + (y1 * 640);

	// Draw the line
	for(cy = y1; cy <= y2; cy++)
	{
		*line_buffer = c;
		line_buffer += 640;
	}
}

If you can just adapt something you already have to perform a new function, it's usually a good idea to try it. Trivial modifications to code that you know works are usually easier to get working than writing the whole thing from scratch.

Hollow boxes

Now that we have the code to draw horizontal and vertical lines, drawing a hollow box should be very easy - we just draw two horizontal lines, and two vertical lines:

void draw_hbox(int x1, int y1, int x2, int y2, uint16 c)
{
	draw_hline(x1, x2, y1, c);
	draw_hline(x1, x2, y2, c);
	draw_vline(x1, y1, y2, c);
	draw_vline(x2, y1, y2, c);
}

Filled boxes

All we do here is draw a series of horizontal lines, which will fill an area of the screen. We know what the left and right coordinates of the box are on each scanline, and we know how far up and down the box goes. So we can just do:

void draw_fbox(int x1, int y1, int x2, int y2, uint16 c)
{
	int cy;
	for(cy = y1; cy <= y2; cy++)
		draw_hline(x1, x2, cy, c);
}

Example

The example program for this tutorial (example2.zip), draws coloured gradients using the draw_hline and draw_vline functions, then draws a pattern using the filled and unfilled box functions. The video code is contained in a separate file which you can use in your own programs. Just copy video.c and video.h, put them into your own program, and #include video.h when you want to use the video functions. All future examples will be set up this way.

General lines

Lines in any direction

So far, we've just drawn horizontal and vertical lines. They were easy, but they're also quite boring. So now we're going to draw lines that can go in any direction we want. Assuming you know some farily basic line geometry, drawing a line is pretty easy. However, the simple way is also very slow, which is where things start to get interesting.

There are a multitude of ways to draw lines, ranging from the obvious to the utterly insane. The method I'm describing here is the most common, which was developed by Jack Bressenham at IBM. It's not the best, but it's comprehensible at least, and can be fairly easily derived.

This kinda assumes that you know some basic line geometry, such as how to find the gradient (slope) of a line, and some other simple things (such as what the gradient actually is, and what you can do with it). I did this kind of stuff at school when I was about twelve or thirteen. If you didn't learn any of this, can't remember it, or fell asleep in class, you're going to find this a little difficult. That's what you get for not paying attention in math class.

Line geometry

In order to draw a line, we must first be able to define a line. Once we can develop a mathematical model of a line, we can try to tell a computer how to draw one.

In general, and line can be defined by two values - it's gradient, and it's y-intercept. The gradient tells us how steep the line is, and the y-intercept tells us where the line intersects with the Y axis. In practical terms, we also need two end points, which simply define the limits of the line in the X axis. The Y coordinates of each end point can be calculated using the Y-intercept and the gradient, and therefore the gradient and Y-intercept can be calculated from the end points.

The general equation for a line is...

y = mx + b

...where "x" and "y" are the coordinates of each point on the line, m is the gradient, and b is the y-intercept. Therefore, if we know the X coordinate of a point, we can find it's Y coordinate by plugging it into the above formula. We can use this to find the Y coordinate of any point between our two end points.

Finally, we need to know how to calculate the Y intercept and gradient, assuming that we know the coordinates of two points on the line - the end points in our case. First, we calculate the gradient by dividing the Y displacement (Y2 - Y1) by the X displacement (X2 - X1). We can then use a slightly modified version of the first equation to find the y-intercept.

A first attempt

Now, that sounds easy (yeah, right), so let's put it into practice...

void draw_line(int x1, int y1, int x2, int y2, uint16 c)
{
	float m, b;
	int dx = x2 - x1;
	int dy = y2 - y1;

	// Calculate gradient and y-intercept
	m = (float)dy / (float)dx;
	b = y1 - m*x1;

	// Work out which way we're going - left or right
	dx = (x2 > x1) ? 1 : -1;

	// Draw start pixel
	DRAW_PIXEL(x1, y1, c);

	// Draw the line
	while (x1 != x2)
	{
		x1 += dx;
		y1 = (int)(m*x1+b);
		DRAW_PIXEL(x1, y1, c);
	}
}

There's just one problem with that. If you try to draw some lines with it, you'll notice that it doesn't work for steep lines. We're moving from left to right, and plotting one pixel at the appropriate height. But, for steep lines, we'll just get a load of dots.

A working attempt

So how do we fix it? It works fine for any lines which are shallow, so we can keep that. All we have to do for steep lines is reverse the X and Y coordinates - we flip all X and Ys in the equations above, and move from top to bottom, calculate an X coordinate, and plot one pixel

void draw_line(int x1, int y1, int x2, int y2, uint16 c)
{
	float m, b;
	int dx = x2 - x1;
	int dy = y2 - y1;

	// Draw start pixel
	DRAW_PIXEL(x1, y1, c);

	if(abs(dx) > abs(dy))
	{
		// Shallow lines
		m = (float)dy / (float)dx;
		b = y1 - m*x1;
		dx = (x2 > x1) ? 1 : -1;
		while (x1 != x2)
		{
			x1 += dx;
			y1 = (int)(m*x1+b);
			DRAW_PIXEL(x1, y1, c);
		}
	}
	else
	{
		// Steep lines
		m = (float)dx / (float)dy;
		b = x1 - m*y1;
		dy = (dy < 0) ? -1 : 1;
		while(y1 != y2)
		{
			y1 += dy;
			x1 = (int)(m*y1+b);
			DRAW_PIXEL(x1, y1, c);
		}
	}
}

Digital differential analyser

Remember I said that this method was slow? Can you see why? When it calculates the X or Y coordinates for each point, it must multiply two numbers together. Since multiplications are quite slow, this slows the whole thing down. We can get around this by using additions instead.

Every time we do a multiplication, we're multiplying the gradient by the next Y or X coordinate. The gradient is always constant, and the X or Y coordinates are always exactly one more or one less than they were before. That means that, instead of the multiplication, we can just add or subtract the gradient each time.

This technique is an example of a digital differential analyzer, apparently. I have no idea what a DDA actually is, but I know that this is one. The same idea applies to some other things, but nothing that's immediately relevant. So you may as well forget about it.

void draw_line(int x1, int y1, int x2, int y2, uint16 c)
{
	float m;
	int dx = x2 - x1;
	int dy = y2 - y1;
	float t = 0.5;

	// Draw start pixel
	DRAW_PIXEL(x1, y1, c);

	// Shallow lines
	if(abs(dx) > abs(dy))
	{
		// Shallow lines
		m = (float)dy / (float)dx;
		t += y1;
		dx = (x2 > x1) ? 1 : -1;
		m *= dx;
		while (x1 != x2)
		{
			x1 += dx;
			t += m;
			DRAW_PIXEL(x1, t, c);
		}
	}
	else
	{
		// Steep lines
		m = (float)dx / (float)dy;
		t += x1;
		dy = (dy < 0) ? -1 : 1;
		m *= dy;
		while(y1 != y2)
		{
			y1 += dy;
			t += m;
			DRAW_PIXEL(t, y1, c);
		}
	}
}

Bresenham's algorithm

This is a refinement of the DDA line algorithm above. To be totally honest, I don't know if this is any faster on the Dreamcast, because it makes some assumptions that aren't necessarily true on the SH-4. Specifically, it assumes that floating point operations are slower than integer operations, and that you can't compare two arbitrary numbers - you can only compare one number to zero. I don't see how it could be any slower, so we might as well give it a try. If anyone can be bothered to benchmark these, tell me what results you get.

Anyway, all this does is removes all floating point operations in favour on integer operations, makes all comparisons relative to zero, and removes the division used to calculate the gradient.

void draw_line(int x1, int y1, int x2, int y2, uint16 c)
{
	int dy = y2 - y1;
	int dx = x2 - x1;
	int stepx, stepy;

	if (dy < 0) { dy = -dy; stepy = -1; } else { stepy = 1; }
	if (dx < 0) { dx = -dx; stepx = -1; } else { stepx = 1; }
	dy <<= 1;
	dx <<= 1;

	DRAW_PIXEL(x1, y1, c);

	if (dx > dy)
	{
		// Shallow lines
		int fraction = dy - (dx >> 1);
		while (x1 != x2)
		{
			if (fraction >= 0)
			{
				y1 += stepy;
				fraction -= dx;
			}
			x1 += stepx;
			fraction += dy;
			DRAW_PIXEL(x1, y1, c);
		}
	}
	else
	{
		// Steep lines
		int fraction = dx - (dy >> 1);
		while (y1 != y2)
		{
			if (fraction >= 0)
			{
				x1 += stepx;
				fraction -= dy;
			}
			y1 += stepy;
			fraction += dx;
			DRAW_PIXEL(x1, y1, c);
		}
	}
}

Making it faster

There's one final thing we can do to make the line drawing function work faster. It still uses DRAW_PIXEL, which means we're going clipping tests and a multiplication for each pixel.

Removing the multiplications is actually quite easy. We keep a pointer to the pixel currently being drawn, and move that pointer around as we need to. The problem is that we can now draw lines outside the screen, which can cause all sorts of problems, along with graphical corruption. That means we'd have to add some clipping routines. There are about as many ways to clip a line as there are to draw a line, and they're all a complete pain in the backside to explain or implement. So I'm not going to go through them now. Maybe later.

If you need more speed, you can use a totally different line drawing algorithm, such as Xiaolin Wu's 2-step algorithm, which is a rather novel approach to drawing lines. If you want to know more about how any of this stuff works, here's some sites you should look at:

• ">Line-Drawing Algorithms

Example

The example program for this tutorial (example3.zip, uses the line function we just developed to draw patterns on the screen. It draws two arch shapes, and a weird spirograph-like shape in the middle of the screen.