Bresenham’s line & circle drawing algorithms
Lecture: 3
Fall 2016
Computer Graphics (CS3388) Department of Computer Science
University of Western Ontario
Bresenham’s line & circle drawing
Outline
Rasterization
Problem with line drawing Bresenham’s line drawing algorithm Slope issues
Bresenham’s circle drawing algorithm
(materials from Zahid Hossain (Stanford), Kenneth I. Joy (UC Davis), Hearn & Baker)
1
Rasterization
Convert vector data to raster – pixel or dot format.
Scan conversion: Figuring out which pixels to shade
2
Frame buffer
3
Frame buffer coordinates
4
Problem
5
Scan Conversion
6
Bresenham
Bresenham’s line drawing algorithm (introduced in 1967)
7
Bresenham line drawing
A simple line drawing: Draw a line between two points (x1,y1) & (x2, y2).
General line equation: y = mx + b We can write:
Therefore,
y1 = mx1 + b, =⇒ b = y1 − mx1 y2 = mx2 + b, =⇒ b = y2 − mx2
y1 −mx1 =y2 −mx2 y1 − y2 = m(x1 − x2) ∆y = m∆x
8
Bresenham line drawing
Consider the line: y = ( 1 )x + ( 2 ) 33
We work with x, starting the line at (1,1)
x y round(y) 111
2 4/3 1
3 5/3 2 422
5 7/3 2 6 8/3 3 733
What’s actually being computed here is:
∆y=m∆x,=⇒ yi+1−yi =m(xi+1−xi) =⇒ yi+1=m+yi,[xi+1−xi =1]
9
Bresenham line drawing
Problem: If m > 1, the line traced will not be solid. The y-difference will be large compared to x-difference. So, the role of x & y is to be reversed, i.e., compute y from x-data.
Bresenham’s algorithm: At xi+1, we need to choose between yi and yi+1 (the assumption is that, 0 < m < 1 and ∆ = 1)
10
Bresenham line drawing
Let0