% $Header: /cvsroot/latex-beamer/latex-beamer/solutions/generic-talks/generic-ornate-15min-45min.en.tex,v 1.5 2007/01/28 20:48:23 tantau Exp $

\documentclass{beamer}

% This file is a solution template for:

% - Giving a talk on some subject.
% - The talk is between 15min and 45min long.
% - Style is ornate.

\providecommand{\R}{\mathbb{R}}

% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 


\mode<presentation>
{
  \usetheme{Warsaw}
  % or ...

  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[english]{babel}
% or whatever

\usepackage[latin1]{inputenc}
% or whatever

\usepackage{times}
\usepackage[T1]{fontenc}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.


\title{Normal Mapping in Video Games}

\subtitle
{Math, and Physics and Computer Science! Oh My! } % (optional)

\author{David Dynerman}

\institute
{
  Department of Mathematics\\
  University of Wisconsin
}

\date{Math Night - October 2008}

\subject{Talks}
% This is only inserted into the PDF information catalog. Can be left
% out. 



% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}




% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}


% Since this a solution template for a generic talk, very little can
% be said about how it should be structured. However, the talk length
% of between 15min and 45min and the theme suggest that you stick to
% the following rules:  

% - Exactly two or three sections (other than the summary).
% - At *most* three subsections per section.
% - Talk about 30s to 2min per frame. So there should be between about
%   15 and 30 frames, all told.

\section{Vectors}

\begin{frame}{Vectors - Motivation}
  \begin{itemize}
  \item Many physical quantities are described by numbers
    \pause
    \begin{itemize}
      \item Speed, temperature, money
    \end{itemize}
    \pause
  \item ...but sometimes we really want more than just a number
    \pause
    \begin{itemize}
      \item Speed and heading of a plane, income and how fast it's changing
    \end{itemize}
  \pause
  \item Vectors are objects that represent BOTH a number and a
    direction
  \pause
  \item To keep things straight: \emph{scalar} and \emph{vector} values
  \end{itemize}
\end{frame}

%% \begin{frame}{Vectors - Examples}

%%   You can create overlays\dots
%%   \begin{itemize}
%%   \item using the \texttt{pause} command:
%%     \begin{itemize}
%%     \item
%%       First item.
%%       \pause
%%     \item    
%%       Second item.
%%     \end{itemize}
%%   \item
%%     using overlay specifications:
%%     \begin{itemize}
%%     \item<3->
%%       First item.
%%     \item<4->
%%       Second item.
%%     \end{itemize}
%%   \item
%%     using the general \texttt{uncover} command:
%%     \begin{itemize}
%%       \uncover<5->{\item
%%         First item.}
%%       \uncover<6->{\item
%%         Second item.}
%%     \end{itemize}
%%   \end{itemize}
%% \end{frame}

\begin{frame}{Vectors - Examples}
\begin{itemize}
\item Direction and distance on a map
\pause
\item Airplane bearing and speed
\pause
\item Board Picture
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Representation}
\begin{itemize}
\item How might we represent direction and distance in 2D?
\pause
\begin{itemize}
\item polar coordinates
\end{itemize}
\pause
\item ...or just the familiar plane: $\R^2$
\pause
\item Points and vectors can be interchanged
\pause
\item $\langle x, y \rangle$ - $\R^2$
\pause
\item $\langle x, y, z \rangle$ - $\R^3$
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Spaces}
\begin{itemize}
\item Consider the set of all vectors with 3 components, each a real
  number
\begin{itemize}
\item $\langle 4, 3, 7 \rangle$, $\langle -4, -5, 1 \rangle$.
\end{itemize}
\pause
\item Another familiar space: $\R^3$
\item $\R^3$ Board Picture
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Space Arithmetic}
\begin{itemize}
\item Like scalars, vector spaces have \emph{operations}
\pause
\item Addition; performed component-wise
\begin{itemize}
\item $\langle 1, 5 \rangle + \langle -4, 3 \rangle = \langle -3, 8 \rangle$
\end{itemize}
\pause
\item Intuition: Stacking arrows end to end
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Space Arithmetic}
\begin{itemize}
\item Multiplication by scalars
\begin{itemize}
\item $6(\langle 4, 3 \rangle) = \langle 24, 18 \rangle$
\end{itemize}
\pause
\item Intuition: Stretching/shrinking
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Space Arithmetic}
\begin{itemize}
\item What about subtraction?
\pause
\begin{itemize}
\item Use addition \& scalar multiplication
\end{itemize}
\pause
\item What about dividing by scalars?
\pause
\begin{itemize}
\item Use scalar multiplication
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Space Arithmetic}
\begin{itemize}
\item If we think of vectors as arrows...
\pause
\item ...knowing the length of the arrow is useful
\pause
\item In 2D, length: $||v|| = \sqrt{x^2 + y^2}$
\pause
\item What is this formula?
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Space Arithmetic}
\begin{itemize}
\item Our operations:
\pause
\begin{itemize}
\item $v_1 + v_2$
\pause
\item $r v_1$
\pause
\item $||v_1||$
\end{itemize}
\pause
\item What are we missing?
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Products}
\begin{itemize}
\item Dot (Scalar) Product
\pause
\begin{itemize}
\item Takes 2 vectors, gives a {\bf scalar}
\pause
\item In 2D: $\langle a, b \rangle \cdot \langle c, d \rangle = ac +
  bd$
