If this page looks like garbage then you need one of these browsers...
Please sign my programmer's page guestbook.
Faster graphics function with Integers
Had you going there for a minute, huh? Okay, let's see if we can derive some ways to draw circles and lines without using floating point math. Doing so will allow us to render these graphics much much much faster than using floats.
Of course figuring out how to use plain integers to do the work is quite a challenge, one I most certainly don't feel like taking on myself. So, needless to say I got these algorithms elsewhere. It just so happens that a mathematician by the name of Bresenham came up with a method for drawing lines and circles really fast by using integers only.
Of course, I cannot take any credit for the algorithms I present below and for the most part I still do not understand them. But I do know that the code works and works fast! Speed is of the essence when creating video games using these algorithms. Let's take a look at them...
Bresenham's algorithm for drawing circles
void Circle(int x, int y, int radius, unsigned char color)
{
int a, b, d;
int xx1, yy1, xx2, yy2;
int xy1, yx1, xy2, yx2;
a = 0;
b = radius;
d = (1 - radius) * 2;
xx1 = x;
yy1 = y + b;
xx2 = x;
yy2 = y - b;
xy1 = x + b;
yx1 = y;
xy2 = x - b;
yx2 = y;
while (b >= a) {
SetPixel(xx1, yy1, color);
SetPixel(xx1, yy2, color);
SetPixel(xx2, yy1, color);
SetPixel(xx2, yy2, color);
SetPixel(xy1, yx1, color);
SetPixel(xy1, yx2, color);
SetPixel(xy2, yx1, color);
SetPixel(xy2, yx2, color);
if (d + b > 0) {
b--;
d -= (b * 2) + 1;
yy1--;
yy2++;
xy1--;
xy2++;
}
if (a > d) {
a++;
d += (a * 2) + 1;
xx1++;
xx2--;
yx1++;
yx2--;
}
}
}
I found this function off of a BASIC news group. Yes, a basic news group. Of course, needless to say I converted it for use in the C programming pages. From what I've seen, it runs pretty fast, put it in a loop and the circles look like a blur.
Like I said, I cannot take credit for this function, this function was converted from a similar BASIC function by Douglas H. Lusher, 05-09-1996.
Bresenham's algorithm for drawing lines.
void Line(int x1, int y1, int x2, int y2, unsigned char color)
{
int dx, dy;
int xIncr, yIncr;
int error = 0, i;
dx = x2 - x1;
dy = y2 - y1;
if (dx >= 0)
xIncr = 1;
else {
xIncr = -1;
dx = -dx;
}
if (dy >= 0)
yIncr = 1;
else {
yIncr = -1;
dy = -dy;
}
if (dx > dy) {
for (i=0; i<=dx; i++) {
SetPixel(x1, y1, color);
error += dy;
if (error>dx) {
error -= dx;
y1 += yIncr;
}
x1 += xIncr;
}
} else {
for (i=0; i<=dy; i++) {
SetPixel(x1, y1, color);
error += dx;
if (error>dy) {
error -= dy;
x1 += xIncr;
}
y1 += yIncr;
}
}
}
This function was adapted from a similar function written by Andre LaMothe. In fact, I only made a few minor changes, since I found this function so well designed and fast. (That's the key.)
As far as how these functions actually work, I'm afraid that I cannot help you out too much there. I know a little more about the line function than I do about circle function. Mainly because Andre explained his line function and Douglas did not explain his circle function. At any rate we now have faster functions than we did previously and I would suggest that you replace my version of the line and circle functions (which used floats and are slow) with these new faster functions.
Make our functions even faster
Both of these new functions, as well as our old functions, have one thing in common. They all call the SetPixel function to actually plot the pixels. Let's look at the way it works and see if we can speed it up.
void SetPixel(int x, int y, unsigned char color)
{
VideoMem[y * 320 + x] = color;
}
At a first glance, there really does not seem like there is a lot we can do with this function. It has one line and does a very basic operation (assignment). Well, the fact that it has only one line brings up the possibility of actually putting that one line within our code. For example, our line function has this following code snippit...
.
.
.
for (i=0; i<=dy; i++) {
SetPixel(x1, y1, color);
error += dx;
if (error>dy) {
error -= dy;
x1 += xIncr;
}
y1 += yIncr;
}
.
.
.
Why not just replace all the SetPixel function calls with the line that the SetPixel function contains and eliminate the SetPixel function altogether?
for (i=0; i<=dy; i++) {
VideoMem[y1 * 320 + x1] = color;
error += dx;
if (error>dy) {
error -= dy;
x1 += xIncr;
}
y1 += yIncr;
}
Doing so eliminates the need to make a function call (and the overhead associated with it). Of course, this does make the pixel plotting functionality a bit more complex since we've replaced the simple function call with it's actual statement used.
Problem with Macros
Macros, unlike functions, do not do any kind of data type checking during compile. Meaning, that the compiler would ensure that the data is of appropriate type before using it in the SetPixel function but not in the SetPixel macro. This is of little concern for us with this implementation, but something I felt I needed to inform you about.
Another way is to keep all the calls to the SetPixel function and to make the SetPixel function an inline function. In other words, tell the C compiler that whenever it encounters a function call to SetPixel, replace it with the actual statement that the SetPixel function uses and match the parameters. The standard headers (such as stdio.h for example) makes use of some of these inline functions, they're known as macros.
Yes, you may have heard of macros, the C header 'stdio.h' has a few of it's own. For example, the getchar function is a macro. Whenever the C compiler encounters your use of the 'getchar' function, it replaces the function call with another function call getc(stdin). If you were to take a look at the actual file called stdio.h, you would see that it was implemented like so...
#define getchar() getc(stdin)
#define putchar(c) putc((c), stdout)
Note that I also included that putchar macro and it's replacement function to illustrate how a parameter can be used in a macro. This opens up a possibility on creating a SetPixel macro. Remove the SetPixel function from your source and replace it with this single line.
#define SetPixel(x,y,c) VideoMem[y * 320 + x] = c
And Viola, instant inline function. Now instead of making a function call whenever you specify the SetPixel function call, it instead replaces the call with the VideoMem element assignment, eliminating a function call and speading up our program.
Before we move on, I want to suggest yet another way to speed up the SetPixel macro even further. You see how we multiplied the 'y' variable by 320 and added the 'x' variable. Well, if we took the multiplication and replaced it with shifting operations we can acheive even greater speed, since shifting is faster than division and multiplication.
I found a code snippet written by Andre LaMothe, it works on the basis that 320 is equal to 256 + 64, both of which are even powers of 2 (and therefore can be used in shifting). The number 256 is 2 to the 8th power and 64 is 2 to the 6th power, so 320 is equal to 2^8 + 2^6. In shifting terms, it would look like 1<<8 + 1<<6, when multiplied with y, our function would look like this...
#define SetPixel(x,y,c) VideoMem[(y<<8) + (y<<6) + x] = c
I ran benchmarks on both functions and the new shifting function is much faster than the old one that used multiplication.
Clearing the garbage off the screen
Of course now we know how to set pixels and draw lines and circles. Well, what if we want to clear that stuff off the screen and return to a blank screen? Hmmmm... Well, we know how to set a pixel, so how about...
void FillScreen(unsigned char c)
{
unsigned int x, y;
for(y=0; y<ScreenHeight; y++)
for(x=0; x<ScreenWidth; x++)
SetPixel(x, y, c);
}
Ummm, well, sure if you like wasting good processing time like that. You see, if you did the math for each iteration, you will find that it is just simply moving one byte at a time from A000:0000 to A000:F9FF and assigning what value you specified in color to each byte.
If that is the case, then wouldn't this function work much better?
void FillScreen(unsigned char c)
{
unsigned int i;
for(i=0; i<ScreenWidth * ScreenHeight; i++)
videoMem[i] = c;
}
Well, the answer is, yep, and much faster too. Fastest possible, no... Because C already has a function that does this type of memory assignment for us. It's called memset. This function takes a pointer to a block of memory along with a byte value to set each byte too and how many bytes it should set. However, memset works with near pointers, so we must use the far version, _fmemset, because videoMem is a char far pointer.
void FillScreen(unsigned char c)
{
_fmemset(videoMem, (c), ScreenWidth * ScreenHeight)
}
Easy function, and it only took one line... Wait a sec, we can make this even better by making it a macro and therefore an inline function which will run the fastest. So let's make it a macro.
#define FillScreen(c) _fmemset(videoMem, (c), ScreenWidth * ScreenHeight)
Now anytime you want to clear the screen to a particular color, you can now use FillScreen with a color code. Like FillScreen(0); to clear the screen to black (the default color for 0).
Send your questions, comments, or ideas to: wilkeg@gamewood.net
This page hosted by
Get your own Free Home Page
