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/
Comments
excellent tutorial!

Aight, Can you take all the parts and put them together in a file? Would be nice :)

All the parts in one file? Which format would you preffer, HTML or just plain Text?


Also on an apologetic note, my site is down at the moment and it may take a bit of time to get it up.If all things go well it should be up very soon.

N3wbi3C0d3r, thanks so much for the suggestion.

Just plain text would be fine. If its on your site, and its up soon, let me know and ill just get it from there.

Unfortunately the site is going to be down for sometime, it seems that the host is having some probelms with it's servers.I will be putting up a temp site soon (if I can)

Now officially the address to my site will be http://xlock.ssr.be which will get you to my site be it the temp one or the main one which ever one I will develop.I can also switch hosts and you can still get there with this address.

Xlock is comming again soon.............

Ok, but i have a question about one of your programs, its the chat one, do you have any servers for it?

Ok, but i have a question about one of your programs, its the chat one, do you have any servers for it?

Which one?If you mean MirrorX then the zip comes with a server and the client.

http://www.polarhome.com:793/~xlock/zip/mirrrorx.zip - older than the current version but has the client + server and a bot called bubble.It is used for testing the SMBS protocol.There are 2 clients, one which is dos (standard client) and the SMBS client.

http://www.polarhome.com:793/~xlock/zip/mirrrorx01.zip is the latest

Which one?If you mean MirrorX then the zip comes with a server and the client.

http://www.polarhome.com:793/~xlock/zip/mirrrorx.zip - older than the current version but has the client + server and a bot called bubble.It is used for testing the SMBS protocol.There are 2 clients, one which is dos (standard client) and the SMBS client.

http://www.polarhome.com:793/~xlock/zip/mirrrorx01.zip is the latest

For one the links dont work, missing page. (Related to down site??)
For two i meant if you had any servers running for people to connect to. :p

http://www.polarhome.com:793/~xlock/zip/mirrorx.zip
http://www.polarhome.com:793/~xlock/zip/mirrorx01.zip


My mistake, there were too many 'r's.

If you mean if I have any public servers running, the answer is unfortunately no.But there are a couple running on my uni's lan network which are not accessable over the internet.

If your school has a network then you can use it there.It's not hard to set it up too.Just put a short-cut in the Start->Programs->Startup to make the mirrorx server start everytime the computer comes on.


P.S:Those links are to the old site's zip archive.The main site should be up in a week or so.

http://www.polarhome.com:793/~xlock/zip/mirrorx.zip
http://www.polarhome.com:793/~xlock/zip/mirrorx01.zip


My mistake, there were too many 'r's.

If you mean if I have any public servers running, the answer is unfortunately no.But there are a couple running on my uni's lan network which are not accessable over the internet.

If your school has a network then you can use it there.It's not hard to set it up too.Just put a short-cut in the Start->Programs->Startup to make the mirrorx server start everytime the computer comes on.


P.S:Those links are to the old site's zip archive.The main site should be up in a week or so.

Awsome, my school is being a pest so ill try to make around it, they have Novell to keep us from installing anything, but we can download to our server sapce on the Student Server. Should alow me to do it ;P

This article has been dead for over six months. Start a new discussion instead.