    %This is a Latex format I have borrowed from a high school mathematics teacher, Dr. Noah Prince. 
%I like this format for mathematical discussion and exposition. Especially because it has a large workable area per page.
\documentclass[12pt]{article}

    \usepackage{fancyhdr,ifthen,amssymb,amsfonts,amsmath,color,graphicx,subfig,url,varwidth, cite}
    \pagestyle{fancy}

    \setlength{\oddsidemargin}{0in}
    \setlength{\evensidemargin}{0in}
    \setlength{\textwidth}{6.5in}
    \setlength{\headwidth}{\textwidth}
    \setlength{\topmargin}{-.5in}
    \setlength{\textheight}{9in}

    %--- cut here ----------------------------------------------------------------
%
%- Picture drawing commands - written by P.N. Balister ---- do not alter! ----
%
\newdimen\unit\newdimen\psep\newcount\nd\newcount\ndx\newbox\dotb\newbox\ptbox
\newdimen\dx\newdimen\dy\newdimen\dxx\newdimen\dyy\newdimen\hgt
\newdimen\xoff\newdimen\yoff
\newcommand\clap[1]{\hbox to 0pt{\hss{#1}\hss}}
\newcommand\vdisk[1]{{\font\dotf=cmr10 scaled #1\dotf.}}
\newcommand\varline[2]{\setbox\dotb\hbox{\vdisk{#1}}\xoff=-.5\wd\dotb
\wd\dotb=0pt\yoff=-.5\ht\dotb\psep=#2\ht\dotb}
\newcommand\varpt[1]{\setbox\ptbox\clap{\vdisk{#1}}\setbox\ptbox
\hbox{\raise-.5\ht\ptbox\box\ptbox}}
\newcommand\cpt{\copy\ptbox}
\newcommand\point[3]{\rlap{\kern#1\unit\raise#2\unit\hbox{#3}}}
\newcommand\setnd[4]{\dx=#3\unit\advance\dx-#1\unit\divide\dx by\psep
\dy=#4\unit\advance\dy-#2\unit\divide\dy by\psep \multiply\dx
by\dx\multiply\dy by\dy\advance\dx\dy\nd=1\advance\dx-1sp
\loop\ifnum\dx>0\advance\dx-\nd sp\advance\nd1\advance\dx-\nd
sp\repeat}
\newcommand\dl[4]{{\setnd{#1}{#2}{#3}{#4}\dline{#1}{#2}{#3}{#4}\nd}}
\newcommand\dline[5]{{\nd=#5\hgt=#2\unit\dx=#3\unit\advance\dx-#1\unit
\divide\dx by\nd\dy=#4\unit\advance\dy-#2\unit\divide\dy by\nd
\advance\hgt\yoff\rlap{\kern#1\unit\kern\xoff\loop\ifnum\nd>1\advance\nd-1
\advance\hgt\dy\kern\dx\raise\hgt\copy\dotb\repeat}}}
\newcommand\ellipse[4]{\qellip{#1}{#2}{#3}{#4}\qellip{#1}{#2}{#3}{-#4}%
\qellip{#1}{#2}{-#3}{#4}\qellip{#1}{#2}{-#3}{-#4}}
\newcommand\qellip[4]{{\setnd{0}{0}{#3}{#4}\dx=\unit\dy=0pt\raise\yoff\rlap{%
\kern#1\unit\kern\xoff\raise#2\unit\hbox{\loop\ifnum\dx>0\rlap{\kern#3\dx
\raise#4\dy\copy\dotb}\hgt=\dx\divide\hgt
by\nd\advance\dy\hgt\hgt=\dy \divide\hgt
by\nd\advance\dx-\hgt\repeat\rlap{\raise#4\dy\copy\dotb}}}}}
\newcommand\bez[6]{{\setnd{#1}{#2}{#3}{#4}\ndx=\nd\setnd{#3}{#4}{#5}{#6}
\ifnum\ndx>\nd\nd=\ndx\fi\dx=#3\unit\advance\dx-#1\unit\dy=#4\unit
\advance\dy-#2\unit\dxx=#5\unit\advance\dxx-#1\unit\dyy=#6\unit\advance
\dyy-#2\unit\advance\dxx-2\dx\advance\dyy-2\dy\divide\dxx
by\nd\divide\dyy by\nd\advance\dx.25\dxx\advance\dy.25\dyy\divide\dx
by\nd\divide\dy by\nd \multiply\nd
by2\dx=100\dx\dy=100\dy\dxx=100\dxx\dyy=100\dyy\divide\dxx by\nd
\divide\dyy by\nd\hgt=#2\unit\raise\yoff\rlap{\kern#1\unit\kern\xoff
\raise\hgt\copy\dotb\loop\ifnum\nd>0\advance\nd-1\advance\hgt0.01\dy
\kern0.01\dx\raise\hgt\copy\dotb\advance\dx\dxx\advance\dy\dyy\repeat}}}
% derived commands and defaults
\newcommand\ptu[3]{\point{#1}{#2}{\cpt\raise1ex\clap{$\scriptstyle{#3}$}}}
\newcommand\ptd[3]{\point{#1}{#2}{\cpt\raise-1.8ex\clap{$\scriptstyle{#3}$}}}
\newcommand\ptr[3]{\point{#1}{#2}{\cpt\raise-.4ex\rlap{$\ \scriptstyle{#3}$}}}
\newcommand\ptl[3]{\point{#1}{#2}{\cpt\raise-.4ex\llap{$\scriptstyle{#3}\ $}}}
\newcommand\ptlu[3]{\point{#1}{#2}{\raise.8ex\clap{$\scriptstyle{#3}$}}}
\newcommand\ptld[3]{\point{#1}{#2}{\raise-1.6ex\clap{$\scriptstyle{#3}$}}}
\newcommand\ptlr[3]{\point{#1}{#2}{\raise-.4ex\rlap{$\,\scriptstyle{#3}$}}}
\newcommand\ptll[3]{\point{#1}{#2}{\raise-.4ex\llap{$\scriptstyle{#3}\,$}}}
\newcommand\pt[2]{\point{#1}{#2}{\cpt}}
\newcommand\thkline{\varline{1600}{.3}}
\newcommand\medline{\varline{800}{.5}}
\newcommand\thnline{\varline{400}{.6}}
\newcommand\dotline{\varline{1000}{4}}
\varpt{2500}\thnline\unit=2em
%
%--- end cut -----------------------------------------------------------------

    \newcounter{questionNumber}
    \setcounter{questionNumber}{1}

    \newcommand{\noi}{\noindent}
    \newcommand{\ds}{\displaystyle}

    \newcommand{\dist}{\mathrm{dist}}


    \definecolor{blue}{rgb}{0,0,1}
    \definecolor{purple}{rgb}{1,0,1}

    \newcommand{\example}[1]{\noindent\textbf{Example:}\quad #1\\[.1in]}
    \newcommand{\definition}[1]{\noindent\textbf{Definition:}\quad #1\\[.1in]}

    %\headandfoot{course}{documentName}{shortDocumentName}{courseCode}
    \newcommand{\headandfoot}[4]{\lhead{#1}\chead{#2}\rhead{\ifthenelse{\isodd{\thepage}}{Name: {\hspace{1.25in}}}{}}
    \lfoot{University of Illinois at Urbana-Champaign}\cfoot{#3.\thepage}\rfoot{#4}}

    %\question{questionText}{verticalSpacing}
    \newcommand{\question}[2]{\noi\thequestionNumber.\quad #1 \vspace{#2}\addtocounter{questionNumber}{1}}

    \lhead{Shadows of 3D Surfaces}
    \chead{}
    \rhead{Molly K. Fane}
    \lfoot{MA198 (Francis)}
    \cfoot{Page \thepage}
    \rfoot{Fall 2015}
    \title{Shadows of 3D Surfaces}
    \author{Molly K.  Fane}

\begin{document}

\maketitle
\begin{center} \includegraphics[width = 6in]{shadowParaKLEIN.png} \end{center}

\pagebreak
\tableofcontents
\pagebreak
\section{Abstract}
As an introduction into OpenGL and as an exploration into the creation of planar projection shadows, also called drop shadows, a semester-long project was undertaken with the following goal: Create a program that displays a point of light, a plane, a user-defined function, and the resulting shadow.This document outlines the process of competing project, nicknamed ``shadow,'' how the program works, and the mathematics behind drop shadows. 
\section{Final Program Details}

\subsection{Program Functionality}
\indent The final program, ShadowPara.py, uses Python 2.7 along with PyOpenGL with GLUT in order to display the shadow scene. To define the displayed parametric function, users have access to the library of functions from the python math module as well as the built-in python functions.

The program requests three functions in terms of $u$ and $v$ set equal to $x$, $y$, and $z$ to create a parametric surface. Although there are preset values, the user may change the bounds of $u$ and $v$ as well as the sampling rate of the functions in $u$ and $v$ used to create the approximate graphical representation of the parametric functions displayed. Finally, if one chooses, they may set the position of the point of light as well as the equation of the plane, however these have very functional preset values as well. 

The display includes a set of $x$, $y$, and $z$ axes colored red, green, and blue respectively. There are keyboard controls of the perspective of the display. The A, D, W, S and Q and E keys control translation and the J, L, I, K, and U and O keys control rotation. Each translates along or rotates about one of the three major axes. 

\subsection{Operation and Avoiding Errors}
The functions must be entered as strings. I cannot stress this enough. The built-in eval() python function is used to assess the values of the $x$, $y$, and $z$ at each pair of $u$ and $v$ values. In Python 2.7, the eval() function can only accept string input values, I cannot find a way around this issue even converting the input function into a string before using eval() does not work.[1] Therefore it is crucial that users enter their functions as strings, using single or double quotation marks around the input function. This problem is solved using Python3, in which the eval() function will accept a raw input that is not in string form.

Examples of interesting parametric surfaces and their bounds are given. However, one may enter any function they may choose as long it only references mathematical functions from the math module library or the python function library. Taking fractional exponents of negative numbers or dividing by zero will result in an error. 

It is better to overdraw a function's bounds. Due to the approximate nature of the graph, ‘off by one errors’ may arise if the range of $u$ is not divisible by deltaU (the change in $u$ between sample points). It is also best to ensure that the function is absolutely between the plan and the point of light, in order to ensure a logical shadow with no errors. No vector from the Light point to a point on the function may be parallel to a point on the plane, this will result in an obstruction infinite quadrilateral in the shadow, obstructing results.
Finally, be sure to use as few as possible sampling points. This means, choose a deltaU and a deltaV sufficiently large so that the computer can render the scne without crashing. The speed at which one can rotate or translate the perspective around the scene is directly related to the number of quadrilateral rendered in the scene. For fast navigation, use few sample points, i.e. large deltaV’s and large deltaU’s. The result varies depending on the specifications of the machine used to run the program.

\section{The Mathematics behind Shadows}
\subsection{Types of Light}
\indent There are two different types of light: directional light and point light. Point light has light rays that emanate from a point in space.  A lightbulb in a room is a good example of a point light source. Directional light is light that emanates from a point at infinity. The light rays that are produced are parallel.[2] A good example of directional light are the light rays from the Sun onto the Earth, because the Sun is far enough away from the Earth that the rays are approximately parallel when they hit the Earth.\\

Points at infinity come from a field of geometry called ``Projective Geometry." Unlike in the Euclidean Plane, the projective plane has the following duality:
\begin{center} \textit{Not only do two different points create a unique line, two different lines create a unique point (at their intersection).} \end{center}
Parallel lines intersect in projective space. They intersect at points at infinity. Similarly parallel planes intersect an lines at infinity in a 3D analogue to the projective plane. It can be said that projective space has more points that Euclidean space because of these points at infinity.[3]\\

\subsection{Planar Projection}
For the sake of interest in computer graphics: the discussion will be limited to only point light sources and 3D images made of sufficiently small polygons. The algorithm I used to create the drop shadows in my program is called the planar projection of shadows. The main concept of planar projection is to take each point of the polygons of the shadow-producing object and project it onto the plane from the light source.\\

\includegraphics[width=6in]{ProjPlaneMath.jpg}\\

In order to find the coordinates of $P_\pi$:\\
Find the equation of the line between the point of light and the object:

$$\vec{LP}: (x,y,z) = (\vec{P}-\vec{L})t+\vec{L}$$

Find the equation of the plane, and format it as such:
$$ \pi: \vec{n} \cdot (x,y,z) = d$$

Substitute:
$$( (\vec{P}-\vec{L})t+\vec{L}) \cdot \vec{n}= d$$

Solve for t:
$$ t = \frac{d-\vec{n} \cdot \vec{L}}{\vec{n} \cdot (\vec{P} - \vec{L})}$$

Subsitute this $t$ back into the equation of the line:

$$ P_\pi: (x,y,z) = (\vec{P}-\vec{L}) \left( \frac{d-\vec{n} \cdot \vec{L}}{\vec{n} \cdot (\vec{P} - \vec{L})} \right)+\vec{L}$$

It is important to note that there is a divide by zero error if $\vec{n}$ is perpendicular to $(\vec{P} - \vec{L})$, as there should be, because this situtaiton would create an infinite shadow. \\

In my program, I use this algorithm on each sampled vertex in order to find its shadow on the plane below. The quadrilaterals drawn in the function above, are redrawn between vertexes with the same indices as in the function above, but at their shadow points on the plane below creating the solid 2D shape of the shadow.\\

\section{How the Code works}
\subsection{Parser}
At the core of every program that graphs functions is a parser. I use the python eval() function as a parser. The default eval() function takes a string, reads the recognizes the functions called, the variables named, and integers and floating point decimal numbers named. It can then execute the commands in order to return the proper value as an output. In my program, I take advantage of the eval() function to essentially evaluate a function at many different values of $u$ and $v$. \\
\subsection{Step by Step Explanation}
The follwoing is a step by step explanation of the core functions of my program. The user inputs a function for $x$, $y$, and $z$  each in terms of $u$ and $v$ as well as the range of values for $u$ and $v$ to graph. A parsing algorithm samples the function at points deltaU and deltaV intervals apart. These samples are added to a list called vertices as the list [x,y,z,a,b] where $a$ and $b$ are index variable that count the number of points sampled past the initial point in the $u$ and $v$ directions respectively. 

Now this list of vertices must become quadrilaterals. Each quadrilateral is made up of four points indexed adjacent to each other. If $(a,b)$ are the values of the indices of the bottom left vertex of a quadrilateral,  than the top left is $(a,b+1)$, top right is $(a+1,b+1)$, and the bottom right vertex is $(a+1,b)$. A relatively inefficient algorithm (it could be made more efficient if it were affecting runtimes) finds the vertices with the correct $a$ and $b$ indices to form the quadrilateral and those four vertices are sent through glBegin(GL\_QUADS) which takes four vertices at a time and draw the quadrilateral between them.[4] During glBegin() sequence, each quad is colored according to $z$ value of the bottom left vertex. The glBegin() sequence is in the drawQuads() function which is called in the glutDisplayFunc() callback function. 

From the vertices list,  the shadow vertices list is defined following the algorithm discussed in the mathematics section, careful to avoid a divide by zero error. In order to avoid depth error, since the plane and the shadow quads will lay in the same plane, the shadow is slightly raised, meaning $t$ is reduced ever so slightly. A shadow vertex is defined for each real vertex and is placed into the shadowverts list the same way the vertices list was formed. And the shadowverts list is also sent through drawQuads() with a different shading so that shadow is dark. 

These functions are, together, the core of my project. Together, they create the function and its shadow. (Though don’t forget this is bundled along with the aid of all of the OpenGL intricacies that allow the function and it’s shadow to be displayed).


\section{Process}
The first form of the Shadow project was a 3D Surface grapher, called shadowPygame.py, that used Python 3.5 and a display module called pygame. The program requested a function of the form $z = f(x,y)$ and it returned a keyboard rotatable display of the  graph of the function’s surface  made up of traces of the surface in the direction of planes parallel to the $yz$-plane.  This program used OpenGL to create edges approximating each trace of the function as a line. This was a typical output of the program:
\\
\\
\includegraphics[width=3in]{shadowPygameEG1.png}
\\
\\
Soon, unsatisfied with simple line traces, and aspiring to create a program similar to DPGraph, I altered the program to use quadrilaterals instead of edges, each quadrilateral requiring four correctly ordered sample points in order to define a part of the surface. This program was called shadowQUAD.py, returning images that look like this:
\\
\\
\includegraphics[width =3in]{pygameQUADEG1.png}
\\
\\
I decided it was important to use software already installed on the classroom lab macs so that I may run my programs in the lab as well as on my computer. This meant I had to convert my program to run using Python 2.7. I also had to do away with pygame and instead use GLUT to display my OpenGL content. This really forced me to learn about how to set up an OpenGL GLUT scene including what functions you must call in order to initialize a window and display content using GLUT.  After a long and arduous conversion process, I had created a similar surface grapher able to run on lab macs called shadowQuadGLUT.py

Finally I was ready to create some shadows. I created a quadrilateral to represent a plane and a yellow asterisk to represent a point of light. Having previously worked out the algorithm with which one may create a drop shadow, I translated this algorithm to python code, translating each vertex on the surfaces to a vertex lying on the plane. This was the first program to achieve the core goal of the project. It is called shadow2.py in the repository.
Here is a picture of what the first drop shadow program creates:
\\
\\
\includegraphics[width = 3in]{shadow2EG1.png}
\\
\\
Shadow2 has one flaw. It will only accept  functions in terms of only $x$ and $y$ and set equal to $z$. While I tried new functions, I discovered this to be increasingly limiting in what was possible to display. I decided that, in order to add versatility to the grapher portion of the project, I created a version of shadow2 with a parametric grapher. This was the final program created for this project. It is called shadowPara.py. The great thing about the parametric grapher is that it can graph parametric surfaces using $u$ and $v$ as well as functions set up as $z = f(x,y)$, simply by setting $x = u$ , $y = v$ and $z = f(u,v)$.  Here are some of the functions and theirs shadows I have graphed using shadowPara.py:\\
\\
\includegraphics[width = 3in]{shadowParaTOR.png}\\
\includegraphics[width = 4.5in]{shadowParaMONK.png}\\
\\
\includegraphics[width = 4.5in]{shadowParaKLEIN.png}\\
\\
This is a Klein Bottle, one of the many suggested surfaces available in the intructions. [5]
\newpage
\section{Bibliography}
\begin{enumerate}
\item		Python.org.{\it Built-in Functions}. (n.d.). Retrieved December 16, 2015, from https://docs.python.org/2/library/functions.html
\item		Ute Rosenbaum, A. (1998). The Axioms of Projective Geometry. {\it In Projective Geometry: From Foundations to Applications}  (p. 8). Cambridge: Cambridge University Press. 
\item		Birn, Jeremy. (2006) {\it Digital lighting and rendering Berkeley}, CA : New Riders.\\
\item		OpenGL.org.{\it GlBegin.} (n.d.). Retrieved December 16, 2015, from https://www.opengl.org/sdk/docs/man2/xhtml/glBegin.xml.\\
\item		Karcher, Hermann.(2004).{\it Klein Bottle},virtualmathmuseaum.org, from virtualmathmuseum.org/Surface/klein\_bottle/klein\_bottle.html.
\end{enumerate}
\end{document}