Welcome to this unit in which we're going to talk about line drawing. Now, in the previous unit we talked about vector graphics and bitmap graphics in general. And we discus the virtues of vector graphics. And among other things, we decided that we're going to implement three graphics primitives, which are drawing a pixel, a single individual pixel on the screen in a certain location. Drawing a line from two points on the screen, and drawing a circle given a center and a radius. So in this unit, we will start with the drawPixel as a point of departure because we've already discuss it in the previous unit. And we will learn how to draw lines using drawPixel and how to draw circles using drawLine. And so, let us begin with draw line and in order to motivate line drawing we go back to this figure that we saw in the previous unit. And one nice thing about vector graphics is that because everything is governed by simple algebraic statements, I can, for example un-group this bunch of polygons into some subsets or sub-images. All of which are drawn using a vector graphics and I will charge arbitrarily the beak to focus on. And I'd like to show you how we can draw this beak. So basically, we can draw it as follows. I draw this line and that line, and I keep on drawing lines, which eventually are going to constitute a polygon, which implements or realizes this beak. And I intentionally grow it slowly because I want you to feel the frustration. I wanted to say, when are we going to finally get this beak drawn on the screen? Well, here it is you've got it. What I wanted to illustrate to you are two things first of all that image drawing is done as a succession of line drawing operations, and second of all, you better do it fast. Because if line drawing is going to be slow, then everything is going to be sluggish. The user is going to be extremely frustrated. We'll have no animation, no video, no YouTube. And the world will be much bleaker. So everything depends on the pace in which we can draw these lines and we want to draw them as quickly as possible. So let's delve into the details of line drawing using this sample grid here. And let me begin with a simplifying assumption. I want to focus on your lines that go northeast. So here's one typical such line, I want to draw the line that goes from x1, y1 to x2, y2. And I want you to notice that it's really impossible to draw such a line. Why? Because the only thing they can do is turn pixels on and off. So in this particular example, you know I have to turn on this pixel and this one, and this one, and that one and notice that I can only approximate the line. And in each iteration, I either go right or up, why? Because we're going northeast, so these are my only two possibilities. Now, look at this pixel right here. It looks like maybe I should turn on this pixel. The one which is diagonally on the top right of it. But I don't want to do it. Because if you do that, you're going to create something that will eventually look like a hole in the middle of the line. So I always go either right or up. And in this particular case, I can make an arbitrary choice. So I decide to go up, then I go right, right, right, once again, I can go either right or up. I go up and right. So what I got is a pixel, the approximation of the desired line. And if the resolution of the screen is sufficiently large and if these pixels are sufficiently small. I'm going to draw something which is going to fool the human brain to think that what we have here, is a smooth line. That's the trick that we do in vector graphics. So once again Draw line is implemented though a sequence of drop pixel operations and in each stage, we have to make a very simple decision, we want to go right or up, that's all. And we better make this decision fast because it turns out that this decision or the time that it takes to compute it, holds the key to the speed of this entire algorithm. So let's look at the details. Here is the line that I want to draw, and I begin by introducing some convenient notation, instead of using absolute coordinates, I used deltas. I begin with x and y but I want to go all the way to x plus dx, y plus dy, which is more convenient. And I'm going to use the following algorithm, which takes a minute or two to get used to. I will use two variables, a and b, to a count, for how many pixels I went to the right so far, this will be a and how many pixels I went up so far, this will be b. And at the beginning a and b equals 0, and I'm going to draw. In each duration of the algorithm, I'm going to draw x plus a, and y plus b. So at the beginning, I'm going to draw the xy pixel, because a and b are 0. And then, the next thing that I'm going to do, is I'm going to decide if I want to go right or up. Now, in this example here I have to go to the right. So to go to the right, I increment a, and I don't touch b. So when I go back to the while, I'm going to draw the pixel, x plus 1, y plus 0. And it's this pixel right here. And now, I see that they have to go up. So I'm going to leave a intact, and b will become 1. And therefore, going back to the while loop, I'm going to draw this pixel now. So you see that in each iteration, I either increment a or b I never increment both, because we decided to avoid going diagonally. So either a goes up by 1, or b goes up by 1. And so, irrespective of how I'm going to snake around this line, at the end, a is going to make a distance of dx And b is going to make a distance of by. And this gives you a clue on how we can implement the while condition. Well, basically, as long as a is less than dx, and b is less than dy, I still have work to do. I haven't reached my target yet. All right, the next thing that I want to delve into is this condition, going right. How do I know if I want to go right or up? Well, here is what we propose to do. Take a look at this line here, and compare these two angles. dy/dx is the desired angle. That's the Holy Grail, that's where you want to go. And b/a is what you ended up doing so far, okay? So if b/a is greater than dy/dx, you want to make a correction to the right. Otherwise you want to make a correction going up. So in this particular case, that's the condition that we get. And now we're going to go right. And we're going to draw this line again. Once again, b/a is greater than dy/dx, so once again we want to manipulate a. And we're going to make a, instead of 3 a will become 4. So we get this pixel, we draw this line. Now b/a is less than dy/dx, so we're going to manipulate b. And we're going to go along the y-axis. So we'll have this pixel. Once again, we compare the two angles, we go to the right. We compare the two angles, we go to the top, and you got the picture. And so if you end up overshooting, you make a correction to the right. If you end up undershooting, you make a correction up. That's the basic algorithm. So it looks like we're done. And yet I told you, and I warned you, that line drawing must be as fast as we can. And if you inspect this algorithm, and in particular, if you look at this condition here, then the only two words that come to my mind are, oy vey! Because we see that in every iteration of this algorithm, for every humble pixel that you want to draw, you have to make two divisions, which are expensive operations. And maybe, if we'll use some ingenious tricks, we can somehow get rid of these two division operations. Or maybe one of them, let's see what we can do. So let's begin by looking at this condition. And we realize, using elementary-school algebra, that b/a greater than dy/dx is the same, it has the same truth value, as a dy less than b dx. With that in mind, let us look at this expression here. a dy- b dx, let's call it diff. Now, obviously this diff is going to change in every iteration, because in every iteration we change either a or b. Now, at the beginning diff is going to be 0, because a and b are 0. And the condition that you have here, this messy condition, can be effectively replaced by the question, is it true that diff is less than 0? So already, we have a nice simplification of the algorithm. And yet we have to maintain diff, right? Whenever a or b change, we have to change diff as well. So what is the impact of incrementing a and b on diff? Well, it turns out that it has a beautiful impact, because when a goes up. Look at the definition of diff, when a goes up by 1, diff goes up by dy. And when b goes up by 1, diff goes down by dx. This comes out of the definition of diff. With that in mind, this entire algorithm can be reduced to what we see here. So that in every iteration we either increment a or b, and we update diff accordingly. And the beauty of this algorithm is that it involves only addition and subtraction operations. And because it involves only addition and subtraction, versions of this algorithm can be implemented highly efficiently on either software or hardware. And the algorithm is as good as it gets, you cannot improve it, okay? And the runtime of this algorithm now depends only on the number of pixels that you have to draw. And you have to draw these pixels anyway, right? You have to draw these pixels, and therefore we get a beautiful algorithm, which once again is as good as we can hope for. All right, so we know how to draw lines. And now that we know how to draw lines using drawPixel, I want to illustrate, how are we going to draw circles using lines? So here's my circle. If I'm asked to draw a circle I should get at least three inputs, which are the center of the circle, x,y, and the radius. And how can I draw it? Well, once again, let us remember. This is not the perfect pure world of geometry. This is the pixelized world of computer screens. So we cannot draw circles, we can only approximate the circles using pixel drawing or line drawing. So in particular, this circle here. If we are content of drawing a filled circle rather than the outline, then we can draw this line, and then this line, and that line, and so on and so forth. We can draw all these lines, and this will create the illusion of a filled circle. If the resolution of the screen is sufficiently small, our brain will think that what it sees is a smooth circle. How do we do it? How do we draw these rows of pixels? Well, here's the algorithm, here's the signature. We're going to draw a circle that starts at the origin x,y and has a radius of r. And to get started I want to draw the entire diameter of the circle. And I want to characterize each one of these rows. I'm going to draw 2r rows, right? We have r pixels going this way, and then another r pixels altogether. We're going to draw 2r rows. And I can characterize each one of these rows by the distance of this row from the origin. And so in the middle of the circle, the longest row is characterized by dy = 0, because the distance from y is 0. And then as I go up the distance goes down. Because remember the 0,0 origin is at the top left of the screen, that's the convention in computer graphics. So as you go up, the distance goes down until it reaches all the way to -r. And as I go down, the distance from the origin goes up until I end up with dy = r. And with that in mind, let's take a look at this typical pixel here and let's try to figure out what is the coordinate of this pixel. Because if we figure out what is the coordinate of this pixel, we're done. Because the other coordinate of the pixel on the other side is going to be symmetrically equivalent. And then we can draw a line between these two pixels, and we can do the same thing in every line along the contour of this circle. So once again, the coordinates of this pixel hold the key for the entire algorithm. So, what are the coordinates? Well, I don't know what the x coordinate is, I call it x1. But the y coordinate must be the origin y plus dy, right? And the same is going to happen in the symmetric pixel on the other side of the circle. So, we know what is y and we still don't know what is x. But we already begin to see the logic of the algorithm. And the logic is such that for every dy going from minus r to r we want to draw a line that goes from x1, y plus dy, to x2 y plus d y, that's the logic of algorithm. And the only thing that remains to be done is to figure out what x one and x two are. If there are no x one and x two, we can finish our, the specification of this algorithm. Now, to compute these two coordinates, what I think every one of you would do after a few seconds of reflection, is you would draw you know these lines here. And you would look at these two triangles, and you can use the pythagorean theorem to compute the base of each one of these triangles, and now that we have the base we are home free. The base, as you see, is defined in terms of the inputs only, r and dy is also a function of y. So here's the coordinate of this pixel. Here's the coordinate of that pixel, which is symmetrically equivalent. And all I have to do is plug these two numbers into my algorithm and I'm done. This is the algorithm for drawing the circles using line drawing. It may not be what we have expected, but it delivers the goods. It will draw a fill circle, and what about drawing just the outline of the circle which maybe required? Well, why don't you think about it yourself. And give yourself one or two minutes to think about this question, and when you have the answer or not continue the tape. So stop the tape now, think about it, how can we modify this algorithm to draw the outline of the circle. And then, run the tape again, and we'll talk about the answer. All right so, the question was, given that we know how to draw a filled circle how do we draw just the contour of the circle or the outline. Well, the answer is instead of doing a drawline you two draw pixel operations, right? You draw the left pixel and the right pixel, the left pixel and the right pixel, left, right, left, right, left, right, left, right, left, right. And you've drawn the entire circle. [COUGH] All right, so this is circle drawing, and we know how to draw pixels, lines and circles. And it's time for our implementation notes. So, up until now everything was very elegant and nice, and from now on we have to deal with the knitted wicked details of actual implementation. So here's our drawPixel algorithm, we saw it in the previous unit. And notice that it has to use peek and poke. So peek and poke are readily available in the memory class that we implemented in one of the previous units. And notice also, if you look at the third line from the bottom, we have to set the xth module 16th bit of value to the current color. So, how can you access an individual bit within a 16 bit value? Well, this can be done using some logical 16 bit operations. So think about it, this is something for you to ponder about and you will figure out how to set individual bits in this value, which is one requirement along the way of writing a jack implementation of drawPixel. What about drawLine? Well, we have to do several modifications. First of all, this algorithm that I showed you because I showed you this graphical metaphor of going up right, and so on. I decided to base this metaphor on a (0,0) origin, which is at the bottom left on the screen. Which is the intuitive mathematical way to think about it but in reality, in computer graphics, the (0,0) is up here, it's in the top left corner of the screen. So, you have to modify this algorithm to account to a top left origin. So that's one modification. And the other modification is that we call, that we made a simplifying assumption. We decided to draw on the lines that go northeast. In reality, we have at least four different situations. We go even northeast or southeast or northwest or southwest. And so you have to modify, you have to somehow handle every one of these four possibilities. And what about lines that go along the cross, go either vertically or exactly horizontally? Well, these lines, I think should be handled as special cases, because maybe, if you think about it a little bit, maybe we can handle them more efficiently than just using the same algorithm for these lines also. Think about it. So, that's another tweak that we can do in order to optimize the line drawing. By the way, it's an important tweak because, many line drawing operations are either horizontal or vertical. For example, whenever you want to draw a rectangle, a square and so on. So, we want everything to be fast but in particular we want popular operations to be fast so it's worth a while trying to optimize drawing of horizontal and vertical lines. All right, what about draw circle. Well, in turns out that this algorithm can overflow. And yet if you set r to a number which is not greater than 181,then you wont run into overflow problems and here we draw circles, this makes it graphic hardware package dependen, it depends on the size of hexscreen. But so be it, every once in a while you have to make some concessions in life and so this is it. That's as much as I wanted to say about the screen class. And we talked about draw pixel, draw line, draw circle. The remaining functions are simple to implement so I trust that you will do it using your own judgment. And that's it. And in the next unit we're going to talk about textual outputs.
