EECE 478 Computer Graphics
HW #3 Solution
Note: All the transformation matrices in this assignment are supposed to work on column vectors.
Problem 1
The DDA is an algorithm derived from the slopeintercept form of a line. From the DDA algorithm, which is first adapted for faster graphics, the Bresenham’s algorithm is derived.
(a) Bresenham’s has more characteristics than the DDA. List them.
Answer:
Some properties of Bresenham’s algorithm from the textbook are:
1. No rounding function
2. Only integer arithmetic
3. Calculation for the point (x_{i+1}, y_{i+1}) based on the point (x_{i}, y_{i}) only.
4. Applicable to the integer computation of circles
5. Line and integer circle algorithms provide the bestfit approximation
Points 1 – 3 imply that the Bresenham’s algorithm is faster than the DDA since rounding, floating arithmetic and nonincremental technique take more computing time.
From the assignments of students, some points NOT the advantages of Bresenham’s algorithm over the DDA are:
1. endpoints are (x_{0}, y_{0}) and (x_{1}, y_{1})
2. slope is between 0 and 1.
3. description of the Bresenham’s algorithm
4. no multiplication or division. (Both DDA and Bresenham’s algorithm do not have these in the main loop.)
5. list of the variables used in the algorithms
(b) Consider the Figure below where a line is to be placed on the grid from the circle in the lower lefthand corner to the circle in the upper righthand corner by Bresenham’s algorithm. Graphically show how Bresenham’s algorithm will generate the line by making appropriate gridpoints. For the critical points, carry out simple calculations for the decision what needs to be done. Explain how you arrived at your answer.
Answer:
The basic idea of the Bresenham’s algorithm is that for a point P at (x_{p}, y_{p}) for a line of slope between 0 and 1, the point at x = x_{p} + 1 can be either E (y = y_{p}) or NE (y = y_{p+1}) depending on which one the line is close to.
To determine which points to turn on, a line is first drawn between the two endpoints.
The line has slope and has equation where b = .
Then, scan from left to right along the xaxis to decide which points to turn on based on the idea shown above.
For point at x = 6, y =7.45. Point (6,7) will be turned on. The points at x = 7 to x = 14 are very obvious. For point at x = 15, . Point (15,12) will be turned on.
Therefore, the result is:
Problem 2
Consider the operation of double shearing, that is, shearing in the xaxis direction followed by shearing in the yaxis direction or vice versa.
(a) Is double shearing commutative? Show algebraically, using homogenous coordinates, that your answer is correct.
Answer:
No, double shearing is not commutative.
Proof:
The matrices for x and y shear transformations are:
The transformation matrix for shearing along the xaxis followed by shearing along the yaxis is:
Remark: This order of the matrices is correct since the matrix closest to the vector transforms the vector first! Column vector to be transformed is placed to the right of the transformation matrix.
The transformation matrix for shearing along the yaxis followed by shearing along the xaxis is:
Since T_{xy} and T_{yx} are not the same, shearing is not commutative.
(b) Can double shearing be carried out simultaneously, that is, be represented by a single matrix? Attempt to derive the transformation matrix and show that this is or not possible.
Answer:
Yes, double shearing can be carried out simultaneously represented by a single matrix. As shown in part (a), each type of double shearing can be represented by a single matrix.
Remark: the matrix is not a double shearing matrix based on the definition of double shearing given above. The effect of this matrix is different from the two matrices obtained in part a.
Problem 3
Explain the effect of the following matrices as related to transformation:
(a) (b) (c)
Answer:
(a)
From the result, this matrix shears the vector along the zaxis by an amount of 4x+3y where x and y are the x and ycoordinates of the vectors.
(b) I think there is a mistake in the matrix in the original question sheet, it should be instead.
Thus it is obviously a matrix for the rotation around the yaxis by 50 degree.
(c)
From the result, this matrix performs reflection at the origin followed by translation in the xdirection by 1 and in the ydirection by 1.
Problem 4
A square as shown in (a) is converted to a parallelogram as in (b) using composite transformation matrix M. Determine such matrix. Explain your work.
Answer:
Based on the data in the graph above:
Then,
Therefore,
Problem 5
Develop a CohenSutherland outcode for 3D and example your steps.
Answer:
Add two more bits to the code to make a 6bit code so that :
First bit y > y_{max}
Second bit y < y_{min}
Third bit x > x_{max}
Fourth bit x < x_{min}
Fifth bit z > z_{max}
Sixth bit z < z_{min}
For the small cube in the center of the large cube shown above consider as the clip region, the outcodes for each small cubes surrounding the central cube are:
Problem 6
Generate the necessary Edge Table and Active Edge Table to fill the polygon in Figure below.
Why was it necessary to generate these tables?
Answer:
Edge Table:
Active Edge Table for Scan Line 1 to 9:
Scan Line 1:
Scan Line 2:
Scan Line 3:
Scan Line 4:
Scan Line 5:
Scan Line 6:
Scan Line 7:
Scan Line 8:
Scan Line 9:
This algorithm takes advantage of the edge coherence to calculate x intersections and scanline coherence to calculate spans. The edge table stores the information for each edge and sorts the edges on their minimum ycoordinates and their corresponding xcoordinates. The active edge table keeps track of each scanline so that edges intersect with this scanline are sorted in ascending order on their xcoordinates of the intersections. Due to the edge coherence and scanline coherence, only a small amount of work is required to update the active edge table for each scanline.
Problem 7
What are the computer graphics system main components? Give example on each component. What are the stateoftheart computer graphics software package available in the market? Have you used any? Explain what you did with them.
Answer:
A computer graphics system includes:
1. input devices
e.g. keyboard, mouse, trackball, joystick, cyberglove, scanner, etc
2. output devices
e.g. monitor, printer etc
3. processing unit
e.g. CPU, video controller, etc
4. softwares
e.g. OpenGL, SRGP, Alias, Director, Animator, etc
Stateoftheart computer graphics software packages:
1. OpenGL
2. Alias
3. Director
4. Photoshop
5. CorelDraw
6. AutoCad
and many many more……
Problem 8
Binary Space Partition (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front, as in painter’s algorithm. Explain how does this algorithm work using a simple example (but not a trivial one).
Answer:
The algorithm of the BSP tree is shown as follows:
1. pick any surface of an object to put on the root of the tree
2. any other surfaces of the object totally behind the surface picked in 1 will be on the left side of the tree.
3. all surfaces of the object totally in front of the surface picked in 1 will be on the right side of the tree.
4. a surface lying on both sides is split and the two halves are assigned to the two groups in steps 2 and 3.
5. for each side of the tree, repeat steps 1 to 4 until there is only one surface left for each node.
Example:
There are four objects or surfaces in the diagram above. If the blue rectangular surface is chosen to be the root of the BSP tree, we will get in the first loop of the algorithm:
Then, in the second loop, the yellow surface on the left side of the tree is shown as the root of this subtree. In the third loop, the red rectangle is chosen as the root of the subtree of the subtree obtained in the second loop. The final BSP tree is:
