Todays Topics

• Drawing Lines (Basic Algorithm)
• Bresenham's Line Algorithm

Drawing Lines (Basic Algorithm)

• Y = m * X + b
  • m = Slope of line
  • b = Displacement
  • X = independent coordinate
    Choose X so as to plot larger number of points
  • Y = Dependent coordinate
    Plot to nearest Y when fractions occur

• Draw Line from (X1,Y1) to (X2,Y2)
  • m = dy/dx
  • dy = (Y2-Y1)
  • dx = (X2-X1)
  • b = Y1
  • Plot(X,m*X+b) for X=X1..X2

• Problem: Basic Line algorithm Requires Slow floating point math

Bresenham's Line Algorithm

• Eliminates floating point calculation

• Use same variables as defined above
  
  • (X1,Y1) = Start point
  • (X2,Y2) = End point
  • m=dy/dx = Slope
  • (X,Y) = Current point

• Track Error in Y as X increases

  

• S = (X+1)*m - Y
  Distance above point (X+1,Y)

• T = 1 - S = Y + 1 - m*(X+1)
  Distance below point (X+1,Y+1)

• S-T = 2*(X+1)*m - 2*Y - 1
  Error above or below midpoint
  • If S < T (i.e., S-T < 0) : Go Horizontal (i.e., X+1,Y)
  • If S > T (i.e., S-T > 0) : Go Diagonal (i.e., X+1,Y+1)

• E = (S-T)*dx
  = 2*(X+1)*dy - 2*Y*dx - 1*dx
  = 2*X*dy - 2*Y*dx + 2*dy - dx
  • Recall m=dy/dx
  • Multiplication by dx does not affect above/below comparison

• E(i) = E(X,Y) = Error at each point
  • E(0) = E(0,0) = 2*dy - dx

• E(i+1)-E(i) = Additive error at each point
  • Diagonal Move: E(X+1,Y+1) - E(X,Y) = 2*dy - 2*dx
  • Horizontal Move: E(X+1,Y) - E(X,Y) = 2*dy

• Algorithm
  • Initially:
    • E = 2*dy - dx
    • X = X1
    • Y = Y1

  • While X <= X2
    • Plot(X,Y)
    • X=X+1
    • If (E < 0) E=E+2dy
    • Else Y=Y+1, E=E+2dy-2dx

• Example
  • (X1,Y1) = (0,0)
  • (X2,Y2) = (6,2)
  • dx=6
  • dy=2

    

    X	Y	E
    0	0	4-6 = -2
    1	0	-2+4 = +2
    2	1	+2+4-12 = -6
    3	1	-6+4 = -2
    4	1	-2+4 = +2
    5	2	+2+4-12 = -6
    6	2	-6+4 = -2

Return to ECE291 Lecture Index