Computer Graphics CSC 2504 — Assignment 2

Behdad Esfahbod 993505827

October 24, 2003

1. (a)
A : (1, 1)
B : (\frac{1}{3}, 2)
C : (2.5, 0.25)

(b)

M_{BC} = [ \begin{matrix}0 & −0.5 & 3.5 \\ −1.5 & 0.25 & 0.25 \\ 0 & 0 & 1 \end{matrix} ]

2. (a) No. Those line families that are normal to the view vector, do not converge to a point and remain parallel. For the given view vector, this means those B = (x, y, z) line families with 3x + 4y = 0, or B = (x, −\frac{3}{4}x, z). For all other line families B which are not normal to the view vector, the family in the VCS has a non-zero z_{vcs} (as B × k is not zero). So the line would be A_{vcs} + B_{vcs}t which is (x_{a} + x_{b}t, y_{a} + y_{b}t, z_{a} + z_{b}t), all in VCS, and z_{b} ≠ 0. Without loss of generality, we assume z_{b} < 0. So the same line after perspective projection would be

P = (\frac{d(x_{a} + x_{b}t)}{(z_{a} + z_{b}t)}, \frac{d(y_{a} + y_{b}t)}{(z_{a} + z_{b}t)}, d) .

So we get

lim_{t→∞} P = (\frac{dx_{b}}{z_{b}} , \frac{dy_{b}}{z_{b}} , d),

. (b)

k = \frac{−V_{view}}{|V_{view}|} = (−0.6, −0.8, 0)
i = \frac{V_{up}×k}{|V_{up}×k|} = (0.8, −0.6, 0)
j = k × i = (0, 0, 1)

The eye-space transform is:

M_{cam}^{−1} = [ \begin{matrix}0.8 & −0.6 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ −0.6 & −0.8 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ]

And projective transform applied to it:

[ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & \frac{1}{d} & 0 \end{matrix} ] [ \begin{matrix}0.8 & −0.6 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ −0.6 & −0.8 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] = [ \begin{matrix}0.8 & −0.6 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ −0.6 & −0.8 & 0 & 0 \\ \frac{−0.6}{d} & \frac{−0.8}{d} & 0 & 0 \end{matrix} ]

(c) B = (1, 0, 0), so B_{vcs} = (0.8, 0, −0.6). So z_{b} ≠ 0 and the line family converges to (\frac{0.8d}{−0.6}, \frac{0d}{−0.6}, d).

3. (a) Let A, B, C, D be the four points of the polygon, which AC is an edge in the given triangulation. We assume that AB, BC, CD, DA are edges of polygon or diameters in the triangulations. Then the algorithm is:

• If four points A, B, C, D form a convex quadrilateral (in other words: none of them is in the triangle formed by the other three), then return true,

• Otherwise, return false.

(b) Now we can skip the convex check above, so here it is:

• return true,

(c) Let P_{0}, P_{1}, …, P_{n−1} be the vertices of the convex polygon in counterclockwise order, and T_{1} and T_{2} are the two triangulation of the polygon. Moreover, let T_{0} be the unique triangulation of the polygon that P_{1} is a vertex of all of the triangles (as the polygon is convex, T_{0} always exists). As diagonal flips are reversible, all we need to do is to show that both T_{1} and T_{2} can be turned into T_{0} in at most n − 3 diagonal flips, which the following lemma does. So the proof is complete. Lemma For the polygon defined above, and any triangulation T of it, T can be turned into T_{0} with at most n − 3 diagonal flips. Proof Let C_{n} be the number of neede flips to do so. We prove by induction. For n = 3, it is trivial, C_{3} = 0. For n > 3, one of the following cases holds:

• P_{1} is a vertex of more than one of the triangles in T: So there should be a diameter in T with P_{1} as one of its heads, let P_{i} be the other head. We can change the two smaller polygons P_{1}, P_{2}, … P_{i} and P_{i+1}, P_{i+2}, …, P_{0} so that P_{1} is a vertex of all of the triangles in them, and we are done. So

C_{n} ≤ C_{i+1} + C_{n−i+1} ≤ (i + 1 − 3) + (n − i + 1 − 3) = n − 4 ≤ n − 3

• P_{1} is a vertex of only one of the triangles in T: This triangle should be P_{0}, P_{1}, P_{2}. There is another triangle in T which P_{0}, P_{2} is an edge of, let it be P_{0}, P_{i}, P_{2}. We do a diagonal flip on P_{0}, P_{1}, P_{i}, P 2, and then apply the method of the previous case. So

C_{n} ≤ 1 + C_{i+1} + C_{n−i+1} ≤ 1 + (i + 1 − 3) + (n − i + 1 − 3) ≤ n − 3

The proof is complete now.