Try the Free Math Solver or Scroll down to Tutorials!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# Line Drawing

Line Drawing

Scan-Conversion Algorithms

• Scan-Conversion:
Computing pixel
coordinates for
ideal line on
2D raster grid
• Pixels best
visualized as circles/
dots
– Why? Monitor hardware

Drawing a Line

• y = mx + B
• m = Δy / Δx
• Start at leftmost x and increment by 1
→ Δx = 1
• yi = Round(mxi + B)
• This is expensive and inefficient
• Since Δx = 1, yi+1 = yi + m
– No more multiplication!
• This leads to an incremental algorithm

Digital Differential Analyzer
(DDA)

• If |slope| is less then 1
Δx = 1
else Δy = 1
• Check for vertical line
m = ∞
• Compute corresponding
Δy (Δx) = m (1/m)

• Round (x,y) for pixel location
• Issue: Would like to avoid
floating point operations

Generalizing DDA

• If |slope| is less than or equal to 1
– Ending point should be right of starting
point
• If |slope| is greater than 1
– Ending point should be above starting
point
• Vertical line is a special case
Δx = 0

Bresenham’s Algorithm

• 1965 @ IBM
• Basic Idea:
– Only integer
arithmetic
– Incremental

• Consider the implicit
equation for a line:

The Algorithm

Assumptions:
0 ≤ slope ≤ 1
Pre-computed:

Bresenham’s Algorithm

Given:
implicit line equation:
Let:
where r and q are points on the line and
dx ,dy are positive

Then:
Observe that all of these are integers
and:
f(x,y) < 0 for points above the line
f(x,y) > 0 for points below the line
Now…..

• Suppose we just
finished (px,py)
– (assume 0 ≤ slope ≤ 1)
other cases symmetric

• Which pixel next?
– E or NE

Assume:
• Q = exact y value at x = px + 1
• y midway between E and NE: M = py + 1/2
Observe:
If Q < M , then pick E
Else pick NE
If Q = M,
it doesn’t matter

• Create “modified” implicit function (2x)

• Create a decision variable D to select,
where D is the value of f at the midpoint:

• If  D > 0then M is below the line f(x,y)
– NE is the closest pixel
• If D ≤ 0then M is above the line f(x,y)
– E is the closest pixel

• Note: because we multiplied by 2x, D is
now an integer---which is very good news
• How do we make this incremental??