Line Plotting Pixel by Pixel

It’s difficult to appreciate what goes on mathematically behind the scenes of high-level drawing methods, such as those used by Pygame methods, unless you’ve written a program to plot objects pixel by pixel – because when it comes down to it, this is how the methods produce their rendered results. To that end, we are going to explore a little deeper the techniques involved in drawing a line pixel by pixel onto the screen. At first, you might assume this is quite a simple thing to do, but you’ll soon discover that it’s quite complex.

As we progress through the content, it will become clear why special algorithms are required to draw mathematical constructs such as lines on a pixel display. The algorithm we are going to explore is also a key technique that can be used for various other graphics and game-related functions wherever straight-line calculations are needed.

Once you’ve completed this chapter, you...

Technical requirements

In this chapter, we will be using Python, PyCharm, and Pygame, as used in previous chapters. Before you begin coding, create a new folder in the PyCharm project for the contents of this chapter.

The solution files containing the code can be found on GitHub at https://github.com/PacktPublishing/Mathematics-for-Game-Programming-and-Computer-Graphics/tree/main/Chapter03.

The Naïve Way: Drawing a line with brute force

So, you have an equation to draw a line and want to plot it on the screen pixel by pixel. The naïve approach would be to loop through a series of x values, calculate what the y value should be at that x location given the equation, and then plot x, y as a colored pixel. When you do, a very unfortunate issue will arise.

An issue occurs because pixel locations are represented as whole numbers; however, points on a straight line can in fact be floating points. Consider the line in Figure 3.1, showing a grid of pixel locations and a line drawn through them:

Figure 3.1: A grid of pixels and a line

If you were to draw every pixel the line touched (shown by the shaded squares), it wouldn’t give a very accurate presentation of the line. In addition, the real location of any point on the line could calculate to a floating-point value. When this occurs, the value is rounded to an integer to find the closest...

Enter Bresenham: The improved approach

Jack Bresenham developed this algorithm while working for IBM in 1962. In short, it plots a straight line but doesn’t leave pixels disconnected from each other. The basic premise is that when drawing a line pixel by pixel, each successive pixel must be at least a distance of 1 in either the x or y (or both) direction. If not, a gap will appear. While the naïve approach we’ve just used creates a plot where all the x values are a distance of 1 apart, the same isn’t always true for the y values. The only way to ensure all x and y values are a distance of 1 apart is to incrementally plot the line from point 1 to point 2, ensuring that either the x or y values are changing by a maximum of 1 with each loop.

Consider the close-up of a steep line being plotted in Figure 3.4:

Figure 3.4: A line being constructed pixel by pixel

The values for dx (change in x values) and dy (change in y values) represent...

Drawing circles the Bresenham way

Drawing circles pixel by pixel can also suffer from the same issue of pixel skipping if the naïve approach of using a circle equation to calculate pixel locations is used. Consider the implicit circle equation:

The naïve approach to drawing this with pixels could be achieved with the following code:

import math
import pygame
pygame.init()
screen_width = 400
screen_height = 400
screen = pygame.display.set_mode((screen_width,
                                  screen_height))
pygame.display.set_caption('Naive Circle')
done = False
white = pygame.Color(255, 255, 255)
radius = 50
center = (200, 200)
while not done:
    for event in pygame.event.get():
        if event.type == pygame...

Anti-aliasing

In the previous sections, we worked on producing pixel-by-pixel lines where one pixel was chosen over another in order to create a continual line or circle. If you zoom in on these pixels, however, you will find that they are quite jagged in appearance, as illustrated by the zoomed-in section of a circle shown in Figure 3.10:

Figure 3.10: A zoomed-in section of the Bresenham circle pixels

This effect occurs because of the way that integer values are chosen to represent the drawing. However, when we looked at the actual equations for lines and circles in the The Naïve Way: Drawing a line with brute force and Drawing Circles the Bresenham way sections, it was clear they involved floating-point values and seemed to pass through more than one pixel. To improve the look of these kinds of drawings, a process called anti-aliasing is employed to blur the pixels that are neighbors of the line pixels to fade the edges of the line. Figure 3.11 shows...

Summary

In this chapter, we’ve created code to force the errors incurred when trying to plot floating points in whole-number pixel locations. Mathematically speaking, the focus of the chapter was on Bresenham’s algorithms for drawing lines and circles that take the respective equations and create a raster image from them while working with integer values to ensure a pixel-perfect drawing.

In Chapter 4, Graphics and Game Engine Components, we will explore the structure of graphics engines and look at how they are put together to cater to the numerous functions they need to serve.