Error-diffusion dithering or dithering with a precomputed blue-noise or white-noise pattern are also deterministic.
One standard point of view is that what introduces noise is quantization, in the sense that the quantized image has an unwanted difference from the desired image, and dithering consists of techniques to shape that noise. The Bayer-matrix ordered dithering algorithm presented here concentrates the noise at high frequencies where the eye is less sensitive to it, but it still retains some noise at lower frequencies, which is the banding you're commenting on.
Dave Long had the sharp observation earlier today that Bresenham-style line drawing is a form of dithering, where the signal being represented is the position of the pen rather than the brightness of the visual field. (I see that dreamcompiler made the same observation two days ago: https://news.ycombinator.com/item?id=45728962 but I don't know if Dave saw it there)
We had a good discussion of dithering here a couple of days ago, connected with a significantly more comprehensive article with a less fancy presentation: https://news.ycombinator.com/item?id=45728231
> Dave Long had the sharp observation earlier today that Bresenham-style line drawing is a form of dithering, where the signal being represented is the position of the pen rather than the brightness of the visual field.
Bresenham is the equivalent of a sharp quantization, with no dithering. Using true 1D dithering for line drawing would instead result in a "wobbly" almost hand-drawn output.
You're still thinking about dithering being about colors. It's about finding the best member of set B to stand in for a member of set A when |A|>|B|.
In color dithering A is the set of colors in the original image and B is a smaller set of colors. Often just pure black and pure white, but that doesn't have to be the case.
In Bresenham A is the relative x,y coordinates of the ideal next pixel in the line if the pixels were infinitely small (thus |A| = infinity), while B contains the relative x,y coordinates of the 3 pixels that are actually available: +1,0; 0,+1; and +1,+1 (with appropriate rotation for the other 3 quadrants).
An important feature of Bresenham's is that the error inherent in this assignment is carried forth into the decision made for the next pixel, such that the total error is diffused along the line and its average value stays close to zero. Such error diffusion is also a feature of the best color dithering algorithms, but not the one described in TFA -- ordered dithering -- because ordered dithering is not a very good algorithm and is not used much today except when its peculiar artifacts are desired.
And yes, Bresenham's original algorithm does set each pixel it chooses to pure black, but this has nothing to do with its error diffusion mechanism. Bresenham's with grayscale is also a thing and it results in even better line approximations, but it's usually referred to as antialiased Bresenham.
I think zozbot was talking about the position and not the color, and they are correct that the positions of the pixels that get drawn in Bresenham are the nearest neighbors of the ideal positions, rather than having any sort of dithering applied to them. (I'm reluctant to call "nearest neighbor" a sort of dithering.) What's getting dithered is the slope, not the position. I was wrong about that.
It's error-diffusion dithering. You maintain an error accumulator from one pixel to the next, which keeps track of your departure from the desired slope, and you make a diagonal rather than paraxial move when it overflows. (Or is that only DDA?) But I guess you're right that the position isn't being dithered. It's the slope.
I'm tempted to try the wobbly algorithm now to see what it looks like!
The cool thing about Bresenham is that you're constantly picking the pixel closest to the desired slope but you never have to do the explicit division of deltaY/deltaX. The division happens implicitly as you draw the line, using only addition and subtraction of integers. Which was quite handy for the primitive computers circa 1960 when Jack Bresenham invented it.
You mean the desired position. If you were always picking the pixel closest to the desired slope, your lines would all be at multiples of 45°.
I agree that the lack of division is surprising and beneficial.