Introduction

Solutions for session 1.

Exercises

Exercise 1: drawing a line

void drawLine1(int x1, int y1, int x2, int y2) {
   	int t;
	if (abs(x2-x1) > abs(y2-y1)) {
		// x = independent var, y = dependent
	 	int i; 
		double y; 
 
		if (x1 > x2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap 
		for (i=x1; i < x2; i++) { 
			y = 1.0*(y2-y1)*(i-x1)/(x2-x1) + y1; 
			point(i, (int)y); 
		} 
	} else {  // y = independent var, x = dependent
		int i; 
		double x; 
 
		if (y1 > y2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap 
		for (i=y1; i < y2; i++) { 
			x = 1.0*(i-y1)*(x2-x1)/(y2-y1)+x1; 
			point((int)x, i); 
		} 
	} 
}

The equation of a line does not prescribe any choice on which variable to choose as the dependent or independent one. We choose x as independent variable when dx > dy. We choose y as independent variable when dx < dy. If dx = dy then it does not matter which variable we choose. Our choice implies that the independent variable always runs along the axis of the biggest change. Imagine we need to draw a line between coordinates (2,20) and (5, 40). Should you choose x as the independent variable, you will only be able to plot 4 points! This will not result in a fluent line. If you choose y, you can plot 21 points, which gives a much better result.

Exercise 2: fixed-point arithmetic

void drawLine2(int x1, int y1, int x2, int y2, int precision) {
   	int t;
	if (abs(x2-x1) > abs(y2-y1)) {
		// x = independent var, y = dependent
	 	int i, y; 
 
		if (x1 > x2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap 
		for (i=x1; i < x2; i++) { 
			y = (precision*(y2-y1)*(i-x1))/(x2-x1) + precision*y1; 
			point(i, y/precision);
		} 
	} else {  // y = independent var, x = dependent
		int i, x; 
 
		if (y1 > y2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap 
		for (i=y1; i < y2; i++) { 
			x = (precision*(i-y1)*(x2-x1))/(y2-y1)+ precision*x1; 
			point(x/precision, i); 
		} 
	} 
}

When choosing a power of 2 as your precision factor, you can replace the integer divisions and multiplications by bitshifts on integers:

x * 2^y = x << y
x / 2^y = x >> y

Exercise 3: drawing a line using DDA

void drawLine3(int x1, int y1, int x2, int y2) {
   int t;
   if (abs(x2-x1) > abs(y2-y1)) {
     // x = independent var, y = dependent
     int i; 
     double y;
     double dy;
   
     if (x1 > x2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap
     dy = 1.0*(y2-y1)/(x2-x1);
     y=y1;
   
     for (i=x1; i < x2; i++) { 
       y += dy; 
       point(i, (int)y); 
     } 
   } else {  // y = independent var, x = dependent
     int i; 
     double x;
     double dx;
   
     if (y1 > y2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap
     dx = 1.0*(x2-x1)/(y2-y1);
     x = x1;

     for (i=y1; i < y2; i++) { 
       x += dx; 
       point((int)x, i); 
     } 
   } 
}

Exercise 4: DDA + Fixed Point

void drawLine4(int x1, int y1, int x2, int y2) {
  int t;
  if (abs(x2-x1) > abs(y2-y1)) {
    // x = independent var, y = dependent
    int i; 
    int y;
    int dy;
       
    if (x1 > x2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap
    dy = (1<<16)*(y2-y1)/(x2-x1);
    y = y1 << 16;
       
    for (i=x1; i < x2; i++) { 
      y += dy; 
      point(i, y >> 16); 
    } 
  } else {  // y = independent var, x = dependent
    int i; 
    int x;
    int dx;
       
    if (y1 > y2) { t=x1; x1=x2; x2=t; t=y1; y1=y2; y2=t; } // swap
    dx = (1<<16)*(x2-x1)/(y2-y1);
    x = x1 << 16;

    for (i=y1; i < y2; i++) { 
      x += dx; 
      point(x>>16, i); 
    } 
  } 
}

Exercise 5: Bresenham's Algorithm

void drawBresenham(Graphics g, int x1, int y1, int x2, int y2) {
  int dX = abs(x2-x1);
  int dY = abs(y2-y1);
  int Xincr, Yincr;
  if (x1 > x2) { Xincr=-1; } else { Xincr=1; } // which direction in X?
  if (y1 > y2) { Yincr=-1; } else { Yincr=1; } // which direction in Y?

  if (dX >= dY) {                // if X is the independent variable
	int dPr  = dY<<1;           // amount to increment decision if right is chosen
	int dPru = dPr - (dX<<1);   // amount to increment decision if up is chosen
	int P    = dPr - dX;        // decision variable start value
	for (; dX>=0; dX--) {       // process each point in the line one at a time
	   point(x1,y1);   // plot the pixel
	   if (P > 0) {             // is the pixel going right AND up?
	      x1+=Xincr;            // increment independent variable
	      y1+=Yincr;            // increment dependent variable
	      P+=dPru;              // increment decision (for up)
	   } else {                 // is the pixel just going right?
	      x1+=Xincr;            // increment independent variable
	      P+=dPr;               // increment decision (for right)
	   }
	}
   } else {                       // if Y is the independent variable
	int dPr  = dX<<1;           // amount to increment decision if right is chosen
	int dPru = dPr - (dY<<1);   // amount to increment decision if up is chosen
	int P    = dPr - dY;        // decision variable start value
	for (; dY>=0; dY--) {       // process each point in the line one at a time
	   point(x1,y1);   // plot the pixel
	   if (P > 0) {             // is the pixel going up AND right?
	      x1+=Xincr;            // increment dependent variable
	      y1+=Yincr;            // increment independent variable
	      P+=dPru;              // increment decision (for up)
	   } else {                 // is the pixel just going up?
	      y1+=Yincr;            // increment independent variable
	      P+=dPr;               // increment decision (for right)
	   }
	}
 }
}

Exercises Computer Graphics

Session 1 - Lines Solutions

Exercise Sessions