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


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

    loop x=0 to R {
       y = sqrt(r*r-x*x);
       v2i(x, y);
       v2i(x, -y);
       v2i(-x, y);
       v2i(-x, -y)
    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);




    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



    Back to COSC 3P98 index

    COSC 3P98 Computer Graphics
    Brock University
    Dept of Computer Science
    Copyright © 2004 Brian J. Ross (Except noted figures).
    Last updated: October 15, 2004