Drawing all lines

In the last section, we had a problem with only lines going from left to right being drawn, some lines having gaps and vertical lines not even being being defined.

We will start with the first issue, as it is the easiest to solve.

We basically just think about how the line looks on the screen. Does it look different, if we go from $\mathbf{b}$ to $\mathbf{a}$ instead of the original order of $\mathbf{a}$ to $\mathbf{b}$?

This will of course still be the same line, if we draw it! So we can just switch $\mathbf{a}$ and $\mathbf{b}$, if the line goes from right to left!

Try it out below!

Exercise:

• Switch the points $\mathbf{a}$ and $\mathbf{b}$, if the line goes from right to left in the rasterizer.js file

Your solution should now show lines on both sides of the middle.

Solution:

Now that we have solved the first issue, we can solve both outstanding problems. As all lines going left are now flipped to the right, we only have to think about the right side.

Which lines do we still have an issue with?

• $|m| > 1$
• $b < 0$
• $mx \neq y$

The slope $m$ determines how much $y$ changes when we move one $x$-unit to the right. If $|m|$ is greater than 1, $y$ will change by more than one (pixel). Thus, it happens, that the line "skips" a pixel in the vertical direction.

We can solve this issue in a similar way to the left-right flip.

Imagine we draw a line with an angle $\alpha < 45^\circ$ with respect to the $x$-axis. Now draw another line with $\alpha$, but this time with respect to the $y$-axis.

When you look at them both, those line basically look the same, just mirrored along the diagonal! You could also flip over your piece of paper and rotate it, such that the $y$-axis now points in the $x$-direction. Then $x$-will point to the old $y$.

We use this knowledge to swap the $x$ and $y$ coordinates, if $|m|>1$. In matrix terms, this is just like transposing the image. $|m|$ will be greater than $1$, when the absolute change in $y$ is greater than the one in $x$.

Using this criterion instead of the value of $m$ also allows us to handle vertical lines! If we used $m$, we might encounter a division by zero or some other issues beforehand, depending on our language of choice.

Switching out the $x$ and $y$ coordinates does change how the line would look, in contrast to the left-right flip. To counter that, we just have to remember, if we switched and switch back when we specify the pixel coordinate to write to.

Keep in mind to do the left-right switch after the transposition, as the line might go from left to right when looked at from the $y$ direction!

Try it out! Below this codeblock, you can find the (hidden) final code, that you can expand to look at. But you can also run it without looking at it to see the expected result.

Exercise:

• Create a variable transpose, initially false

• Check, if we need to flip $x$ and $y$ ($|m| > 1$)

  • If we need to flip, set transpose to true
  • Flip the points $x$ and $y$ components

• In the drawing loop

  • If transpose is true, the pixel coordinate is $(y,x)$ instead of $(x,y)$

Solution:

What else can we do?

With the knowledge of the previous algorithm, which is often called the Digital Differential Analyzer (DDA) line drawing algorithm, you basically know a whole bunch of similar ones, that can do more or are a bit smarter. We will only mention a few improvements/ideas here (though the first one can be found in the course code...) and encourage you to have a look yourself!

First of all, one thing to notice is that we do a bunch of floating point operations. In JavaScript, this doesn't really matter, as only the Number type exist, which is a float. Many other languages do have integers, which often are (or were) faster than floats. Even if its just a bit, this matters when you draw a lot of lines and pixels, so these kinds of micro optimizations make sense. One of the best known examples of such an optimization is the Bresenham line drawing algorithm.

The Bresenham algorithm only considers the first octant (angles $0^\circ$ to $45^\circ$) and moves along $x$. At each step it asks: "Is middle of the next pixel above or below the line?". If it is below, $y$ is increased by $1$, otherwise it stays the same. The important part is, that by some rearranging and manipulation of terms, the computation of this check can be done completely using integers. Lines with different angles are handled the same way we did and in general the code looks nearly identical to our code, so it shouldn't be hard to implement the Bresenham algorithm.

One issue with our current version and especially Bresenham is, that lines look a bit jaggy and can only lie on integers. A way to solve that is anti-aliasing. Ony way would be to just draw in a higher resolution and downsample. This is if course a lot of extra work. A different idea is for example to adjust the brightness of our pixel writing depending on how close the line is to the center of a pixel. If the line is on it, give it full brightness, if it is far away, let the color fade as well.

This is the basic idea of the anti-aliased line drawing algorithm by Xiaolin Wu. It is slightly more complicated, but only by a little and produces anti-aliased lines that don't look as pixelated.

Other algorithms and implementations (parallelism, vectorization,...) exist, with various pros and cons, but our current version (or the Bresenham version) is a reasonably fast and nice implementation!