23-07-2012, 12:36 PM
Computer Graphics 4:Bresenham Line Drawing Algorithm, Circle Drawing & Polygon Filling
Computer Graphics.ppt (Size: 1.08 MB / Downloads: 107)
In today’s lecture we’ll have a look at:
Bresenham’s line drawing algorithm
Line drawing algorithm comparisons
Circle drawing algorithms
A simple technique
The mid-point circle algorithm
Polygon fill algorithms
Summary of raster drawing algorithms
The Bresenham Line Algorithm
The Bresenham algorithm is another incremental scan conversion algorithm
The big advantage of this algorithm is that it uses only integer calculations
The Big Idea
Move across the x axis in unit intervals and at each step choose between two different y coordinates.
For example, from position (2, 3) we have to choose between (3, 3) and (3, 4)
We would like the point that is closer to the original line
Bresenham Exercise
Go through the steps of the Bresenham line drawing algorithm for a line going from (21,12) to (29,16)
Bresenham Line Algorithm Summary
The Bresenham line algorithm has the following advantages:
An fast incremental algorithm
Uses only integer calculations
Comparing this to the DDA algorithm, DDA has the following problems:
Accumulation of round-off errors can make the pixelated line drift away from what was intended
The rounding operations and floating point arithmetic involved are time consuming
Mid-Point Circle Algorithm
Similarly to the case with lines, there is an incremental algorithm for drawing circles – the mid-point circle algorithm
In the mid-point circle algorithm we use eight-way symmetry so only ever calculate the points for the top right eighth of a circle, and then use symmetry to get the rest of the points