\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
%\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{pstricks}
\usepackage{listings}
%\usepackage{ngerman}

\title{\textsc{Computer Graphics I \\ \large Assignment 11 \\ \small Group III (Yavor Kaloyanov)}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \footnotesize 2031259} \and \shortstack[c]{Pascal Gwosdek\\ \footnotesize 2505221}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 11}
\chead{}
\rhead{Dithmar (2031259), Gwosdek (2505221)}
\lfoot{Computer Graphics 1}
\cfoot{Page \thepage}
\rfoot{WS 2006/2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{11}

\exercise{Extended Bresenham}
Line from $(x_0,y_0)$ to $(x_1,y_1)$ with slope in $]0,1[$ (slope at $0$ or $1$ is trivial). \\
Here is some pseudo-code:
\lstset{language=c++}
\begin{lstlisting}
a = y1 - y0;
b = x1 - x0;

x = x0;
y = y0;
d = 2a - b;

while (2x <= x0 + x1)
{
	setpixel(x, y);
	setpixel(x1 - x + x0, y1 - y + y0);
	if (d <= 0)
		d += 2a;
	else
	{
		d += 2a - 2b;
		y++;
	}
	x++;
}
\end{lstlisting}
\begin{figure}[h]
\centering
\begin{pspicture}(-0.5,-0.5)(5,1.5)
\psframe[fillcolor=red,  fillstyle=solid](0.0,0.0)(0.5,0.5)
\psframe[fillcolor=green,fillstyle=solid](0.5,0.0)(1.0,0.5)
\psframe[fillcolor=gray, fillstyle=solid](1.0,0.0)(1.5,0.5)
\psframe[fillcolor=gray, fillstyle=solid](1.5,0.5)(2.0,1.0)
\psframe[fillcolor=gray, fillstyle=solid](2.0,0.5)(2.5,1.0)
\psframe[fillcolor=gray, fillstyle=solid](2.5,0.5)(3.0,1.0)
\psframe[fillcolor=gray, fillstyle=solid](3.0,0.5)(3.5,1.0)
\psframe[fillcolor=gray, fillstyle=solid](3.5,1.0)(4.0,1.5)
\psframe[fillcolor=green,fillstyle=solid](4.0,1.0)(4.5,1.5)
\psframe[fillcolor=red,  fillstyle=solid](4.5,1.0)(5.0,1.5)

\rput(0.25,-0.25){0}
\rput(0.75,-0.25){1}
\rput(1.25,-0.25){2}
\rput(1.75,-0.25){3}
\rput(2.25,-0.25){4}
\rput(2.75,-0.25){5}
\rput(3.25,-0.25){6}
\rput(3.75,-0.25){7}
\rput(4.25,-0.25){8}
\rput(4.75,-0.25){9}

\rput(-0.25,0.25){0}
\rput(-0.25,0.75){1}
\rput(-0.25,1.25){2}
\end{pspicture}
\caption{Sample visualisation of the Bresenham algorithm for lines, here shown from (0,0) to (9,2). The line is being constructed in a 'mirrored' manner.}
\end{figure}

\newpage
\exercise{Bresenham for Parabola}
Here is some pseudo-code:
\begin{lstlisting}
x = 0;
y = 2;
d = -0.5 / 1.2;

while (x != b)
{
	setpixel(x, y);
	if (d <= 0)
		d += 1/6 * x + 1/12;
	else
	{
		d += 1/6 * x + 1/12 - 1;
		y++;
	}
	x++;
}
\end{lstlisting}
\begin{figure}[h]
\centering
\begin{pspicture}(-0.5,-0.5)(3.5,2.0)
\psframe[fillcolor=gray, fillstyle=solid](0.0,0.0)(0.5,0.5)
\psframe[fillcolor=gray, fillstyle=solid](0.5,0.0)(1.0,0.5)
\psframe[fillcolor=gray, fillstyle=solid](1.0,0.0)(1.5,0.5)
\psframe[fillcolor=gray, fillstyle=solid](1.5,0.5)(2.0,1.0)
\psframe[fillcolor=gray, fillstyle=solid](2.0,0.5)(2.5,1.0)
\psframe[fillcolor=gray, fillstyle=solid](2.5,1.0)(3.0,1.5)
\psframe[fillcolor=gray, fillstyle=solid](3.0,1.5)(3.5,2.0)

\rput(0.25,-0.25){0}
\rput(0.75,-0.25){1}
\rput(1.25,-0.25){2}
\rput(1.75,-0.25){3}
\rput(2.25,-0.25){4}
\rput(2.75,-0.25){5}
\rput(3.25,-0.25){6}

\rput(-0.25,0.25){2}
\rput(-0.25,0.75){3}
\rput(-0.25,1.25){4}
\rput(-0.25,1.75){5}
\end{pspicture}
\caption{Visualisation of the Bresenham algorithm for the parabula from (0,2) to (6,5).}
\end{figure}

\end{document}
