Thanks for inspiration topics:

Dr Nicolas Holzschuch, University of Cape Town & Longin Jan Latecki

Modified by:

VisualFX

University of Algarve, Portugal

Bresenham line and circle algorithms

Intro:

First of all, here’s a definition:

Rasterizing à To know where to put the pixels on the screen in order to draw a line

How does the software manages to draw primitives (objects) on the screen?

• It converts geometric definitions to pixels
• Rasterization is the method to select the pixels drawn

Primitives rasterization is a rather frequent task on computer graphics, so it must fast. To achieve more speed, rasterization uses:

• Integer arithmetic (instead of decimal values, that need huge amounts of processing)
• Addition instead of multiplication (2*5 == 5+5)

Rasterization Algorithms (currently implemented in all graphics libraries):

• Line-drawing : Bresenham, 1965
• Polygons drawing : uses line drawing to create more complex structures
• Circles drawing : Bresenham, 1977

Why should you bother learning these algorithms?

1.      Because they are an excellent example of efficiency since they use no superfluous computations

2.      They allow possible drawing extensions, among them, efficient drawing of parabolas, hyperbolas

3.      Has application to similar areas such as robot moving or volume rendering

4.      It’s the CG equivalent to Euler’s algorithm (approximation algorithm)

Line Drawing algorithm

(2 algorithms: naïve algorithm , Bresenham algorithm)

• naïve algorithm for lines

Line generic definition: Ax + By + C = 0

Also expressed as: y = mx + b              ; m = ∆y / ∆x

• m = slope (how to calculate line slope)
• b = y coordinate of point of intersection between y axis and the line

Algorithm:

            For x = xmin to x = xmax

                        y = m * x + b

                        light pixel (x,y)

            However, this algorithm only works for -1 ≤ m ≤1 , as the other values cannot represent a clear line on screen:

The perfect line would be the m = 1 line. Above that the pixels aren’t enough to fill the line.

Problems of this algorithm:

• uses 2 floating point operations per pixel ( “m*x” and “-b” )
• we can try to improve performance this way:

y =  b                          // y initial value

light pixel (xmin, y)

For  x = (xmin + 1) to x = xmax

           y += m

           light pixel (x,y)

• there’s still 1 floating point operation per pixel ( y+=m )
• computation in floats (“m” might not be integer) and pixels in integers create a conversion necessity

• Bresenham algorithm for lines

Ø      core idea

o       At each step (pixel to draw), chooses between 2 pixels (0 ≤ m ≤ 1):

o       We need a criterion to choose between the two of them:

§         Distance between the line and the center of the pixel (error of each near pixel)

Ø      The sum of the two errors (two nearest pixels) equals 1

o       So, we will always pick the pixel with error ≤ 1/2

If error of current pixel ≤ 1/2

draw this pixel

                        Else

                                   draw the other pixel

                                   error of current pixel = 1 - error

Ø      How to calculate the error of each pixel?

o       We know that origin (0,0) is the lower left corner

o       Also that, line is define as: y = m*x + b

o       Start cycle here (for all pixels):

·        The distance from pixel (Xp,Yp) to the line:

·        d = y(Xp) – Yp = m * Xp + b – Yp

·        Draw this pixel if  d ≤ 1/2

·        Update for next pixel

·        x += 1 ; b += m

Ø      We’re still in floating point !

o       But now we can get back to integers

·        e = 2 * m * Xp – 2 * Yp + 2 * b – 1 

·        if e<0 stay horizontal, if e>0, move up

·        update for next pixel:

·        if you stay horizontal: x+=1 , e+=2 * m

·        if you move up: x+=1 , y+=1 , e += 2 * m – 2

Ø      Bresenham algorithm : summary

o       It has several good ideas:

§         Use of symmetry to reduce complexity

§         Reduces the choice to two pixels (easier)

§         Defines an error function for choice criterion

§         Stays in integer arithmetics

o       It’s very straightforward:

§         Good for hardware implementation

§         Good for assembly language

Circle Drawing algorithm

(2 algorithms: naïve algorithm , Bresenham algorithm)

• naïve algorithm for circle

Ø      A circle is defined by the equation: x² + y² – r² = 0

Ø      Simple algorithm:

For x = xmin to x = xmax

            y = sqrt (r*r – x*x)

            draw pixel (x,y)

Ø      Works by octants and uses symmetry

• Bresenham algorithm for circle

Ø      Mid-point algorithm for choosing the appropriate pixel

Ø      Error function: d = x² + y² – r²

Ø      Calculate d at the midpoint:

o       If the last pixel drawn is (x,y)        

o       Then E = (x+1 , y)  ; SE = (x+1 , y–1)

o       Hence, the midpoint = (x+1 , y – 1/ 2)

Ø      Which to draw?

o       d(x,y) = (x+1)² + (y – ½)² – r²

o       if d<0

§         draw E

o       if d≥0

§         draw SE

Ø      Updating the error:

Ø      In each step (go to E or SE), i.e., increment x: x+=1

o       d+=2x+3

Ø      If you go to SE , i.e, x+=1 , y+= -1  :

o       d+=-2y + 2

Ø      Two multiplications, two additions per pixel … can you do better?

Ø      Doing even better

§         The error is not linear

§         However, what you add to the error is:

·        Keep ∆x and ∆y :

o       At each step:

§         ∆x += 2 , ∆y += -2

§         d += ∆x

o       If I decrement y, d += ∆y

§         4 additions per pixel

Ø      Mid-point algorithm summary

§         Extension of the line drawing algorithm

§         Test based on mid-point position

§         Position checked using function

·        Sign of (x² + y² – r²)

§         With two steps, uses only additions

Ø      Extension to other functions

o       Mid-point algorithm is easy to extend to any curve defined by: (f,y)=0

o       If the curve is polynomial, can be reduced to only additions using n-order differences