Note: All the transformation matrices in this assignment are supposed to work on column vectors

HW #3 Solution

Problem 1

(a) Bresenham’s has more characteristics than the DDA. List them.

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 best-fit approximation
Points 1 – 3 imply that the Bresenham’s algorithm is faster than the DDA since rounding, floating arithmetic and non-incremental 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₀, y₀) and (x₁, y₁)

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 left-hand corner to the circle in the upper right-hand corner by Bresenham’s algorithm. Graphically show how Bresenham’s algorithm will generate the line by making appropriate grid-points. 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 line has slope and has equation where b = .

Problem 2

Consider the operation of double shearing, that is, shearing in the x-axis direction followed by shearing in the y-axis 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 x-axis followed by shearing along the y-axis 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 y-axis followed by shearing along the x-axis 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 z-axis by an amount of 4x+3y where x and y are the x- and y-coordinates 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 y-axis by 50 degree.

(c)

From the result, this matrix performs reflection at the origin followed by translation in the x-direction by 1 and in the y-direction 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 Cohen-Sutherland outcode for 3D and example your steps.
Answer:

Add two more bits to the code to make a 6-bit 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 y-coordinates and their corresponding x-coordinates. The active edge table keeps track of each scanline so that edges intersect with this scanline are sorted in ascending order on their x-coordinates 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 state-of-the-art 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

State-of-the-art 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 sub-tree. In the third loop, the red rectangle is chosen as the root of the sub-tree of the sub-tree obtained in the second loop. The final BSP tree is:

Directory: ~saifz -> eece478
eece478 -> A roadmap to the Course

Download 23.44 Kb.

Share with your friends: