% 14 Mar 96, 6pm;  written
% 15 Mar 96, 1:20pm;  tiny changes to clarify wording

\documentstyle[times,12pt]{article}

\setlength{\textwidth}{6in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{-.5in}	% top of page to top of running head minus 1in
% \setlength{\headsep}{.5in}	% bottom of running head to top of text
\setlength{\oddsidemargin}{.5in}	% left margin minus 1in on odd pages
\setlength{\evensidemargin}{0in}	% left margin minus 1in on even pages
\setlength{\parskip}{2ex}		% vertical space between paragraphs

% matrix with rounded brackets
\def\rmatrix #1{\left\lgroup\matrix{ #1 }\right\rgroup}

\def\U{\hskip-.6em\relax&}
\def\ur{\cr\noalign{\vskip 1.5ex}}
\def\ud{\cdot}
\def\homodiv{\mbox{homodiv}}
\def\tim{\!\times\!}
\def\teq{\!=\!}
\def\tpl{\!+\!}
\def\tmi{\!-\!}
\def\S{\mskip 10mu}
\def\s{\mskip 6mu}
\def\p{{\bf p}}
\def\q{{\bf q}}
\def\x{{\bf x}}
\def\y{{\bf y}}
\def\M{{\bf M}}

\def\prob #1#2 {\vspace{8ex}\noindent {\bf \Huge #1} [#2]\\ }
\def\ba{{\bf a)\ }}
\def\bb{{\bf b)\ }}
\def\bc{{\bf c)\ }}
\def\bd{{\bf d)\ }}
\def\be{{\bf e)\ }}
\def\bF{{\bf f)\ }}

\begin{document}
\begin{center}
{\LARGE Written Assignment W2} \\
Computer Graphics 2 (15-463) \\
14 Mar. 1996
\vskip 2ex
Due 11:59pm Thursday, 21 Mar. 1996, at my office (DH 4301A)
\end{center}

\prob{1.}{10 pts.}
Prove that perspective transformation preserves lines,
that is, that lines transform to lines, not curves, through a perspective
transformation.
This is an important property that allows
screen space $z$ to be linearly, and quickly, interpolated in z-buffer
algorithms.

