2D CGA - Midtest 2014

-

COMPUTER GRAPHICS AND ANIMATION
MID TEST
150 minutes. Open book. No electronic devices allowed.

  • Answer the questions below. You can score more than 100, but the maximum score is capped to 100.
  • There are a lot of questions and you might not have enough time to answer all of them. Start by answering the questions that you think are easy to answer.
  • The questions are not too hard to answer; if you paid attention during class, tried doing the review questions and exercises at the end of each PPT file, and did the homeworks without mindlessly copying them from someone else, you should not have too much trouble answering the questions. But should you become frustrated during the test, feel free to create your own handmade graphics on your answer sheet.

  1. The basics
  1. Explain the difference between Computer Graphics, Image Processing, and Image Interpretation. Give an example for each. (10 points)
Answer

Computer graphics is a field that focused on representing/drawing an object on the computer.
Example: Drawing a 2D sprite and 3D model

Image processing is a field that focused on processing an image into another image.
Example: Image filter

Image interpretation is a field that focused on recognizing some object from an image.
Example: Animal image classifier
  1. Which is more complicated: rasterization or vectorization? Explain. (5 points)
Answer

Vectorization, because ...
  1. Which representation is used to store data for 3D models: vector or bitmap? Explain. (5 points)
Answer

Vector, because ...
  1. Drawing lines
    1. Explain what kind of line can be drawn with the following DDA algorithm (explain the properties of such line):

Procedure Line(x1: integer, y1: integer, x2: integer, y2: integer)
Definitions
x : integer
m, y : real
Algorithm
m (y2–y1)/(x2–x1)
x x1
y y2
While y y1 do
Set(x, Round(y))
y y - 1
x x + m
{y < y1}

Give an example of a line with starting point (x1, y1) and and end point (x2, y2) that can be drawn using the above algorithm. (10 points)

Answer

The algorithm above are traversing through the y-axis, then the dy > dx. So it's a steep line. Since it traverse from y2 to y1 with y2 < y1 and x1 < x2 because the x is increased by m, y1 would have lower y-position than y2, and x1 will be on the left of x2.

So the line is going to up right forming an angle greater than 45 degree.

For the example case, (0, 0) to (10, 10) is a line with 45 degree angle, just decrease the x2 position to get the steep line.

Starting point (0, 0) and end point (8, 10)
    1. Is it possible to further optimize the midpoint line algorithm using second order difference? Explain. (5 points)
Answer

Yes
...
  1. Drawing Circles
  1. Explain why the midpoint circle algorithm is done by dividing the circle into octants and not quarters. (5 points)
  1. Modify the midpoint circle algorithm to draw a “Pac Man” with a radius of R. A “Pac Man” can be defined as a three-quarter circle that arcs from 45o to 315o with two lines from the center of the circle to each “arc-end” of the circle. For example, shown below is a “Pac Man” centered at (0,0) with a radius of 10.



Write the code for the procedure DrawPacMan which draw a “Pac Man” as specified below.

Procedure DrawPacMan(In xc : integer, In yc : integer, In R : integer)
{Draws a Pac Man centered at (xc,yc) with a radius of R}
{I.S. : xc, yc, and r can be any value}
{F.S. : the Pac Man is drawn}

The only primitive that you may use is Set(x,y) to draw a point at (x,y). You have to draw the lines and circle by using Set.

Tips:
  • It is easier to draw the three-quarter circle first, then draw the lines from the arc-ends to the center of the circle. This way, you will know where the lines start and end.
  • Note that the lines might not end exactly at the center of the circle if you follow the above tip; they might end at (xc 1, yc) or (xc, yc 1). A one-pixel difference in this case is tolerated.
(20 points)

Answer

void DrawPacman(int xc, int yc, int r)
{
    int x, y;

    // 3/4 circle
    x = 0;
    y = r;
    int d = 5 - 4 * r;
    while(x >= y)
    {
        set(xc + x, yc + y); // top right steep
     
        set(xc - x, yc + y); // top left steep
        set(xc - y, yc + x); // top left shallow
     
        set(xc - x, yc - y); // bottom left steep
        set(xc - y, yc - x); // bottom left shallow
     
        set(xc + x, yc - y); // bottom right steep

        if (d >= y)
        {
            d += 8 * x + 12;
        }
        else
        {
            d += 8 * (x - y) + 20;
            y--;
        }
        x++;
    }

    // Line
    x = 0;
 
    while(x <= r)
    {
        set(xc + x, yc + x); // Line 45 degree to top right
        set(xc + x, yc - x); // Line 45 degree to bottom right
        x++;
    }
}

  1. Second Order Difference
