Drawing algorithms

The aim of today's exercise is to discuss 3 algorithms for drawing by modifying the pixel buffer:

• drawing algorithm based on the formula for a line y=ax+b
• the Bresenham line drawing algorithm
• a recursive algorithm for filling in any shape

Let's start with preparing the environment for work, with this simple project:

<style> body { background-color:#ccc; } </style>

<script src="//cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.7/p5.js"></script>

<script type="text/javascript">

function setup() {

    createCanvas(512,512);

    background(255);

}

</script>

Users with Retina displays should also set their pixel density to 1:

pixelDensity(1);

See the first task in the previous exercise for a more detailed explanation.

We will add to the script (under the setup function) 4 variables representing respectively the start and end coordinates of the drawn line:

var x0=-1;

var y0=-1;

var x1=-1;

var y1=-1;

We will not enter the coordinates directly in code, however, but we will allow the user to select them by clicking in the canvas. As soon as the user presses down the left mouse button, we will save the initial coordinates:

function mousePressed() {

    x0=mouseX;

    y0=mouseY;

}

Then, when the user moves the mouse (with the key pressed) we will draw two circles corresponding to the selected start and end:

function mouseDragged() {  

    x1=mouseX;

    y1=mouseY;  

    background(255);

    noStroke();

    fill('red');

    ellipse(x0-3,y0-3,6);

    fill('green');  

    ellipse(x1-3,y1-3,6);

}

After releasing the key, we will erase the screen and run the appropriate algorithm to draw a line:

function mouseReleased() {

  background(255);

  loadPixels();

  draw_line();

  updatePixels();

}

Before we implement the draw_line function we can use a function for painting pixels in greyscale (for more details see previous lesson):

function set_pixel(x,y,c) {

    idx=(y*512+x)*4;

    pixels[idx]=c;

    pixels[idx+1]=c;

    pixels[idx+2]=c;

    pixels[idx+3]=255;

}

Now we can declare the line drawing function (leave it empty for now):

function draw_line() {  

}

If you run your program now, you should see the circles being drawn correctly, but no line will be drawn yet.

Direct line drawing algorithm

(task for grade 3)

This algorithm creates the approximate shape of a line, pixel by pixel, on the screen. For each column of the raster, the row in which a pixel should appear is calculated according to the formula for a straight line:

To achieve this, we will need the length of the line in the x-axis:

And the y-axis:

Given these two variables, we can compute the slope coefficient:

And the intercept:

The algorithm works by computing the value of y, by using the topmost formula (y=ax+b), for each value of x, going from x₀ to x₁. Use the set_pixel function to draw the individual pixels using the black color (i.e. value 0).

One important detail is worth noting. The x and y values are real number variables (in Javascript), but pixel positions can only be integers. The values NEED to be rounded to an integer value in order for the algorithm to work! The default rounding usually discards everything after the decimal point (i.e. Math.floor). To maintain compliance with the Bresenham algorithm (in subsequent tasks), it is better to use the Math.round method instead.

After the algorithm has been implemented, you should see it in operation. Is the line drawn regardless of which starting and ending point you choose? Does it always look good? Do you know what to do to make the algorithm work in every case (you don't have to actually do this)? If any of these things isn't clear, ask your teacher for assistance.

Bresenham's line algorithm

In the past, computers were not too fast and capable of doing much, but the use of computer graphics and its algorithms date back to the distant past, for example in a 1958 film or computer games from 1964. One of the basic problems of early computers was performing mathematical computation on real numbers. Even today we can see a significant difference in the performance of integers vs real number computation.

Some of the primary goals of the Bresenham algorithm are therefore:

• the replacement of real numbers with integers
• the removal of computationally expensive operations like real division (as in the formula for the slope a) and replacement with simple addition and subtraction

Introduction to the algorithm (task for grade 3.5)

The end goal of this whole section is to make an algorithm that draws a line in the first octant, i.e. lines sloped between 0 and 45 degrees (as expressed using screen coordinates - 0 degrees is a horizontal line running from left to right, 90 is a vertical line running from top to bottom). Note that in such lines, the x coordinate of subsequent pixels is always increased by exactly 1, while y is increased by 1 only some times and stays the same at others:

The coordinates of the pixels of the line above:

(1,1) (2,1) (3,2) (4,2) (5,3) (6,3) (7,3) (8,4) (9,4) (10,5) (11,5)

Notice also how the ideal (black) line, for each x value, crosses between two neighboring pixels for the different cases of y (the "increasing" and "staying the same" one). For example, for x=2, the line crosses in between the pixels that have coordinates y=1 and y=2. The ultimate goal is to draw the pixel that is "closest" to the line. To that end, we can define a function that computes the distance of the line to each individual pixel. We do this by taking a standard formula for the line (y=ax+b) and moving all the variables to the right side of the equation:

Now, let's replace all the unknown variables with the constants we are given by the user:

Note that this formula effectively reduces to 0 for the start and the end point of the line. If we give x₀ for x and y₀ for y we will get 0 for both brackets and 0 for the formula. Same happens if we put x₁ for x and y₁ for y - the first bracket changes to dx and the second to dy and after a bit of arithmetic we get 0 for the formula. For all other values of x and y we get the distance of the line to the given (x,y) coordinate.

Modify the program from the previous task to compute the value of D_x,y for the whole image: use set_pixel for all pixels in the image, with the color being set to the value of D_x,y. To improve the image, modify the set_pixel function to put any negative value into the red channel (as a positive value) and any positive value to the green. After doing this task, you should get the following image:

The green pixels represent positive values, red pixels negative and the color intensity (i.e. the value from the HSV model) represents the distance of the pixel to the line on the segment chosen by the user. The most black color (i.e. closest to 0) are the pixels closest to the line.

We could start working on using this formula for our line drawing algorithm, but we still haven't solved our main goal of removing the computationally expensive operations, like the dy/dx division. As it will be clear later on, we are not really interested in the exact value of the distance to the line, but only if the pixel in question is above or below the line. We can therefore modify the formula by multiplying both sides with a constant - such an operation changes only the magnitude of the results, but not their order. This way we will define a new formula, called "D hat", as D multiplied by 2dx (this will simplify our calculations, you will see why later):

If you introduce this change to your program, you will get a similar drawing as before, but it will split the screen into 3 cases: pixels below the line (red color), above the line (green color) and on the line (black):

To get full mark for this task, show both of the above solutions.

Line drawing algorithm (task for grade 4)

Let's return do the actual line drawing algorithm now. The goal for this task is to get a similar image to the one in task for grade 3, but using the Bresenham algorithm.

The first step is to draw the pixel at coordinates x₀, y₀ (this is a given). This leaves us with computing the next and all the other pixels. Using the same example as in the previous tasks, we know that the second pixel has to be either (2,1) or (2,2). On order to choose the right one, let's think about the value of the D function at the single point lying exactly between those two candidates. This point has the location (2,1.5) or in other words (x₀+1,y₀+0.5):

This point is called the midpoint of the two aforementioned pixels. This value of the D function is -0.1 and can be computed using the following formula:

If the line we wish do draw is above this point, we would like to draw the top pixel. If it is below, we would draw the bottom one. Another way of putting it is that if the D value of the midpoint is less than 0, we will draw the upper pixel (i.e. x₀+1,y₀) and if it is greater than 0, we will mark the lower one (i.e. x₀+1,y₀+1).

It's worth reminding ourselves that this algorithm should work equally good if we use the D hat function, instead. The computation complexity is, however, much simpler in this case, because we do not need to do any division and only integer values are ever used. The value of this function for the same point is -2 (or D multiplied by 2dx, which is 20). It can be computed using the following formula:

Now that we have computed both the first and the second point, we would like to compute all the others. We could use the same algorithm as above and attempt to compute the value of D_x,y for all the midpoints in the line, but there is a smarter way. Let's observe that the difference (i.e. change) of the consecutive values of D for all the midpoints in the line is generally constant (this comes from the linearity property of this function). That means we can compute the difference between any two points in the line and simply keep adding this value to each pixel, thus skipping the computation of D_x,y directly. This method is often used in computer graphics, for example in the DDA algorithm.

There is a little falsehood here, however. Looking at the image below, note that this distance is not entirely constant. If the two pixels that we need to draw are one next to the other, the distance is different than if they are diagonally oriented. For example, if we wish to draw the third pixel, we need to add the distance between the green (D(x₀+2,y₀+0.5)) and the red (D(x₀+1,y₀+0.5)) midpoints, which corresponds to the length of the yellow line. On the other hand, to draw the fourth pixel, we need to add the distance between the blue (D(x₀+3,y₀+1.5)) and the green (D(x₀+2,y₀+0.5)) point, which is the length of the orange line:

To get the values for these two cases, we can simply substitute the variables using the values above and we will get the following results (complete, step-by-step calculation is left as an exercise to the reader):

To reiterate, we can use the above two values for the two cases (remaining on the same level or moving one level down) and simply add these values to the previously computed D value, instead of computing the D from scratch for each midpoint.

Now let's repeat the whole algorithm from the start. Given the values x₀,y₀,x₁ i y₁ we will define the following:

Starting value for D:

Value added to D, if we stay on the same level in the y coordinate:

Value added to D, if the y coordinate is increased:

The algorithm is as follows

1. compute the above constants
2. set D to Dp and y to y₀
3. for each value of x from x₀ to x₁ (inclusive!)
   1. draw the current pixel (marked by the coordinates x,y)
   2. if D is smaller than 0 increase D by Deq
   3. otherwise (if D is greater equal 0) increase D by Dinc and also increase y by 1

To get full marks for this task, show the Bresenham algorithm (as shown above) only for the first octant of the circle.

Flood fill algorithm

(task for the grade 4.5)

This algorithm is used to fill a closed area marked by a curve of a uniform color. This is analogous to the paint bucket tool available in most drawing applications. There are several algorithms that can be used to solve this problem, but on this lesson, we will implement the simplest (and probably the least efficient) version.

The algorithm works by performing a simple depth-first search of all the pixels on the screen and stopping whenever it reaches a border of the fill area. The easiest method of achieving this is using the recursive approach. Unfortunately, this doesn't work too well in the browser, due to limits on the stack size. Therefore, we must implement our own approach to do recursion, without the help of the ones that come built-in with the language.

The execution of a function is achieved thanks to the concept of a stack. This stack has a limited size, depending on the environment, allowing us to run only a limited number of recursions. However, instead of the built-in "system" stack, we can simply implement our own. The best data structure implementing a stack in Javascript is the Array:

• an array is initialized by assigning empty square brackets to a variable: stack=[];
• use push method to put elements on the stack: stack.push([x,y]);
• remove the last added element using the pop method: [x,y]=stack.pop();
• we can read the number of elements on the stack with the length method: if(stack.length>0)

Let's start this task with the following program:

<style> body { background-color:#ccc; } </style>

<script src="//cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.7/p5.js"></script>

<body oncontextmenu="return false;">

<script type="text/javascript">

function setup() {

    createCanvas(512,512);

    background(255);

}

var last_x=-1;

var last_y=-1;

function mouseDragged() {  

  if(mouseButton != LEFT) return;

  if(last_x>0) {

    line(last_x,last_y,mouseX,mouseY);

  }

  last_x=mouseX;

  last_y=mouseY;

}

function mouseReleased() {

  last_x=last_y=-1;

  if(mouseButton == RIGHT) {

    loadPixels();

    flood_fill(mouseX,mouseY);

    updatePixels();

  }

}

function set_pixel(x,y,c) {

    idx=(y*512+x)*4;

    pixels[idx]=c;

    pixels[idx+1]=c;

    pixels[idx+2]=c;

    pixels[idx+3]=255;

}

function get_pixel(x,y) {

 idx=(y*512+x)*4;

 return pixels[idx];

}

//fill this function

function flood_fill(x,y) {

}

</script>

</body>

This is an expansion of the previous program. The left mouse button is used to draw a solid line. We can use it to quickly draw a closed shape for filling. The right mouse button executes the flood_fill method. Your task is to implement this method using the following pseudo code:

1. create an empty stack
2. add the mouse click (x,y) coordinates to this stack - they are given as arguments to the function
   • WARNING: sometimes the retrieved mouse coordinates are not integers and this will make rest of this algorithm not work correctly - you should do x=floor(x) and y=floor(y) to round them down to an integer value
3. while the stack is not empty
   1. remove the last coordinate pair from the stack
   2. check coordinate correctness
      • if the coordinates don't fit on the screen do continue
   3. retrieve the color of the current pixel using the get_pixel method
   4. if the color isn't white (i.e. something we can draw on - note this should be an integer value, i.e. 255), do continue
   5. draw the current pixel using some color (preferably something different than black, e.g. 200)
   6. add all the neighbors of the current pixel to the stack
      • so the one above (x,y-1), below (x,y+1), to the left (x-1,y) and to the right (x+1,y)

WARNING: While implementing this algorithm, it's easy to make a mistake which causes the program to enter an infinite loop. This will almost certainly crash your browser tab. It is recommended to use a service that will save your work (eg. jsbin.com) - otherwise make sure you save your work often! It's a good idea to add a counter to the main loop that breaks after too many iterations. In point 3 above, instead of only checking the stack size, add an extra condition:

while(stack.length>0 && cnt>0)

Initialize the cnt value with eg. 10000 before the loop and decrease it by one at each iteration inside the loop.

Extending the Bresenham algorithm

to draw lines in all directions (task for grade 5)

The goal of this task is to fix the solution from the task with the grade 4 in order to be able to draw lines in any direction, regardless of the start and end points.

You can try and use the Wikipedia solution, but a slightly different one is recommended, using the following tips:

• dx and dy should be absolute values
• if x₀ is less than x₁, the x should be increasing by 1, otherwise it should be decreasing by 1 (also, note that the condition for exiting the for loop should be x!=x1 instead of x<x1)
• this also refers to how we increase/decrease y depending on y₀ < y₁

With these few hints, the program should work much better, but some lines will still not appear correctly. If the angle is between 45 and 90 degrees, we get a shorter line that is exactly 45 degrees. The problem is that in these cases we would ideally need to iterate by y and compute x from that, rather than the other way around. A simpler solution is to leave the loop as it is, but simply change the x and y coordinates of the whole program at the very start of the function (on input) and the very end (on output, before executing set_pixel):

• to check if the above has to be performed, simply compare dx and dy - if dy is smaller than dx, everything is ok, otherwise we have a problem and need to do as follows
• at the start of the function (after computing dx and dy) change all the x and y variables: x₀ with y₀, x₁ with y₁ and dx with dy
• run the set_pixel, but change the order of the arguments, i.e.: set_pixel(y,x)

If everything was set up correctly, the algorithm should draw lines in all directions, regardless of the start and end points.