\pause
\item $v_1 \cdot v_2 = ||v_1||||v_2||\cos \theta$
\end{itemize}
\pause
\item Intuition: $v_1 \cdot v_2$ measures how $v_1$ \emph{projects}
  onto $v_2$
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Vector Products}
\begin{itemize}
\item Cross (Vector) Product
\pause
\begin{itemize}
\item Takes 2 3D vectors, gives a 3D {\bf vector}
\pause
\item $\langle a, b, c \rangle \times \langle d, e, f \rangle =
  \langle (bf - ce), (cd - af), (ae - bd) \rangle$
\pause
\item $v_1 \times v_2 = ||v_1||||v_2||\sin \theta \textnormal{ \bf \^n}$
\end{itemize}
\pause
\item Intuition: $v_1 \times v_2$ gives you a vector perpendicular to
  the first two
\end{itemize}
\end{frame}

\begin{frame}{Vectors - Audience Participation}
\begin{itemize}
\item Warmup:
\begin{itemize}
\item What is the difference between a \emph{vector} and a \emph{scalar}?
\end{itemize}
\pause
\item $\langle 7, 4 \rangle + \langle -5, 10 \rangle = $
\pause
\item $\langle \frac{1}{4}, \pi \rangle + \langle 0, 5 \rangle = $
\pause
\item $4(\langle 7, 3 \rangle) = $
\pause
\item $\frac{1}{6}(\langle 36, -12 \rangle) = $
\pause
\item $\langle 4, 2 \rangle + -1(\langle 4, 2 \rangle) = $
\pause
\item $||\langle 3, 4 \rangle|| = $
\pause
\item $\langle 2, 5 \rangle \cdot \langle 3, 4 \rangle = $
\pause
\item $\langle 3, 4, 0 \rangle \times \langle -2, 3, 0 \rangle = $
\end{itemize}
\end{frame}

\section{Lighting}

\begin{frame}{Lighting - Introduction}
\begin{itemize}
\item Proper lighting is the key to creating a meaningful picture
\pause
\item Lighting hints at depth, perspective...
\begin{itemize}
\item ...allows our imagination to fill in the rest
\end{itemize}
\end{itemize}
\pause Compare:
\begin{center}
\begin{columns}[c]
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{cornell_unlit.jpg}}
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{cornell_lit.jpg}}
\end{columns}
\end{center}

\end{frame}

\begin{frame}{Lighting - Introduction}
\begin{itemize}
\item Lighting need not be realistic 
\pause
\begin{itemize}
\item Artists have been experimenting with lighting for a long time...
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Lighting - Examples}
\begin{center}
\begin{columns}[c]
\column{2.0in}
\framebox{\includegraphics[width=2.0in]{vermeer.jpg}}
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{disney.jpg}}
\end{columns}
\end{center}
\end{frame}

\begin{frame}{Lighting - Examples}
\begin{columns}[c]
\column{2.25in}
\framebox{\includegraphics[width=2.25in]{zelda.jpg}}
\column{2.25in}
\framebox{\includegraphics[width=2.25in]{gears_of_war.jpg}}
\end{columns}
\end{frame}


\begin{frame}{Lighting - Lighting Models}
\begin{itemize}
\item Pictures rendered by a computer need lighting too...
\pause
\item Lighting models: methods of computing how light interacts with
  your picture
\pause
\item Most lighting models \emph{shade} surfaces
\begin{itemize}
\pause
\item We see photons, not surfaces, but the effect is the same
\end{itemize}
\pause
\item In general, lighting can be very complicated
\begin{itemize}
\item Photons interact with surfaces; Quantum Mechanics
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Lighting - Lighting Models}
\begin{itemize}
\item The Cadillac of lighting models is based on \emph{bidirectional
  reflectance distribution functions}
\begin{itemize}
\pause
\item This function defines how photons reflect off a particular
  surface
\begin{itemize}
\item marble, skin, hair, water, etc
\end{itemize}
\end{itemize}
\pause
\item $L(x, \theta_0, \phi_0 ) = L_e( x, \theta_0, \phi_0 ) +
  \int_{\Omega} \rho_{bd}(x, \theta_0, \phi_0, \theta, \phi )L_i(x,
  \theta, \phi ) \cos \theta d\omega$
\pause
\item This is \emph{currently} too complicated to use in real-time
  applications
\end{itemize}
\end{frame}

\begin{frame}{Lighting - Lighting Models}
\begin{itemize}
\item Simpler models use clever ways to approximate $L$
\pause
\item One simple model can't do it all...
\begin{itemize}
\pause
\item \emph{Diffuse lighting} - light is reflected in all directions
\pause
\item \emph{Specular lighting} - mirror-like reflection of light along
  a particular direction
\pause
\item \emph{Ambient lighting} - base-level light added uniformly everywhere
\end{itemize}
\pause
\item We use separate simple models, then combine results in the final result
\end{itemize}
\end{frame}

\begin{frame}{Lighting - Lighting Models}
\begin{center}
\includegraphics[width=4in]{ambient_diffuse_specular_final.jpg}
\end{center}
\end{frame}

\begin{frame}{Lighting - Lighting Models}
\begin{itemize}
\item \emph{Lambertian} lighting - diffuse lighting model
\pause
\item $L = N \cdot L_i$, where $L$ is the final shading, $N$
  is the normal at a point, and $L_i$ is the incoming light
\pause
\item What does this equation do?
\pause
\item Scales the shading based on the angle the light hits the surface
\pause
\item Board Picture
\end{itemize}
\end{frame}

\begin{frame}{Lighting - Audience Participation}
\begin{itemize}
\item Warmup - How is diffuse lighting characterized?
\pause
\item Diffuse is one type of lighting, what's another? How is it
  characterized?
\pause
\item How does the quantity $N \cdot L_i$ change as $L_i$ changes?
\end{itemize}
\end{frame}

\section{Normal Mapping}

\begin{frame}{Normal Mapping - Introduction}
\begin{itemize}
\item We've talked about vectors and lighting models...
\pause
\item now we want to apply them to make neat pictures
\pause
\item e.g. a video game
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping - Basics}
\begin{itemize}
\item The world you \emph{see} in a video game is really just a
  collection of 3D objects
\begin{itemize}
\item rooms, tables, chairs, enemies
\end{itemize}
\pause
\item 3D objects live in a \emph{vector space} and are
  themselves collections of triangles called \emph{meshes}
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping - Mesh Examples}
\begin{center}
\begin{columns}[c]
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{mesh_1.jpg}}
\column{1.5in}
\framebox{\includegraphics[width=1.75in]{mesh_2.jpg}}
\end{columns}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping - Textures}
\begin{itemize}
\item Having a mesh isn't enough...
\pause
\begin{itemize}
\item Unless we're in the \emph{Tron} universe 
\end{itemize}
\pause
\item We need to \emph{paint} surface detail onto the mesh
\pause
\item Texture mapping efficiently adds surface detail to a mesh by
  painting a picture (\emph{texture}) onto the triangles of a mesh
\pause
\item Example: instead of modeling each brick in a wall, use a few
  large triangles for the \emph{entire} wall and apply a texture
\end{itemize}
\begin{center}
\pause
\includegraphics[width=1.25in]{brick_texture.jpg}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping - Diffuse Lighting}
\begin{itemize}
\item Recall: What information do we need for Lambertian diffuse
  lighting?
\pause
\item Normals! Many other lighting models depend on this too...
\pause
\item We can easily compute normals at each vertex of the mesh:
\pause
\begin{itemize}
\item Audience Participation: How? Think vector operations...
\end{itemize}
\pause
\item Board Picture
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping}
\begin{itemize}
\item Notice that we have normals at each vertex...
\pause
\item ...but we need normals inside each triangle too
\begin{itemize}
\item Since we want to light the insides of the triangles too
\end{itemize}
\pause
\item How can we get inside normals?
\begin{itemize}
\item Board picture
\end{itemize}
\pause
\item The traditional method: interpolate normals across the surface
\end{itemize}
\begin{center}
\includegraphics[width=3.25in]{normal_interpolation.jpg}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping}
\begin{itemize}
\item Normal mapping provides an alternative way of getting normals
  inside mesh triangles
\pause
\item Much like texture mapping ``fills in'' surface detail across
  each triangle...
\pause 
\item ...normal mapping fills in \emph{normal detail} across each
  triangle
\pause
\item We can then use these normals to light the inside of our triangle
\pause
\item Board Picture
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping}
\begin{itemize}
\item So what's the point?
\pause
\item Normal interpolation is often a poor approximation for surface
  detail...
\pause
\item ...and more surface detail requires more triangles, which can be
  slow
\pause
\item By having more accurate normal information inside a triangle, we
  can change the way light interacts, giving the \emph{appearance} of
  geometric detail that isn't actually there
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping - An Orange}
\begin{columns}[c]
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{no_normal_map.png}}
\column{1.5in}
\framebox{\includegraphics[width=1.5in]{normal_map_orange.png}}
\end{columns}
\begin{center}No additional geometry!\end{center}
\end{frame}

\begin{frame}{Normal Mapping - A Face}
\begin{center}
\includegraphics[width=2.5in]{normal_mapping_1.jpg}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping}
\begin{itemize}
\item OK - we want normal maps for more lighting information...
\pause
\item ...but how do we make normal maps?
\pause
\item 1) By hand: Your artists will hate you
\pause
\item 2) Automatically: take a higher-polygon version of a mesh, and
  use the extra polygons to generate normal maps that will be applied
  to a low-polygon version
\end{itemize}
\end{frame}

\begin{frame}{Normal Mapping - Procedural Examples}
\begin{center}
\includegraphics[width=4in]{normal_map_comparison.png}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping - Examples}
\begin{center}
\includegraphics[width=3.25in]{quake4_normal.jpg}
\end{center}
\end{frame}

\begin{frame}{Normal Mapping - Audience Participation}
\begin{itemize}
\item Board Picture - What are some ways you could get interior
  normals for this triangle?
\end{itemize}
\end{frame}

\begin{frame}{Summary}
  \begin{itemize}
  \item Vectors
    \begin{itemize}
      \item
        How to add them, multiply them by scalars, take dot products
    \end{itemize}
    \pause
   \item Lighting
\begin{itemize}
\item What a lighting model is, the importance of $N \cdot L_i$
\end{itemize}
\pause
\item Normal Mapping
\begin{itemize}
\item A neat technique for sneaking in more \emph{lighting} information
  (e.g. \emph{normal vectors}) over a lower quality mesh.
\end{itemize}
\pause
\item Science involved:
\begin{itemize}
\item CS: texture and normal mapping, run-time performance
\item Physics: Lighting models
\item Math: Vector spaces
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{References}
\begin{itemize}
\item Images sources - All images Copyright to their respective authors
\begin{itemize}
\item \url{http://graphics.ucsd.edu/~henrik/images/cbox.html}
\item \url{http://www.productdesignforums.com/index.php?showtopic=8970}
\item \url{http://www.naturewizard.com/tutorial0107.html}
\item \url{http://www.amoeblog.com/}
\item \url{http://www.nintendo.com/}
\item \url{http://www.disney.com/}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{References}
\begin{itemize}
\item Images sources - All images Copyright to their respective
  authors
\begin{itemize}
\item \url{http://www.epicgames.com/}
\item
  \url{http://www.codesampler.com/d3dbook/chapter_05/chapter_05.htm}
\item \url{http://www.cakovan.com/}
\item \url{http://escience.anu.edu.au/lecture/cg/TextureJ3D/printNotes.en.html}
\item
  \url{http://www.computerarts.co.uk/tutorials/3d__and__animation/normal_mapping}
\item \url{http://www.wikipedia.org}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{References}
\begin{itemize}
\item Bibliographical sources
\begin{itemize}
\item Dr. Stephen Chenney's CS779 lecture notes
\item Wikipedia articles on: Lambertian Lighting and Phong Shading
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Acknowledgements}
I'd like to thank:
\begin{itemize}
\item Cynthia Chin
\item Michael Childers, Daniela Banu
\item Djordje Cakovan and Stephen Chenney
\end{itemize}
Questions?
\end{frame}

\end{document}