The following code draws the parabola y = x2/100 from (0,0) to (50,25) using the midpoint algorithm.

Procedure DrawParabola
{Draws the parabola y = x2/100 from (0,0) to (50,25)}

Definitions:
x, y, d, dR, dUR: integer
Algorithm
x 0; y 0 {start from (0,0)}
d 49 {initial d value}
Iterate
Set(x,y)
Stop x = 50
If d > 0 then {choose UR}
dUR 2 * x - 97
d d + dUR
y y + 1
Else {choose R}
dR 2 * x + 3
d d + dR
{end if}
x x + 1
{end of loop}

Modify the above algorithm to draw the parabola using second order difference.
Tips:
  • For each case (choosing UR or R), find d(dUR) and d(dR) and use them to update the values of dR and dUR.
  • Find the initial values of dR and dUR.
(10 points)

Answer

void Draw()
{
     int x, y, d, dUR, dR;
     x = 0;
     y = 0;
     d = 49;
     while(x != 50)
     {
         set(x, y);
         if (d > 0)
         {
               dUR = 2 * x - 97;
               d = d + dUR;
               y = y + 1;
          }
           else
          {
               dR = 2 * x + 3;
               d = d + dR;
          }
          x++;
     }
}

R
dUR_old = 2 * x - 97
dUR_new = 2 * (x + 1) - 97 = 2 * x - 95
ddUR = dUR_new - dUR_old = 2

dR_old = 2 * x + 3
dR_new = 2 * (x + 1) + 3 = 2 * x + 5
ddR = dR_new - dR_old = 2

UR
dUR_old = 2 * x - 97
dUR_new = 2 * (x + 1) - 97 = 2 * x - 95
ddUR = dUR_new - dUR_old = 2

dR_old = 2 * x + 3
dR_new = 2 * (x + 1) + 3 = 2 * x + 5
ddR = dR_new - dR_old = 2

Initial
     UR = 2 * x - 97 = 2 * 0 - 97 = -97
     R = 2 * x + 3 = 2 * 0 + 3 = 3

void Draw()
{
     int x, y, d, dUR, dR;
     x = 0;
     y = 0;
     d = 49;
     dUR = -97;
     dR = 3;
     while(x != 50)
     {
         set(x, y);
         if (d > 0)
         {
               d = d + dUR;               dUR = dUR + 2;
               dR = dR + 2;
               y = y + 1;
          }
          else
          {
               d = d + dR;               dUR = dUR + 2;
               dR = dR + 2;
               d = d + dR;
          }
          x = x + 1;
     }
}
  1. Polygon data

A polygon is represented as a list of points:

Type TPoint
< x : real, y : real>
Type TElmtPoint
< Info : TPoint, Next : TElmtPoint>
Type TPolygon
< First : TElmtPoint>

  1. Write the code for the function IsValidPolygon which checks if a polygon is valid. A polygon is considered valid if it has at least three vertices (points) regardless of the coordinates of each vertex. You may write the code in Basic*, C*, or just good ol' algorithmic notation.

Function IsValidPolygon(P : TPolygon) boolean
{checks whether P is a valid polygon}
{Input : P may or may not be a valid polygon}
{Output : True if P has at least three vertices,
False if otherwise}

(5 points)

Answer

bool IsValidPolygon(TPolygon p)
{
    TElmtPoint *ploygon_point = &p.First;
    int total = 1;
    while(polygon_point->Next != NULL)
    {
         total++;
         polygon_point = polygon_point->Next;
    }
     return total >= 3;
}
  1. Write the code for the procedure TranslatePolygon which translates (moves) a polygon.

Procedure TranslatePolygon(In/Out P : TPolygon, In x : real,
In y : real)
{Translates polygon P by (x,y)}
{I.S. : P is a valid polygon; x and y are any numbers}
{F.S. : each vertex of P is translated x untis right and
y units up}
{Assume that y+ is up}

(5 points)

Answer

void TranslatePolygon(TPolygon *p, float x, float y)
{
     TElmtPoint *ploygon_point = p->First;
     polygon_point->Info.x += x;
     polygon_point->Info.y += y;
     while(polygon_point->Next != NULL)
     {
          polygon_point->Info.x += x;
               polygon_point->Info.y += y;
          polygon_point = polygon_point->Next;
     }
}
  1. Write the code for the function PolygonPerimeter which calculates the perimeter (keliling) of a polygon.

Function PolygonPerimeter(P : TPolygon) real
{returns the perimeter of a polygon}
{Input : P is a valid polygon}
{Output : the perimeter of P}

Tip: you may use the Distance function below to calculate the distance between two points.

Function Distance(P1 : TPoint, P2 : TPoint) real
{returns the distance between two points}
{Input : P1 and P2 are any points}
{Output : the distance between P1 and P2}
{Example : Distance(<0,0>,<3,4>) returns 5}
{You do not have to write the code for this function}

(5 points)

Answer

float PolygonPerimeter(TPolygon p)
{
    TElmtPoint *ploygon_point = &p.First;
    float total = 0.0f;
    while(polygon_point->Next != NULL)
    {
         total += Distance(polygon_point->Info, *polygon_point->Next);
         polygon_point = polygon_point->Next;
    }
     total += Distance(polygon_point.Info, p.First.Info);
     return total;
}
  1. Cohen-Sutherland Clipping
    1. In the trivial accept case for line clipping in the Cohen-Sutherland method, a line is accepted if the area codes of each end equal to 0. Let C1 be the area code of one end point and C2 be the area code of the other. Explain how/why we can compute the following expression (in C):

(C1 == 0) && (C2 == 0)

as:

!(C1 || C2)

(5 points)

    Answer

    De Morgan Law, ~(p & q) can be translated as ~p | ~q and ~(p | q) can be translated as ~p & ~q. In C, 0 is false. Thus !(C1 || C2) is equal with !(C1 != 0 || C2 != 0), or ~(c1 | c2) . And (C1 == 0) && (C2 == 0) is equal with ~c1 & ~c2.
    1. If we extend the Cohen-Sutherland clipping algorithm for 3D clipping, how many bit codes do we need to indicate the region of a point? Explain. (5 points)
     Answer
     27 region, since in 2D Cohen-Sutherland clipping is devided into 9 region with 2 axis x and y which consist of left up, up, up right, left, middle, right, left bottom, bottom, right bottom. If it's on 3D, ... 
  1. Nicoll – Lee – Nicoll (NLN) Clipping
Given a line with two end points: A(0,3) and B(5, 7), use the NLN clipping algorithm to clip line AB with a rectangular window having opposing corners at (2, 2) and (4, 6).
    1. Using bit area codes, verify that both A and B are outside the clipping window. (5 points)

    1. Find m1, m2, m3, and m4 which are the gradients of the lines from A to the bottom-left (m1), bottom-right (m2), top-right (m3), and top-left (m4) corners of the clipping window. Also find m which is the gradient of the line AB. (5 points)

    1. Based on the values of m, m1, m2, m3, and m4, which edges of the clipping window intersect line AB? Explain your answer. (5 points)

    1. Find the end points of line A’B’ where A’B’ is the result of clipping line AB with the clipiing window. (5 points)

  1. Cyrus-Beck Clipping
    1. The following table is the result of clipping a polygon with 5 edges and points A, B, C, and D. “In” indicates that a point is “inside” an edge, and “out” indicates that a point is “outside” an edge.
A
B
C
D
E
Edge 1
Out
In
In
In
In
Edge 2
Out
In
Out
In
In
Edge 3
In
In
In
Out
In
Edge 4
Out
In
In
Out
In
Edge 5
In
In
Out
In
In

Determine whether the following lines are accepted, rejected, partially accepted (one point is inside the polygon while the other is outside), or cannot be directly determined (“neither”). Explain each case.
  • Line BC
  • Line AC
  • Line CD
  • Line AD
  • Line BE
(5 points)

    1. Given a line with two end points: A(5, 2) and B(-3, 9), use the Cyrus-Beck point clipping method to determine whether P(-1, 5) is below or above the line.
(5 points)

Answer
Line AB is a line that goes to left top (x1 > x2, y2 > y1), so we can check wether a point is below (left side of line AB) or above (right side of line AB) the line.

Note
[-dy dx] is a vector that goes to left and [dy -dx] is a vector that goes to right

Vector A is [5 2]
Vector B is [-3 9]
Vector AB is [-8 7]

Then normal to left (N) is [-7 -8]

Vector A is [5 2]
Vector P is [-1 5]
Vector AP is [-6 3]
Then vector AP · N is [-6 3] · [-7 -8] = 42 + (-24) = 18

Because AP · N is greater than 0, then AP has the same direction with the normal (left) or below the line AB
    1. Let P be a polygon with five vertices: (3,0), (0,5), (4,6), (7,5), and (6,2). Prove that P is a convex polygon without drawing the polygon. (5 points)

  1. Polygon Clipping

    1. Perform a polygon clip with the Sutherland-Hodgman algorithm on the following polygon and clipping window:



Perform the clipping in the following order: right edge, top edge, left edge, and bottom edge. Draw the results after clipping each edge (yes, draw 4 times!). Name the vertices of each resulting polygon in proper order.
(10 points)
    1. One problem that might occur when clipping a polygon using the Weiler-Atherton algorithm is when there are no intersections between the clipped polygon and the clipping window. There are three cases where such condition might occur. Explain each case.
Tip:
  • For each case, compare the position of the clipped polygon to the clipping window. Provide an illustration for each case.
      1. points)
Answer

  • When the polygon is inside the clipping window
  • When the clipping window is inside the polygon
  • When the polygon is outside clipping window 

  1. Extra Credit
This question is worth 5 points.
Write down the question written below on your answer sheet and answer it. No points will be given if you do not write the question.

If a zombie came and attacked you, what weapon would you use to exterminate it?

Answer
You can give the zombie 2D Computer Graphics and Animation course, it will make the zombie brain explodes 

Comments

Post a Comment

Popular posts from this blog

HW 2D CGA - PPT 5 - Clipping 2

-
Image
Question 1 Solution: We need to declare:  $$A=\begin{bmatrix}2\\7\end{bmatrix}, B=\begin{bmatrix}10\\2\end{bmatrix}, C=\begin{bmatrix}7\\4\end{bmatrix}$$ And then find \(\overrightarrow {AB}\) and \(\vec N\): $$\overrightarrow {AB}=\begin{bmatrix}10-2\\2-7\end{bmatrix}=\begin{bmatrix}8\\-5\end{bmatrix}$$ Here are some basic rule you need to know to easily define \(\vec N\): $$if \ \vec N \ is \ to \ the \ left \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}$$  $$if \ \vec N \ is \ to \ the \ right \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}dy\\-dx\end{bmatrix}$$ From the rule above, we can see that because \(\vec N\) is facing to the left (up as stated in the question) of \(\overrightarrow {AB}\), we can conclude as stated below: $$\vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}=\begin{bmatrix}5\\8\end{bmatrix}$$ Variable \(dx\) and \(dy\) is taken from \(\overrightarrow {AB}\). After that the question requires us to find \(\o
Read more

HW 2D CGA - PPT 8 - Polygon Fill

-
Image
Question Solution: First of all, we need to know the element to be inserted into SET and AEL. The element must contain \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Also carry but only in AEL, carry doesn't need to be inserted into SET. With that said, let's begin with the first polygon. Polygon 1 A(1, 6), B(5,4), C(3,1) From these 3 vertices we need to find the edges element containing \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Let's take a look at edge AB , the \(y_{max}\) is 6, the \(x \ of \ y_{min}\) is 5, the \(dx\) is 4, and the \(dy\) is -2. Now if we found \(dy < 0\) we need to make it positive, by multiplying \(dx\) and \(dy\) with -1, so we got \(dx\) = -4 and \(dy\) = 2. The same rule applies with edges BC and CA. After we've found all of the elements then, we put it into the SET just like below. SET y Edges \(y_{max}\) 6 5 4 \( \rightarrow AB \) 6 5 -4 2 3 2 \(y_{min}\) 1 \( \rightarrow
Read more