2.Lines
[prev][next]

Pixel Screen Positions Stored Linearly in Row Major Order Within the Frame Buffer

Finding Pixels that are on a Line

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

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 )

Incremental Calculation of (xi, yi)

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 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 );
   }
}

Midpoint Line Algorithm

Midpoint Line Algorithm

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) )

Varying Intensity of Raster Lines as a Function of Slope

[prev][next]
Made by dynaPage 0.2