3. 2D Raster algorithms

Brock University
COSC 3P98 Computer Graphics
Instructor: Brian J. Ross



2d Raster algorithms


2D primitives


2d basics

 


Drawing Lines: 1. basic algorithm

dy := y1-y0;        /* x, y increments of line */
dx := x1-x0;
m := dy / dx;       /* slope of line */
y := y0;
for x:=x0 to x1 {
   write_pixel(x, round(y), colour);
   y := y + m;
}


Lines: basic alg


Lines: 2. Midpoint algorithm (Bresenham's)


Midpoint program

dx := x1 - x0;
dy := y1 - y0;
d := dy * 2 - dx;
incrE := dy * 2;
incrNE := (dy - dx) * 2;
x := x0;
y := y0;
drawPixel(x, y, colour);
while (x < x1) {
   if (d <= 0) {
      d += incrE;
      x++;
   } else {
      d += incrNE;
      x++; y++;
   }
   drawPixel(x, y, colour);
}


Drawing Solid Rectangles

for y=ymin to ymax       /* by scan line */
   for x = xmin to xmax  /* by pixel in rectangle span */
      writepixel(x, y, colour);


Shared edges

for y=ymin to ymax-1       /* by scan line */
   for x = xmin to xmax-1  /* by pixel in rectangle span */
      writepixel(x, y, colour);


Polygons

  • 2 techniques...
  • Both techniques need to know where the interior of a polygon resides


    Polygon interior test


    Polygon interior: special cases


    Scan converting solid polygons


    Scan converting solid polygons


    Filling Polygons


    Filling Poly's


    Floodfill

    FloodFill(x, y, oldColour, newColour) {
       if (readPixel(x, y) == oldColour) {
          writePixel(x, y, newColour);
          FloodFill(x, y-1, oldColour, newColor);
          FloodFill(x, y+1, oldColour, newColor);
          FloodFill(x-1, y, oldColour, newColor);
          FloodFill(x+1, y, oldColour, newColor);
       }
    }


    Boundary Fill

    BoundaryFill(x, y, boundaryColour, newColour) {
       c := readPixel(x, y);
       if (c <> boundaryColour and c <> newColour) {
          writePixel(x, y, newColour);
          BoundaryFill(x, y-1, oldColour, newColor);
          BoundaryFill(x, y+1, oldColour, newColor);
          BoundaryFill(x-1, y, oldColour, newColor);
          BoundaryFill(x+1, y, oldColour, newColor);
       }
    }


    Pattern filling


    Scan converting circles

    R^2 = X^2 + Y^2

    Y = +/- sqrt(R^2 - X^2)

    glBegin(GL_POINTS);
    loop x=0 to R {
       y = sqrt(r*r-x*x);
       v2i(x, y);
       v2i(x, -y);
       v2i(-x, y);
       v2i(-x, -y)
    glEnd();
    glBegin(GL_POINTS); 
    loop A=0 to 90 {  
       x = R * cos(A);
       y = R * sin(A);
       v2i(x, y);
       v2i(x, -y);
       v2i(-x, y);
       v2i(-x, -y);
    }
    glEnd();
    


    Circles

     


    Clipping

    1. Brute force: "scissoring"
      • test each pixel as its about to be drawn to see if its within bounds or not
      • can be efficient if hardware supported
    2. Analytically: compute the new geometry of clipped line or polygon
      • line: compute new endpoints
      • polygon: compute new polygon(s) vertices and edges
    3. Generate entire drawing on a scratch canvas, and then cut and copy visible portion to the screen
      • simple to do (especially for text), but wasteful


    Clipping lines


    Clipping lines

    A. Find new endpoints that intersect window boundary lines


    Clipping Lines

    B. Cohen-Sutherland


    Line Clipping

     


    Clipping polygons


    Clipping Polygons


    Antialiasing


    References:



    Back to COSC 3P98 index

    COSC 3P98 Computer Graphics
    Brock University
    Dept of Computer Science
    Copyright © 2004 Brian J. Ross (Except noted figures).
    http://www.cosc.brocku.ca/Offerings/3P98/course/lectures/2d/
    Last updated: October 15, 2004