\documentclass[11pt]{article}
\usepackage{graphics}

\topmargin=-1in
\oddsidemargin=-.5in
\textwidth=7.2in
\textheight=9in

\newcommand{\VCS}{{vcs}}
\newcommand{\vcs}{{vcs}}

\begin{document}
\title{Computer Graphics\\CSC 2504 --- Assignment 2}
\author{Behdad Esfahbod\\993505827}
\maketitle

\begin{enumerate}

\item
\begin{enumerate}
\item
\begin{eqnarray*}
A:& (1, 1)\\
B:& (\frac13, 2)\\
C:& (2.5, 0.25)
\end{eqnarray*}
\item
$$
M_{BC} = 
\left[
\begin{array}{rrr}
0\phantom{.0} & -0.5\phantom{0} & 3.5\phantom{0} \\
-1.5 & 0.25 & 0.25 \\
0\phantom{.0} & 0\phantom{.00} & 1\phantom{.00}
\end{array}
\right]
$$
\end{enumerate}

\item
\begin{enumerate}

\item
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, -\frac34x, 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\times k$ is not zero).  So the
line would be $A_\vcs+B_\vcs t$ which is $(x_a+x_bt, y_a+y_bt, z_a+z_bt)$, all
in VCS, and $z_b\not=0$.  Without loss of generality, we assume $z_b<0$.  So the
same line after perspective projection would be
$$P=\left(\frac{d(x_a+x_bt)}{(z_a+z_bt)},\frac{d(y_a+y_bt)}{(z_a+z_bt)},
	d\right).$$  
So we get $$\lim_{t\rightarrow\infty}P = (\frac{dx_b}{z_b}, \frac{dy_b}{z_b},
	d),$$.

\item
\begin{eqnarray*}
k=&\frac{-V_{view}}{|V_{view}|}&=(-0.6, -0.8, 0)\\
i=&\frac{V_{up}\times k}{|V_{up}\times k|}&=(0.8, -0.6, 0)\\
j=&k\times i&=(0,0,1)
\end{eqnarray*}

The eye-space transform is:
$$
M_{cam}^{-1} = 
\left[\begin{array}{rrrr}
0.8& -0.6& 0& 0\\
0\phantom{.0}& 0\phantom{.0}& 1& 0\\
-0.6& -0.8& 0& 0\\
0\phantom{.0}& 0\phantom{.0}& 0& 1
\end{array}\right]
$$

And projective transform applied to it:
$$
\left[\begin{array}{rrrr}
1& 0& 0& 0\\
0& 1& 0& 0\\
0& 0& 1& 0\\
0& 0& \frac1d& 0\\
\end{array}\right]
\left[\begin{array}{rrrr}
0.8& -0.6& 0& 0\\
0\phantom{.0}& 0\phantom{.0}& 1& 0\\
-0.6& -0.8& 0& 0\\
0\phantom{.0}& 0\phantom{.0}& 0& 1
\end{array}\right]
=
\left[\begin{array}{rrrr}
0.8& -0.6& 0& 0\\
0\phantom{.0}& 0\phantom{.0}& 1& 0\\
-0.6& -0.8& 0& 0\\
\frac{-0.6}d& \frac{-0.8}d& 0& 0
\end{array}\right]
$$

\item $B=(1,0,0)$, so $B_{vcs}=(0.8,0,-0.6)$.  So $z_b\not=0$ and the line
family converges to $(\frac{0.8d}{-0.6},\frac{0d}{-0.6},d)$.

\end{enumerate}


\item
\begin{enumerate}

\item
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:
\begin{itemize}
\item
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 \texttt{true},
\item  Otherwise, return \texttt{false}.
\end{itemize}

\item
Now we can skip the convex check above, so here it is:
\begin{itemize}
\item
return \texttt{true},
\end{itemize}

\item
Let $P_0, P_1, \dots, 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.

\noindent\textbf{Lemma\space}  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.

\noindent\emph{Proof\space}  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:
\begin{itemize}

\item  $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, \dots
P_i$ and $P_{i+1}, P_{i+2}, \dots, P_0$ so that $P_1$ is a vertex of all of the
triangles in them, and we are done.  So
$$
C_n\leq C_{i+1}+C_{n-i+1}\leq (i+1-3) + (n-i+1-3)=n-4\leq n-3
$$

\item  $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, P2$, and then apply the method of the previous case.  So
$$
C_n\leq 1+C_{i+1}+C_{n-i+1}\leq 1+(i+1-3) + (n-i+1-3)\leq n-3
$$

The proof is complete now.

\end{itemize}

\end{enumerate}


\end{enumerate}

\end{document}
