The authors analyze a variation of the Bresenham line scan-conversion algorithm. Wu and Rokne have previously presented the concept of a double-step scan-conversion for lines, circles, and even ellipses. The originality of this paper is to introduce yet another optimization: the symmetry characteristics of a line segment.

An introduction mentions various previous works on line and curve scan-conversion and reviews the history of the study of line symmetry characteristics. The authors then recall some discussions on the double-step principle of the Wu and Rokne scan-conversion algorithm and how this method was said to be twice as fast as the Bresenham algorithm. It is important to note that in reality, when one implements such an algorithm this factor of two is never reached, because the same number of pixels have to be drawn (this is the goal of scan-conversion), and the time used in drawing pixels is generally well above the time spent in the scan-conversion inner loops.

The authors then introduce the symmetry in the double-step method and explain in a rather long proof how the proposed algorithm meets all the necessary conditions. The resulting algorithm scans the line segment from both ends, applying patterns chosen from three possible patterns, and ending at the middle of the line with a special midpoint termination. The paper details the basic algorithm and gives the precision of some special cases called 1/2 crossings in which forward and backward patterns can differ. A complexity study shows that the extra cost due to the introduction of symmetry in the original double-step method is negligible.

A comparison of the proposed method with both the  Bresenham  and the Wu and Rokne algorithms shows 3 to 3.9 times less overhead than the Bresenham method. The authors acknowledge that the actual drawing time is not taken into account in these numbers and that a given implementation would not reflect a significant time improvement.

This paper presents an interesting improvement of the double-step line scan-conversion method. Real and practical speed improvements can be achieved using this method if multiple pixel writes are possible, which is typically the case when using 16-bit or 32-bit architectures with an 8-bit frame buffer. The algorithm has previously been published, with fewer details, but including an implementation example in C [1].