Graphics In Pixel
Part II B
'Realization of an Enigma'Introduction
------------
Life's unfair, writing good tutorials take a lot of time, not typing it, but thinking up
the content does. Life's fun too, I had quite a good time learning new stuff. My hobby
at present is learning rasterization techniques. It's quite fun, but learning how the
things are done, is best done mathematically. The best part I love about algebra is the
way in which one proves something - make an assumption then derive something and
using the derivation prove the assumption was right.
Anyway rasterization is an approximation of reality. A raster is the medium used to
represent, in our case, the primitive (i.e. line, circle etc).This is usually, on computers,
a grid of square pixels.
Date:29/10/2004
Graphics Output
---------------
This series goes in for Mode13h (which is a very ancient mode) and DOS based. If you
can get this working then well and good. Incase you are unable then there is GCL which
stands for GDI Console Layer. It provides you a linear frame buffer just like mode13h but
uses windows gdi for output,=> win32 mode13h. You will be able to use the code given here
without any problem. Also If enough people ask for it, I will start providing GCL based code
too.
Razterization of a Circle
-----------------------
Razterization is a big fake joke. During this we are not actually calculating where the next
point is, we are just choosing to increment x,y coordinate of the current point (usually
by 1) to find the next one. That's because our raster (i.e. the screen) is composed up with
just pixels arranged in a grid, like on graph paper. This way of thought can be used to
raster anything be it line or circle.
Since the circle is symmetrical it can be divided into equal 8 parts .Each part represents
a 45* angle's arc. So we draw just one part and the rest can be mirrored easily .We can
start with from the 90* to 45* arc. We start for the point which is at 90* from the x-axis
(i.e. x=0,y=radius of circle)
Now suppose we have a point x,y which is on the circle, how do find the next one?
There are only two options available to us, i.e.
1> Increase x by 1
2> Increase x by 1 and decrease y by 1
Now there's a function f = fn(x,y) = x^2 + y^2 - r^2 which show the relationship of a
point to the circle. They are as follows:
f < 0 (x,y) inside the circle
f = 0 (x,y) on the circle
f > 0 (x,y) outside the circle
Now let point T be (x+1,y) [i.e. option 1] and S be (x+1,y-1) [i.e. option 2].Now lets look
at a point which is halfway between T and S i.e. P = (x+1,y-1/2)
Now if we plug this into the function mentioned before we get:
Pi = fn(x+1,y-1/2) = (x+1)^2 + (y-1/2)^2 - r^2
Now by using the properties, if Pi is negative the mid-point is inside the circle and we
choose T to be displayed, else S the point we want.
Now the point i.e. Pi+1 , we have x = x+1 so:
Pi+1 - Pi = [Xi+1]^2 - (X+1)^2 + (Yi-1/2)^2 - (Y-1/2)^2
Pi+1 - Pi = [(X+1)+1]^2 - (X+1)^2 + (Yi-1/2)^2 - (Y-1/2)^2
Hence: Pi+1 = Pi + 2(Xi+1) + 1 + (Yi^2 - Y^2) - (Yi-Y)
If T is chosen then Yi = Y, therefore:
Pi+1 = Pi + 2(Xi+1) + 1 + (Y^2 - Y^2) - (Y-Y)
=> Pi + 2(Xi+1) + 1
=> Pi + 2Xi + 3 in the case pi < 0
If S is chosen they Yi = Y-1, therefore:
Pi+1 = Pi + 2(Xi+1) + 1 + ([(Y-1)^2] - Y^2) - ((Y-1)-Y)
=> Pi + 2(Xi+1) + 1 - 2(Yi-1)
=> Pi + 2(Xi - Yi) + 5 in the case pi >= 0
Gee, all this creepy math formulae are actually simple stuff we do when we first learn
algebra, the derivations I wrote took lot of short cuts and look really weird in anscii.
Sorry if you did not understand the derivation , just take it as a fact like the rules we
should follow when we do things in geometry, like the theorems (which all have their
proofs).To sum it up:
Pi is used to choose between points T and S.
If Pi < 0 we choose T which is at (x+1,y) and the Pi for the next point is => Pi + 2Xi + 3
If Pi >= 0 we choose S which is at (x+1,y-1) and the Pi for the next point is => Pi + 2(Xi - Yi) + 5
So let look at how to generate the 45* section for which we derived all the above stuff.
int x = 0, y = r, p = 1 - r;
while(x<=y)
{
//Make all the 8 parts
pixel(x,y,color);
pixel(x,-y,color);
pixel(-x,y,color);
pixel(-x,-y,color);
pixel(y,x,color);
pixel(y,-x,color);
pixel(-y,x,color);
pixel(-y,-x,color);
if(p < 0)
{
p += 2*x + 3;
}
else
{
p += 2*(x-y)+5;
--y;
}
++x;
}How did we get p = 1-r, it is from the mid-points's equation (X+1)^2 + (Y+1/2)^2 - r^2
=> (0 +1)^2 + (r+1/2)^2 - r^2 = 5/4 - r. We just take 1 - r just to get the sign for p
and because the difference is less than 1/4, so it does not affect the algorithm at all.
This algorithm to scan-convert a circle is called the Mid-Point Circle algorithm.
In short, we are trying choose between the two points (i.e. options 1 & 2) T and S by using
the function fn(x,y) = x^2 + y^2 - r^2 which shows the relationship of a point to the circle.
The two equations we derived are used with the current points coordinates to calculate the
NEXT mid-point's relation to the circle (via f(x,y), i.e. check if it is in or out.
That's about it for making your circle ;)
Double Buffering (Virtual Screen)
--------------------------------
As I mentioned in the last part how the screen works, i.e. by drawing the screen line by line.
Now this produces a problem when we change things on the screen. Suppose are filling the
screen with a single color by setting all the pixels in the screen's memory to the color we
want. Now suppose we do it at the time when the screen's electron gun is somewhere at the
middle of the screen, what will happen?
The part above the electron gun will be of the previous screen color while the rest will be
fill with the new color we specified. This causes some horrible flashes and tears in the picture.
Just check out flick.exe to see what I mean, yuck.
Now a good way to prevent this is to draw everything to the screen when the electron gun
in a CRT monitor is moving up, this called the Vertical Retrace. Now a problem arises and
this is that drawing what ever we want may take longer than the time it takes the monitor
to complete it's vertical retrace.
We can overcome this very easily, by using another buffer on to which we can draw, and
then copy the completed picture to the screen in one step. This buffer is called the
Virtual Screen.
Creating a virtual screen is quite easy. Just create an array which is the exact size of the
screen , which can be calculated by multiplying it's width and height.
VirtualScreen = new DATATYPE[width*height];
For mode13h
unsigned char *VirtualScreen = new char [320*200];
Animation
----------
Animation is simple, anything moving can be called animation. I got a nasty idea now,
I will let you do the animation yourself since I taught you how to draw things, now
let me see you move them.
Just kidding, I will leave you with some advice and an example. First of all, always
represent your objects (i.e. the stuff you animate), using classes or structures.
In 2D, the object's position can be represented using two int vars x,y and to move
it, just increase the x,y coordinated by how much they should be moved.
struct loc2D
{
int x;
int y;
};Canning rhetoric talk, let do a pixel which bounces around the screen. The bounce effect
is very simple to do. When the object hits anything on at particular axis, just reverse the
sign of that coordinate's x or y which ever it maybe.
Let's do it.
int SCREEN_X_MIN = 0;
int SCREEN_Y_MIN = 0;
int SCREEN_X_MAX = 319;
int SCREEN_Y_MAX = 119;
struct obj
{
loc2D loc;
loc2D bounce;
};
obj Object;
Object.loc.x = SCREEN_X_MIN;
Object.loc.y = SCREEN_Y_MIN;
Object.bounce.x = 1;
Object.bounce.y = 1;
while(!kbhit())
{
drawpixel(Object.loc.x,Object.loc.y,color);
Object.loc.x += Object.bounce.x;
Object.loc.y += Object.bounce.y;
if(Object.loc.x <= SCREEN_X_MIN || Object.loc.x >= SCREEN_X_MAX)
{
Object.loc.x *= -1;
}
if(Object.loc.y <= SCREEN_Y_MIN || Object.loc.y >= SCREEN_Y_MAX)
{
Object.loc.y *= -1;
}
}Oh and btw, you will have to do few additions, like adding the code to get into mode13h.
Conclusion
----------
Animation is one of the best things when it comes to graphics, so that will be taken up
in Part 4, where we will discuss things like time-based movement and sprites. In Part 3,
things will be general and we will see how to prevent our programs from crashing, and
taking the PC with it ;).
Send me any doubts or questions you have, and it's most welcome. Later guys/gals.Post comment here too ;).
Mail: xfirenet@hotmail.com
Website: http://xlock.hostcubix.com/