In this project-centered course you will build a modern software hierarchy, designed to enable the translation and execution of object-based, high-level languages on a bare-bone computer hardware platform. In particular, you will implement a virtual machine and a compiler for a simple, Java-like programming language, and you will develop a basic operating system that closes gaps between the high-level language and the underlying hardware platform. In the process, you will gain a deep, hands-on understanding of numerous topics in applied computer science, e.g. stack processing, parsing, code generation, and classical algorithms and data structures for memory management, vector graphics, input-output handling, and various other topics that lie at the very core of every modern computer system. This is a self-contained course: all the knowledge necessary to succeed in the course and build the various systems will be given as part of the learning experience. The only prerequisite is knowledge of programming at the level acquired in introduction to computer science courses. All the software tools and materials that are necessary to complete the course will be supplied freely after you enrol in the course. This course is accompanied by the textbook "The Elements of Computing Systems" (Nisan and Schocken, MIT Press). While not required for taking the course, the book provides a convenient coverage of all the course topics. The book is available in either hardcopy or ebook form, and MIT Press is offering a 30% discount off the cover price by using the discount code MNTT30 at https://mitpress.mit.edu/books/elements-computing-systems. The course consists of six modules, each comprising a series of video lectures, and a project. You will need about 2-3 hours to watch each module's lectures, and about 15 hours to complete each one of the six projects. The course can be completed in six weeks, but you are welcome to take it at your own pace. You can watch a TED talk about this course by Googling "nand2tetris TED talk". *About Project-Centered Courses: Project-centered courses are designed to help you complete a personally meaningful real-world project, with your instructor and a community of learners with similar goals providing guidance and suggestions along the way. By actively applying new concepts as you learn, you’ll master the course content more efficiently; you’ll also get a head start on using the skills you gain to make positive changes in your life and career. When you complete the course, you’ll have a finished project that you’ll be proud to use and share.
Unit 6.7: Line Drawing
Loading...
Из курса от партнера Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
168 оценки
Hebrew University of Jerusalem
168 оценки
Из урока
Operating System
Познакомьтесь с преподавателями
Shimon SchockenProfessor
Computer Science
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
