Computer Graphics

Week 11 Solution

Question 1

I made both x and y floats to simplify things: Solving the reverse line problem by swapping x1 and x2 works in this case, but in a general solution does not work because we might want to texture the line (to make a dashed line for example).

    void drawPixel(float x, float y){
        super.drawPixel(Math.round(x),Math.round(y));
    }

  void drawLine(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    if (dx == 0 && dy == 0) {
        drawPixel(x1,y1);
        return;
    }

    if (Math.abs(dx) > Math.abs(dy)) {
        float m = dy / (float) dx;
        float b = y1 - m*x1;
        if ( x1 < x2) { //increment x
            for (x = x1; x <= x2; x++) {
                y = m*x+b;
                drawPixel(x,y);
            }
        } else {
            for (x = x1; x >= x2; x–) {
                y = m*x+b;
                drawPixel(x,y);
            }
        }
    } else {
        float m1 = dx / (float) dy;
        float b1 = x1 - m1*y1;
        if ( y1 < y2) { //increment y
            for (y = y1; y <= y2; y++) {
                x = m1*y+b1;
                drawPixel(x,y);
            }
        } else {
            for (y = y1; y >= y2; y–) {
                x = m1*y+b1;
                drawPixel(x,y);
            }
        }

    }
  }

Question 2

In the third octant we must choose between U and L.

$\begin{array}{rcl} dx&=&x_b-x_a\\ dy&=&y_b-y_a\\ m&=&dy/dx\\ b&=&y_a-mx_a\\ x&=&(y-b)/m\\ P&=&(x_i,y_i)\\ U&=&(x_i,y_i+1)\\ L&=&(x_i-1,y_i+1)\\ M&=&(x_i-1/2,y_i+1)\\ Q&=&((y_i+1-b)/m,y_i+1)\end{array}$

Go to L if Q is to left of M, i.e. if

Multiply the LHS by 2dy to get rid of fractions

$\begin{array}{rcl} p_i&=&2dy((y_i+1-b)/m - x_i+1/2)\\ &=&2dx(y_i+1-b) - 2dyx_i+dy)\\ &=&2dxy_i-2dyx_i +2dx -2bdx +dy\end{array}$

Calculate p incrementally:

$\begin{array}{rcl} p_{i+1}-p_{i}&=&2dxy_{i+1}-2dyx_{i+1} - 2dxy_i+2dyx_i\\ &=&2dx(y_{i+1}-y_i)-2dy(x_{i+1}-x_i)\\ &=&\left\{ \begin{array}{ll} 2dy + 2dx & \mbox{if $p_i < 0$};\\ 2dx & \mbox{otherwise}.\end{array} \right. \end{array}$

The initial value of p is

$\begin{array}{rcl} p_0&=&2dxy_0-2dyx_0 +2dx -2bdx +dy\\ &=&2dxy_a-2dyx_a +2dx -2(y_a-mx_a)dx +dy\\ &=&2dxy_a-2dyx_a +2dx -2dxy_a-2dyx_a +dy\\ &=&2dx+dy\end{array}$

Code is

dx = xb - xa;
dy = yb - ya;
const1 = 2*dy+2*dx;
const2 = 2*dx;
p = 2*dx + dy;
x = xa;
for (y=ya; y <= yb; y++) {
   drawPixel(x,y);
   if (p < 0) {
     x--;
     p+= const1;
   } else {
     p += const2;
   }
}

Question 3

AEL = [ ((2,3),(2,10)), ((2,3),(7,6)), ((8,4),(7,6)), ((12,2),(13,9))]
IEL = [ ((13,9),(7,12)), ((2,10),(7,12)) ]

pixels (2,5) (3,5) (4,5) (5,5) and (8,5) (9,5) (10,5) (11,5) (12,5) will be filled. NOTE: (7,5) will not be filled. Since the intersection of y=5 with the ((8,4), (7,6)) line occurs at 7.5, filling in (7, 5) would be filling a point outside the polygon.

The general rules are:

- On the left edge, round up to the nearest integer, with round(n) = n if n is an integer.

- On the right edge, round down to the nearest integer, but with round(n) = n-1 if n is an integer.

Question 4

Rearrange a,b,c so that a.y < b.y < c.y.

Assume that fillSpan(y, x1, x2) fills in all the pixels between x1 and x2 regardless of whether x1 < x2 or vice versa.

Let the equation of the line ac be y = m1*x + b1 (or x = (y-b1)/m1)
Let the equation of the line ab be y = m2*x + b2 (or x = (y-b2)/m2)
Let the equation of the line bc be y = m3*x + b3 (or x = (y-b3)/m3)

void fillTriangle(Point a, Point b, Point c){ 
  float m1 = (a.y-c.y)/(a.x-c.x);
  float b1 = c.y - m1*c.x;
  float m2 = (a.y-b.y)/(a.x-b.x);
  float b2 = b.y - m1*b.x;
  float m3 = (c.y-b.y)/(c.x-b.x);
  float b3 = b.y - m1*b.x;

  for (int y = a.y; y < b.y; y++) {
    fillSpan(y,Math.round(0.5+(y-b1)/m1),Math.round(0.5+(y-b2)/m2));
  }

  for (int y = b.y; y < c.y; y++) {
    fillSpan(y,Math.round(0.5+(y-b1)/m1),Math.round(0.5+(y-b3)/m3));
  }
}

Question 5

There are several ways to triangulate a polygon. The simplest method is to search for diagonals, where a diagonal is a line connecting two polygon vertices that lies inside the polygon and does not cross any edge of the polygon. Once you have found a diagonal, you can use it to divide the polygon into two smaller polygons and recursively triangulate each one.

An inefficient search method for diagonals is to look at the line formed by each possible pair of vertices, test if this line is inside the polygon and then test this line against each polygon edge to see if it crosses. This could take time O(n^3) (O(n^2) pairs and O(n) tests for each pair) to find a diagonal.

There is an efficient way to search for diagonals. Find a convex corner XYZ.

X.........Z
 \.A...../
  \..B../
   \.C./  (dots mark inside of poly)
    \./
     Y

If XZ is not a diagonal, some polygon edge must cross XZ and there must be some polygon vertices inside the triangle XYZ. Find the one that is furthest from XZ (C in the diagram above). Then YC is a diagonal.

This method takes O(n) time to find a convex corner and then O(n) time to find the vertex inside the triangle that is furthest from XZ.

This entry was posted on Friday, October 2nd, 2009 at 2:02 am and is filed under Tutorial Solutions. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

You must be logged in to post a comment.