Plotting curves

Plotting curves of various types, such as straight lines, functions, parametric functions and polygons of various types form the basis of most graphic functionalities.

To understand how to deal with plotting curves, first we need to understand how a screen works. In most cases, the interaction between the computer itself and the screen is done via an array representing individual pixels. If we have to draw on an area of width $w$ and height $h$, this will be a $w \times h$ array. Most commonly, the $0$ of this array corresponds to the top left of the screen, with incrementing values going first to the right, up to the value of the pixel $w - 1$, corresponding to the top right of the screen. The following pixel $w$ will then be the pixel right underneath pixel $0$. This convention is a leftover from the era where the pixels on the physical screen were displayed in that order because that was the direction of the scanning by the electron beams of a CRT monitor.

Hence, the conversion of screen coordinates to its actual array value can be done simply as

int convertToPixel(int x, int y)
{
	return (x + y * width) * 4;
}

function convertToPixel(x, y)
{
	return (x + y * width);
}

These values may need to be multiplied by some constant, such as in the case of javascript, where every pixel is described by 4 bytes, describing the 4 color channels of the canvas (red, green, blue and alpha channel). The inverse transformation will be

int convertToCoordinates(int p)
{
	return Tuple(p - p % width, p % width);
}

function convertToCoordinates(p)
{
	var pixel = p / 4;
	var y = pixel % width
	return [ p - y, y ];
}

This suggests a very simple method to plot both horizontal and vertical lines, by simply iterating over increasing values of the array, either by increments of $1$ (for a horizontal line), or increments of $w$ (for vertical lines).

int f(int p)
{
	stuff
}

function drawHorizontal(start, l)
{
	var step = (l < 0)?-4:4;
	var end = start + l * 4;
	for(var p = start; p != end; p+=step)
	{
		drawPixel(p);
	}
}

function drawVertical(start, l)
{
	var step = (l < 0)?-4 * width:4 * width;
	var end = start + l * width * 4;
	for(var p = start; p != end; p+=step)
	{

		drawPixel(p);
	}
}

A problem appears : when the pixel value exceeds the line $[n \times w, n \times w + (w - 1)]$, a horizontal line will continue on the next or previous line, including trying to go beyond the array itself. The same thing will happen with vertical lines, which will always go beyond the array if they are too large. Since this can cause an out of bound error, as well as not being what we want to display, we'll need to either make sure that the line is of proper length beforehand, or clamp the boundaries when drawing them.

int f(int p)
{
	stuff
}

function drawHorizontal(start, l)
{
	var step = (l < 0)?-4:4;
	var end = start + l * 4;
	var first = start % width;
	var last = first + 4 * width;
	end = (end < first)? first : end;
	end = (end > last)? last-1 : end;
	for(var p = start; p != end; p+=step)
	{
		drawPixel(p);
	}
}

function drawVertical(start, l)
{
	var step = (l < 0)?-4 * width:4 * width;
	var end = start + l * width * 4;
	end = (end < 0)?0 : end;
	end = (end >= width * height)? width * height - 1 : end;
	for(var p = start; p != end; p+=step)
	{

		drawPixel(p);
	}
}

In this case the start of the line cannot exceed any boundary, but it may also be necessary to check it as well in some circumstances. Also if the pixel integer is unsigned, it may be useful to check for any underflow to avoid a line going from $1$ to $-1$ turning into a line from $1$ to $255$, especially since with this code, the for loop would never terminate.

The other class of line that remains possible to draw very simply with a single instruction in a loop is a diagonal line. This is simply done by combining the two methods, and every turn will increment the pixel by either $w + 1$, $w-1$, $-w+1$ or $-w-1$, depending on the direction of the diagonal.

int f(int p)
{
	stuff
}

function drawDiagonal(start, l)
{
	var step = (l < 0)?-w * 4 + 4:w * 4 + 4;
	var end = start + l * (w * 4 + 4);
	for(var p = start; p != end; p+=step)
	{
		drawPixel(p);
	}
}

With those three types of lines, we can already draw on screen many shapes, the most important one being a rectangle. This is quite practical as it is a very common shape in graphics and this is a very fast algorithm compared to more general line drawing algorithms. Rectangles can be simply implemented by the simultaneous plotting of two horizontal and two vertical lines.

int f(int p)
{
	stuff
}

function drawRectangle(start, sideWidth, sideHeight)
{
	var offset = 4 * sideHeight * width;
	for(var p = start; p < sideWidth; p++)
	{
		drawPixel(p);
		drawPixel(p + offset);
	}
	for(var p = start + 4*width; p < sideWidth - 1; p++)
	{
		drawPixel(p);
		drawPixel(p + offset);
	}
}

The other convex polygons possible with these are diamonds (or any variety of rectangles rotated by $45°$, isoceles right triangles and octogons.

General line plotting algorithms

While it is possible to implement by hand many more types of lines, it will be more interesting beyond those basic cases to get a generic algorithm to plot any line.

The most obvious method to plot a curve, including lines, would be to do it as a basic mathematical function, where we plot a point at the coordinate $(x, f(x))$. With this method we can try to plot a variety of curves beyond straight lines, although one important omission is that as with mathematical functions, we cannot plot anything with a vertical line. This will be a major issue of the idea as we will see.

The algorithm is fairly simple : If we consider the $x$ axis horizontal and the $y$ axis vertical (and pointing downward, due to the screen), then for a given function $f$, the plot will be

int f(int p)
{
	stuff
}

function plotFunction(xmin, xmax, f)
{
	for(var x = xmin; x < xmax; x++)
	{
		drawPixel(x, f(x));
	}
	
}

Up to some eventual rotations or translations (having the $0$ at the top left of the screen isn't necessarily the most convenient).

The Bresenham's line algorithm

Last updated : 2017-10-13 12:28:32

Tags : graphics