Graphic Algorithms

This page is about algorithms to rasterize (represent with pixels) graphic objects (lines, circles, textures) using simple integer math.

Some history...

These algorithms I developed in my young coding times (1992~1995) for usage in assembler code routines that conformed a i386-architecture 320x200 resolution graphic library I would use for games & demos.

At that time, Bressenham's line algorithms appealed to me as too 'slow', as it used some non-integer operations. I felt I could do a little bit 'better', specially faster by not using anything else but integers and the simplest integer operations. I must say I had very imperfect knowledge of Bressenham's work.

The original intention in using just integer operations was to speed up the code. Later I discovered that integers can deliver optimal accuracy and nicest results, apart from the best speed in typical PC architectures.

Years later (and ago :-)) I included a few of these algorithms in "4bpp" library (http://fourbpp.sourceforge.net/), aimed at 4 bits-per-pixel (2 pixel pet byte) framebuffers. and several unpublished pieces of work.

Simple Math

The key ideas are:

• X-Y plane is represented by a 2-dimensional array. Coordinates are integers, corresponding to array indexes. Array elements represent unitary squares in the X-Y plane (or pixels in a screen).

• Think as the Greek! -- That is, a/b "a divided by b" is "the number of times you can substract b from a". Then don't discard the remainder, it might be useful next time around ;-). Also do as the ancient Greek, work graphically with a compass and you will learn a lot about numbers in the 2-dimensional plane...

• We are (kind of!) plotting a function x = F(y) in X-Y plane, whose derivative tells how much to move in Y-direction for each unitary step in X-direction.

Line Drawing by Integer Operations

Line drawing is the basic problem in rasterized graphics. It consists of connecting two pixels with those that approximate best the linear segment between them. After much work to obtain nice and symmetric results, I came to the following rationalization of the problem:

1. The pixels will be chosen from those crossed by an ideal line connecting the centers of the two extremes.
2. Starting from one extreme, each pixel will be vertically, horizontally, or diagonally adjacent to its predecessor.
3. Each subsequent pixel will be nearer to the other end. This leaves no more than 3 candidates.
4. When several candidates are possible, select the one whose center is closer to the ideal line. In the rare case when 2 pixels are equidistant, pick any.

Let's have an example to brighten things up:

This is a line connecting (0,0) and (10,4), or a "11x5" line. It is worth mentioning that most algorithms out there won't produce this result, as they usually don't follow the centered line, or just don't care about symmetry etc.

Some examples to get it right, for a line 10 pixels wide by 3 pixels high:

The "good":

o o o · · · · · · ·

· · · o o o o · · ·

· · · · · · · o o o

The "bad" ('x' points don't comply condition about distance to ideal line):

o · · · · · · · · ·

· x · · · · · · · ·

· · x x x x o o o o

And the "ugly" (may comply conditions but following a non-centered line, a very commnly found implementation):

o o o o · · · · · ·

· · · · o o o · · ·

· · · · · · · o o o

The algorithm

This algorithm provides a solution for the line between points P1 and P2 with coordinates (x1,y1) and (x2,y2). For the sake of simplicity we'll assume the case where dx = x2 - x1 > 0, dy = y2 - y1 > 0, and dx > dy.

The main idea is to "divide by repeated substraction", that is: For each x-step substract dy from an accumulator (a := a - dy) initialized as (a := dx). Then whenever the accumulator comes to 0 or below "we walked enough in x-direction to have one step in y-direction". At that point, we take that y-step, and 'reload' the accumulator (a := a + dx)...

START of gatopeich's Integer Line Algorithm

1: dx = ( x2 - x1 ) + 1

2: dy = ( y2 - y1 ) + 1

3: x = x1

4: y = y1

5: a = dx - (dy/2)

6: select/draw pixel at (x, y)

7: x = x + 1

8: a = a - dy

9: if ( a > 0 ) go to step #6

10: y = y + 1

11: a = a + dx

12: if ( y <= y2 ) go to step #6

END

Result for the 10x3 case is the "good" one, as shown above.

Notes:

• All operations are on integers, results are truncated down.
• At step 5, the substraction of (dy/2) is intended for simmetry. It is like "centering" the accumulator, by substracting 1/2 steps from it, as we don't really start from zero but from the center of the first pixel. Removing it would result in the "ugly" result. Being dy/2 an integer operation it will round down the result. To compensate this I opt for "strict major" comparison at step #9 "( a > 0 )", where "(a >= 0)" renders roughly the same results. I have yet to do more testing to determine if this matters at all.

Similarity with Bresenham's

Though this algorithm was developed 'from scratch', I recently online a very similar one as an optimized version of Bresenham's algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Optimisation). This is because of the idea of optimizing Bresenham's by scalating the real numbers and operations in order to work with integers, which on a mathematical plane translates to roughly the same as my 'original' idea.

Thus said, I can hardly claim that my algorithm is 'new' or 'original'. I seem to have "reinvented the wheel" :-).

Performance

This is NOT the fastest line algorithm I have tested, but I still think it is the most elegant.

When implemented in C (gILA.c) and using Po-Han Lin's benchmark code (http://www.edepot.com/algorithm.html), my "integer line algorithm" performs slower than Po-Han's "EFLA Variation E", and roughly faster than the others in his benchmark code: Wu's, Bressenham's or "DDA".

Circle Drawing by Integer Operations

Well, I was all about to explain my 'original' idea about iteratively obtaining square numbers, and the circle algorithm I developed from it in my youth days... Then I found it perfectly explained as a circle variant of Bresenham's line algorithm: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Circle_Variant

This makes me see (again) how terribly useful it would have been to have Wikipedia some ten years ago, and the always-recurrent question: Can one come up with anything new anymore?