gatopeich's 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 (ang 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.

 

gatopeich's Graphic Algorithms Some history... Simple Math Line Drawing by Integer Operations The algorithm Similarity with Bresenham's Performance Circle Drawing by Integer Operations

 

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 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, I have seen things like this):

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 know about, 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".

Here are some results for the number avid, obtained after adding my code to the mentioned benchmark (ILA-EFLA-bench.c):

Line algorithms speed comparison (58 loops on a 1024x1024 framebuffer on a P4@2GHz)

Algorithm	Speed without optimization	Speed with "gcc -O3"
gatopeich's Integer Line Algorithm	(sorry, measure was wrong)	(sorry, measure was wrong)
EFLA Variation E	59765.536 lps (93%)	112060.377 lps (85%)
Wu's	50014.316 lps (77%)	89143.715 lps (68%)
Bresenham's (non optimized?)	52969.452 lps (82%)	102843.290 lps (78%)
DDA	31034.356 lps (48%)	55120.186 lps (42%)

 

Line algorithms cost comparison:

Line algorithms cost comparison:

Algorithm	Cost measured with oprofile (hits, statistical)	Cost according to cachegrind (millions of cpu cycles for 10 loops)
gatopeich's Integer Line Algorithm	(sorry, measure was wrong)	(sorry, measure was wrong)
EFLA Variation E	3590	1307
Wu's	6303	1389
Bresenham's (non optimized?)	21284	1702
DDA	19935	2311

Raw data:

gila-efla-oprofile.txt: statistical performance profile of benchmark run without optimization.

cachegrind.out.25887: cachegrind output (open with kcachegrind, look at cpu cycle estimations).

 

Note: Though I have used and thoroughly tested this algorithm, this particular C implementation was written almost on the fly and I haven't had the time to unit test it.

Thanks a lot to Stuart Fischer for discovering the nasty error that made me think my algorithm was the fastest!

 

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 allways-recurrent question: Can one come up with anything new anymore?

 

 

Back to gatopeich's front page