\documentclass[a4paper, 11pt]{article}

\usepackage[latin1]{inputenc}
\usepackage{amssymb , amsmath}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{algorithm}
\usepackage{algorithmic}

\title{Rendering SS2011, Andrea Weidlich}
\author{Onur Dogangönül}

\begin{document}

\maketitle

\tableofcontents

\part{Rendering Theory}
\section{Rendering Equation}
\subsection{Surface Area Formalism}
	\begin{itemize}
	\item 1986 Kajia version of RE (Fredholm Integro-differential equation) $$I(x,x') = g(x,x')  [ \epsilon(x,x') + \int_S\rho(x,x',x'') I(x',x'') dx'' ]$$
	\item $I(x,x')$: Amount of light from x' to x
	\item $g(x,x')$
		\begin{itemize}
		\item Geometric term desribes setting between x' and x
		\item Usually light energy reduced by $\frac{1}{r^2}$
		\item Is zero, if an object lies between these points
		\end{itemize}
	\item $\epsilon(x,x')$: Direct light energy, if $x'$ emitter
	\item $\rho(x,x',x'')$: Indirect light, which is recived from $x''$ via $x'$ (BRDF etc.)
	\item $\int_S$: Must be evaluated over all surfaces in the scene
	\item Completely describes problem of image synthesis
	\end{itemize}

\subsection{Directional Formalism}
	\begin{itemize}
	\item Alternative RE geometry $$L(\vec{x}, \omega) = L^e(\vec{x},\omega) + \int_{\Omega} L(h(\vec{x}, -\omega'),\omega') \cdot f_r(\omega',\vec{x}, \omega) \cdot \cos{\theta} \mathrm{d} \omega'$$
	\item $L(\vec{x}, \omega)$  
		\begin{itemize}
		\item Describes amount of light on pos x in direction $\omega$
		\item Correlates to $I(x,x')$
		\end{itemize}
	\item $h(\vec{x}, -\omega')$: Correlates to $g(x,x')$.
	\item $L^e(\vec{x},\omega)$
		\begin{itemize}
		\item Direct light emitted from x in $\omega$ direction
		\item Correlates to $\epsilon(x,x')$
		\end{itemize} 
	\item $f_r(\omega',\vec{x}, \omega)$: Correlates to $\rho(x,x',x'')$.
	\item $\int_{\Omega}$: Evaluated over whole hemisphere.
	\item Emission term is outside of sintegral
	\end{itemize}

\subsection{Short Form}
	\begin{itemize}
	\item Given the directional formalism, integral operator T introduces $$TL(\vec{x}, \omega) =  \int_{\Omega} L(h(\vec{x}, -\omega'),\omega') \cdot f_r(\omega',\vec{x}, \omega) \cdot \cos{\theta} \mathrm{d} \omega'$$
	\item Short: $L = L^e + TL$
	\item Analytical solutions are usually impossible
	\item Contractivity of the integral operator T or adjunct operator T'
		\begin{itemize}
		\item In physically plausible environments, operators T and T' are contractive since surface reflectances are $< 1$
		\item Successive application yields smaller results
		\item Highly specular surfaces less contractive than diffuse environments (i.e. iterative algorithms take longer to converge)
		\end{itemize}
	\end{itemize}

\section{Potential Equation}
	\begin{itemize}
	\item From viewpoint of emitter $$(T'W)(\vec{y},\omega')=\int_{\Omega} W(h(\vec{y},\omega'), \omega') \cdot f_r(\omega', h(\vec{y},\omega'),\omega) \cdot \cos \theta \mathrm{d} \omega$$
	\item T' is the adjoint operator of T from RE
	\item Short: $W = W^e + T'W$
	\end{itemize}

\subsection{RE, PE Symmetry and Difference}
	\begin{itemize}
	\item Symmetry
		\begin{itemize}
		\item RE: From viewpoint of the receiver
		\item PE: From viewpoint of the emitter
		\item Both equations of similar tpye and approached in similar ways
		\item PE suites better for certain methods
		\end{itemize}
	\item Differences
		\begin{itemize}
		\item RE: Radiance values for viewing ray (immediately useful for rendering)
		\item PE: Radiance state of entire scene, results are stored and evaluated later
		\end{itemize}
	\end{itemize}

\section{Global Illumination Solution Strategies}
	\begin{itemize}
	\item Solution Technique Classification
		\begin{itemize}
		\item Local illuminations models
			\begin{itemize}
			\item Coupling ignored
			\item No recursion
			\end{itemize} 
		\item Recursive ray-tracing
			\begin{itemize}
			\item Easy couplings are followed
			\item Specular and transmission
			\end{itemize}  
		\item Global illumination methods: Full treatment of RE coupling
		\end{itemize}
	\item GI solutions
		\begin{itemize}
		\item Inversion: Not used in practice, forget it
		\item Expansion: Mostly stochastic techniques (ray tracers are exception)
		\item Iteration: Both stochastic and deterministic (finite element) approaches
		\end{itemize}
	\end{itemize}

\subsection{Inversion}
	\begin{itemize}
	\item Inversion brings variables to one side
	\item Is a solution for simple equations but does not apply to the infinite dimensional integral operator (cannot be inverted in closed form)
	\item Finite element approaches 
		\begin{itemize}
		\item Yield a system of linear equations
		\item Have to be inverted
		\item Algorithms not used due to cubic complexity and numerical instability
		\end{itemize} 
	\end{itemize}

\subsection{Expansion}
	\subsubsection{Recursive Substiution}
		\begin{itemize}
		\item $L = L^e + TL$
		\item $L = L^e + T(L^{e}+TL) = L^e + TL^{e} + T^{2}L$
		\item Repeating n times results in neumann series $$L = \sum_{i=0}^n T^i L^e + T^{n+1} L$$
		\item T is a contraction and the infinith iteration is zero. $$\lim_{n \rightarrow \infty} T^{n+1} L = 0$$
		\item Leads to $$L = \sum_{i = 0}^\infty T^i L^e$$ as a solution for rendering problem
		\item Intractable equation with infinite series of integrals is replaced by integrals with successively higher dimensionality ($T^i$ has i integrals)
		\item Gathering expansion (Rec. subst. RE): Corresponds to recursion levels during ray-casting from eye
		\item Shooting expansion (Rec. sub. PE): Corresponds to recursion levels during ray shooting from emitter
		\end{itemize}

	\subsubsection{Integral Evaluation}
		\begin{itemize}
		\item Integral evaluation
			\begin{itemize}
			\item At each recursion level integral (high dimensional) is sampled
			\item Numerical quadrature
				\begin{itemize}
				\item Finite number of samples taken from integration domain
				\item Integrand evaluated for samples
				\item Numerical result of integral is weighted sum of evaluated samples
				\end{itemize}
			\item Classical Numerical Integration
				\begin{itemize}
				\item Brick rule, Simpsons rule - simple and effective for low-dim integrands
				\item Effort rises exponentially with dimension of integrand
				\item Monto carlo only viable method
				\end{itemize}
			\end{itemize}
		\item Monte Carlo Quadrature
			\begin{itemize}
			\item Converts calculation of integral to expected value problem. 
			\item Number of samples needed not dependent on dimension
			\item Random sampling basis for determing result
			\item Choosing samples
				\begin{itemize}
				\item Two strategies
					\begin{itemize}
					\item Importance sampling: Find best sample points by guessing distribution
					\item Stratification: Using samples which cover integrant very evenly
					\end{itemize}
				\item Discrepancy measure for sampling quali
					\begin{itemize}
					\item Regular grid high discrepancy
					\item Real random numbers also high discrepancy
					\end{itemize}
				\item Quasi Monte Carlo (Stratification)
					\begin{itemize}
					\item Deterministic low-discrepancy sequences
					\item Halton sequences for arbitrary numbers of points
					\item Hammersley sequences if number of needed points is known before
					\item TMS nets for 2d integrands
					\end{itemize}
				\end{itemize}
			\item QMC substantial performance and quality gains
			\end{itemize}
		\end{itemize}

	\subsubsection{Path termination}
		\begin{itemize}
		\item Fractional propagation / Attenuation
			\begin{itemize}
			\item Absorbed energy is subtracted at every step
			\item Path terminated when energy is less than threshold
			\item Biased but more intuitive
			\end{itemize} 
		\item Russian Roulette
			\begin{itemize}
			\item Random termination of ray according to propagation probability
			\item No bias, less intuitive
			\end{itemize}  
		\end{itemize}

	\subsubsection{Expansion Advantages and Disadvantages}
		\begin{itemize}
		\item Advantages:
			\begin{itemize}
			\item Gathering expansion: No temp rep of complete radiance function required 
			\item Shooting expansion: Flexible storage techniques
			\item Algorithms work on original geometry (no tesselation)
			\item Walks independent -can be parallelised.
			\item No temporary rep of the radiance function required.
			\end{itemize}
		\item Disadvantages:
			\begin{itemize}
			\item Paths independet, no coherency between them
			\item Evaluation of very high dimensional integrals
				\begin{itemize}
				\item Walk termination when biased threshold is reached or russian roulette
				\item Reduces sampling of higher recursion levels (scenes with mirrors)
				\end{itemize}
			\end{itemize}
		\end{itemize}

\subsection{Iteration}
	\begin{itemize}
	\item Solution of RE is fixed point of series $$L_n = L^e + TL_{n-1}$$
	\item If T contractive, series converges from any initial distribution $L_0$
	\item Finite element techniques used, with discretisation error
	\end{itemize}
	
	\subsubsection{Iteration Advantages and Disadvantages}
		\begin{itemize}
		\item Advantages
			\begin{itemize}
			\item Coherence exploited well
			\item Approximating functions $L_n$ viewpoint-independent: potential advantage for animations
			\item Provides implicit smoothing through discretisation, i.e. more visually pleasing images than noisy expansion
			\item More robust for highly reflective environments
			\end{itemize}
		\item Disadvantages
			\begin{itemize}
			\item Requires object tesselation and finite element rep
				\begin{itemize}
				\item Geometric accuracy and coherence lost
				\item Substantial storage requirements also for moderately complex scenes
				\end{itemize}
			\item Accuracy of high frequency shadows, reflections, caustics problematical
			\item Solution computed even for invisible parts of scene 
			\end{itemize}
		\end{itemize}

\section{Expansion Algorithms}
	\begin{itemize}
	\item Random Walk Algorithms Overview
		\begin{itemize}
		\item Gathering type RW 
		\item Shooting type RW
		\item Bi-directional algorithms
		\item Global methods
		\end{itemize}
	\item Heckbert's Taxonomy
		\begin{itemize}
		\item Provides further information
		\item Used to categorize rendering algorithms
		\item Short names
			\begin{itemize}
			\item E ... eye
			\item L ... lightsource
			\item D ... non-ideal reflection or refraction
			\item S ... ideal relfection or refraction
			\item * ... iteration
			\item $\lbrack \rbrack$ ... optional
			\item $|$ ... selection
			\end{itemize}
		\end{itemize}
	\end{itemize}

	\subsection{Gathering Type Random Walk}
		\begin{itemize}
		\item Starts at eye, gathers emission of the visited points
		\item Differences in trace() function determine actual algorithm
		\item Pseudo code illustrated in algorithm \ref{pcode_gatheringTypeRandWalk} 
			\begin{algorithm}
				\caption{Gathering Type Random Walk}
				\label{pcode_gatheringTypeRandWalk}
				\begin{algorithmic}
				\FORALL{pixels}
					\STATE colour = 0
					\FOR{$i = 1 \to N$}
						\STATE ray = random ray through pixel
						\STATE sampleColour = c * trace(ray)
						\STATE colour += sampleColour / N
					\ENDFOR
				\ENDFOR
				\end{algorithmic}
			\end{algorithm}
		\item Gathering Type Algorithms
			\begin{itemize}
			\item Ray Casting (LDE): Intersect single ray with a scene
			\item Ray Tracing: $L\lbrack D \rbrack S^*E$
				\begin{itemize}
				\item Photorealistic rendering algorithm
				\item Raytracers and more sophisticated renderes use raycasters
				\end{itemize}
			\item Distribution raytracing: $L\lbrack D|S \rbrack^*E$
			\item Path tracing: $L\lbrack D|S \rbrack^*E$
			\end{itemize}
		\end{itemize}

		\subsubsection{Ray Casting}
			\begin{itemize}
			\item First hit raytracing or nonrecursive raytracing
			\item Possible as real time renderer
			\item Potentially more efficient than OpenGL for complex scenes ($>$ 10M polygons)
			\item Pseudo code illustrated in algorithm \ref{pCode_RayCastTraceFunc}
				\begin{algorithm}
				\caption{Ray Casting Trace Function}
				\label{pCode_RayCastTraceFunc}
					\begin{algorithmic}
					\STATE hit = FirstIntersect(ray)
					\IF{no intersection}
						\RETURN bgColour
					\ELSE \RETURN emission(@hit,-ray.dir) + directLighting(@hit,-ray.dir)
					\ENDIF
					\end{algorithmic}
				\end{algorithm}
			\item Realtime RT
				\begin{itemize}
				\item Based on ray casting
				\item Certain limited types of recursion possible
				\item GI also possible
				\item State of the art: 1 billion polygons 640x480
				\end{itemize}
			\end{itemize}

		\subsubsection{Ray Tracing}
		\begin{itemize}
		\item Classical raytracing (CG1), known as Whitted Raytracing (Turner Whitted)
		\item Hybrid algorithm
			\begin{itemize}
			\item Recursion is evaluated for perfect mirrors
			\item Coupling is ignored otherwise
			\end{itemize}
		\item Steps
			\begin{itemize}
			\item Ray through pixel: Visibility calculation, Object intersection
			\item Shading based on direction to lightsource
			\item Multiple lightsources are taken into account
			\item Determining shadows
			\item Handling of reflections
			\item Shading of reflections
			\item Sum of influences
			\end{itemize}
		\item Pseudo code illustrated in algorithm \ref{pCode_RayTraceTraceFunc}
			\begin{algorithm}
			\caption{Ray Tracing Trace Function}
			\label{pCode_RayTraceTraceFunc}
				\begin{algorithmic}
				\STATE hit = firstIntersect(ray)
				\IF{no intersection} \RETURN bgColour \ENDIF
				\STATE colour = emission(@hit, -ray.dir) + directLighting(@hit, -ray.dir)
				\IF{kr $>$ 0}
					\STATE colour += kr * trace(reflectedRay)
				\ENDIF
				\IF{kt $>$ 0}
					\STATE colour += kt * trace(transmittedRay)
				\ENDIF
				\RETURN colour
				\end{algorithmic}
			\end{algorithm}
		\end{itemize}

		\subsubsection{Distribution RayTracing}
		\begin{itemize}
		\item Distribution raytracing: $L\lbrack D|S \rbrack^*E$
		\item Impractical due to fan out of N at every level
		\item Very slow convergence
		\item Pseudo Code: Pdf page 12 slide 3
		\item Pros and Cons
			\begin{itemize}
			\item + Simple
			\item + Process eventually converges to true solution
			\item - Bad convergence
			\end{itemize}
		\item Other algorithms are used instead of this one
		\end{itemize}

	\subsubsection{Path Tracing}
	\begin{itemize}
	\item Path tracing: $L\lbrack D|S \rbrack^*E$
		\begin{itemize}
		\item Single path traced through scene
		\item New ray is generated within hemisphere on diffuse object intersection
		\item With or without intermediate light source evaluation exist
		\end{itemize}
	\item Simple path tracing (Pseudo Code: Pdf page 13 slide 2)
		\begin{itemize}
		\item + Fast 
		\item + Simple to code: Follow path untillight source or threshold
		\item - Does not work for small lightsources
		\end{itemize}
	\item Improved Path Tracing
		\begin{itemize}
		\item Sampling of the light sources: Multiple importance sampling
		\item Key problem: correct weighting of two samples
		\end{itemize}
	\item Path tracing: Sample weighting
		\begin{itemize}
		\item At each surface intersection there are two possibilities to continue the ray
			\begin{itemize}
			\item According to the BRDF
			\item Through sampling of lightsources
			\end{itemize}
		\item Both have merits depending on situation
		\item Problem: Choosing right one requires knowledge of the solution
		\item Simple averaging: Retains worst properties of both
		\item Both samples without scaling yields wrong results
		\item No simple solution: Heuristic base on relative sample probabilities
		\item The Balance Heuristic
			\begin{itemize}
			\item Only used when both rays hit same light source, all other cases are simply added
			\item Key idea: Weight each sample according to its relative probability
			\item Weights sum up to one, no energy is counted twice
			\item Each ray has two probabilities
				\begin{itemize}
				\item Brdf probability (how probable that this ray gets created, e.g. Lambertian surface, phong-type specular lobe, mirror)
				\item Lightsource sample probability (how probable that ray gets created as a light source sample, e.g. area light source probability)
				\end{itemize}
			\end{itemize}
		\end{itemize}
	\item Path Tracing: Pros and Cons
		\begin{itemize}
		\item + Simple
		\item + Converges to true solution
		\item + Better convergence than distribution RT
		\item - bad converge for arbitrary scenes, especially when the lightsources are small
		\end{itemize}
	\end{itemize}

\subsection{Shooting Type Random Walk}
	\begin{itemize}
	\item Starts at lightsources, spreads the emission to visited points, which are projected into image
	\item Differences in shoot() function determine algorithm
	\item  Pseudo code illustrated in algorithm \ref{pCode_ShootTypeRandWalk}
		\begin{algorithm}
		\caption{Shooting Type Random Walk}
		\label{pCode_ShootTypeRandWalk}
			\begin{algorithmic}
			\STATE clearImage
				\FOR{$i = 0 \gets N$}
					\STATE ray = random ray from light with selection probablity $p_e$
					\STATE power = $L_e$ * cos($\phi$) / ($P_e$ * N)
					\STATE shoot(ray, power)
				\ENDFOR
			\end{algorithmic}
		\end{algorithm}
	\end{itemize}

	\subsubsection{Forward Raytracing - Photon Tracing}
		\begin{itemize}
		\item $LS^*DE$
		\item Inverse of raytracing
		\item Unuseable convergence speed
		\item Limited to RT-type images
		\item Pseudo Code on page 17 slide 5
		\end{itemize}

	\subsubsection{Light Tracing - Forward Path Tracing}
		\begin{itemize}
		\item $L\lbrack D|S\rbrack ^* E$
		\item Inverse of path tracing
		\item High variance
		\item Converges to true solution
		\item Unuseable in practice
		\item Pseudo Code on page 18 slide 1
		\end{itemize}

	\subsubsection{Gathering vs Shooting Algorithms}
		\begin{itemize}
		\item Dual algorithms, solve same problem
		\item Performance depends on factors
			\begin{itemize}
			\item Image size vs scene size
			\item Surface types
			\item Light sources
			\end{itemize}
		\end{itemize}

\subsection{Bidirectional Random Walk}
	\begin{itemize}
	\item Overcome difficulties of gathering and shooting by combining them
	\item Two algorithms exist
		\begin{itemize}
		\item Bidirectional path tracing
		\item Metroplois light transport
		\end{itemize}
	\end{itemize}

	\subsubsection{Bidirectional Path Tracing}
		\begin{itemize}
		\item Similar to path or light tracing, except
			\begin{itemize}
			\item Two paths randomly cast, from the eye, and the lightsources
			\item Convert shooting type walk to gathering type walk, the radiance ise multiplied by a facter (see pdf)
			\end{itemize}
		\item One version, all mutual inter-connections evaluated, in the other just last one
		\item Both paths are stopped when below importance threshold, or russian roulette is applied
		\end{itemize}

	\subsubsection{Metropolis Light Transport}
		\begin{itemize}
		\item Bidirectional tracing until a useful path found (costly and rare)
		\item Attempt to change path a little bit, to find another usefull path
		\item Problem: not breaking the stochastic simulation - metropolis sampling
		\item Changing a path
			\begin{itemize}
			\item Bidirectional Mutations: Changes in path length - vertices are added or deleted
			\item Perturbations: Directions are slightly altered at points in path
			\end{itemize}
		\item Pros and Cons
			\begin{itemize}
			\item + Handles difficult situations well
			\item - Startup bias not optimal for normal scenes
			\item - very difficult to implement
			\end{itemize}
		\end{itemize}

\section{Iterative Algorithms}
	\subsection{Idea, Advantages and Disadvantages}
		\begin{itemize}
			\item Idea
				\begin{itemize}
				\item Solution to RE is a fixed point of $$L_n = L^e + TL_{n-1}$$
				\item If T contractive, converges from any initial distribution $L_0$
				\item Finite element techniques (discretisation error) used for storing intermediate approximating functions $L_n$
				\item Viewpoint independent, also more computations involved
				\end{itemize}
			\item Advantages
				\begin{itemize}
				\item Coherency can be better exploited
				\item Approximating functions $L_n$ viewpoint independent: advantage for animations
				\item Implicit smoothing due discretization, i.e. better than noisy expansion
				\item More robust for highly reflective environments
				\end{itemize}
			\item Disadvantages
				\begin{itemize}
				\item Requires object tesselation and finite element representation
					\begin{itemize}
					\item Geometric accuracy and coherency is lost
					\item High storage requirements even for moderately complex scenes
					\end{itemize}
				\item Accuracy of high frequency shadows, reflections and caustics problematical
				\item Solution also for occluded parts
				\end{itemize}
			\end{itemize}

	\subsection{Storage-Based Methods Overview}
		\begin{itemize}
		\item Classical Radiosity - Iteration
			\begin{itemize}
			\item Deterministic
			\item Form-factor based
			\item Discretization of scene into patches
			\end{itemize}
		\item Stochastic Approaches - Expansion
			\begin{itemize}
			\item Global lines
			\item Photon tracing
			\end{itemize}
		\end{itemize}

	\subsection{Form-Factor Radiosity}
		\subsubsection{Radiosity Equation}
			\begin{itemize}
			\item Assume perfectly diffuse scattering
			\item Radiosity B is engery per unit area leaving patch surface per discrete time interval and is the combi
			\item Derive Discrete Radiosity Equation from RE (surface patches - finite element mehtod) $$B_i = E_i + \rho_i \sum_{j=1}^n B_j F_{ij}, 1 \leq i \leq n$$
			\item $B_i$: Radiosity Patch i (Sum of emission und reflection per surface area)
			\item $E_i$: Emission patch i
			\item $\rho_i$: Reflection patch i
			\item n: Num patches
			\item $F_{ij}$: Amount of energy from patch j to i (form factor)
			\end{itemize}

		\subsubsection{Algorithm}
			\begin{itemize}
			\item Surfaces divided up into patches
			\item View factor (form factor) computed for each pair of patches
			\item Factors describe visibility between patches
			\item Small view factors - patches are far away or at oblique angle (zero if occluded)
			\item Factors used as coefficients in linearized form of RE - yields a linear system of equations
			\item Solving equations yields radiosity (brightness) of patches with diffuse interreflections and soft shadows
			\item Progressive radiosity solves system iteratively, after each iteration tmp radiosity values for patches (bounce levels)
			\item PR usefull for getting interactive preview 
			\item No numerical converging needed - stop iteration when looking good
			\item Compute matrix solution at once too expensive: Jacobi-Iteration and Gauss-Seidel method (Gathering Radiosity), Progressive-Refinement and Southwell-Iteration (Shooting Radiosity)
			\item Shooting solutions converge better
			\end{itemize}

		\subsubsection{Form Factor Calculation}
			\begin{itemize}
			\item Nusselt
				\begin{itemize}
				\item Point of receiving surface patch is center of sphere
				\item Project other surface on sphere
				\item Project projected surface on sphere on plane
				\item Approximates form factor
				\end{itemize}
			\item Hemicube
				\begin{itemize}
				\item Cube with grid
				\item Each grid point on cube has delta formfactor depending on position of grid plane
				\item Surface patch projected on hemi cube
				\item Delta form factors are summed up on projected areas: form factor relationship
				\end{itemize}
			\item Binary space partitioning tree (BSP-tree): better performance for determining hidden patches
			\item Adaptive integration: newer methods
			\end{itemize}

		\subsubsection{Limitations and Scope}
			\begin{itemize}
			\item Only polygonal scenes
			\item Only diffuse materials
			\item Extensions for mirrors possible
			\item Newer, stochastic methods are state of research
			\item Form factor radiosity is state of the art in commercial products
			\end{itemize}

		\subsubsection{Progressive-Refinement-Radiosity}
			\begin{itemize}
			\item Shoot radiosity from all patches
			\item First take patches with high radiosity then lower radiosity
			\end{itemize}

		\subsubsection{Hierarchical Radiosity}
			\begin{itemize}
			\item Patchhierarchie: Bigger patches contain many smaller patches
			\item Radiosity on different levels: If error small stay on higher level, else lower level 
			\item Cluster enhancement: bigger hierarchie level
			\end{itemize}

		\subsection{Global Lines}
			\begin{itemize}
			\item Stochastic radiosity solver 
			\item Cast rays through scene, record all light transport along intersections
			\item Difusse environments only
			\item Also tesselated geometry
			\item Sometimes faster than photon tracing
			\item Good for animation sequences
			\item Theoretical better than form-factor radiosity but not used in practice (research only)
			\end{itemize}

	\subsection{Photon Mapping}
	\begin{itemize}
	\item Multipass renderer (usually 2-pass)
	\item Photon paths traced through scene and intersection point and incoming dir stored in cache (photon map)
	\item Usually different photon maps (Global, Caustics, etc..)
	\item Photon map usually arranged (kD-tree) for optimal k-nearest neighbor algorithm (photon look-up time depends on spatial distri)
	\item Caustic Photon Map
		\begin{itemize}
		\item Many photons are emitted towards specular objects
		\item Stored upon intersection with diffuse surfaces
		\item Visualize directly by nearest n photons for illumination reconstruction
		\end{itemize}
	\item Global Photon Map
		\begin{itemize}
		\item Photons are emitted towards all objects in a scene
		\item Used as a rough approximation of light transport in a scene
		\item Not visualized directly
		\end{itemize}
	\item Shadow Photon Map
		\begin{itemize}
		\item Rays with origin at lightsource traced through entire scene 
		\item First intersection recorded as light, subsequent as shadow
		\item Used for improvement raytracing pass
		\end{itemize}
	\item Photon Maps Disadvantages
		\begin{itemize}
		\item Slow
		\item Memory consumption
		\item Illumination reconstruction depends on distance
		\item Biased (Averaging many renders does not converge to correct solution of RE)
		\end{itemize}
	\item Lightmaps
		\begin{itemize}
		\item 2d light textures on objects 
		\item Each texture element averages the energy of all photon hits it receives
		\item Higher order representations possible
		\item Area of texels has to be known and has to be computed as a preprocessing step
		\item Interpolation over texels after tracing pass
		\end{itemize}
	\item Photon Tracing
		\begin{itemize}
		\item Memory consumption: texels on all primitives are wasteful
		\item Preprocessing: area computation for large numbers of texels takes too long
		\item Execution time: far too many photons have to be cast for a stable estimate
		\item Impossible to attach to implicit objects, e.h. L-systems
		\end{itemize}
	\end{itemize}

\part{Advanced Topics}
\section{Surface Models}
	\subsection{Light Matter Interaction}
		\begin{itemize}
		\item Surface reflectance properties determine look
		\item Surface - light interaction
			\begin{itemize}
			\item Key term for surface reflectance $\rho(x,x', x'')$
			\item How light from a given direction is modified upon reflection from a surface
			\item Has to be answereable for all directions and surface points
			\end{itemize}
		\end{itemize}

	\subsection{Bi-Directional Reflectance Distribution Function (BRDF)}
		\subsubsection{Definition}
			\begin{itemize}
			\item Returns ratio of reflected radiance along outgoing dir to irradiance incident on surface from ingoing dir
			\item $f_r(w_i \rightarrow w_r) \equiv \frac{L_r(w_r)}{L_i(\omega_i) cos\theta_i d\omega_i}$
			\end{itemize}

		\subsubsection{Related Distribution Functions}
			\begin{itemize}
			\item BTDF (Bi-directional Transmission Distribution) for rays that point into material
			\item BSDF (Bi-directional Scattering Distribution) combination of both, but rarely used
			\item BTF (Bi-directional Texture Function)
				\begin{itemize}
				\item BRDF for entire texutres (carpet, cloth, ...)
				\item Positional info to combine BRDFs
				\item Problems: Seamless textures from BTF data, acquisition of samples
				\end{itemize}
			\end{itemize}

		\subsubsection{Isotropy vs Anisotropy}
			\begin{itemize}
			\item Isotropy
				\begin{itemize}
				\item Rotational invariance 
				\item Holds for large number of surfaces
				\item Reduces number of variables by one
				\item No alignment needed
				\end{itemize}
			\item Anisotropy: Reflectance properties change with rotation of the surface around normal vector
			\end{itemize}

		\subsubsection{Requirements}
			\begin{itemize}
			\item Reasonable amounts of storage
			\item Capture key characteristics of surface
			\item Fast easy sampling by Monte Carlo
				\begin{itemize}
				\item Apart perfectly diffuse andperfect mirrors, other reflection properties only tractable through MC rendering
				\item Casting rays according to distribution function is crucial
				\end{itemize}
			\end{itemize}

		\subsubsection{Data Sources}
			\begin{itemize}
			\item Tabulated measurements or simulation results
				\begin{itemize}
				\item Gonioreflectometer: Expensive, hard to maintain and operate, generates huge data.
				\item High memory when stored as set of finely spaced samples
				\item Compression essential
				\item Hard, time-consuming to measuring
				\item Bad stochastic sampling characteristics: Rejection sampling
					\begin{itemize}
					\item Given hard to sample probability distri other easy to sample envelope distri
					\item Samples from envelope distri are accepted or rejected
					\item Many unwanted samples possible
					\end{itemize}
				\end{itemize}
			\item Approximation by analytical functions and requirements
				\begin{itemize}
				\item Reciprocity: Sampling directions can be interchanged (Helmholtz reciprocity principle) $$f_r(\omega_i \rightarrow \omega_r) \equiv f_r(\omega_r \rightarrow \omega_i)$$
				\item Energy conservation
				\item Fast evaluation
				\item Expressivity
				\item Easy stochastic sampling
				\end{itemize}
			\end{itemize}

	\subsection{Analytical BRDFs}
		\begin{itemize}
		\item Empirical models
			\begin{itemize}
			\item Lambert, Phong, Blinn, Lafortune
			\item Superposition of different components
			\end{itemize}
		\item Physically based models
			\begin{itemize}
			\item Torrance-Sparrow, Cook-Torrance, Kajiya, He-Sillion-Torrance-Greenberg (HTSG)
			\item Physical material constants needed
			\end{itemize}
		\end{itemize}

		\subsubsection{Overview}
			\begin{itemize}
			\item Lambert: only diffuse component
			\item Phong: generalized cosine lobe
			\item Ward: anisotropic
			\item Can be combined for higher realism
			\item Energy conservation dependent on coefficients and combination (esp. for Phong)
			\item Easy to sample
			\item Generalizations possible
			\end{itemize}

		\subsubsection{Perfectly Diffuse}
			\begin{itemize}
			\item Reflect the incoming light equally in all directions over the hemisphere
			\item Viewing direction independent
			\item E.g. Lambert, Oren-Nayar
			\item Lambert Surface
				\begin{itemize}
				\item Percectly diffuse isotropic surface
				\item Light proportional to cosine of incident angle
				\item Color defined by wavelength-dependent diffuse absorption coefficient
				\end{itemize}
			\item Oren-Nayar Surface
				\begin{itemize}
				\item Microfacet-based diffuse surface
				\item Takes into account masking, shadowing and interreflections
				\item Often gaussian distri used to model distri of micro-facets (cavities)
				\item Variance (sigma) of gaussian distri measure for roughness
				\item Simplifies to Lambert's cosine model when sigma is zero
				\item More and more retro-reflective for increasing sigma
				\end{itemize}
			\end{itemize}

		\subsubsection{Rough Specular}
			\begin{itemize}
			\item Some light is reflected off ideal specular angle (highlights)
			\item Phong Surface
				\begin{itemize}
				\item Visual approximation by ambient, diffuse and specular term
				\item Adds specular highlight (parametrized through exponent)
				\item Also combined phong lobes possible
				\end{itemize}
			\item Ward's BRDF Model
				\begin{itemize}
				\item Anisotropic micro-faceted surfaces
				\item Physically correct (energy conserving) and fast
				\item Again gaussian distri for cavities
				\item Based on real measurements with a gonio-reflectometer
				\end{itemize}
			\end{itemize}

		\subsubsection{Perfectly Specular}
			\begin{itemize}
			\item One outgoing dir (reality not existent)
			\item Incoming angle ~ outgoing angle
			\item Simulate smooth glass, metallic surfaces
			\item For realistic materials: Fresnel coefficients
			\end{itemize}

		\subsubsection{Directional Diffuse}
			\begin{itemize}
			\item Combination of rough specular reflector and ideal diffuse reflector
			\item E.g. Cook-Torrance, Ward, He,...
			\item Torrance-Sparrow Surface
				\begin{itemize}
				\item Physically plausible BRDF model three main components
					\begin{itemize}
					\item Microfacet model
					\item Fresnel term for reflectance
					\item Roughness term
					\end{itemize}
				\item Requires material constants to be known
				\item Geometric Factor: Facets perfect reflectors except attenuation (self-shadowing, masking)
				\item Evaulation
					\begin{itemize}
					\item + Physically corrent 
					\item + Excellent results
					\item - Hard to sample
					\item - Hard to code
					\item - Depends on material constants
					\end{itemize}
				\end{itemize}
			\item He, Torrance, Sillion, Greenberg
				\begin{itemize}
				\item Based on wave optics and diffraction theory, can take polarization into account 
				\item Additional split between diffuse and directional diffuse term
				\item Expensive to compute
				\item Input: auto-correlation, variance of surface height
				\end{itemize}
			\end{itemize}

\section{Advanced Materials}
	\subsection{Beyond Normal BRDFs}
		\begin{itemize}
		\item Some surfaces not characterized through standard BRDFs
		\item Phosphorescent paint
		\item Fluorescent paint
		\item Metallic paint
		\item Pearlescent paint
		\item Complex structure
			\begin{itemize}
			\item Fibers (e.g. hair, textiles)
			\item Sparkles (e.h. snow, lacquer)
			\item Thin layers (e.g. leaves, skin)
			\end{itemize}
		\item BSSRDFs
		\end{itemize}

	\subsection{Fluorescence}
		\begin{itemize}
		\item Re-radiation of incident energy at different wavelengths
		\item If only re-radiation to lower energy levels
			\begin{itemize}
			\item Extends reflection spectra to matrices
			\item Hard to handle otherwise
			\end{itemize}
		\item Common effect, hard to measure: bispectral photometers needed
		\item In some areas the reflection intensity appears to be larger than 1
		\item Bi-Coloured Reflection Pattern
			\begin{itemize}
			\item Rays reflected by the substrate retain color
			\item Rays which interact with colorant molecules undergo wavelength shift
			\item First Approximation: Phong lobes
				\begin{itemize}
				\item Superposition of different phong lobes
				\item Fixed ratio between lobes
				\item Large diffuse fluorescent component
				\item Small specular, non-fluorescent part
				\item Advantage: simple
				\item Disadvantage: results are not good
				\end{itemize}
			\end{itemize}
		\item Layered Torrance-Sparrow Model
			\begin{itemize}
			\item Rough dielectric layer over lambertian fluorescent surface 
			\item Blinn microfacet distribution
			\item No attenuation in the substrate
			\item Simplified sub-surface scattering, re-emission at the point of incidence
			\end{itemize}
		\end{itemize}

	\subsection{Fibers}
		\begin{itemize}
		\item Many materials composed of bundles of thin fiber
		\item E.g. hair, textiles, finished wood
		\item Hair
			\begin{itemize}
			\item Not possible to model as a volume
			\item Strands modelled as cylinders
			\item Three light paths (R Reflect, T Transmission: R, TT, TRT)
			\item Gaussian distribution (roughness) times attenuation
			\end{itemize}
		\end{itemize}

	\subsection{Asterism and Chatoyance}
		\begin{itemize}
		\item Reflected light forms luminous band (star)
		\item Caused by small needle-like inclusions
		\item Simulated with a phong-like model
		\end{itemize}

	\subsection{Heterogeneous Gemstones}
		\begin{itemize}
		\item Appearance depends on viewing direction
		\item Often heterogenous
		\item Combining several textures
		\end{itemize}

	\subsection{Sparkling Effects}
		\begin{itemize}
		\item E.g. snow, metallic paint, gemstones 
		\item Small flecks of material has a high specular reflectance
		\item Two options: Statistically, Explicitly
		\item Metallic Paint
			\begin{itemize}
			\item Statistical model
			\item Substrate: Lambert reflector
			\item Flakes are modelled with a distribution
			\item Top: clear coat (Fresnel reflectance)
			\item Explicitly modelled flakes
				\begin{itemize}
				\item Bigger flakes can be modelled explicitly
				\item E.g. BTFs or voronoi textures
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{Pearlescent Paint}
		\begin{itemize}
		\item Interference effect
		\item Aluminium or mica flakes coated with thin layers
		\end{itemize}

	\subsection{Subsurface Scattering}
		\begin{itemize}
		\item BRDFs: light scatters exactly at point where it hits the surface
		\item Subsurface scattering: light enters material, bounces around and leaves at different place
		\item Extension of BRDFs
		\item BSSRDFs: Bidirectional surface scattering reflectance distribution function
		\item 8 degrees of freedom (pos and direction)
		\item Monte Carlo evaluation expensive
		\item Diffusion Approximation
			\begin{itemize}
			\item Light distri in highly scattering media becomes isotropic
			\item Two point sources are placed near surface
			\item Complete BSSRDF sum of diffusion approximation and single scattering term
			\end{itemize}
		\item Rendering BSSRDFs
			\begin{itemize}
			\item BSSRDF model applies to semi infinite homogeneous media
			\item For practical model consider
				\begin{itemize}
				\item Efficient integration of BSSRDF
				\item Single scattering evaluation for arbitrary geometry
				\item Diffusion approximation for arbitrary geometry
				\item Texture (spatial variation)
				\end{itemize}
			\item Efficient Rendering (2 pass approach): first irradiance at surface points, then evaluate BSSRDF
			\end{itemize}
		\end{itemize}

\section{Spectral Rendering}
	\subsection{Introduction}
		\begin{itemize}
		\item Basic Properties
			\begin{itemize}
			\item Light as electromagnetic radiation out of particular region of entire spectrum
			\item Distinguishing criterion: its frequency
			\end{itemize}
		\item Spectrum
			\begin{itemize}
			\item Ray of light contains many different waves with individual frequencies
			\item Distribution of wavelength intensities per wavelength  referred as spectrum of ray or lightsource
			\end{itemize}
		\end{itemize}

	\subsection{Colour Space Rendering}
		\begin{itemize}
		\item Conventional
		\item Mostly RGB space, also CIE XYZ space
		\item RGB (Tristimulus) Rendering
			\begin{itemize}
			\item RGB (3 wavelengths) define light and material props
			\item Process 3 channels sep
			\item Device dependent
			\item RGB rep not ideal
			\end{itemize}
		\item CIE XYZ
			\begin{itemize}
			\item Derived from RGB
			\item Outside the human visual gamut (only positive XYZ values)
			\item Valid colors  subspace of first octant
			\item XYZ not closed under multiplication
			\end{itemize}
		\item CIE XYZ vs RGB
			\begin{itemize}
			\item RGB closed under multiplicaiton
			\item RGB negative values to rep all colors
			\item RGB corresponds to real colour
			\item XYZ virtual positive values
			\end{itemize}
		\end{itemize}

	\subsection{Spectral Rendering}
		\begin{itemize}
		\item Few products available: Maxwell renderer, luxrender, indigo
		\item Few known about internal details
		\item Rendering steps
			\begin{itemize}
			\item Get spec
			\item Prepare spec
			\item Process spectral samples sep throughout rendering calculation
			\item Compute final display color using CIE color matching functions and standard transformations
			\end{itemize}
		\end{itemize}

		\subsubsection{Measuring Spectra}
			\begin{itemize}
			\item Measured with spectroradiometer
			\item First calibration of measurement device
			\item Reference standard needed
				\begin{itemize}
				\item Source of known emissivity (blackbody, refernece lamps)
				\item Detector with an exactly known response
				\item Surface with exactly known reflectivity
				\end{itemize}
			\item Reference Lamps
				\begin{itemize}
				\item Desinged lamps
				\item Repeatability of lamp manufacturing good enough to duplicate lamps
				\item Tungsten halogen lamps of 1000, 200 and 45W developed for general use
				\item Burning time limited
				\end{itemize}
			\item Detectors: pdf...
			\end{itemize}

		\subsubsection{Preparation}
			\begin{itemize}
			\item Light as freq distri (usually smooth, sharp peaks - fluorescense, spectral colours)
			\item Colour collections: munsel, ncs, ral... 
			\item Discritize distris
				\begin{itemize}
				\item Regular sampling: aliasing, fast convolution
				\item Linear or higher order rep: efficient storage, slow convolution
				\item Hybrids: slow but more efficient storage
				\item Amount of samples depends on spectrum
					\begin{itemize}
					\item More samples for spectra with sharp peaks
					\item CIE F11 representations
					\item error map sampling points
					\end{itemize}
				\end{itemize}
			\end{itemize}

		\subsection{Spectral vs RGB Rendering}
			\begin{itemize}
			\item RGB 
				\begin{itemize}
				\item Fast, widely supported 
				\item Limited accuracy (sharp spectra, different illuminations)
				\end{itemize}
			\item Spectral Rendering
				\begin{itemize}
				\item Accuracy, prediction of nature
				\item High cost, aliasing, data mixing, input data
				\item Hard to code
				\end{itemize} 
			\end{itemize}

		\subsection{Spectral Effects}
			\begin{itemize}
			\item Metamerism (different spectra - same color, problem for paint and pigment industry)
			\item Volume absorption
			\item Dispersion (prisms, rainbows): wavelength dependency of interference and refraction
			\item Interference and diffraction
			\item Fluorescent materials and light sources
			\item Polarisation: essential for predictive rendering or crystals and transparent objects or outdoor scenes
				\begin{itemize}
				\item Specular surfaces governed by fresnel terms
				\item Show discrepancy for diff orientiations of polarised incoming light (.e.g. skylight)
				\item Spec scenes with water, glass, car roots etc are affected
				\item Describing polarisation see pdf
				\end{itemize}
			\end{itemize}

\section{Participating Media}
	\subsection{Introduction}
		\begin{itemize}
		\item In vaccum, radiance is constant along the ray
		\item Real-world light scattered and attenuated (e.g. fog, smoke, ..)
		\item Two difficulties
			\begin{itemize}
			\item Intersection phenomena within any point of the medium
			\item Spectral dependence of medium characteristic parameters
			\end{itemize}
	\item Radiation three different kinds of phenomena
		\begin{itemize}
		\item Absorbtion
			\begin{itemize}
			\item Energy is reduced (converted into e.g. heat)
			\item Given by absorption coefficient 
			\item Beer's law: see pdf
			\end{itemize}
		\item Emission
			\begin{itemize}
			\item Energy added from luminous particles and converted to visible light
			\item Chemical, thermal or nuclear processes
			\end{itemize}
		\item Scattering
			\begin{itemize}
			\item Out-scattering: Radiance reduced along ray (e.g. clouds)
			\item In-scattering: Radiance increased from other dirs (e.g. mist)
			\end{itemize}
		\end{itemize}
	\item Phase Function: Spatial distri of the scattered light
		\begin{itemize}
		\item Isotropic (counterpart of diffuse BRDF)
		\item Rayleigh (small spherical particles, e.g. smoke)
		\item Mie (particles have size of light, e.h. clouds)
		\item Henyey-Greenstein (approximation of Mie)
		\end{itemize}
	\end{itemize}

	\subsection{Transport Equation}
		\begin{itemize}
		\item TE takes all these phenomena into account
		\item Describes variation of radiance
		\item Challenges
			\begin{itemize}
			\item Input data (homogeneous - constant parameters, inhomogeneous - properties are varying in the medium)
				\begin{itemize}
				\item Explicit storage of measured data (voxel grids) 
				\item Numerical solutions (simple analytical functions: perlin noise, exp func, fluid sim)
				\end{itemize}
			\item Solving the TE (Full solution expensive - simplified models)
			\end{itemize}
		\item TE simplifications
			\begin{itemize}
			\item No scattering case (e.g. fire)
			\item Single scattering case (not realistic, strongly related to the medium)
				\begin{itemize}
				\item Scattering of light by a single particle
				\item Material is either very thin or very transparent
				\end{itemize}
			\item For homogeneous non-emitting materials - there is another formula
			\item For heterogeneous materials break up integral and compute it incrementally by ray marching
				\begin{itemize}
				\item Compute distribution from medium, by dividing the ray into smaller segments
				\item Different Ray Sampling strategies
				\end{itemize}
			\item Absorption and emission only
			\item Multiple Scattering
				\begin{itemize}
				\item Scattering of light from multiple particles
				\item Two Stages
				\item Illumination pass (source radiance is computed, e.g. volume photon mapping)
				\item Visualization pass (TE is solved, e.g. ray marching)
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{Volume Photon mapping}
		\begin{itemize}
		\item Extend surface photon maps to volume photon maps
		\item Photons stored in volume
		\item Two pass algorithm: First trace photons through volume, then evaluate photon maps using ray marching
		\item Photon can pass unaffected or interact with medium (scattered or absorbed)
		\item Russion roulette decides photon is scattered or absorbed
		\item Stored in photon map, if not from light source and interacts
		\item Importance sampling of phase function to find new direction
		\end{itemize}

		\subsubsection{Estimating Radiance}
			\begin{itemize}
			\item Different for surfaces and volumes
			\item Direct light by sampling of the light source using ray marching
			\item Indirect light: volume radiance estimate
			\end{itemize}

		\subsubsection{Analytical Models}
			\begin{itemize}
			\item CIE: Monochrome (luminance only), validated to some degree
			\item Perez: improved CIE model
			\item Preetham: based on perez model, spectral colours for each solar elevation
				\begin{itemize}
				\item Five parameters
				\item A darkening or brightening of the horizon
				\item B luminance gradient near the horizon
				\item C relative intensity of the circum-solar region
				\item D width of the circum-solar region
				\item relative backscattered light
				\end{itemize}
			\end{itemize}

\section{Cameras}
	\subsection{Camera Models}
		\begin{itemize}
		\item Perspective Camera (perspective projection)
			\begin{itemize}
			\item Pinhole (Perspective) Camera
			\item Simplest device for taking photos
			\item Light enters through small hole and falls on film, hole is the eye point
			\item Includes foreshortening
			\item Doesn't perserve distances or parallel lines
			\end{itemize}
		\item Orthographic Camera (parallel projection)
			\begin{itemize}
			\item Perserves relative distance between objects, parallel lines 
			\item No foreshortening
			\item View volume is an aligned box
			\end{itemize}
		\item Fisheye Camera
		\item Environment (Spherical) Camera
			\begin{itemize}
			\item Rays are traced in all directions around a point
			\item 2d view of everything that is visible from that point
			\item All rays have same origin
			\item Useful for environment lighting
			\end{itemize}
		\end{itemize}

	\subsection{Pinhole Concept vs Aperture}
		\begin{itemize}
		\item Sharp for all parts of a scene
		\item Pinhole is an idealized concept, but not realistic
		\item Real cameras need an aperture and a lens
		\item Aperture
			\begin{itemize}
			\item Pinhole has to have nonzero diameter - reason for aperture
			\item Cameras have variable with - which is determined by a mechanical iris
			\item Lens is needed to create an image with aperture and iris
			\end{itemize}
		\item Thin Lens Assumption
			\begin{itemize}
			\item For sophisticated CG renderings with DOF etc more realistic concept of lens systems is needed than a pinhole camera 
			\item For most purposes, it is sufficient to assume a planar lens with negligible curvature and fixed index of refraction
			\item Fat lenses have to be explicitly simulated
			\end{itemize}
		\item Focal Length Definition
			\begin{itemize}
			\item Parallel rays that fall through lens are focused in F
			\item Small F .. wide angle lens
			\item Large F .. tele lens
			\end{itemize}
		\item Thin Lens Camera Implications
			\begin{itemize}
			\item Possible to perfectl focus any plane source image onto the receiving film
			\item It is not possible to focus all objects which are in different depths
			\item Resolution of the film is always limited
			\end{itemize}
		\item Depth of Field
			\begin{itemize}
			\item Small aperture... image is sharper over a wider range, but longer exposure needed 
			\item Big aperture ... small exposure, low DOF
			\end{itemize}
		\item f-number: focal length divided by aperture diameter
		\item Real Camera Lens Errors
			\begin{itemize}
			\item Spherical Aberration, Astigmatism and Coma
			\item Distortion affects the image geometry
			\item Field curvature is due to lens curvature: local lack of sharpness
			\item Chromatic aberration (occurs near edges)
			\item Diffraction upper-bounds the imaging capabilities of a given lens
			\end{itemize}
		\end{itemize}

\section{Introduction to Stereo Projection}
	\begin{itemize}
	\item Physical properties of stereo setup
		\begin{itemize}
		\item Linear vs circular polarization 
		\item 2 beamers with filters for circular polarized light
		\item Retroreflective screen: Perserves polarization state
		\end{itemize}
	\item Basics
		\begin{itemize}
		\item Render scene twice: With eye offset
		\item Also view matrix changed sometimes
			\begin{itemize}
			\item Toe in: shift towards focus point
			\item Offaxis: shit view matrix
			\item Create asymmetric proj: No vertical parallax
			\end{itemize}
		\end{itemize}
	\end{itemize}

\section{Post-processing: Tone Reproduction and White Balance}
	\subsection{Introduction}
		\begin{itemize}
		\item Image Synthesis Pipeline
			\begin{itemize}
			\item Modelling
			\item Rendering
				\begin{itemize}
				\item Output RGB, XYZ or spectral 
				\item Predictive rendering yields hdr images
				\end{itemize}
			\item Display has limited range for luminance and color
			\end{itemize}
		\item HDR
			\begin{itemize}
			\item Dynamic range: contrast ratio between brightest and darkest parts
			\item Hdr cannot be displayed on normal display hw
			\item Special iamge formats necessary
			\item Usually impossible to solve repro task perfectly
			\item Strongly depnds on output device
			\item Various heuristics of increasing complexity exist
			\item Full perception models difficult
			\item Animations pose additional challenges (frame to frame coherency)
			\end{itemize}
		\item Image Types
			\begin{itemize}
			\item Relative values: Measured as max output device capability
				\begin{itemize}
				\item Screens: Two orders of magnitude
				\item Printouts: Range of 10 luminance units
				\item 8bit images: 256 steps
				\end{itemize}
			\item Absolute Radiometric Values
				\begin{itemize}
				\item Captures of reality: Scene ref images
				\item Digital cameras ought to capture
				\end{itemize}
			\end{itemize}
		\end{itemize}

	\subsection{Image Formats}
		\subsubsection{Conventional formats}
			\begin{itemize}
			\item RGB (TIFF, PNG, JPEG)
			\item TIFF also in CIE L*a*b*
			\item Normally 8 bits per channel
			\item TIFF: 16 bit possible (JPEG 12bit)
			\item Brightness ends at 1 - device dependent
			\item No physical meaning of values
			\item Compact size, standardised but lots of info lost
			\end{itemize}

		\subsubsection{HDR formats}
			\begin{itemize}
			\item Values have physical meaning
			\item Floating point components: Large range
			\item Compact size, standardised, few quantization errors, Compression introduce artefacts
			\item Not understood by photoshop
			\item Radiance RGBE, Pixar Log and LogLuv TIFF, ART XYZ (uncompressed), OpenEXR
			\item OpenEXZ HDR Image Format
				\begin{itemize}
				\item Tailored to needs of movie industry
				\item 8bits unsuitable for movie work, 16bit limited post-processing
				\item 16 and 32 bit floating point colors
				\item 16 bit float compatible with Nvidia CG HALF (EXR directly used in hardware)
				\item Lossless compression: 35\%-55\%
				\item Arbitrary info can be stored alongside image data
				\item Arbitrary image channels
				\end{itemize}
			\end{itemize}

		\subsubsection{Spectral Image Formats}
			\begin{itemize}
			\item N spectral samples per pixel
			\item Floating point components: Large range
			\item Values have physical meaning
			\item FITS and ARTRAW lonely formats
			\item No quantization or compression errors, no info lost but huge files (400mb for 640x480) and rare support
			\end{itemize}

	\subsection{Image Post-Processing}
		\begin{itemize}
		\item Gamut Mapping: Getting colours into display gamut
			\begin{itemize}
			\item Local: Outlying points are individually moved (fast but highlights lost)
			\item Global: All points analysed, point cloud shrunk so it fits into gamut 
				\begin{itemize}
				\item Relation between colours is maintained
				\item Desaturation of img
				\end{itemize}
			\end{itemize}
		\item Tone Mapping: Fitting the luminance range to a given device
		\item Tone Rep: Gamut and tone mapping together
		\end{itemize}

		\subsubsection{Tone Reproduction Operators}
			\begin{itemize}
			\item 3 diff approaches
			\item Global methods: spatially uniform, linear scale factor, non-linear scale factor
				\begin{itemize}
				\item Scalling all luminance values by factor
				\item Primitive and fast
				\item Automatic determination of factor
				\item Sufficient for many scenes
				\item Result in dark images if the DR big
				\item Linear operators: same fac for all values
					\begin{itemize}
					\item Mean value mapping
						\begin{itemize}
						\item Mean value of the hist is mapped to 0.5
						\item Values outside the constrast interval are clipped
						\end{itemize}
					\item Interactive calib: Interactively define area and range of available contrast interval
					\item Ward's scaling fac
						\begin{itemize}
						\item MAx display luminance and environment adaption degree parametrization
						\item Good results: just visible differences remain
						\item Image has to be given in absolute units
						\end{itemize}
					\end{itemize}
				\item Non-linear operators
					\begin{itemize}
					\item Exponential Mapping
						\begin{itemize}
						\item Corresponds to human perception
						\item Reduces overproportional influence of few bright pixels
						\end{itemize}
					\item Schlick's Method
						\begin{itemize}
						\item Behaviour similar to exponential mapping
						\item Good for high contrast images
						\item Can fail completely
						\end{itemize}
					\item Mapping by Tumblin and Rushmeier
					\item Visual Adaption Model
					\end{itemize}
				\end{itemize}
			\item Local methods: spatially non-uniform
				\begin{itemize}
				\item Differences between parts of the image are taken into account
				\item Image sep into zones to determine brightness targets (similar to photography)
				\item Local kernel of var size used for final tone rep step
				\item Can look artificial
				\end{itemize}
			\item Perceptual approaches
				\begin{itemize}
				\item Results from physiology and psychology used to reproduce behaviour of human vis sys
				\item 2 approaches
					\begin{itemize}
					\item Determiens what person would see if scene was real
					\item Try to rep sensation using on display
					\end{itemize}
				\item Takes into account
					\begin{itemize}
					\item Threshold sensitivity
					\item Color appearance
					\item Visual acuity
					\item Light adaption
					\item Dark adaption
					\end{itemize}
				\end{itemize}
			\item Colour Correction / White balance
				\begin{itemize}
				\item Challenging task
				\item Most algorithms image based, only two scene driven
				\item Workflow
					\begin{itemize}
					\item Determining illuminant colour
					\item Applying transform that compensates for the illuminant
					\end{itemize}
				\item Many algorithms:
					\begin{itemize}
					\item Gray world
						\begin{itemize}
						\item Avg of all pixels is gray
						\item Avg is mapped to gray
						\item Fails if assumption is violated
						\end{itemize}
					\item White patch
						\begin{itemize}
						\item Always a white obj in the img, 
						\item Brightest pixel is mapped to white, 
						\item Fails if no white obj
						\end{itemize}
					\item Neural networks
					\end{itemize}
				\item CC State of the art
					\begin{itemize}
					\item Scene based (better approach)
					\item Reliable CC method that used additional info (gathered during rendering)
					\end{itemize}
				\item Algorithm Overview
					\begin{itemize}
					\item All directly viewed surfaces set to neutral
					\item All lights set to neutral on directly viewed surfaces
					\end{itemize}
				\end{itemize}
			\end{itemize}

\section{Pixar RenderMan}
	\subsection{Introduction}
	\begin{itemize}
	\item REYES architecture
		\begin{itemize}
		\item Render everything you ever saw
		\item PRMan ref implementation
		\item Assumptions and Goals
			\begin{itemize}
			\item High possible model complexity
			\item Diverse primitives: fractals, procedural models etc
			\item Shading complexity
				\begin{itemize}
				\item Complexity of scenes more comes from surface specs than geometry
				\item Programmable shaders needed
				\end{itemize} 
			\item Minimal ray tracing: Approximation of non-local effects through other means (e.g. shadow maps)
			\item Speed: 2h movie in 1 year
			\item Image quality: Anti-aliasing and proper pixel filtering needed
			\end{itemize}
		\end{itemize}
	\item RenderMan: Used for today's industrial CG work
	\item RenderMan Naming Confusion
		\begin{itemize}
		\item RenderMan SL: 3d scene description language
		\item RenderMan Interface: Interface between modelling and rendering
		\item PRMan: The RenderMan-compliant hybrid scanline renderer
		\end{itemize}
	\item For long time Pixar PRMan was the only Rman-compliant system
	\item Pixar Photorealistic RenderMan (PRMan)
		\begin{itemize}
		\item Evolved since 1982/84 from Lucasfilm Renderer
		\item Sophisticated scanline renderer
		\item Currently at release 14.0
			\begin{itemize}
			\item Indirect illumination / GI
			\item Hair and fur optimizations
			\item Parallel network rendering
			\item On demand raytracing
			\end{itemize}
		\end{itemize}
	\end{itemize}

	\subsection{REYES Desing Principles}
		\begin{itemize}
		\item Bound: Computes bounding box
		\item Culling: Discard inv primitives
		\item Diceable test
			\begin{itemize}
			\item Examines micropolygon size and number
				\begin{itemize}
				\item All primitives are diced into micropolygons
				\item Shading process operates on MPs
				\item MP generation operates in eye space
				\item Subdivision done in the primitives (u,v) space
				\end{itemize}
			\item Split: Subdivision into other geometric primitives
			\item Dice: Perform the actual split into micropolygons
			\item Backdoor feature intended to incorporate raytracing
			\item Sampling
				\begin{itemize}
				\item Micropolygons are nyquist limit for their pixels 
				\item Jittered samples trade aliasing artifacts for noise
				\item Sampling can be influenced
				\end{itemize}
			\item Reconstruction functions are user choice: RiFilter
			\end{itemize}
		\end{itemize}

	\subsection{REYES Advantages and Disadvantages}
		\begin{itemize}
		\item Advantages
			\begin{itemize}
			\item Can handle arbitrary number of primitves
			\item No inversions - projections of pixel onto textures
			\item Computations can easily be vectorised (e.g. shading)
			\item No clipping calculations
			\item Frequently no texture filtering is needed
			\end{itemize}
		\item REYES Disadvantages
			\begin{itemize}
			\item No natural way to dice polygons
			\item Shading before sampling causes problems for motion blur
			\item Dicing is difficult for some types of primitives (like e.g. blobs)
			\item No coherency for large uniform objects, everything is diced into micropolygons
			\item No GI info of any kind is computed
			\end{itemize}
		\end{itemize}

	\subsection{RenderMan Interface}
		\begin{itemize}
		\item Interface between rendering and modelling 
		\item Powerful set of primitive surface types: quadric surf, polygons, parametric surfaces
		\item Hierarchical modeling, geometry
		\item Constructive solid geometry
		\item Camera model (orthographic, perspective)
		\item Generalized shading model
		\end{itemize}

		\subsubsection{Using the RM Interface}
			\begin{itemize}
			\item Two basic options exist
				\begin{itemize}
				\item Use of RM function calls from high-level language (e.g. C) implementation of the RM API
				\item Feeding archived RM function calls from a RenderMan Interface Bytestream (RIB) to a compliant renderer (Hand generated, output from modelling program)
				\end{itemize}
			\item Acutal renderers are usually non-interactive
			\item Separate preview renderes are used during the design phase
			\end{itemize}

		\subsubsection{RM Programm Structure}
			\begin{itemize}
			\item Consistent naming of API calls (Ri..)
			\item All function calls bracketed between one pair of RiBegin and RiEnd
			\item One global graphics state is maintained within this bracket
			\item All API calls modify this state
			\item API calls are frequently varargs, and have to be terminated with RI NULL
			\item Most calls deal with surface properties
			\end{itemize}

		\subsubsection{RIB File}
			\begin{itemize}
			\item Sequence of requests to the renderer
			\item No loops, branches, ...
			\item Hierarchical attributes, transformations
			\item Geometry, lights and materials are specified insidde a WorldBegin, WorldEnd block
			\item Normally RIB file contains just one frame's worth of data
			\end{itemize}

	\subsection{Shading}
		\subsubsection{Shape vs Shading}
			\begin{itemize}
			\item Shape: Geometry of object
			\item Shading
				\begin{itemize}
				\item Appearance of object in scene
				\item Defined by: light and surface specs and pos, pos and orientation of object
				\end{itemize}
			\end{itemize}

		\subsubsection{Shading pipeline}
			\begin{itemize}
			\item Three types of shaders
			\item Emission at the light source
			\item Interaction of light with surface
			\item Atmospheric effects between surface and viewpoint
			\end{itemize}

		\subsubsection{Types of Shaders}
			\begin{itemize}
			\item RenderMan Interface supports
				\begin{itemize}
				\item Light source shaders
					\begin{itemize}
					\item Calculates intensity and colour of light sent by the light source to a point on a surface
					\item Describes lightsource
					\end{itemize}
				\item Surface shaders
					\begin{itemize}
					\item Determines the colour of light reflecting from a point on a surface in a particular direction
					\item Does not have to be physically plausible
					\end{itemize}
				\item Volume shaders: Generalizes the idea of atmosphere affecting light passing through space between surface and eye
				\item Displacement shaders
					\begin{itemize}
					\item Distort geometry of basic object
					\item Difference to bump maps (surface shader): silhouette is correct
					\item Costly to evaluate
					\end{itemize}
				\item Imager shaders
					\begin{itemize}
					\item Transform already computed colours to something else 
					\item Applications: e.g. cartoonish distortions of realistic renderings
					\item Only colour information and z-Buffer data are provided
					\end{itemize}
				\item Transformation Shaders
					\begin{itemize}
					\item Similar to displacement shaders in that they modify object geometry resp. point coordinates
					\item Difference: used at a different, earlier stage of the rendering pipeline
					\item Used to transform entire objects
					\item Restricted variable set
					\end{itemize}
				\end{itemize} 
			\item Each shader has specific variables and result types
				\begin{itemize}
				\item Floats
				\item Colours: multi colour models, RGB default
				\item Points
				\item Strings
				\item Uniform vs Varying variables
					\begin{itemize}
					\item Uniform vars constant everywhere over area
					\end{itemize} 
				\end{itemize}
			\item Shadows
				\begin{itemize}
				\item Automatic shadow generation not classic RM
				\item Shadow maps prepared for each lightsource
				\item Surface shaders use this info
				\item Raytracing and GI in newer RM obsolete this
				\end{itemize}
			\item Deep Shadow Maps
				\begin{itemize}
				\item Store rep of the fractional visibility through a pixel at all possible depths
				\item Transmittance function describes light falloff
				\item Stored as array of floating-point pairs
				\item Handles volumentric effects and semi-transparent surfaces
				\end{itemize}
			\item Reflections
				\begin{itemize}
				\item Similar to depth images for the lights, reflections have to be pre-computed 
				\item Reflection maps have artefacts: no multiple inter-reflections
				\item Fast
				\item (Sort of obsoleted by raytracing on demand)
				\end{itemize}
			\item Reflection / Refraction Multipass Rendering
				\begin{itemize}
				\item Multi-pass rendering
				\item Tank shader: Each wall has unique pair of reflection and refraction camera
				\item Texture is projected
				\end{itemize}
			\item Ray Tracing On Demand
				\begin{itemize}
				\item Scanline: fast, can handle complex scenes, shadows and reflections are problematic
				\item Ray tracing can not deal with complex scenes
				\item Ray differentials
				\item First-level rays originate from REYES shading points
				\end{itemize}
			\item Implementations
				\begin{itemize}
				\item Original Pixar renderer (REYES): Micropolygon-based hybrid with raytracing capabilities
				\item BMRT: Raytracer, has disappeared after legal action was taken against author
				\item Pixie: Open-source RenderMan
				\item Realtime techniques: Ongoing research topic
				\end{itemize}
			\end{itemize}

\section{Unsolved Problems}
	\begin{itemize}
	\item First suggested by Ivan Sutherland in 1965
	\item Become focus of future developments in 70/80s
	\item When is a problem solved? e.g. RE .. theoretically solved, but unsovled practical sense
	\item Cheap and fast solutions needed
	\item Sutherland 1966
		\begin{itemize}
		\item Cheap machines with basic capability
		\item Basic interaction techniques
		\item Coupling simulation to their display
		\item Describing motion
		\item Continuous tone displays (haftoning)
		\item Making structure of drawings explicit
		\item Hidden line removal
		\item Program instrumenation and visualization
		\item Automatic placement of elements in network diagrams
		\item Workin with abstractions (scientific visualization)
		\end{itemize}
	\item Heckbert 1987
		\begin{itemize}
		\item Converting implicit models to parametric
		\item High-quality texture filtering
		\item Antialiasing
		\item Shadows without ray tracing
		\item Practical ray tracing
		\item Practical radiosity
		\item Frame-to-frame coherence
		\item Automating model culling
		\item Smooth model transitions
		\item Affordable real-time rendering hardware
		\end{itemize}
	\item Jim Blinn's 10 Unsolved Problems (More sociological or marketing issues than technical problems)
		\begin{itemize}
		\item Novely
			\begin{itemize}
			\item Simply find something new
			\item Easy problems have been solved
			\end{itemize}
		\item Education
			\begin{itemize}
			\item Learning: Keeping up with what has been done (Related to problem 1, don't reinvent the wheel)
			\item Teaching: Dissemination of new discoveries
			\item System Integration: How to use all the tricks in one production
			\item Simplicity: Make things simple
			\end{itemize}
		\item Better Pixel Arithmetic Theory
			\begin{itemize}
			\item RGBA pixel concept incomplete
			\item 3 probs
				\begin{itemize}
				\item Pre-multiplication of colour channels by alpha channel (local / global distinction)
				\item Correlated edges of foreground and background object
				\item Combining compositing operations with light reflection models
				\end{itemize}
			\item Unified field theory of pixel arithmetic
			\end{itemize}
		\item Legacy compatibility
			\begin{itemize}
			\item Technological improvements change trade-off
			\item Legacy applications and data, e.g. 3d apis, file formats
			\item How to no abandon the old while allowing the new
			\end{itemize}
		\item Arithmetic Sloppiness
			\begin{itemize}
			\item Programmers tempted to do sloppy job of pixel arithmetic for speed
			\item E.g. texture filtering: bilinear interpolation between four nearest texels (diamond shaped artifacts)
			\item Phong BRDF model
			\item How accurate do we need to be?
			\end{itemize}
		\item Antialiasing: Textures in perspective will be either too fuzzy or to jaggy
		\item A Modeling, Rendering, Animation Challenge
			\begin{itemize}
			\item 1 shape - piles of rope or string and even conceivably to protein folding
			\item Modeling is figuring out the shape of it
			\item Rendering is making picture of it
			\item Animation is figuring out how it moves with time
			\end{itemize}
		\item Finding a use for real-time 3d
			\begin{itemize}
			\item Find large-scale uses for it: Entertainment (movies, games), Engineering (CAD, CAM), Visualization
			\item Interaction and communication (GUIs, printed media, art, ecommerce, web3d and virtual communities)
			\end{itemize}
		\end{itemize}
	\item Unsolved issues in PR
		\begin{itemize}
		\item Acquisition and modeling BRDFs
		\item Reliable, accurate and cheap
		\item Render and measurement time too long
		\item Measure more samples where more accuracy needed
		\item Acquisition of geometry and surface appearance
		\item Problematic for non-diffuse and transparent surfaces or when illuminant is unknown
		\item Self-adaptive light transport
		\item Some algorithms perform better in specific situations than others
		\item Adaptive overall global illumination algorithm picks mode depending on surface, illuminations,...
		\item Scalable and robust rendering
		\item Complex scenes without user intervention
		\item Especially important in interactive and dynamic applications, e.g. games
		\item Geometry-independent rendering
		\item Currently many ray-objects interection calculations
		\item What if geometry is not known explicitly (e.g. light field, photographs)
		\item Radiometric accuracy main dirven force
		\item Usually not necessary
		\item Psychoperceptual rendering: Perceptual correct images
		\item Viewer might still judge the image to be realistic
		\item Integration with real elements
		\item Put real objects in virtual scene and virtual object in real scene, e.g. with projectors
		\item Blend between real and virtual elements
		\end{itemize}
	\item Ultimate Photorealistic Renderer
		\begin{itemize}
		\item Interactivity
		\item Any material, any geometry (pure specular to pure diffuse)
		\item Many different input models
		\item Realism slider
		\end{itemize}
	\end{itemize}

\listofalgorithms

\end{document}
