2.Lines

# Finding Pixels that are on a Line

```for y in [ 0, n ]
for x in [ 0, n ]
if | y-mx-b | = 0
setPixel ( x, y )
```

# Finding Pixels that are nearly on a Line

```for y in [ 0, n ]
for x in [ 0, n ]
if | y-mx-b | <= [delta]
setPixel ( x, y )
```

# Finding the Pixels on a Line - Implicit

```for x in [ 0, n ]
y = 1/2 x
setPixel ( x, y )
```

# Finding the Pixels on a Line - Implicit

```for x in [ 0, n ]
y = 2 x
setPixel ( x, y )
```

# Finding the Pixels on a Line - Implicit

```for x in [ 0, n ]
y = 5x
setPixel ( x, y )
```

# Finding the Pixels on a Line - Implicit

```for y in [ 0, n ]
x = 1/5 y
setPixel ( x, y )
```

# Finding the Pixels on a Line - DDA

```y = 0

for x in [ 0, n ]
y = y + 1/10
setPixel ( x, y )
```

# Finding the Pixels on a Line - DDA

```y = 0

for x in [ 0, n ]
y = y + 1/10
setPixel ( x, y )
```

 ```void Line ( int x0, int y0, int x1, int y1, int value ) { /* Assumes -1 <= m <= 1, x0 < x1 */ int x; /* x runs from x0 to x1 in unit increments. */ float dy, dx, y, m; dy = y1 - y0; dx = x1 - x0; m = dy / dx; y = y0; for ( x = x0; x <= x1; x++ ) { WritePixel ( x, (int) floor ( y + 0.5 ), value ); /* Set pixel to value */ y += m; /* Step y by slope m */ } } ```

# Midpoint Line Algorithm

Midpoint: F(M) < 0?

Bresenham: d1 > d2?

# Midpoint Algorithm

Equations:

• y = dy / dx x + B
• F(x, y) = ax + by + c = 0

# Midpoint Algorithm

Equations:

• y = dy / dx x + B
• F(x, y) = ax + by + c = 0
=>
F(x, y) = dy.x - dx.y + B.dx = 0

-> a = dy, b = -dx, c = B.dx

# Midpoint Algorithm

Equations:

• y = dy / dx x + B
• F(x, y) = ax + by + c = 0
=>
F(x, y) = dy.x - dx.y + B.dx = 0

-> a = dy, b = -dx, c = B.dx

# Midpoint Criteria

```   d = F(m) = F(xp+1, yp+ 1/2)
if d > 0,
choose NE
else
choose E
```

# Midpoint Algorithm - Book Keeping

 Case EAST: increment m by 1 in x dnew = F(mnew) = F(xp + 2, yp + 1/2) deltaE = dnew - dold = a = dy

# Midpoint Algorithm - Book Keeping

 Case EAST: increment m by 1 in x dnew = F(mnew) = F(xp + 2, yp + 1/2) deltaE = dnew - dold = a = dy Case NORTHEAST: increment m by 1 in both x and y dnew = F(mnew) = F(xp + 2, yp + 1 1/2) deltaNE = dnew - dold = a + b = dy - dx

# Midpoint Algorithm - Book Keeping

 Case EAST: increment m by 1 in x dnew = F(mnew) = F(xp + 2, yp + 1/2) deltaE = dnew - dold = a = dy Case NORTHEAST: increment m by 1 in both x and y dnew = F(mnew) = F(xp + 2, yp + 1 1/2) deltaNE = dnew - dold = a + b = dy - dx Starting out dstart = F(x0 + 1, y0 + 1/2) a x0 + a + by0 + 1/2 b + c = F(x0, y0) + a + 1/2 b = dy - 1/2 dx

# Midpoint Algorithm - Book Keeping, Integer Calculations

 Case EAST: increment m by 1 in x dnew = F(mnew) = F(xp + 2, yp + 1/2) deltaE = dnew - dold = a = 2 dy Case NORTHEAST: increment m by 1 in both x and y dnew = F(mnew) = F(xp + 2, yp + 1 1/2) deltaNE = dnew - dold = a + b = ( dy - dx ) 2 Starting out dstart = F(x0 + 1, y0 + 1/2) a x0 + a + by0 + 1/2 b + c = F(x0, y0) + a + 1/2 b = ( dy - 1/2 dx ) 2 = 2dy - dx

 ```void MidpointLine ( int x0, int y0, int x1, int y1, int value ) { int dx, dy, incrE, incrNE, d, x, y; dx = x1 - x0; dy = y1 - y0; d = dy * 2 - dx; incrE = dy * 2; incrNE = (dy - dx) * 2; x = x0; y = y0; WritePixel ( x, y, value ); while ( x < x1 ) { if ( d <= 0 ) { d += incrE; x ++; } else { d += incrNE; x ++; y ++; } WritePixel ( x, y, value ); } } ```

OctantChange
1none
2
3
4
5
6
7
8

# Midpoint Line Algorithm

OctantChange
1none

2swap roles of x and y
( swap(x1, y1), swap(x0, y0), swap(dx, dy), plot(y, x))
3
4
5
6
7
8

# Midpoint Line Algorithm

OctantChange
1none

2swap roles of x and y
( swap(x1, y1), swap(x0, y0), swap(dx, dy), plot(y, x))

3
4

5draw from P1 to P0
(swap P1, P0)

6
7
8

# Midpoint Line Algorithm

OctantChange
1none

2swap roles of x and y
( swap(x1, y1), swap(x0, y0), swap(dx, dy), plot(y, x))

3
4

5draw from P1 to P0
(swap P1, P0)

6
7

8use y = -y
( y = -y, plot (x, -y) )

# Midpoint Line Algorithm

OctantChange
1none

2swap roles of x and y
( swap(x1, y1), swap(x0, y0), swap(dx, dy), plot(y, x))

3

4

5draw from P1 to P0
(swap P1, P0)

6

7

8use y = -y
( y = -y, plot (x, -y) )