One way to prove this is as follows
(if you find another way, we'll accept that too!).
Define a line in some ``object space'' through the object space
points $\p^o \teq ( p^o_x, p^o_y, p^o_z, 1 )^T$ and
$\q^o \teq ( q^o_x, q^o_y, q^o_z, 1 )^T$.
Superscript ``o'' denotes object space, not exponentiation.
A point in object space on the line through them is
$\x^o(\alpha) \teq \p^o \tpl \alpha (\q^o \tmi \p^o)$, where $\alpha$ is a free parameter.
Transform this line into ``screen space'' using an arbitrary
$4 \tim 4$ matrix $\M$, yielding some curve.

Meanwhile, transform just the points $\p^o$ and $\q^o$ to homogeneous
screen space like so:
$\p \teq ( p_x, p_y, p_z, p_w )^T \teq \M\p^o$,
and
$\q \teq ( q_x, q_y, q_z, q_w )^T \teq \M\q^o$.
Note that these are homogeneous coordinates before division by $w$.
To find the line through them, we first do homogeneous division on each,
then interpolate:
$\y(\beta) \teq \p/p_w \tpl \beta (\q/q_w \tmi \p/p_w)$,
where $\beta$ is a free parameter.
(I'm leaving superscript ``s'' off these screen space points for simplicity).

We want to show that the ``curve'' and the latter line are everywhere
coincident.
Points on the ``curve'', in screen space,
are found by transforming the object space
point $\x^o(\alpha)$ by $\M$ and doing the homogeneous division:
$$
{ \M \x^o(\alpha) \over [\M \x^o(\alpha)]_w } =
{ \p + \alpha (\q-\p) \over \p_w + \alpha (\q_w-\p_w) }
$$
for any $\alpha$.
Points on the line, in screen space, are given by $\y(\beta)$, above.
Equate a point on the curve with a point on the line,
and solve for the function $\beta(\alpha)$.
Note that the parameterization is nonuniform; $\beta(\alpha)$ is nonlinear.
Write out your derivation neatly, explaining your steps.
If there's always such a $\beta$, then the curve is a line.


\newpage
\prob{2.}{20 pts.}
You are hardware designer for the new Nintendo {\it Z Boy} game 
machine.
You need to figure out how many bits of z to use in the z-buffer.
Fewer bits mean a cheaper machine.
The game programmers want
to set the near and far clipping planes at depths of 1mm
and 10 meters, in world space, and they want 1cm 
depth resolution, or better, throughout.
This means that no two points whose world space depths differ by
more than this amount should round to the same integer screen
space z value.
You suspect the programmers don't understand z-buffers very well,
the way they're planning to set the near clipping plane so close.

The transformations from world space to screen space that you'll use
are given by the Scene commands\footnote{
The commands ``\verb|zrange| $n$ $f$''
followed by \verb|persp|,
map $z \teq n$ to $z \teq -1$ and $z \teq f$ to $z \teq 1$.
Typically, objects before the near or beyond the far clipping planes are
clipped away.
}:
\begin{quote}
    \verb|screensize| $\S a\S b\S d$\\
    \verb|zrange| $\S n\S f$\\
    \verb|persp 90| $\S a/b$\\
\end{quote}
By referring to the \verb|scene.c| source file, write out the formula to
transform a world space point $(x,y,z)$ to screen space, yielding
$(x_s,y_s,z_s)$.
(Rather than use $(x_w,y_w,z_w)$ to denote world space, I suggest
this simpler notation for this problem.)
Your formula for screen space coordinates will have the form:
$$
\rmatrix{x_s \cr y_s \cr z_s}
= \homodiv\Bigl(\M \rmatrix{x \cr y \cr z \cr 1}\Bigr)
$$
where $\M$ is a product of three $4 \tim 4$ matrices corresponding to the
three transformation commands above, and
``homodiv'' does homogeneous division:
$$
\homodiv\Bigl(\rmatrix{x \cr y \cr z \cr w}\Bigr) = \
\rmatrix{x/w \cr y/w \cr z/w}
$$

\noindent\ba
How does $z$ transform?
Find the formula for $z_s(z)$, that is, screen space depth as a function
of world space depth.
It will have parameters $d$, $n$, and $f$.
Simplify it as much as possible.
The final formula should not involve matrix algebra.
Check that $z_s(n) \teq -d/2$ and $z_s(f) \teq d/2$.

\noindent\bb
Define the {\it z-buffer resolution} to be the change in world space depth
corresponding to a unit change in screen space depth.
Since $z_s$ is a nonlinear function of $z$, the z-buffer resolution
is not constant, but a function of depth.
What is the z-buffer resolution at the near and far clipping planes?
That is, what is the slope of the inverse function $z(z_s)$
at $z_s \teq -d/2$ and $z_s \teq d/2$?

\noindent\bc
Is 16 bits enough to meet the programmers' request?
For 16 bits, $d \teq 65536$, and $z_s$ values lie in the range
[-32768,32768).
When $n \teq .001$ and $f \teq 10$, what is the z-buffer resolution at the far
clipping plane?

\noindent\bd
Would moving the near clipping plane solve the problem?
What's the smallest value of $n$ that would give you 1cm z-buffer
resolution, without changing $f$ or $d$?

\noindent\be
Plot the curves for \bc and \bd.

Tip: \verb|gnuplot| is an easy-to-use plotting program.
Type the following to get a demo of what it can do:
{\small
\begin{verbatim}
    <setenv DISPLAY appropriately>
    gnuplot
    set xlabel "x axis"
    set ylabel "y axis"
    f1(z) = sin(z)
    f2(z) = cos(z)+cos(3*z)
    plot [z=-pi:pi] [-2.5:2.5] f1(z) title "f1", f2(z) title "f2"
\end{verbatim}
}
I couldn't find full documentation on \verb|gnuplot| on Andrew,
but there is some at\\
\verb|http://arachnid.cs.cf.ac.uk/Latex/Gnuplot/index.html| .
For hardcopy plots, try \verb|gnuplot|'s ``\verb|terminal|'' command.

\noindent\bF
With $n \teq .001$,
how many bits in your z-buffer would be needed to get 1cm z-buffer resolution?

\end{document}
