\documentclass{article}
\textwidth 7 in
\oddsidemargin -0.25 in
\textheight 9 in
\topmargin -0.5in
\title{Review Materials for the Computer Graphics Qualifying Exam\\ University of Wisconsin, Madison}
\author{Matt Anderson}
\date{September 22, 2002}
\newcommand{\R}{\mathcal{R}}
\usepackage[dvips]{color}
\usepackage{fancybox}
\usepackage{supertabular}
\usepackage{graphicx}
\definecolor{gray70}{gray}{0.7}
\definecolor{abcolor}{gray}{0.85}

\begin{document}
\maketitle

\tablehead{\hline\hline}
\tabletail{\hline\hline}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Core Topics}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Signal Processing}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Perlin Noise}

%================================================================
\subsubsection{An Image Synthesizer \hfill{\tt Perlin.1985.AIS}}


\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\parbox{6in}{
      We introduce the concept of a Pixel Stream Editor.  This forms the basis for an interactive
      synthesizer for designing highly realistic Computer Generated Imagery.  The designer works
      with an interactive Very High Level programming environment which provides a very fast
      concept/implement/view iteration cycle.

      Naturalistic visual complexity is built up by composition of non-linear functions, as opposed
      to the more conventional texture mapping or growth model algorithms.  Powerful primitives are
      included for creating controlled stochastic effects.  We introduce the concept of "solid
      texture" to the field of CGI.

      We have used this system to create very convincing representations of clouds, fire, water,
      stars, marble, wood, rock, soap films and crystal.  The algorithms created with this paradigm
      are generally extremely fast, highly realistic, and asynchronously parallelizable at the pixel
      level.
}}\end{quote}


\paragraph{Notes}
\begin{itemize}

  \item    Perlin defines a {\em Pixel Stream Editing Language}, which filters each output pixel
           with an expression or program.

  \item    Perlin defines the idea of a {\em solid texture}, which is a function whose domain is the
           entirety of $\R^3$ space, a {\em space function}.  We can {\em carve} solid objects
           from the solid texture, using its value at the point in space as the texture color.
           Shape and texture become independent.

  \item    Perlin defines his {\tt Noise} function.  He creates an integer lattice, and associates a
	   pseudo-random gradient/value pair with each lattice point.  The noise function is equal
	   to the value at a lattice point, or a cubic polynomial interpolation of lattice equation
	   coefficients when between lattice points.

  \item    The function {\tt Dnoise} is also briefly described, which is the valued as the vector
           which is the instantaneous rate of change in the noise function.

  \item    He then goes on to show how one can create marble, fire, and water, cloud and bubble-like
           effects with the language and the {\tt Noise} function.
\end{itemize}


%================================================================
\subsubsection{Improving Noise \hfill{\tt Perlin.2002.IN}}

\paragraph{Abstract}

\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
     Two deficiencies in the original Noise algorithm are corrected: second order interpolation
     discontinuity and unoptimal gradient computation.  With these defects corrected, Noise both
     looks better and runs faster.  The latter change also makes it easier to define a uniform
     mathematical reference standard.
\end{minipage}}\end{quote}
%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Rotations}

%================================================================
\subsubsection{Animating Rotations with Quaternion Curves \hfill{\tt Shoemake.1985.ARW}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Solid bodies roll and tumble through space.  In computer animation, so do cameras.  The
      rotations of these objects are best described using a four coordinate system, quaternions, as
      is shown in this paper.  Of all quaternions, those on the unit sphere are most suitable for
      animation, but the question of how to construct curves on spheres has not been much explored.
      This paper gives one answer by presenting a new kind of spline curve, created on a sphere,
      suitable for smoothing in-betweening (i.e. interpolating) sequences of arbitrary rotations.
      Both theory and experiment show that the motion generated is smooth and natural, without
      quirks found in earlier methods.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{Practical Parameterizations of Rotations Using the Exponential Map\hfill{\tt Grassia.1998.PPO}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Parameterizing three degree-of-freedom (DOF) rotations is difficult to do well.  Many graphics
      applications demand that we be able to compute and differentiate positions and orientations of
      articulated figures with respect to their rotational (and other) parameters, and interpolate
      orientations.  Widely used parameterizations such as Euler angles and quaternions are well
      suited to only a few of these operations.  The exponential map maps a vector in $R^3$
      describing the axis and magnitude of a three-DOF rotation to the corresponding rotation.
      Several graphics researchers have applied it with limited success to interpolation of
      orientations, but it has been virtually ignored with respect to the other operations mentioned
      above.  In this paper we present formulae for computing, differentiating, and integrating
      three-DOF rotations with the exponential map.  We show that our formulation is numerically
      stable in the face of machine precision issues, and that for most applications all
      singularities in the map can be avoided through a simple technique of dynamic
      reparameterization.  We demonstrate how to use the exponential map to solve both the "freely
      rotation body" problem, and the important ball-and-socket joint required to accurately model
      should and hip joints in articulated figures.  Examining several common graphics applications,
      we explain the benefits of our formulation of the exponential map over Euler angles and
      quaternions, including robustness, small state vectors, lack of explicit constraints, good
      modeling capabilities, simplicity of solving ODEs, and good interpolation behavior.

\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item There are five primitive means of describing and controlling rotations in graphics:
           forward kinematics, inverse kinematics, forward and inverse dynamics, and spacetime
           optimization.

     \item Applications built on these primitives will require some of the following operations:
	\begin{enumerate}
	   \item The ability to compute positions and orientations of points on body parts as
	         functions of the parameters, which is one aspect of forward kinematics
	   \item the existence of and the ability to compute derivatives of these positions and
	         orientations with respect to the parameters, which is necessary for inverse
	         kinematics, dynamics, and spacetime.
	   \item the ability to integrate ODEs in parameter space, which is also required by inverse
	         kinematics, dynamics, and spacetime.
	   \item the ability to interpolate smoothly and controllably between sequences of parameter
	         keyframes.
	   \item the ability to combine rotations, either in parameter space, or in rotation space
	         itself.
	   \item the existence of an inverse operation that calculates the parameter values from the
	         corresponding rotation.
	\end{enumerate}

     \item {\bf $\bf 3\times 3$ Rotation Matrices}.  If used directly, would require six non-linear
           constraints to ensure that the matrix remained in SO(3).  Similarly, each ODE integration
           step would require the rotation be re-orthonormalized.
     \item {\bf Euler Angles}.  Gimbal lock.  
     \item {\bf Quaternions}.  Potential to do very good interpolation.  Hard to take derivatives,
           integrate.
     \item {\bf The Exponential Map}.  Maps a vector in $\R^3$ describing an axis and magnitude of a
           three DOF rotation to the corresponding rotation.  The exponential map has singularities
           on the spheres of radius $2n\pi$, for $n\in \{1, 2, 3, \dots\}$.
\end{itemize}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Image Processing and Manipulation}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Image Processing}

%================================================================
\subsubsection{Fundementals of Texture Mapping and Image Warping \hfill{\tt Heckbert.1989.FOT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The applications of texture mapping in computer graphics and image distortion in image
      processing share core fundamental techniques.  We explore two of these techniques, the
      two-dimensional geometric mappings that arise in the parameterization and projection of
      textures onto surfaces, and the filters necessary to eliminate aliasing when an image is
      resampled during texture mapping or warping.  With respect to mappings, this work presents a
      tutorial on three common classes of mapping: the affine, bilinear, and projective.  For
      resampling, this work develops a new theory describing the ideal, space variant antialiasing
      filter for signals warped and resampled according to an arbitrary mapping.  Efficient
      implementations of the mapping and filtering techniques are discussed and demonstrated.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
    \item Problems occur if one linearly interpolates $(u,v)$ and this is inconsistent with the
          geometry transformation for vertices.

    \item Affine mappings are linear mappings plus a translation.

    \item The reverse mapping for an affine transformation can be found by inverting the affine
          transformation matrix.

    \item Affine mapping maps any triangle $\rightarrow$ any triangle, or rectangle $\rightarrow$
          parallelogram.

    \item Bilinear mapping maps a square $\rightarrow$ quadrilateral.

    \item Bilinear mapping preserves horizontal and vertical lines, but not at other orientations.
          Composition is biquadratic, not bilinear.  Inverse transform is multi-valued, and more
          difficult to compute.

    \item Projective mapping is a mapping from a plane, through a point to another plane.

    \item The general form of a projective mapping is a rational linear mapping:
	\[x = \frac{au+bv+c}{gu+hv+i} \ \ \ \ \ \ \ \ y = \frac{du+ev+c}{gu+hv+i}\]

    \item Projective mappings preserve the {\em cross-ratio} of points, and map lines at all
          orientations into lines.

    \item The inverse of a projective mapping is a projective mapping.  The adjoint matrix is a
          scalar multiple of the inverse, and can be used in its stead (if the matrix is not
          invertible, for example).

    \item A projective mapping can be inferred from 4 $2D$ point correspondences by solving a linear
          system.  It can also be done as special cases, with significantly better speed than linear
          systems solving.

\end{itemize}


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Image Compositing}

%================================================================
\subsubsection{Compositing Digital Images \hfill{\tt Porter.1984.CDI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Most computer graphics pictures have been computed all at once, so that the rendering program
      takes care of all computations relating to the overlap of objects.  There are several
      applications, however, where elements must be rendered separately, relying on compositing
      techniques for the anti-aliased accumulation of the full image.  This paper presents the case
      for four-channel pictures, demonstrating that a matte component can be computed similarly to
      the color channels.  The paper discusses guidelines for the generation of elements and the
      arithmetic for their arbitrary compositing.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{Blue Screen Matting \hfill{\tt Smith.1996.BSM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      A classical problem of imaging - the matting problem - is separation of a non-rectangular
      foreground image from a (usually) rectangular background image - for example in a film frame,
      extraction of an actor from a background scene to allow substitution of a different
      background.  Of the several attacks on this difficult and persistent problem, we discuss here
      only the special case of separating a desired foreground image from a background of a
      constant, backing color.  This backing color has often been blue, so the problem, and its
      solution, have been called blue screen matting.  However, other backing colors, such as yellow
      or (increasingly) green, have also been used, so we often generalize to constant color
      matting.  The mathematics of constant color matting is presented and proven to be unsolvable
      as generally practiced.  This, of course, flies in the face of the fact that the technique is
      commonly used in film and video, so we demonstrate constraints on the general problem that
      lead to solutions, or at least significantly prune the search space of solutions.  We shall
      also demonstrate that an algorithmic solution is possible by allowing the foreground object to
      be shot against two constant backing colors - in fact, against to completely arbitrary
      backings so long as they differ somewhere.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The Matting Problem: Given $C_f$ and $C_b$ at corresponding points, and $C_k$, a known
           backing color, and assuming $C_f = C_0 + (1 - \alpha_0) C_k$, determine $C_0$ which then
           gives the composite color $C = C_0 + (1 - \alpha_0) C_b$ at the corresponding point, for
           all points that $C_f$ and $C_b$ share in common.

     \item So, the goal is to extract objects {\em and} find their transparencies.

     \item They were inspired to work on this problem by the expiration of the Vlahos patents.  One
           of their purposes was to review the field -- the general one of pulling a matte from a
           constant color shot plus related subproblems such as blue spill, blacking impurities, and
           backing shadows.

     \item Their principal idea is that an image from which a matte is to be pulled can be
           represented by a model of two images, an uncomposited foreground image and a backing
           color image, linearly combined using the alpha channel of the foreground object.  Their
           results are deduced from this model.

     \item They introduced an algorithmic solution, the triangle solution, by adding a new step to
           the blue screen process as usually practiced: Another shot of the foreground object
           against a second backing color.  This {\em multi-background} technique cannot be used for
           moving foreground objects, because it requires reproducibility.  The backing colors must
           be different from each other in every pixel.   Illumination must also be the same in both
           images.

     \item They touched on the blue spill / blue flare problem, and propose the idea of modeling
           blue spill by an additional blue spill image, with its own alpha.

\end{itemize}





%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\pagebreak
\subsection{Image Warping}

%================================================================
\subsubsection{Feature-Based Image Metamorphosis \hfill{\tt Beier.1992.FIM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      A new technique is presented for the metamorphosis of one digital image into another.  The
      approach gives the animator high-level control of the visual effect by providing natural
      feature-based specification and interaction.  When used effectively, this technique can give
      the illusion that the photographed or computer generated subjects are transforming in a fluid,
      surrealistic, and often dramatic way.  Comparisons with existing methods are drawn, and the
      advantages and disadvantages of each are examined.  The new method is then extended to
      accommodate keyframed transformations between image sequences for motion image work.  Several
      examples are illustrated with resulting images.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item They use a ``reverse mapping'', calculating a pixel in the destination image by mapping
           back to the source image, thus leaving no holes.

     \item A pair of corresponding lines in the source and destination images defines a coordinate
           mapping from the destination pixel coordinate ${\bf X}$ to the source image pixel
           coordinate ${\bf X'}$.

     \item For each corresponding pair of lines, ${\bf u}$ (from 0 to 1) parameterizes the distance
           along a line, and ${\bf v}$ parameterizes distance from the line in the perpendicular
           direction.

     \item To do the transformation, for each pixel ${\bf X}$ in the destination image:
	\begin{enumerate}
	   \item find the corresponding ${\bf u, v}$
	   \item find the ${\bf X'}$ in the source image for that ${\bf u,v}$
	   \item {\tt destinationImage(${\bf X}$) = sourceImage(${\bf X'}$)}
	\end{enumerate}

     \item For multiple pairs of lines, one can define constants $a, b,$ and $p$ which influence the
           behavior of the algorithm.  Very small values of $a$ result in very precise placement
           around lines, larger values lead to smoother transitions.  Variable $b$ defines how the
           relative strength of a line falls off with distance.  Variable $p$ determines the
           weighting of a line relative to its length.

	\[ weight = \left(\frac{length\ ^p}{a + dist}\right)^b \]

	   The position of source image point ${\bf X'}$ is then computed as a weighted average of
	   the individual line mappings.

     \item For an image morph, for each both images are distorted by the mapping above, and
           cross-dissolved to produce a morph sequence.

     \item This technique is purported to be much more expressive than mesh warping.  Because it is
           a global technique though, speed is potentially vastly reduced, and local control can be
           an issue.

%	\begin{eqnarray*}
%		{\bf u} & = & \frac{({\bf X}-{\bf P})\cdot({\bf Q}-{\bf P})}{||{\bf Q}-{\bf P}||^2}\\
%		{\bf v} & = & \frac{({\bf X}-{\bf P})\cdot Perpendicular({\bf Q}-{\bf P})}%
%				   {||{\bf Q}-{\bf P}||}\\
%		{\bf X'}& = & 	{\bf P'} + %
%				{\bf u} \cdot ({\bf Q'} - {\bf P'}) +%
%				\frac{{\bf v}\cdot Perpendicular({\bf Q'}-{\bf P'})}{||{\bf Q'}-{\bf P'}||}
%	\end{eqnarray*}

\end{itemize}


%================================================================
\pagebreak
\subsubsection{Image Morphing \hfill{\tt Wolberg.1998.IMA}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Image morphing has received much attention in recent years.  It has proven to be a powerful
      tool for visual effects in film and television, enabling the fluid transformation of one
      digital image into another.  This paper surveys the growth of this field and describes recent
      advances in image morphing in terms of feature specification, warp generation methods, and
      transition control.  These areas relate to the ease of use and the quality of results.  We
      describe the role of radial basis functions, thin plate splines, energy minimization, and
      multilevel free-form deformations in advancing the state-of-the-art in image morphing.  Recent
      work on a generalized framework for morphing among multiple images is described.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item Image morphing consists of:
	\begin{itemize}
	   \item Feature correspondence creation
	   \item Creation of mapping function from feature correspondences (warp functions)
	   \item Intermediate images are created by warping each image into alignment and
	         cross-dissolving between them
	\end{itemize}

     \item Mesh warping:
	\begin{itemize}
	   \item pioneered at ILM in 1988
	   \item mesh is aligned with features of both images, with the locations of mesh vertices
	         being placed at corresponding feature points
	   \item mesh vertex locations ($M$) are linearly interpolated between source ($M_s$) and
	         target ($M_t$) meshes; warp function from $I_s$ to $I$ defined by mesh faces in
	         $M_s$ and $M$, and correspondingly for $I_t$.  Bicubic spline interpolation was used.
	\end{itemize}

     \item Field morphing:
	\begin{itemize}
	   \item pairs of corresponding lines constitute features
	   \item warp function defined for a point as a weighted sum of displacements from lines,
	         weighted by line length and distance from a given line
	   \item more expressive than mesh warping, much slower than mesh warping, additional
	         features may have to be specified to counter unexpected displacements.
	\end{itemize}

     \item Radial basis functions / thin plate splines:
	\begin{itemize}
	   \item Consider $M$ corresponding feature points labeled $(u_k,v_k)$ in the source image
	         and $(x_k,y_k)$ in the destination image.  Deriving warp functions that map points
	         is equivalent to determining two smooth surfaces that pass through the point sets
	         $(x_k,y_k,u_k)$ and $(x_k,y_k,v_k)$.  This allows us to utilize the scattered data
	         interpolation literature.
	\end{itemize}
\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\pagebreak
\subsection{Multi-resolution Image Methods}

%================================================================
\subsubsection{A Multiresolution Spline with Application to Image Mosaics \hfill{\tt Burt.1983.AMS}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We define a multiresolution spline technique for combining two or more images into a larger
      image mosaic.  In this procedure, the images to be splined are first decomposed into a set of
      band-pass filtered image component images.  Next, the component images in each spatial
      frequency band are assembled into a corresponding band-pass mosaic.  In this step, component
      images are joined using a weighted average within a transition zone which is proportional in
      size to the wavelengths represented in the band.  Finally, these band-pass mosaic images are
      summed to obtain the desired image mosaic.  In this way, the spline is matched to the scale of
      the features within the images themselves.  When coarse features occur near borders, these are
      blended gradually over a relatively large distance without blurring or otherwise degrading
      finer image details in the neighborhood of the border.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{Pyramidal Parametrics \hfill{\tt Williams.1983.PP}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The mapping of images onto surfaces may substantially increase the realism and information
      content of computer-generated imagery.  The projection of a flat source image onto a curved
      surface may involve sampling difficulties, however, which are compounded as the view of the
      surface changes.  As the projected scale of the surface increases, interpolation between the
      original samples of the source image is necessary; as the scale is reduced, approximation of
      multiple samples in the source is required.  Thus a constantly changing sampling window of
      view-dependent shape must traverse the source image.

      To reduce the computation implied by these requirements, a set of prefiltered source images
      may be created.  This approach can be applied to particular advantage in animation, where a
      large number of frames using the same source image must be generated.  This paper advances a
      "pyramidal parametric" prefiltering and sampling geometry which minimizes aliasing effects and
      assures continuity within and between target images.

      Although the mapping of texture onto surfaces is an excellent example of the process and
      provided the original motivation for its development, pyramidal parametric data structures
      admit of wider application.  The aliasing of not only surface texture, but also highlights and
      even the surface representations themselves, may be minimized by pyramidal parametric means.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The mip-mapping paper.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Modeling}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Parametric Surfaces}

%================================================================
\subsubsection{Subdivision for Modeling and Animation \hfill{\tt Zorin.2000.SFM}}

\paragraph{Notes}
\begin{itemize}
     \item Subdivision elegantly addresses:
	\begin{itemize}
	   \item arbitrary topology
	   \item scalability - adaptive approximation / LoD
	   \item uniformity of representation
	   \item numerical stability - suitable for numerical simulation
	   \item code simplicity
	\end{itemize}

     \item A rule is affinely invariant if its weights sum to one.

     \item \textcolor{red}{\bf Section 2.2.3 might be worth another look.}

     \item It turns out that if you continue to apply the refinement equation, that the control
           points of a B-Spline converge to the spline curve itself.

     \item A subdivision scheme consists of a set of matrices, one for each valence.

     \item To do creases, crease edges are tagged as boundary edges?  This way, they don't depend on
           `interior' edges.
\end{itemize}
\textcolor{red}{\bf {\tt Zorin.2000.SFM} probably needs some more work.}



%================================================================
\subsubsection{Subdivision Surfaces in Character Animation \hfill{\tt DeRose.1998.SSI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The creation of believable and endearing characters in computer graphics presents a number or
      technical challenges, including the modeling, animation and rendering of complex shapes such
      as heads, hands, and clothing.  Traditionally these shapes have been modeled with NURBS
      surfaces despite the severe topological restrictions that NURBS impose.  In order to move
      beyond these restrictions, we have recently introduced subdivision surfaces into our
      production environment.  Subdivision surfaces are not new, but their use in high-end CG
      productions has been limited.

      Here we describe a series of developments that were required in order for subdivision surfaces
      to meet the demands of high-end production.  First, we devised a practical technique for
      constructing provably smooth variable-radius fillets and blends.  Second, we developed methods
      for using subdivision surfaces in clothing simulation including a new algorithm for
      constructing smooth scalar fields on subdivision surfaces, thereby enabling the use of a wider
      class of programmable shaders.  These developments, which were used extensively in our
      recently completed short film Geri's game, have become a highly valued feature in our
      production environment.
\end{minipage}}\end{quote}

\paragraph{Issues}
\begin{enumerate}
     \item Constructing smooth fillets and blends
     \item Subdivision surfaces in clothing simulation
     \item Method of constructing smooth scalar field on surface (shaders)
\end{enumerate}
\paragraph{Notes}
\begin{itemize}
     \item (Motivation:) Historically, in character animation, one uses a patchwork of trimmed NURBS
           surfaces to model/animate characters.  Trimming however is expensive and prone to error,
           and the patchwork is difficult to keep seamless while animating.  NURBS surfaces also
           have a global planar parameterization, which restricts their topology to a
           sheet/cylinder/torus.

     \item Catmull-Clark was chosen by Pixar because they strictly generalize to uniform tensor
           product B-Splines, and because quads are a more natural modeling primitive.

     \item (Hybrid Subdivision:) To create variably sharp edges, they assign a sharpness value $s$
           to an edge.  The edge is then subdivided $s$ times using the infinitely sharp subdivision
           rule, and then to the limit with the smooth rule.  If $s$ is not an integer, they
           calculate geometry for $\lfloor s\rfloor$ and for $\lceil s\rceil$, and linearly
           interpolate.  They have a more complex form for varying sharpness along a crease.

     \item (Cloth Energy:) They use a finite difference approach, and approximate clothing with a
           mass-spring model, with mass at control points.  They have three energy terms.  They ad
           an anti-stretch term along the edges of the control mesh, fixed rest-length springs.  To
           resist diagonal skew, they ad diagonal springs with an energy term which is the product
           of the diagonally crossing spring energies.  Finally, to resist bending, they add an
           anti-bend term along the "virtual threads".  All of these terms can be varied with the
           scalar field over the surface.

     \item (Cloth Collisions:) The construct a bounding volume tree over the surface, using a
           coarsening process to define a hierarchy.  It is updated, bottom up, each time the
           control mesh is deformed.

     \item (Scalar Fields:) They define smooth scalar fields over the surface by subdividing
           $(x,y,z,s,t)$ instead of $(x,y,z)$.  Texture coordinates are a scalar field.

\end{itemize}



%================================================================
\subsubsection{Exact Evaluation of Catmull-Clark Subdivision Surfaces \hfill{\tt Stam.1998.EEO}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      In this paper we disprove the belief widespread within the computer graphics community that
      Catmull-Clark subdivision surfaces cannot be evaluated directly without explicitly
      subdividing.  We show that the surface and all its derivatives can be evaluated in terms of a
      set of eigenbasis functions which depend only on the subdivision scheme and we derive
      analytical expressions for these basis functions.  In particular, on the regular part of the
      control mesh where Catmull-Clark surfaces are bi-cubic B-splines, the eigenbasis is equal to
      the power basis.  Also, our technique is both easy to implement and efficient.  We have used
      our implementation to compute high quality curvature plots from subdivision surfaces.  The
      cost of our evaluation scheme is comparable to that of a bi-cubic spline.  Therefore, our
      method allows many algorithms developed for parametric surfaces to be applied to Catmull-Clark
      subdivision surfaces.This makes subdivision surfaces an even more attractive tool for
      free-form surface modeling.
\end{minipage}}\end{quote}
\paragraph{Notes}
\begin{itemize}
     \item They show that a Catmull-Clark subdivision surface and its derivatives can be evaluated
           in terms of a set of eigenbasis functions which depend only on the subdivision scheme,
           and they derive analytical expressions for these functions.

     \item The technique is based on work on smoothness theorems for subdivision surfaces.  The
           subdivision is transformed to its eigenspace, where subdivision corresponds to scaling
           its eigenvectors by its eigenvalues.

     \item The tricky bit are those surface patches that feature an extraordinary vertex, as those
           without are simply uniform B-spline patches.

     \item They order the vertices in a particular way, to give the subdivision matrix a particular
           structure.  They then do some fancy-schmancy eigen analysis on that matrix, and end up
           with a set of eigenbasis functions $\rho_i$.  Because of a special relationship of
           Catmull-Clark subdivision and the power basis, they can re-write the evaluation of a
           surface patch as $s(u,v) = \sum_{i=1}^k \rho_i(u,v) p_i$, where $p_i$ are the projected
           control points.

     \item To implement they precompute the eigenstructure of the subdivision scheme, and save it.
           They must then use the {\tt ProjectPoints} function to initialize or after each change to
           the control mesh, and then can quickly use the {\tt EvalSurf} function to find the
           location of a point on a surface.

     \item The method can be extended to other subdivision schemes, easily to Loop's triangular
           scheme, and with some cleverness to Doo-Sabin.

\end{itemize}




%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Multiresolution Surface Methods}

%================================================================
\subsubsection{Hierarchical B-Spline Refinement \hfill{\tt Forsey.1988.HBR}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Refinement is usually advocated as a means of gaining finer control over a spline curve or
      surface during editing.  For curves, refinement is a local process.  It permits the change of
      control vertices and subsequent editing of fine detail in one region of the curve while
      leaving control vertices in other regions unaffected.  For tensor-product surfaces, however,
      refinement is not local in the sense that it causes control vertices far from a region of
      interest to change as well as changing the control vertices that influence the region.
      However, with some care and understanding it is possible to restrict the influence of
      refinement to the locality at which an editing effect is desired.  We present a method of
      localizing the effect of refinement through the use of overlays, which are hierarchically
      controlled subdivisions.  We also introduce two editing techniques that are effective when
      using overlays: one is direct surface manipulation through the use of edit points and the
      other is offset referencing of control vertices.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item In the conventional formulation, "refinement" necessitates refining the entire spline
           surface, not just the area of interest.

     \item In an initial formulation, a patch of surfaces is replaces with a refined surface that
           has the same geometry.  The center or interior of the refined region can then be edited,
           and continuity will be preserved.  The refined region replacement can grow to allow
           larger interiors for editing.

     \item To allow hierarchical editing, a second formulation uses the refined surface overlays as
           offsets rather than replacements.  Expressive power is unchanged, and we can now make
           edits in a refined region at multiple scales.

     \item Because the hierarchy of control points is cumbersome to work with, they implement direct
           manipulation of the surface at multiple scales.  Edits of the surface is translated to
           sensible motion of the control points.  They implement this by only allowing points
           maximally influenced by some control vertex to be picked and manipulated, and then only
           translating that control point to create the motion.
\end{itemize}

%================================================================
\pagebreak
\subsubsection{Progressive Meshes \hfill{\tt Hoppe.1996.PM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Highly detailed geometric models are rapidly becoming commonplace in computer graphics.  These
      models, often represented as complex triangle meshes, challenge rendering performance,
      transmission bandwidth, and storage capacities.  This paper introduces the progressive mesh
      (PM) representation, a new scheme for storing and transmitting arbitrary triangle meshes.
      This efficient, lossless, continuous-resolution representation addresses several practical
      problems in graphics: smooth geomorphing of level-of-detail approximations, progressive
      transmission, mesh compression, and selective refinement.

      In addition, we present a new mesh simplification procedure for constructing a PM
      representation from an arbitrary mesh.  The goal of this optimization procedure is to preserve
      not just the geometry of the original mesh, but more importantly its overall appearance as
      defined by its discrete scalar appearance attributes such as material identifiers, color
      values, normals, and texture coordinates.  We demonstrate construction of the PM
      representation and its applications using several practical models.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Motivating Issues: mesh simplification, LOD-approximation, progressive transmission, mesh
           compression, and selective refinement.

     \item In PM-form, a mesh is stored as a coarse base mesh $M^0$ and $n$ detail meshes that show
           how to refine $M^0$ to the original mesh.

     \item A mesh is represented as $M = (K,V,D,S)$, where $K$ is the simplical complex specifying
           connectivity, $V$ is the vertex positions, $D$ is the discrete attributes associated with
           the faces, and $S$ is the set of scalar attributes associated with the corners $(v,f)$ of
           $K$.

     \item Hoppe uses edge collapses for coarsening, and vertex-splits for refinement.
           Edge-collapse and vertex-split need to be annotated with some additional information,
           such as destination vertex positions.

     \item A PM-mesh is represented by the coarse mesh $M^0$ and n vertex-split records.  The vertex
           splits may be animated to prevent popping.  Progressive transmission is done by
           transmitting the coarse mesh and then a stream of vertex-split records.

     \item Thoughtful construction and compression techniques similar to {\tt Deering.1995.GC} (see
           \ref{Deering.1995.GC}) allow PM-meshes to be stored in a comparable amount of space to
           other compressed formats.

     \item Selective refinement is possible by only performing some of the vertex-splits.  The
           closest ancestor of a vertex must be present in the mesh, and then some "should-refine"
           criteria must be met.

     \item The coarsening process is based on the mesh optimization work in {\tt Hoppe.1993.MO}, and
           is posed as an energy minimization problem.  The energy metric used is:

        \[E(M) = E_{dist}(M) + E_{spring}(M) + E_{scalar}(M) + E_{disc}(M)\]

     \item $E_{dist}$ and $E_{spring}$ are used to preserve surface geometry.  $E_{scalar}$ measures
           the accuracy of the scalar attributes, and $E_{disc}$ measures the geometric accuracy of
           the discontinuity curves.
\end{itemize}


%================================================================
\pagebreak
\subsubsection{Surface Simplification Using Quadric Error Metrics \hfill{\tt Garland.1997.SSU}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Many applications in computer graphics require complex, highly detailed models.  However, the
      level of detail actually necessary may vary considerably.  To control processing time, it is
      often desirable to use approximations in place of excessively detailed models.

      We have developed a surface simplification algorithm which can rapidly produce high quality
      approximations of polygonal models.  The algorithm uses iterative contractions of vertex pairs
      to simplify models and maintains surface error approximations using quadric matrices.  By
      contracting arbitrary vertex pairs (not just edges), our algorithm is able to join unconnected
      regions of models.  This can facilitate much better approximations, both visually and with
      respect to geometric error.  In order to allow topological joining, our system also supports
      non-manifold surface models.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item They do not make any assumption about surfaces being manifold, and expect their algorithm
           will regularly generate non-manifold surfaces.

     \item They use an iterative pair contraction, $(v_1,v_2)\rightarrow v'$, $v_1$ and $v_2$ are
           moved to a new position, all incident edges are connected to $v_1$, $v_2$ is deleted, and
           degenerate edges/faces are culled.

     \item (Pair Selection) $(v_1,v_2)$ is a valid pair if $(v_1,v_2)$ is an edge, or \(||v_1 -
           v_2|| < t\), where $t$ is some threshold parameter.  When $(v_1,v_2)\rightarrow v'$, $v'$
	   must become both $v_1$ and $v_2$ for pair purposes.  A $t=0$ is then edge contraction.

     \item They define the error at a vertex $v = [v_x v_y v_z 1]^T$ to be the quadric form
           $\Delta(v) = v^T Q v$.  For a contraction $(v_1,v_2)\rightarrow v'$, $Q' = Q_1+Q_2$.

     \item To choose the target point for $v'$, we can optimally compute this as a linear
           optimization if the matrix $Q'$ is invertible.  If it is not, we choose the best position
           from the midpoint and the endpoints.

     \item The Algorithm:
	\begin{enumerate}
           \item Compute Q for all initial vertices
           \item Select all valid pairs
           \item Compute the optimal contraction target for each valid pair.  The error of a
                 contraction becomes that cost.
           \item Place all valid pairs on a heap by minimum cost
           \item Iteratively remove least-cost pair from heap, update pairs involving $v_1$.
	\end{enumerate}

     \item The error metric for a vertex is its distance from the planes containing its adjacent
           triangle faces.  This can be encoded in a matrix, and the set of planes encoded can be
           unioned by adding the matrices.  The initial matrices Q are the sums of all the matrices
           for distances from the incident triangles of each vertex.

     \item Boundaries can be preserved by generating additional constraint planes, weighting them
           heavily, and adding them to the inital error quadrics.  Color discontinuities are
           examples of such a boundary.

     \item Mesh inversion is prevented by penalizing a contraction if it flips the normal of a face.
\end{itemize}



%================================================================
\subsubsection{Concepts and Algorithms for Polygonal Simplification \hfill{\tt Cohen.1999.CAA}}

\paragraph{Notes}
\begin{itemize}
     \item The common formulations of the simplification problem:
	\begin{itemize}
           \item min-\# problem: given some error bound, $\epsilon$, and some input model, $I$,
                 compute thee minimum complexity approximation, $A$, such that no point of $A$ is
                 further than $\epsilon$ distance from $I$ and vice versa
           \item min-$\epsilon$ problem: Given some target complexity, $n$, and some input model,
                 $I$, compute the approximation, $A$, with minimum error, $\epsilon$.
	\end{itemize}

     \item Computing optimal or even near optimal solutions may be very hard.  Most algorithms in
           graphics literature use greedy, local heuristics.

     \item Local Operations:
	\begin{itemize}
           \item Vertex Remove (then fill holes/retriangulate)
           \item Edge Collapse (remove edge, join vertices, place new vertex, remove degenerate
                 edges/faces)
           \item Face Collapse (like edge collapse, faster, coarser)
           \item Vertex Cluster (vertices w/i region joined, fast, quality issues)
           \item Generalized Edge Collapse (or vertex-pair)
           \item Un-Subdivide (coarsen a subdivision surface)
	\end{itemize}

     \item Topological Considerations:
	\begin{itemize}
           \item Manifold vs. Non-Manifold
           \item Topology Preservation (sometimes good, sometimes bad)
	\end{itemize}

     \item Level-of-Detail Representations:
	\begin{itemize}
           \item Static LoD - collection of static meshes, transitions are discrete, blended, or
                 morphing.
           \item Dynamic LoD - progressive meshes, vertex hierarchies, MRA / subdivision techniques
	\end{itemize}

     \item Comparison: Static LoD allows retained mode rendering, but has transition issues.
           Dynamic LoD requires some visualization compute time, and uses immediate mode rendering

     \item Error Metrics:
	\begin{itemize}
           \item Hausdorff Distance - $H(A,B) = \max(h(A,B),h(B,A))$, where \(h(A,B) = \max_{a\in
                 A}\min_{b\in B} ||a-b||\).
           \item Mapping Distance - take topology and LoD into account?
           \item Mesh Optimization - use distance of point samples on original mesh to any point on
                 simplified mesh
           \item Vertex Clustering - Lay uniform grids over models and cluster w/i grid cells,
                 Hausdorff distance must be less than cell size; very conservative metric
           \item Superfaces - merge adjacent triangles, simplify, retriangulate... how is this a
                 metric?
           \item Error Tolerance Volumes - uses error volumes built around simplified surface
           \item Simplification Envelopes - precomputes conservative envelopes which are tested for
                 intersection against during simplification.
           \item Error Quadrics - distance from triangle planes, cleverly encoded
           \item Mapping Error - measure bijective (one-to-one and onto) mapping onto plane before
                 and after simplification
           \item Hausdorff Error - one-sided measure of Hausdorff distance
           \item Memory-Efficient Simplification - measure only incremental, local changes in
                 surface
	\end{itemize}
     \item Appearance attribute preservation:
	\begin{itemize}
           \item Scalar Field Deviation
           \item Color Preservation
           \item Normal Vector Preservation
	\end{itemize}
\end{itemize}


%================================================================
\subsubsection{Multiresolution Signal Processing for Meshes \hfill{\tt Guskov.1999.MSP}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We generalize basic signal processing tools such as downsampling, upsampling, and filters to
      irregular connectivity triangle meshes.  This is accomplished through the design of a
      non-uniform relaxation procedure whose weights depend on the geometry and we show its
      superiority over  existing schemes whose weights depend only on connectivity.  This is
      combined with know mesh simplification methods to build subdivision and pyramid algorithms.
      We demonstrate the power of these algorithms through a number of application examples
      including smoothing, enhancement, editing, and texture mapping.
\end{minipage}}\end{quote}


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Spatial Deformation}

%================================================================
\subsubsection{Free-Form Deformations of Solid Geometric Models \hfill{\tt Sederberg.1986.FDO}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      A technique is presented for deforming solid geometric models in a free-form manner.  The
      technique can be used with any solid modeling system, such as CSG or B-rep.  It can deform
      surface primitives of any type or degree: planes, quadrics, parametric surface patches, for
      example.  The deformation can be applied either globally or locally.  Local deformations can
      be imposed with any degree of derivative continuity.  It is also possible to deform a solid
      model in such a way that its volume is preserved.

      The scheme is based on trivariate Bernstein polynomials, and provides the designer with an
      intuitive appreciation for its effects.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Forsey describes this work thusly:
	\begin{quote}
	      Sederberg and Parry embed surfaces in a trivariate spline volume, distort the volume
	      by control vertex manipulation, and then compute, approximately, the corresponding
	      deformation of the embedded surface, by a process of point sampling.
	\end{quote}

     \item FFD involves a mapping of $R^3$ to $R^3$ through a trivariate tensor-product Bernstein
           polynomial.

     \item As we're deforming space, not the objects themselves, object contact points remain
           through the mapping.  Parametric surfaces remain parametric.  I imagine if you deform
           space so that it passes through itself, then the object could collide with itself.

     \item Because they chose Bezi\'er volumes, they have continuity issues.  They fix them.

     \item Again, because they chose Bezi\'er volumes, they have issues with locality.  They fix
           those too.

     \item The volume change that an FFD imposes on each differential element is given by the
           Jacobian of the FFD.  The volume of the entire deformed surface is given by triple
           integral of this differential volume enclosed by the undeformed surface.  If \(Jac(F)
           \equiv 1\), then the FFD is volume preserving.
\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\pagebreak
\subsection{Geometric Compression}

%================================================================
\subsubsection{Geometry Compression \hfill{\tt Deering.1995.GC}}
\label{Deering.1995.GC}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper introduces the concept of Geometry Compression, allowing 3D triangle data to be
      represented with a factor of 6 to 10 times fewer bits than conventional techniques, with only
      slight losses in object quality.  The technique is amenable to rapid decompression in both
      software and hardware implementations; if 3D rendering hardware contains a geometry
      decompression unit, application geometry can be stored in memory in compressed format.
      Geometry is first represented as a generalized triangle mesh, a data structure that allows
      each instance of a vertex in a linear stream to specify an average of two triangles.  Then a
      variable length compression is applied to individual positions, colors, and normals.  Delta
      compression followed by a modified Huffman compression is used for positions and colors; a
      novel table-based approach is used for normals.  The table allows nay useful normal to be
      represented with index deltas of 8 bits or less.  Geometry compression is a general space-time
      trade-off, and offers advantages at every level of the memory/interconnect hierarchy: less
      storage is needed on disk, less transmission time is needed on networks.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Deering claims that he introduces the idea of geometry compression.

     \item He demonstrates a lossy compression rate between 6 and 10 to 1.

     \item They describe the "generalized triangle mesh", which is a generalized triangle strip
           coupled with a length 16 mesh buffer used for storing vertices which will be used again
           in the strip soon.  They claim that this allows them to avoid specifying up to 94\% of
           the redundant geometry.  They also store other information (normals, colors, etc) in the
           mesh buffer.  (Position Compression) Right off, they claim the 8-bit floating point
           exponent can be safely discarded ("specified only once in the current modeling matrix").
           "Based on empirical tests", they then decide that 16-bits per component is enough, and
           "with sufficient care being taken", multiple modeling spaces can be stitched together
           without cracks.  They will delta encode positions.

     \item (Color Compression) RGBA color is first quantized into 12-bit unsigned fraction
           components (0 black, 1 100\% reflectivity), and they allow for less.  They then use the
           same delta encoding as for vertex positions.

     \item (Normal Compression) The unit sphere is broken up into octants, and each octant is broken
           up into sextants.  Which sextant can be specified with 6 bits; 3 for the containing
           octant, 3 for the sextant within the octant, with 2 identifiers left over.  They then use
           2 orthogonal 6-bit angular addresses to encode the position within the sextant.  The
           remaining 2 identifiers are used for boundary cases.  The angular addresses are delta
           encoded.

     \item All delta encoded values are computed as differences from previous values in the
           ordering, and then variable-length encoded with a Huffman technique.  XYZ postiions are
           encoded as a single value rather than three.

     \item All of this is then implemented as a "geometry compression instruction set".
\end{itemize}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Rendering}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Global Illumination Rendering}

\paragraph{Notes}
\begin{itemize}

     \item {\tt Watt.2000.3CG} describes two models of the global illumination problem.
	\begin{quote}
	     The first is a mathematical formulation and the second is a classification in terms of
	     the nature of the type of interaction that can occur when light travels from one
	     surface to the other.
	\end{quote}

     \item The rendering equation is:
	\[
	I(x,x') = g(x,x') \left[ \epsilon(x,x') + \int_S \rho(x,x',x'') I(x',x'')dx''\right]
	\]
	Where

\begin{center}\begin{tabular}{rp{4in}}
  $I(x,x')$		& is the transport intensity from point $x'$ to point $x$\\
  $g(x,x')$		& is the visibility function between $x$ and $x'$\\
  $\epsilon(x,x')$	& is the transfer emittance from $x'$ to $x$\\
  $\rho(x,x',x'')$	& is the scattering term with respect to direction $x'$ and $x''$; related
			  to the BRDF (the foreshortened BRDF?)
\end{tabular}\end{center}

     \item Three general points come out of considering the rendering equation:
	\begin{itemize}
	   \item The complexity of the integral means that it cannot be evaluated analytically.
	         Most practical algorithms reduce the complexity in some way.  Direct evaluation of
	         the equation can be undertaken by using Monte Carlo methods, and many algorithms
	         follow this approach.
	   \item It is a view-independent statement of the problem.  The point $x'$ is every point
	         in the scene.  View dependence, where only $x'$ visible by the viewer are
	         evaluated, is seen as one way to reduce the complexity of the rendering equation.
	   \item It is a recursive equation one must evaluate $I(x', x'')$ in order to evaluate
	         $I(x,x')$.  This gives rise to the light tracing methods.
	\end{itemize}

\end{itemize}

\paragraph{Monte Carlo Integration} \ \\
If we have an integral
 \[ I = \int_a^b g(x)dx \]
we can use one of two major Monte Carlo techniques to try and evaluate it.

\begin{enumerate}
     \item If we put a bounding box around $g(x)$, then the integral can be interpreted as the
           fraction of the bounding box occupied by $g(x)$.  We can then randomly sample points
           inside the bounding box, and count the fraction of the points which are inside $g(x)$ to
           approximate the area.  {\em Very inefficient}.

     \item We can rewrite the integral equation as
	\[ I = \int_a^b g(x)f(x)dx = \frac{1}{V} \int_a^b g(x)f(x)Vdx \]
	   where $f(x)$ is equal to 1 if inside the domain of $g$, 0 otherwise.  We can then use the
	   approximate procedure:
	\[ I \approx \frac{1}{n} \sum_{i}^{n} g(x_i)f(x_i)V = \frac{V}{n}\sum_i^n g(x_i)\]


\end{enumerate}


%================================================================
\subsubsection{Radiosity and Global Illumination \hfill{\tt Sillion.1994.RAG}}

\paragraph{Notes - Definitions}
\begin{itemize}
     \item {\em Radiometry} is the science of measuring radiant energy transfers.

     \item {\em Radiance} is the quantity used to describe radiant energy transfers.  It is measured
           as the amount of energy traveling at some point in a specified direction, per unit time,
           per unit area perpendicular to the direction of travel, per unit of solid angle.

     \item {\em Radiosity} is the total power leaving a point on a surface, per unit area on the
           surface.

     \item {\em Irradiance} is the amount of energy incident, or arriving at, a point on a surface.
           It is measured in the same units as radiosity (which represents the quantity leaving a
           point on a surface).

     \item {\em Solid angle} is a three dimensional extension to the angle between two lines.
	\begin{quote}
	   The solid angle subtended by an object from point $P$ is the area of the projection of
	   the object onto the unit sphere centered at $P$.
	\end{quote}
	   Solid angle is measured in {\em steradians}.  The solid angle subtended by the entire
	   sphere is $4\pi$.

     \item One can say {\em luminosity} instead of radiosity, {\em illuminance} instead of
           irradiance, and {\em luminance} instead of radiance, if one is talking about light.

     \item {\em BRDF} stands for {\em bidirectional reflectance distribution function}, and
           describes the directional distribution of reflected light.  BRDF is measured in inverse
           steradians, and can range in value from 0 to $\infty$.

	   A more easily understood quantity is the {\em directional-hemispherical reflectance},
	   $\rho_{dh}$.  This is the fraction of incident radient flux density in a given direction
	   that is reflected by the surface (in all possible directions).

     \item An {\em ideal diffuse reflector} is a surface characterized by a uniform BRDF, one that
           does not depend on outgoing or incoming direction.

     \item An {\em ideal specular reflector} reflects light only in the mirror direction -- the
           outgoing direction is contained in the plane of incidence, and the outgoing polar angle
           is equal to the incident polar angle.  The BRDF is not well-behaved; it is characterized
           by a ``Dirac distribution''.
\end{itemize}

\paragraph{Notes - Radiosity Methods}

\begin{itemize}
     \item The radiosity method solves a simplified problem: the interreflection of light in an
           enclosure made up of ideal diffuse surfaces.

     \item The diffuse surface assumption reduces the global illumination equation to a much simpler
           energy balance equation.  With each reflection we don't require information on where the
           reflected light came from, since it is reflected equally regardless of direction.

     \item The radiosity at point $x$ is expressed as a continuous function of all the radiosities
           in the scene:
	\[
	  B(x) = E(x) + \rho_d(x) \int_{y\in S} B(y) F(x,y) V(x,y) dy
	\]
	where
	\begin{center}\begin{tabular}{rp{4in}}
	$B(x)$		& is the radiosity at point $x$\\
	$E(x)$		& is the emittance at point $x$\\
	$F(x,y)$	& is the foreshortening between $x$ and $y$\\
	$V(x,y)$	& is the visibility (0 or 1) between $x$ and $y$\\
	\end{tabular}\end{center}

     \item The heart of the radiosity method is the idea of breaking down the surfaces in the
           environment into a finite number of patches, and then solving a discrete version of the
           continuous integral radiosity equation.

     \item To further simplify, we approximate the radiosity function as a piecewise constant,
           giving each patch a uniform radiosity.  This can be changed to a smother basis function
           for improved accuracy.

     \item The form factor $F_{ij}$ is the proportion of the total power leaving patch $P_i$ that is
           received by patch $P_j$.
	\[
	F_{ij} = \frac{P}{A_iB_i} =
		 \frac{1}{A_i} \int_{x\in P_i}\int_{y\in P_j} \frac{\cos\theta \cos\theta'}{\pi r^2} V(x,y) dy dx
	\]
	where
	\begin{center}\begin{tabular}{rp{4in}}
	$P$		& is the power transferred from patch $i$ to patch $j$\\
	$A_i$		& is the area of patch $i$\\
	$B_i$	        & is the area-weighted average of the pointwise radiosites of patch $i$\\
	$\frac{\cos\theta \cos\theta'}{\pi r^2}$ & is the projected area\\
	$V(x,y)$	& is the visibility (0 or 1) between $x$ and $y$\\
	\end{tabular}\end{center}

     \item Since the form factors are strictly geometric quantities, they can be precomputed and
           used as long as the geometry doesn't change.  There are a couple of properties of form
           factors:
	\begin{itemize}
	   \item {\bf Reciprocity}.  A known $F_{ij}$ can be used to easily compute an unknown
	         $F_{ji}$.
	   \item {\bf Additivity}.  For three disjoint patches, $x,y,z$, the power received by the
	         union of $y$ and $z$ is equal to the sum of the powers received by each of $y$ and
	         $z$.
	\end{itemize}

     \item The radiosity equation is written in terms of a single patch.  To solve for an entire
           scene, one has a system of $N$ linear equations with $N$ unknowns.  The system can be
           written as ${\bf MB = E}$, where {\bf B} is a vector of radiosities for the patches, {\bf
           E} is a vector of exitances for the patches, and {\bf M} is a big hairy matrix, a
           function of the diffuse reflectances and form factors of the patches.

     \item To generate a radiosity image, we:
	\begin{enumerate}
	   \item Calculate form factors ({\em Input:} scene geometry)
	   \item Calculate elements of {\bf M} ({\em Input:} reflectance properties)
	   \item Solve the system of equations
	   \item Calculate visualization ({\em Input:} viewing conditions)
	\end{enumerate}

     \item A {\em radiosity solution} consists of a set of patch radiosities.  For image synthesis,
           we must finish with a rendering step, assigning a color to a pixel based on patch
           radiosities.

     \item The system of linear equations can be solved in any standard way, but the structure of
           the radiosity linear system is particularly amenable to an iterative solving technique
           called {\em Gauss-Seidel relaxation}.  A {\em diagonal dominance} property of the system
           ensures that the relaxation will converge.

     \item To deal with different colors, we must discretize the visible wavelengths into buckets,
           and solve the system of equations for each exitance bucket.  We end up with a vector of
           radiosities for each patch.

     \item Once we have a solution, if we used a piecewise constant approximation to the radiosity
           function, we'll want to interpolate the radiance values across patches for a smoother
           image.  Smoother does not mean more accurate.

     \item There are $N^2$ form factors for $N$ patches.  Though the reciprocity relationship can
           save some work, we'll still have to do work for $\mathcal{O}(N^2)$ form factors.  For
           each of the form factors, a visibility computation is needed, and even simple occlusion
           testing can require $O(N)$ time (though with a spatial subdivision scheme, this shouldn't
           happen).

	   Form factors are only dependent upon geometry though, not material properties,
	   illumination, or even view.  Once a solution is computed, it can be visualized from any
	   point interactively.
\end{itemize}

\paragraph{Notes - Computing Form Factors}
\begin{itemize}
     \item The hemi-cube method, more or less, renders five views from a patch and uses the pixel
           count that an object occupies in the images as the form factor.
\end{itemize}

\paragraph{Notes - Substructuring, Meshing, and Hierarchical Radiosity}
\begin{itemize}
     \item The roles assumed by surface patches in the radiosity algorithm, that of receive and
           emitter of light, can be somewhat decoupled, and computed at separate resolutions.
           Emission can be coarser; reception must be finer to avoid visual artifacts in high
           gradient areas.  We call the emitters of energy {\em patches} (as before), and the
           receivers of energy {\em elements}.

     \item Each element inside of patch $P_i$ has a distinct radiosity value.  For the purposes of
           illuminating elements inside of other patches, all elements of $P_i$ yield an aggregate
           radiosity.

     \item A substructured radiosity solution would be computed by:
	\begin{enumerate}
	   \item Compute the $M\times N$ matrix of element-to-patch form factors.
	   \item From that matrix, compute the $N\times N$ matrix of patch-to-patch form factors, by
	         averaging rows corresponding to elements within patches.
	   \item Compute a coarse radiosity solution using the $N\times N$ matrix.
	   \item Gather energy to the $M$ elements using the coarse solution.
	\end{enumerate}

     \item A mesh can be adaptively refined by approximating a coarse solution as before, detecting
           elements of high gradient, and refining them into smaller elements.  Iterate the process
           until no gradients larger than some threshold are found.

     \item Patches are probably best represented as quad trees of elements.  Elements can be
           automatically refined if any one of their neighbors has a sufficiently different
           intensity (indicating a region of high gradient).

     \item The substructuring approach will not get the cases where the emitter patches need to be
           refined as well, such as when they are near and very influential on high-gradient areas.
           This can be solved by the {\em Hierarchical radiosity formulation}.

     \item In the hierarchical formulation, the idea of adaptive mesh refinement is extended by
           removing the separation between patches and elements, replacing them with a continuum of
           hierarchical elements.  Radiosity exchanges are computed at various levels of the
           hierarchy.  For each pair of surfaces, an appropriate level of subdivision is chosen to
           compute the energy exchange.

     \item The hierarchy is constructed using a top-down approach.  The scene begins with a coarse
           mesh, and each pair of faces is considered in turn.  If the current level of subdivision
           is not sufficient, the faces are refined.  The appropriate level of subdivision is
           recorded at both ends of the pair, forming a link.

     \item The hierarchical problem is solved by iterating:
	\begin{enumerate}
	   \item Determine completely the radiosity values for each node in the hierarchy:
		\begin{enumerate}
		   \item Push radiosity values down to the leaves
		   \item Pull radiosity values up the hierarchy
		\end{enumerate}
	   \item Propagate energy along all links
	\end{enumerate}
	I'm not sure if there is a ``solving the linear system'' equivalent to this process.

     \item {\em Discontinuity meshing} refers to algorithms that generate a mesh according to the
           predicted locations of radiosity discontinuities.  It builds meshes that are well suited
           to accurate radiosity computations, but is often prohibitively expensive to use.

\end{itemize}


\paragraph{Notes - Hybrid Methods}
\begin{itemize}
     \item The bidirectional ray tracing method of Heckbert.1990.ART (section
           \ref{Heckbert.1990.ART}) is considered a hybrid method.

     \item A simple ray tracing pass or local illumination pass can be done after the radiosity
           calculations are complete.  However, this will fail to capture many important lighting
           effects in the scene.

     \item A better solution is to first extend the radiosity formulation to include extended form
           factors $F_{ij}^{\mathrm{ext}}$.  Extended form factors represent the energy transferred
           from patch $P_i$ to $P_j$ after any number of ideal specular bounces.  The form factors
           can be computed in the normal way if geometry is reflected through planar mirror surfaces
           for purposes of form factor computation.

     \item After the extended form factor radiosity solution is computed, a view dependent pass can
           add specular details to the scene.  This can be done with classical ray tracing,
           distribution ray tracing, a Z-buffer algorithm, or however one wishes.


\end{itemize}

%================================================================
\subsubsection{The Rendering Equation \hfill{\tt Kajiya.1986.TRE}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present an integral equation which generalizes a variety of known rendering algorithms.  In
      the course of discussing a Monte Carlo solution we also present a new form of variance
      reduction, called Hierarchical sampling and give a number of elaborations shows that it may be
      an efficient new technique for a wide variety of monte carlo procedures.  The resulting
      rendering algorithm extends the range of optical phenomena which can be effectively simulated.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item Kajiya presents the rendering equation and then rewrites it as:
	\[ I = g\epsilon + gMI \]
	   where $M$ is the linear operator given by the integral in the rendering equation.  This
	   equation can in turn be rewritten as an infinite series known as a Neuman series:
	\[ I = g\epsilon + gMg\epsilon + g(Mg)^2\epsilon + g(Mg)^3\epsilon + \cdots \]
	   This means $I$ is the sum of a direct term, a once scattered term, a twice scattered
	   term, etc.

     \item The above formulation leads to {\em path tracing}.  Light rays are traced backwards (as
           in Whitted ray tracing) from pixels and bounce around the scene through the hit points to
           some depth, which is equivalent to truncating the series at some (insignificant) depth.

     \item Path tracing is of course view-dependent, and is capable of simulating fully L(D$|$S)*E
           interactions.

     \item In Kajiya's path tracing approach, 40 rays per pixel are emitted.  Each ray is reflected
           in turn off of each object, by sampling the BRDF at the point of impact on the surface.
           At each point of impact, a `shadow ray' is cast to each light source, and a direct
           illumination contribution is added if the light source is visible.  I can't find a
           statement as to when the recursion is terminated.
\end{itemize}

%================================================================
\pagebreak
\subsubsection{Distributed Ray Tracing \hfill{\tt Cook.1984.DRT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Ray tracing is one of the most elegant techniques in computer graphics.  Many phenomena that
      are difficult or impossible with other techniques are simple with ray tracing, including
      shadows, reflections, and refracted light.  Ray directions, however, have been determined
      precisely and this has limited the capabilities of ray tracing.  By distributing the
      directions of the rays according to the analytic function they sample, ray tracing can
      incorporate fuzzy phenomena.  This provides correct and easy solutions to some previously
      unsolved or partially solved problems, including motion blur, depth of field, penumbras,
      translucency, and fuzzy reflections.  Motion blur and depth of field calculations can be
      integrated with visible surface calculations, avoiding the problems found in previous methods.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Whitted ray tracing is limited to producing only `sharp' phenomena, as light ray
           directions are computed precisely from geometry.  By distributing the rays, or
           antialiasing them, fuzzy phenomena can be modeled.

     \item Sampling / antialiasing can achieve:
	\begin{itemize}
	   \item sampling reflected ray according to specular distribution function produces gloss
	   \item sampling transmitted ray produces translucency (blurred transparency)
	   \item sampling solid angle of light produces penumbras
	   \item sampling camera lens area produces depth of field
	   \item sampling in time produces motion blur
	\end{itemize}

     \item The complexity of integrating the rendering equation is avoided by making some
           assumptions:
	\begin{itemize}
	   \item Assume that the Illumination Function, $L$, is a $\delta$ function, i.e., that $L$
	         is zero except for the light source directions and that the light sources can be
	         treated as points.  The integral is now replaced by a sum of certain discrete
	         directions.  This assumption causes sharp shadows.

	   \item Assume that all the directions that are not light source directions can be grouped
	         together into an ambient light source.  This ambient light is the same in all
	         directions, so that $L$ is independent of the angle of incidence and it may be
	         removed from the integral.  The integral of the Reflection Function, $R$, may then
	         be replaced by an average, or ambient, reflectance

	   \item Assume that the reflectance function $R$ is a $\delta$ function, i.e., that the
	         surface is a mirror and reflects light only from the mirror direction.  This
	         assumption causes sharp reflections.  A corresponding assumption for transmitted
	         light causes sharp  refraction.
	\end{itemize}
     \item Summary of Algorithm (per ray):
	\begin{enumerate}
	   \item Choose a time for the ray and move objects accordingly.  The number of rays at a
	         certain time is proportional to the value of the desired temporal filter at that
	         time.

	   \item Construct a ray from the eye point (center of the lens) to a point on the screen.
	         Choose a location on the lens, and trace a ray from that location to the focal
	         point of the original ray.  Determine which object is visible.

	   \item Calculate the shadows.  For each light source, choose a location on the light and
	         trace a ray from the visible point to that location.  The number of rays traced to
	         a location on the light should be proportional to the intensity and projected area
	         of that location as seen from the surface.

	   \item For reflections, choose a direction around the mirror direction and trace a ray in
	         that direction from the visible point.  The number of rays traced in a specific
	         direction should be proportional to the amount of light from that direction that is
	         reflected toward the viewer.  This can replace the specular component.

	   \item For transmitted light, choose a direction around the direction of the transmitted
	         light and trace a ray in that direction from the visible point.  The number of rays
	         traced in a specific direction should be proportional to the amount of light from
	         that direction that is transmitted toward the viewer.

	\end{enumerate}

\end{itemize}

%================================================================
\subsubsection{Adaptive Radiosity Textures from Bidirectional Ray Tracing \hfill{\tt Heckbert.1990.ART}}
\label{Heckbert.1990.ART}
\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a rendering method designed to provide accurate, general simulation of global
      illumination for realistic image synthesis.  Separating surface interaction into diffuse plus
      specular, we compute the specular component on the fly, as in ray tracing, and store the
      diffuse component (the radiosity) for later-reuse, similar to a radiosity algorithm.
      Radiosities are stored in {\em adaptive radiosity textures (rexes)} that record the pattern of
      light and shadow on every diffuse surface in the scene.  They adaptively subdivide themselves
      to the appropriate level of detail for the picture being made, resolving sharp, shallow edges
      automatically.

      We use a three-pass, bidirectional ray tracing algorithm that traces rays from both the lights
      and the eye.  The ``size pass'' records visibility information on diffuse surfaces; the
      ``light pass'' progressively traces rays from lights and bright surfaces to deposit photons on
      diffuse surfaces to construct the radiosity textures; and the ``eye pass'' traces rays from
      the eye, collecting light from diffuse surfaces to make a picture.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item A technique is presented for bidirectional ray tracing.  The algorithm proceeds in three
           phases:
	\begin{itemize}
	   \item {\bf Size Pass}.  Records information about mapping between surface parameter space
	         and screen space.
	   \item {\bf Light Pass}. Light is emitted and bounced about the scene, being stored in
	         adaptively resized illumination maps or rexes.
	   \item {\bf Eye Pass}.  Like a standard ray tracing algorithm except diffuse intensity is
	         extracted from the illumination map, instead of with a shadow ray.
	\end{itemize}

     \item The light pass:
	\begin{itemize}
	   \item Light is emitted from the light sources and deposited onto the illumination maps of
	         surfaces as a first approximation to the radiosities.  To simulate diffuse
	         interreflection, bright surfaces progressively re-emit rays.
	   \item The radiosities calculated are view independent, but the sampling pattern of
	         radiosities is not.  Illumination maps are adaptively refined to approach
	         appropriate sizes determined in the size pass, an element being no smaller than the
	         preimage of a screen pixel.
	   \item The emitted light is also adaptively sampled so as to concentrate emission to high
	         gradient areas (shadow boundaries, specularities).
	   \item The emissions of a light are organized into a quadtree, which is adaptively
	         subdivided and energy reduced as the light pass goes on its merry way.


	\end{itemize}

\end{itemize}


%================================================================
\pagebreak
\subsubsection{Photon Maps in Bidirectional Monte Carlo Ray Tracing \hfill{\tt Jensen.1995.PMI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes a bidirectional Monte Carlo ray tracing method simulating global
      illumination in models containing complex objects that do not have to be tessellated.  The two
      pass method combines a first pass light ray tracing (ray casting) with a second pass optimized
      Monte Carlo ray tracing.  In the first pass, the light emitted from light sources hit objects
      in the scene and may be reflected or transmitting, a kind of backward path tracing.  This step
      handles all kinds of reflections and not only the specular to diffuse reflections.  This turns
      out to be a valuable optimization.  At every object-interaction, energy is stored on the
      surface of the object.  For simple objects an illumination map is used.  For complex objects
      e.g., procedurally based objects like fractals, energy is stored in a photon map.  This new
      concept makes it possible to treat caustics upon such objects without having to parameterize
      the surface of the objects.  The second pass, Monte Carlo ray tracing from the eye, visualizes
      the scene based upon the result from the first pass.  We use the irradiance gradient method to
      model diffuse reflections seen directly from the eye.  All secondary reflections are taken
      from the photon maps or the illumination maps.  Only the caustic part of the ray casting step
      is visualized directly.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Their main goal is to set up a method that does not require tessellation of the model.
           Patch based approaches (radiosity) can obviously not be used.

     \item The two pass approach emits light from light sources by an emitted light distribution
           function, then collects light for visualization with a Monte Carlo method.

     \item Light Path Tracing:
	\begin{itemize}
	   \item Rays are emitted from some number of different positions on each light source, the
	         number being a function of the area of the light source and the dimensions of the
	         room.
 	   \item At each emission point, a projection map is created.  The projection map encodes
 	         the positions of diffuse and specular surfaces.  Rays are emitted to the objects in
 	         the projection map using stratified sampling, with a greater concentration focusing
 	         on specularities.
	   \item Each ray carries a fraction of the light source energy, and it is deposited into
	         the irradiance map of a given location.  After the energy is deposited, a Russian
	         roulette technique is used to determine whether the ray is reflected or absorbed by
	         the surface.
	   \item Objects use two illumination maps (texture maps with irradiance information), a
	         diffuse map and a higher resolution caustic map for specularities.  Resolution of
	         the diffuse map is a function of the size of the object with respect to the light
	         sources, and the resolution of the caustic map is a function of the number of
	         pixels occupied by the specular region in the output image.
	   \item For objects which are difficult to describe parametrically (like fractals), they
	         introduce a caustic and diffuse photon map.  With every photon deposited in the
	         map, they store the intersection point, the normal, the energy, and a bit
	         specifying whether this point is part of a caustic (which they encode in 28 bytes)
	         in a $k$-D tree.
	   \item To calculate an irradiance from a photon map, the consider a point in space and
	         find the $n$ nearest neighbors in the map to that point, and use those points to
	         calculate the irradiance.  They special case the edges of caustic regions to avoid
	         blur.
	\end{itemize}

     \item Visualization:
	\begin{itemize}
	   \item The model is visualized with a Monte Carlo ray tracing which reduces aliasing but
	         can give rise to noise.
	   \item The radiance at a pixel, $L_p$, is modeled as $L_p = L_e + L_r$, light emitted plus
	         light reflected.  Light reflected is in turn represented as a diffuse plus a
	         specular component, $L_r = L_{r,d} + L_{r,s}$.  The reason for this split is that
	         $L_{r,s}$ is highly directional, while $L_{r,d}$ is only weakly directional.

	   \item Monte Carlo ray tracing is used to calculate $L_{r,s}$, but this is not convenient
	         for $L_{r,d}$.  Instead, the diffuse component is in turn represented as light
	         coming from light sources, plus light coming from multiple diffuse sources, plus
	         light coming from specular sources, $L_{r,d} = L_{r,d,l} + L_{r,d,s} + L_{r,d,d}$.
	         These are each calculated separately, using a stratified sampling of the light
	         source, computing directly from the irradiance maps, and using an irradiance
	         gradient method, respectively.
	\end{itemize}


\end{itemize}

%================================================================
\subsubsection{Metropolis Light Transport \hfill{\tt Veach.1997.MLT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a new Monte Carlo method for solving the light transport problem, inspired by the
      Metropolis sampling method in computational physics.  To render an image, we generate a
      sequence of light transport paths by randomly mutating a single current path (e.g. adding a
      new vertex to the path).  Each mutation is accepted or rejected with a carefully chosen
      probability, to ensure that paths are sampled according to the contribution they make to the
      ideal image.  We then estimate this image by sampling many paths, and recording their
      locations on the image plane.

      Our algorithm is unbiased, handles general geometric and scattering models, uses little
      storage, and can be orders of magnitude more efficient than previous unbiased approaches.  It
      performs especially well on problems that are usually considered difficult, e.g. those
      involving bright indirect light, small geometric holds, or glossy surfaces.  Furthermore, it
      is competitive with previous unbiased algorithms even for relatively simple scenes.

      The key advantage of the Metropolis approach is that the path space is explored locally, by
      favoring mutations that make small changes to the current path.  This has several
      consequences.  First, the average cost per sample is small (typically only one or two rays).
      Second, once an important path is found, the nearby paths are explored as well, thus
      amortizing the expense of finding such paths over many samples.  Third, the mutation set is
      easily extended.  By constructing mutations that preserve certain properties (e.g. which light
      source is used) which changing others, we can exploit various kinds of coherence in the scene.
      It is often possible to handle difficult lighting problems efficiently by designing a
      specialized mutation in this way.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item The MLT algorithm is summarized by:\nopagebreak\\
	{\tt \nopagebreak
	${\tt\bar{x}}$ = initialPath()\\\nopagebreak
	image = arrayOfZeros()\\\nopagebreak
	foreach i (1 .. N)\\\nopagebreak
	\verb#    # ${\tt\bar{y}}$ = mutate(${\tt\bar{x}}$)\\\nopagebreak
	\verb#    # a = acceptProb(${\tt\bar{y}|\bar{x}}$)\\\nopagebreak
	\verb#    # if (random() < a)\\\nopagebreak
	\verb#        # ${\tt\bar{x} = \bar{y}}$\\\nopagebreak
	\verb#    # recordSample(image,${\tt\bar{x}}$)
	}

     \item To build the MLT algorithm, there are three tasks.  First, reduce the light transport
           problem so it is posed in the Metropolis framework.  Second, show how to avoid start up
           bias.  Third, most importantly, design a set of suitable mutations on paths so that the
           method will work efficiently.

     \item In the Metropolis framework, the estimate of each pixel is given by:
	\[ m_j = E \left[ \frac{1}{N} \sum_{i=1}^N b w_j(\bar{X}_i) \right] \]
	where
	\begin{center}\begin{tabular}{ll}
	$m_j$		& is the pixel value at $j$\\
	$E$		& is ?\\
	$N$		& is the number of samples\\
	$b$		& is the normalization constant \\
	$w_j$		& is the filter function for pixel $j$\\
	$\bar{X}_i$	& is the sample path $i$\\
	\end{tabular}\end{center}

     \item To initialize the process, $n$ initial samples are computed
           $\bar{X}_0^{(1)},\dots,\bar{X}_0^{(n)}$.  The value of $n$ is determined indirectly, by
           generating a fixed number of eye and light subpaths (e.g. 10000 pairs), and considering
           all the ways to link the vertices of each pair.  The $\bar{X}_0^{(i)}$ are then resampled
           into a much smaller $n'$, possibly $n' = 1$, to use in the Metropolis phase of the
           algorithm.

     \item The algorithm will behave better if the samples are mostly uncorrelated.  Correlated
           samples happen if too many samples are rejected, the path mutations are too small or the
           allowable mutations are too restricted.  MLT uses three mutation strategies, which to use
           is sampled (the probabilities of each are set at the beginning of each step) when a
           mutation is needed.  They are:
	\begin{itemize}
	   \item {\bf Bidirectional mutations}.  This is the foundation of the algorithm, and is
	         responsible for making the largest changes to the path.  Basically, choose a
	         subpath of the current path, and replace it with a different subpath.
	   \item {\bf Perturbations}.  For a more local change, necessary sometimes around caustics
	         or around difficult visibility, is to take a subpath of the current path and
	         perturb the vertex locations.
	   \item {\bf Lens subpath mutations}.  The goal of this mutation type is to stratify
	         samples over the image plane, and to reduce the cost of sampling by re-using
	         subpaths.  A lens current lens subpath $\bar{x}_e$ (of the form (L|D)S*E) is kept
	         and used to replace the lens subpath of $\bar{x}$.  The subpath $\bar{x}_e$ is used
	         some number of times ($n_e$) then discarded and recomputed.
	\end{itemize}

     \item MLT is refined in several ways:
	\begin{itemize}
	   \item {\bf Direct Lighting}.  Standard techniques are used for direct lighting (see {\em
	         Monte Carlo methods for direct lighting calculations}), as they give better results
	         at a lower cost than the Metropolis algorithm.
	   \item {\bf Using the expected sample value}.  A technique which effectively replaces a
	         random variable with its expected value (a common variance reduction technique) can
	         be effective for sampling the dim regions of an image.
	   \item {\bf Importance sampling for mutation probabilities}.  A form of importance
	         sampling can be implemented by reweighting the possible mutations according to the
	         probability with which the deleted subpath can be regenerated.
	\end{itemize}

     \item The result is an algorithm which produces far superior results on difficult lighting
           conditions, in the same time, compared to bidirectional path tracing.  Metropolis samples
           vary according to pixel brightness, so there is more noise in dark regions and less in
           bright regions, again compared to bidirectional path tracing.
\end{itemize}


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Local Illumination Rendering}

\paragraph{Notes}
\begin{itemize}
     \item According to some website I found, the nFiniteFX engine inside the GeForce4 4600 is
           capable of rendering 136 million polygons per second, and has a texture unit capable of a
           fill rate of 4.8 billion texels per second.

     \item The OpenGL 1.2 pipeline is:\\
	\includegraphics[width=5in]{glpipe1-2.eps}

     \item A graphics pipeline (from {\tt Watt.2000.3CG}):
	\begin{enumerate}
	   \item Local Coordinate Space
		\begin{itemize}
		   \item Object definition
		\end{itemize}

	   \item World Coordinate Space
		\begin{itemize}
		   \item Scene composition
		   \item Lighting Definition
		   \item Camera Definition
		   \item Advanced Visibility
		\end{itemize}
	   \item View Space
		\begin{itemize}
		   \item Set camera parameters
		   \item Culling
		   \item Clipping
		\end{itemize}
	   \item 3D Screen Space
		\begin{itemize}
		   \item Rasterization
		   \item Hidden surface removal
		   \item Shading
		\end{itemize}
	   \item Display Space
		\begin{itemize}
		   \item Convert virtual screen to real screen (taken care of by windowing system)
		\end{itemize}
	\end{enumerate}

     \item What to draw?
	\begin{itemize}
	   \item Z-buffer
	   \item A-buffer (list of polygons per pixel)
	   \item Depth sorting
	   \item BSP trees (can get back to front rendering order)
	\end{itemize}

     \item Local Illumination Shading Model
	\begin{itemize}
	   \item Diffuse term 
	 	 \[k_d I_i ({\bf L\cdot N})\] 
 	  	where $I_i$ is the incoming intensity, ${\bf L}$ is the light direction, ${\bf N}$
 	  	is the surface normal, and $k_d$ is the surface diffuse constant.
	   \item Specular (Phong Shading) term 
		 \[ k_s I_i ({\bf H \cdot V})^n\]
		where $I_i$ is the light intensity, ${\bf H} = ({\bf L} + {\bf V})/2$, ${\bf L}$ is
		the light direction, ${\bf V}$ is the viewing direction, $n$ is the specular size
		parameter, and $k_s$ is the surface specular constant.
	   \item Ambient term
		 \[ k_a I_a \]
		where $I_a$ is the global ambient light intensity, and $k_a$ is the surface ambient
		constant.
	   \item All together, we have
		 \[I = k_a I_a + I_i \left(K_d ({\bf L \cdot N}) + k_s ({\bf H \cdot N})^n\right)\]
		which of course must be done for each color.
	\end{itemize}

     \item Shading Interpolation
	\begin{itemize}
	   \item {\bf Flat Shading}.  Compute shading at representative point and apply to entire
	         polygon.
	   \item {\bf Gourand Shading}. Compute shading at each vertex point, linearly interpolate
	         across polygon.
	   \item {\bf Phong Interpolation}. Interpolate normals across polygon, shade each pixel.
	\end{itemize}

\end{itemize}



%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Image-Based Rendering}

%================================================================
\subsubsection{Quicktime VR \hfill{\tt Chen.1995.QVI}}
\label{Chen.1995.QVI}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Traditionally, virtual reality systems use 3D computer graphics to model and render virtual
      environments in real-time.  This approach usually requires laborious modeling and expensive
      special purpose rendering hardware.  The rendering quality and scene complexity are often
      limited because of the real-time constraint.  This paper presents a new approach which uses
      360-degree cylindrical panoramic images to compose a virtual environment.  The panoramic image
      is digitally warped on-the-fly to simulate camera panning and zooming.  The panoramic images
      can be created with computer rendering, specialized panoramic cameras or by "stitching"
      together overlapping photographs taken with a regular camera.  Walking in space is currently
      accomplished by "hopping" to different panoramic points.  The image-based approach has been
      used in the commercial product QuickTime VR, a virtual reality extension to Apple Computer's
      QuickTime digital multimedia framework.  The paper describes the architecture, the file
      format, the authoring process and interactive players of the VR system.  In addition to
      panoramic viewing, the system includes viewing of an object from different directions and
      hit-testing through orientation-independent hot spots.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}
Representation	& %
		 Cylindrical Environment Maps and a transition graph to move between maps.\\\hline
Creation	& %
		 Acquire sample images, stitch them together into panoramic images. Author panoramic
		 nodes if multiple locations are needed. Embed panoramic images and graph nodes as
		 two QuickTime video tracks and a special panoramic node track.\\\hline
Display		& %
		 Warp a section of the panoramic image into a view image.\\\hline
Acquisition	& %
		 Sideways mounted camera is rotated 360 degrees and some number of images are
		 acquired (12 in their example).\\\hline
Compression	& %
		 Video compression in the QuickTime environment is used. \\
\end{supertabular}


%================================================================
\subsubsection{Plenoptic Modeling \hfill{\tt McMillan.1995.PMA}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Image-based rendering is a powerful new approach for generating real-time photorealistic
      computer graphics.  It can provide convincing animations without an explicit geometric
      representation.  We use the "plenoptic function" of Adelson and Bergen to provide a concise
      problem statement for image-based rendering paradigms, such as morphing and view
      interpolation.  The plenoptic function is a parameterized function for describing everything
      that is visible from a given point in space.  We present an image-based rendering system based
      on sampling, reconstructing, and resampling the plenoptic function.  In addition, we introduce
      a novel visible surface algorithm and a geometric invariant for cylindrical projections that
      is equivalent to the epipolar constraint defined by planar projections.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{View Morphing \hfill{\tt Seitz.1996.VM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Image morphing techniques can generate compelling 2D transitions between images.  However,
      differences in object pose or viewpoint often cause unnatural distortions in image morphs that
      are difficult to correct manually.  Using basic principles of projective geometry, this paper
      introduces a simple extension to image morphing that correctly handles 3D projective camera
      and scene transformations.  The technique, called view morphing, works by prewarping two
      images prior to computing a morph and then postwarping the interpolated images.  Because no
      knowledge of 3D shape is required, the technique may be applied to photographs and drawings,
      as well as rendered scenes.  The ability to synthesize changes both in viewpoint and image
      structure affords a wide variety of interesting 3D effects via simple image transformations.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The basic premise of View Morphing is that image morphing between two parallel views of
           an object creates a {\em shape-preserving} transformation.  If the projection matrices
           for the images can be derived (and they can), the images can be reprojected onto a common
           plane and interpolated there, and then being reprojected back into the desired view.
\end{itemize}


%================================================================
\subsubsection{Light Field Rendering \hfill{\tt Levoy.1996.LFR}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      A number of techniques have been proposed for flying through scenes by redisplaying previously
      rendered or digitized views.  Techniques have also been proposed for interpolating between
      views by warping input images, using depth information or correspondences between multiple
      images.  In this paper, we describe a simple and robust method for generating new views from
      arbitrary camera positions without depth information or feature matching, simply by combining
      and resampling the available images.  The key to this technique lies in interpreting the input
      images as 2D slices of a 4D function - the light field.  This function completely
      characterizes the flow of light through unobstructed space in a static scene with fixed
      illumination.

      We describe a sampled representation for light fields that allows for both efficient creation
      and display of inward and outward looking views.  We have created light fields from large
      arrays of both rendered and digitized images.  The latter are acquired using a video camera
      mounted on a computer-controlled gantry.  Once a light field has been created, new views may
      be constructed in real time by extracting slices in appropriate directions.  Since the success
      of the method depends on having a high sample rate, we describe a compression system that is
      able to compress the light fields we have generated by more than a factor of 100:1 with very
      little loss in fidelity.  We also address the issues of antialiasing during creation and
      resampling during slice extraction.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}
Representation	& Light Slab representation; 4 light slabs\\\hline
Creation	& %
		 Render object with sheared perspective projection into a 2D collection of cells
		 across the uv plane of the light slab, or generate physical equivalent. Use fewer,
		 higher resolution images.\\\hline
Display		& %
		 Ray trace through light slab and interpolate somehow; point sample, bilinearly
		 interpolating, or quadralinearly interpolating.\\\hline
Acquisition	& %
		 Constructed a computer-controlled gantry to move a camera around in a plane near
		 the object of interest. The object of interest and a lighting rig are rotated to
		 capture the four separate light slabs. Camera points at the object of interest, and
		 images are reprojected to lie in a common plane.\\\hline
Compression	& %
		 Vector quantize the light slabs into codebook and indices; LZ compress each into a
		 bitstream. Good results at 120:1 compression.\\

\end{supertabular}

%================================================================
\subsubsection{The Lumigraph \hfill{\tt Gortler.1996.TL}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper discusses a new method for capturing the complete appearance of both synthetic and
      real world objects and scenes, representing this information, and then using this
      representation to render images of the object from new camera positions.  Unlike the shape
      capture process traditionally used in computer vision and the rendering process traditionally
      used in computer graphics, our approach does not rely on geometric representations.  Instead
      we sample and construct a 4D function, which we call a Lumigraph.  The Lumigraph is a subset
      of the complete plenoptic function that describes the flow of light at all positions and
      directions.  With the Lumigraph, new images of the object can be generated very quickly,
      independent of the geometric or illumination complexity of the scene or object.  The paper
      discusses a complete working system including the capture of samples, the construction of the
      Lumigraph, and the subsequent rendering of images from this new representation.
\end{minipage}}\end{quote}

\paragraph{Notes} \ \\

\begin{supertabular}{r|p{5in}}
Representation	& %
		 Light Slab representation with low-poly approximate model; 6 light slabs\\\hline
Creation	& %
		 Render object with sheared perspective projection from multiple jittered locations
		 for each of the 2D collection of cells across the st plane of light slab, weight
		 and average according to the kernel \~B. Use fewer, higher resolution
		 images.\\\hline
Display		& %
		 Can ray trace the Lumigraph by casting rays and interpolating cells via basis
		 functions appropriately, and depth correcting (u,v) coordinates before
		 interpolation.

		 Can also tile the st plane with polygons and texture map them, averaging images as
		 appropriate for basis functions. \\\hline
Acquisition	& %
		 Use a conventional hand-held camera and photograph against a stage with special
		 calibration markers (concentric rings). Use voxel coloring to obtain a rough 3D
		 shape approximation. \\\hline
Compression	& %
		 No compression implemented, but initial analysis suggests that a wavelet or DCT
		 transform of the 4D array could compress to 200:1 with little degradation.\\
\end{supertabular}

%================================================================
\pagebreak
\subsubsection{Modeling and Rendering Architecture from Photographs \hfill{\tt Debevec.1996.MAR}}
\label{Debevec.1996.MAR}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a new approach for modeling and rendering existing architectural scenes from a
      sparse set of still photographs.  Our modeling approach, which combines both geometry-based
      and image-based techniques, has two components.  The first component is a photogammetric model
      which facilitates the recovery of the basic geometry of the photographed scene.  Our
      photogammetric model is effective, convenient, and robust because it exploits constraints that
      are characteristic to architectural scenes.  The second component is a model-based stereo
      algorithm, which recovers how the real scene deviates from the basic model.  By making use of
      the model, our stereo technique robustly recovers accurate depth from widely spaced image
      pairs.  Consequently, our approach can model large architectural environments with far fewer
      photographs than current image-based modeling approaches.  For producing renderings, we
      present view-dependent texture mapping, a method of compositing multiple views of a scene that
      better simulates geometric detail on basic models.  Our approach can be used to recover models
      for use in either geometry-based or image-based rendering systems.  We present results that
      demonstrate our approach's ability to create realistic renderings of architectural scenes from
      viewpoints far from the original photographs.
\end{minipage}}\end{quote}

\paragraph{Notes} \ \\

\begin{supertabular}{r|p{5in}}
Representation	& %
		 View-dependent texture maps and depth maps on low-poly models \\\hline
Creation	& %
		 Interactive photogrammetric modeling program to generate approximate geometry;
		 original images stored for texturing; automatic model-based stereo to compute depth
		 maps.\\\hline
Display		& %
		 Use a polygon renderer to generate the scene, displace low-poly models with depth
		 maps, texture models using original images with view-dependent technique.\\\hline
Acquisition	& %
		 Conventional photography. \\\hline
Compression	& %
		 Amount of data relatively small...no compression discussed. \\
\end{supertabular}

%================================================================
\subsubsection{Recovering High Dynamic Range Radiance Maps from Photographs \hfill{\tt Debevec.1997.RHD}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a method of recovering high dynamic range radiance maps from photographs taken with
      conventional imaging equipment.  In our method, multiple photographs of the scene are taken
      with different amounts of exposure.  Our algorithm uses these differently exposed photographs
      to recover the response function of the imaging process, up to a factor of scale, using the
      assumption of reciprocity.  With the single response function, the algorithm can fuse the
      multiple photographs into a single, high dynamic range radiance map whose pixel values are
      proportional to the true radiance values in the scene.  We demonstrate our method on images
      acquired with both photochemical and digital imaging processes.  We discuss how this work is
      applicable in many areas of computer graphics involving digitized photographs, including
      image-based modeling, image compositing, and image processing.  Lastly, we demonstrate a few
      applications of having high dynamic range radiance maps, such as synthesizing realistic motion
      blur and simulating the response of the human visual system.
\end{minipage}}\end{quote}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\pagebreak
\subsection{Stylized Rendering}

%================================================================
\subsubsection{Paint By Numbers \hfill{\tt Haelberli.1990.PBN}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Computer graphics research has concentrated on creating photo-realistic images of synthetic
      objects.  These images communicate surface shading and curvature, as well as depth
      relationships in the scene.  These renderings are traditionally represented by a rectangular
      array of pixels that tile the image plane.

      As an alternative to photo-realism, it is possible to create abstract images using an ordered
      collection of brush strokes.  These abstract images filter and refine visual information
      before it is presented to the viewer.  By controlling the color, shape, size, and orientation
      of individual brush strokes, impressionistic paintings of computer generated or photographic
      images can be easily created.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

%\begin{tabular}{r|p{5in}}\hline\hline
\begin{supertabular}{r|p{5in}}
NPR Effect      & Painterly style imagery \\\hline
Automation      & Interactive program to specify a "painting", a description of brush stroke colors,
                  sizes, shapes, orientations. An automated filtering program transforms the
                  description into an RGB image.\\\hline
Frame Coherence & Inherently interactive, single image-based process; not very suitable for
		  animation. No temporal coherence issues discussed.\\\hline
Notes           &  %
		   The program samples colors underneath the cursor, and draws a brush stroke
		   (parameterized by location, color, size, direction and shape) if the mouse button
		   is depressed, in a stochastic neighborhood around the cursor's position. The size
		   of the stroke is controlled by the speed of the mouse movement (faster ==
		   larger), or by selecting with arrow keys. The orientation of the stroke is
		   controlled by mouse movement, mouse gesture to set, or through the use of other
		   input devices. Brush shape is chosen from a popup menu.

		   Once the description is interactively specified and saved, a raster image of any
		   resolution can be generated by another program. Unary operators can add noise to
		   brush stroke parameters, add constants to parameters, or reorder strokes sorting
		   by some parameter. Binary operators interpolate between parameter sets of
		   multiple paintings [correspondence?].\\

\end{supertabular}


%================================================================
\subsubsection{Computer-Generated Pen-and-Ink Illustration \hfill{\tt Winkenbach.1994.CPI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes the principals of pen-and-ink illustration, and shows how a great number
      of them can be implemented as part of an automated rendering system.  It introduces "stroke
      textures," which can be used for achieving both texture and tone with line drawing.  Stroke
      textures also allow resolution-dependent rendering, in which the choice of strokes used in an
      illustration is appropriately tied to the resolution of the target medium.  We demonstrate
      these techniques in complex architectural models, including Frank Lloyd Wright's "Robie
      House".
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Pen and ink illustration\\\hline
Automation	& %
		  Automated 3D pipeline. "Stroke textures" are used instead of conventional image
		  textures, and these must be pre-assigned to the polygonal models. \\\hline
Frame Coherence & %
		  System makes thorough use of randomness, temporal coherence issues would
		  abound. They list animation as an area for future work.  \\\hline
Notes		& %
		 The rendering pipeline includes standard features including: polygonal models,
		 assignment of texture, a lighting model for a "reference solution", a visible
		 surface algorithm, and a shadowing algorithm.

		 They also needed to add a few features: a 2D spatial subdivision in image space to
		 consider adjacent surfaces, coupling the rendering of texture and tone as they are
		 both implemented as some form of hatching, stroke-based clipping (rather than pixel
		 based), and outlining.

		 Strokes are parameterized by a waviness function and a pressure function. Stroke
		 textures are collections of prioritized strokes; strokes are drawn in sequence
		 until the tone reaches the correct level. "Indications" are selective amounts of
		 detail which suggest texture, rather than fully texturing the surface. A
		 semi-automated tool allows a user to specify regions which should get full / high
		 detail, and indications are used elsewhere. Outlines vary with the type of texture
		 they border on / separate, may not be drawn at all if region tones are sufficiently
		 different, and are dependent on the viewing direction.\\
\end{supertabular}





%================================================================
\pagebreak
\subsubsection{Painterly Rendering For Animation \hfill{\tt Meier.1996.PRF}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a technique for rendering animations in a painterly style.  The difficulty in using
      existing still frame methods is getting the paint to "stick" to surfaces rather than randomly
      change with each frame, while still retaining a hand-crafted look.  We extend the still frame
      method to animation by solving two major specific problems of previous techniques.  First our
      method eliminates the "shower door" effect in which an animation appears as if it were being
      viewed through textured glass because brush strokes stick to the viewplane not to the
      animating surfaces.  Second, our techniques provide for frame-to-frame coherence in animations
      so that the resulting frames to not randomly change every frame.  To maintain coherence, we
      model surfaces as 3d particle sets which are rendered as 2d brush strokes in screen space much
      like an artist lays down brush strokes on a canvas.  We use geometric and lighting properties
      of the surface to control the appearance of brush strokes.  This powerful combination of using
      3d particles, surface lighting information, and rendering 2d brush strokes in screen space
      gives us the painterly style we desire and forces the brush strokes to stick to animating
      surfaces.  By varying the lighting and choosing brush stroke parameters we can create many
      varied painterly styles.  We illustrate with images and animated sequences and present
      specific technical and creative suggestions for achieving different looks.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Painterly style imagery\\\hline
Automation	& %
		  Automated 3D pipeline. 		    \\\hline
Frame Coherence & %
		  Surfaces are modeled as particle sets, and painterly effects are functions of
		  those. They can choose to animate the particle locations. Temporal coherence is
		  controlled.  \\\hline
Notes		& %
\vspace{-0.2in}\begin{verbatim}
GeometryToParticles()
foreach (frame)
    RenderReferenceImages()
    AnimateParticlesForFrame()
    SortParticlesByDistanceFromViewpoint()
    foreach (particle) // furthest from viewpoint first
        ParticleToScreenSpace()
        GenerateStrokeAttributes()
        CompositeStrokeToPaintBuffer()
    end
end
\end{verbatim}

		{\tt RenderReferenceImages()} generates a smooth shaded color reference image, a
		reference image that encodes orientation, and a reference image that encodes brush
		size.

		{\tt GenerateStrokeAttributes()} works from reference images and particle
		attributes, sets position according to particle screen space location, and randomly
		perturbs them based on user parameters.

		{\tt CompositeStrokeToPaintBuffer()} places brush image, transformed by the stroke
		attributes, into the paint buffer.  \\
\end{supertabular}

%================================================================
\subsubsection{Computer-Generated Watercolor \hfill{\tt Curtis.1997.CW}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes the various artistic effects of watercolor and shows how they can be
      simulated automatically.  Our watercolor model is based on an ordered set of translucent
      glazes, which are created independently using shallow-water fluid simulation.  We use a
      Kubelka-Munk compositing model for simulating the optical effect of the superimposed glazes.
      We demonstrate how computer-generated watercolor can be used in three different applications:
      as part of an interactive watercolor paint system, as a method of automatic image
      "watercolorization", and as a mechanism for non-photorealistic rendering of three-dimensional
      scenes.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Watercolor painterly style imagery\\\hline
Automation	& %
		 They implement an interactive watercolor paint program, a "watercolorization"
		 filter (which requires object mattes be specified), and a 3D renderer. \\\hline
Frame Coherence & %
		 Implementation does not take temporal coherence into account, and frames are
		 rendered in isolation. Animation is an area for future work.  \\\hline
Notes		& %
		 They implement a fluid simulation to generate watercolor images. The structure of
		 the simulated paper consists of the {\em shallow-water layer} (water flow), the
		 {\em pigment-deposition layer}, and the {\em capillary layer} (water is absorbed
		 and diffused).

		The simulated quantities in the simulation are: the wet area mask, the velocity of
		each water element, the pressure of each water element, the concentration of each
		pigment in each water element, the slope of the rough paper surface, the viscosity
		and viscous drag of the medium, the water saturation of the paper, and the
		fluid-holding capacity of the paper. A heightfield is used to represent the surface
		of the paper.

\vspace{-0.1in}\begin{verbatim}
MainLoop:
    foreach (step)
        MoveWater()
        MovePigment()
        TransferPigment()
        SimulateCapilaryFlow()
    end
\end{verbatim}

		They have an editor to generate (paint) the initial conditions for the simulator, an
		image filter that takes an image and simulation parameters and performs
		"watercolorization", and a 3D model rendering pipeline which generates some of the
		simulation parameters from the geometry.  \\
\end{supertabular}

%================================================================
\subsubsection{Processing Images and Video for An Impressionist Effect \hfill{\tt Litwinowicz.1997.PIA}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes a technique that transforms ordinary video segments into animations that
      have a hand-painted look.  Our method is the first to exploit temporal coherence in video
      clips to design an automatic filter with a hand-drawn animation quality, in this case, one
      that produces an Impressionist effect.  Off-the-shelf image processing and rendering
      techniques are employed, modified and combined in a novel way.  This paper proceeds through
      the process step by step, providing helpful hints for tuning off-the-shelf parts as well as
      describing the new techniques and bookkeeping used to glue the parts together.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Painterly style imagery\\\hline
Automation	& %
		 Automated video processing pipeline -- requires parameters be set for the first
		 frame of a segment, remainder generated automatically.  \\\hline
Frame Coherence & %
		 They use optical flow techniques to calculate a vector field for the video image
		 regions over time. Temporal coherence is good.  \\\hline
Notes		& %
		  Strokes are a line parameterized by a {\em center}, a {\em length}, a thickness
		  {\em radius}, an orientation, and a {\em color}. Strokes are initially distributed
		  according to some user specified parameter for spacing. All stroke parameters are
		  randomly perturbed small amounts to give a hand-drawn look. Color is sampled from
		  the input image. Orientation is determined by fitting a spline surface to the
		  image gradient; gradients near zero are replaced by interpolating steeper nearby
		  gradients.

		  For rendering, strokes are grown from their centers, and clipped against image
		  edges from the original image (edges found with an edge detection algorithm).

		  For frame-to-frame coherence, optical flow is calculated from adjacent frames in
		  the video sequence. Existing strokes are moved according to the optical
		  flow. Strokes are culled from overly dense regions, and strokes are generated in
		  overly sparse regions.  \\
\end{supertabular}

%================================================================
\pagebreak
\subsubsection{A Non-Photorealistic Lighting Model  \hfill{\tt Gooch.1998.ANL}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Phong-shaded 3D imagery does not provide geometric information of the same richness as
      human-drawn technical illustrations.  A non-photorealistic lighting model is presented that
      attempts to narrow this gap.  The model is based on practice in traditional technical
      illustration, where the lighting model uses both luminance and changes in hue to indicate
      surface orientation, reserving extreme lights and darks for edge lines and highlights.  The
      lighting model allows shading to occur only in mid-tones so that edge lines and highlights
      remain visually prominent.  In addition, we show how this lighting model is modified when
      portraying models of metal objects.  These illustration methods give a clearer picture of
      shape, structure, and material composition than traditional computer graphics methods.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Technical illustration style imagery\\\hline
Automation	& %
		   Automated 3D pipeline.  \\\hline
Frame Coherence & %
		 No randomness in system(???), so temporal coherence shouldn't be an issue.

		NOT TRUE, though. They'll need to do something regarding the random intensities in
		the metal striping...shouldn't be that bad.  \\\hline
Notes		& %
		They observe several characteristics from technical illustrations:

		\begin{itemize}
		   \item edge lines are drawn with black curves
		   \item matte objects shaded with medium intensities with warmth or coolness of
		         color indicating surface normal; single light provides white highlights
		   \item shadowing not shown
		   \item metal objects shaded as if very anisotropic
		\end{itemize}

		A new lighting equation for real-time graphics is presented:
		\[{\bf I} = (1 + \hat{\bf l}\cdot\hat{\bf n}) \times k_{cool} +
			    (1 - (1 + \hat{\bf l}\cdot\hat{\bf n}) / 2) \times k_{warm} \]

		The cool and warm colors are linear blends of blue/yellow and
		black/object-color. The cool and warm colors are parameterized to give control over
		the temperature shifts and prominence of object color.

		To simulate milled objects (which are used for all metals), 20 stripes are mapped
		onto the parametric axis of maximum curvature. Stripe intensities are random between
		0.0 and 0.5, with the strip closest to the light source direction being overwritten
		with 1.0.

		The model can be mostly approximated with a phong shading model. Edge lines can be
		generated in a number of different ways.  \\
\end{supertabular}

%================================================================
\subsubsection{Painterly Rendering with Curved Brush Strokes of Multiple Sizes\hfill{\tt Hertzmann.1998.PRW}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We present a new method for creating an image with a hand-painted appearance from a
      photograph, and a new approach to designing styles of illustration.  We "paint" an image with
      a series of spline brush strokes.  Brush strokes are chosen to match colors in the source
      image.  A painting is built up in a series of layers, starting with a rough sketch drawn with
      a large brush.  The sketch is painted over with progressively smaller brushes, but only in
      areas where the sketch differs from the blurred source image.  Thus, visual emphasis in the
      painting roughly corresponds to the spatial energy present in the source image.  We
      demonstrate a technique for painting with long, curved brush strokes, aligned to normals of
      image gradients.  Thus we begin to explore the expressive quality of complex brush strokes.

      Rather than process images with a single manner of painting, we present a framework for
      describing a wide range of visual styles.  A style is described as an intuitive set of
      parameters to the painting algorithm that a designer can adjust to vary the style of painting.
      We show examples of images rendered with different styles, and discuss long-term goals for
      expressive rendering styles as a general-purpose design tool for artists and animators.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}
NPR Effect	& Painterly style imagery\\\hline
Automation	& %
		 Automated image filter which takes a source image, a list of brush sizes, and some
		 style parameters.  \\\hline
Frame Coherence & %
		 Single-frame image filtering; no animations were attempted. They do state that:
		\begin{quote}
		   new techniques will be required to maintain temporal coherence for complex brush
		   strokes with various size and shape attributes, while maintaining or changing
		   rendering styles.
		\end{quote}\\\hline
\end{supertabular}\ \\

\begin{supertabular}{r|p{5in}}
Notes		& %
		The painting algorithm lays down successive layers of brush strokes, from coarse to
		fine. For each brush stroke size, a reference image is created by a Gaussian blur,
		the size of the blur being a function of the size of the brush. The current canvas
		(which is initialized to a special, maximal error, color) is given to the {\tt
		paintLayer()} function, along with the reference image and the current brush.

		The {\tt paintLayer()} function visits a series of grid positions, the spacing
		defined by the size of the brush. The area around the grid point on the canvas is
		compared to the same area on the reference image, if the error exceeds a threshold,
		then {\tt makeStroke()} is called on the point in the area of greatest error. The
		strokes are then composited onto the canvas in a random order, after all strokes are
		made.

		The {\tt makeStroke()} function places a series of spline control points along the
		normal to the image gradient, starting at the stroke's origin. The brush is swept
		along the spline curve until either both the minimum stroke length and a color error
		threshold is exceeded, or a maximum stroke length is reached.

		They've implemented a number of style parameters to control the painting process,
		which include:
		\begin{itemize}
		   \item approximation threshold (error threshold to make a stroke)
		   \item brush sizes (smallest, largest brush sizes, number of brushes)
		   \item curvature filter constant (influences stroke curvature)
		   \item blur factor constant
		   \item minimum / maximum stroke lengths
		   \item paint opacity
		   \item grid size constant
	    	   \item color jitter (random alteration of rgb, value, saturation)
		\end{itemize}

		They have parameter settings that they feel emulate "impressionist",
		"expressionist", "colorist wash", and "pointillist" styles.  \\
\end{supertabular}

%================================================================
\pagebreak
\subsubsection{Art-Based Rendering of Fur, Grass, and Trees \hfill{\tt Kowalski.1999.ARO}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Artists and illustrators can evoke the complexity of fur or vegetation with relatively few
      well-placed strokes.  We present an algorithm that uses strokes to render 3D computer graphics
      scenes in a stylized manner suggesting the complexity of the scene without representing it
      explicitly.  The basic algorithm is customizable to produce a range of effects including fur,
      grass and trees, as we demonstrate in this paper and accompanying video.  The algorithm is
      implemented within a broader framework that supports procedural stroke-based textures on
      polyhedral models.  It renders moderately complex scenes at multiple frames per second on
      current graphics workstations, and provides some interframe coherence.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& Cartoony object silhouettes / image style\\\hline
Automation	& %
		   Automated 3D pipeline.  \\\hline
Frame Coherence & %
		   DIA component of the algorithm has no concept of interframe coherence, so graftal
		   structures can be crowded out and popping can occur. Distracting.  \\\hline
Notes		& %
		The graftal textures are placed according to a "difference image" algorithm. A
		reference image is rendered, with darker regions indicating high graftal density,
		and lighter regions indicating lower graftal density. This is the initial difference
		image. The image is then searched for the pixel most in need of "darkening", or the
		application of the texture. A graftal is placed, and a Gaussian dot whose size
		corresponds to the graftal in screen space is subtracted from the difference
		image. The search is repeated until no further locations needing graftal placement
		are found.

		The graftal textures themselves are polygonal objects which are oriented in a
		sensible way (outward if on the edge, for example), and turned to face the
		camera. In general, they're placed so they "bend down", though this is a parameter
		and can be changed. The graftals maintain some minimum amount of screen space if
		they are going to be drawn at all; they do not necessarily follow realistic
		perspective resizing.  \\
\end{supertabular}

%================================================================
\subsubsection{View-Dependent Geometry \hfill{\tt Rademacher.1999.VG}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      When constructing 3D geometry for use in cel animation, the reference drawings of the object
      or character often contain various view-specific distortions, which cannot be captured with
      conventional 3D models.  In this work we present technique called View-Dependent Geometry,
      wherein a 3D model changes shape based on the direction it is viewed from.  A view-dependent
      model consists of a base model, a set of key deformations (deformed versions of the base
      model), and a set of corresponding key viewpoints (which relate each 2D reference drawing to
      the 3D base model).  Given an arbitrary viewpoint, our method interpolates the key
      deformations to generate a 3D model that is specific to the new viewpoint, thereby capturing
      the view-dependent distortions in the reference drawings.
\end{minipage}}\end{quote}

\paragraph{Notes}\ \\

\begin{supertabular}{r|p{5in}}

NPR Effect	& View-specific geometry distortions\\\hline
Automation	& %
		   This is more "non-physical geometry", than NPR. User interactively specifies a
		   number of key geometry deformations, which are then automatically interpolated
		   based on view direction.  \\\hline
Frame Coherence & %
		   Interpolation of key deformations is smooth, so temporal coherence should not be
		   an issue.  \\\hline
Notes		& %
		To create view-dependent models, one orients the model with a reference image and
		then deforms the model somehow so that it conforms or resembles the reference
		image. Do this for each reference image.

		To render a view-dependent model, the three nearest key viewpoints to the current
		view are found. Based on the current view's proximity to each of these key views,
		blending weights are calculated for the key deformations. The model vertex positions
		are interpolated between the interpolations, and the model is rendered. The
		interpolation is parameterized for small visual effects ("sharpness of a transition"
		and whatnot).

		If the convex hull of the viewpoints does not enclose the center of the viewsphere,
		then some viewpoints will not have associated key deformations. In this case, for
		these views, the original, undeformed, model is used.

		For animated models, one has key deformations for different views over time. They
		"factor out the deformation offsets, propagate those over the animation cycle, and
		then add them back into the underlying animated model". Em, yep.  \\
\end{supertabular}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Visibility}

%================================================================
\subsubsection{Visibility Preprocessing for Interactive Walkthroughs \hfill{\tt Teller.1991.VPF}}
\label{Teller.1991.VPF}
\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The number of polygons comprising interesting architectural models is many more than can be
      rendered at interactive frame rates.  However, due to occlusion by opaque surfaces
      (e.g. walls), only a small fraction of a typical model is visible from most viewpoints.

      We describe a method of visibility preprocessing that is efficient and effective for
      axis-aligned or axial architectural models.  A model is subdivided into rectangular cells
      whose boundaries coincide with major opaque surfaces.  Non-opaque portals are identified on
      cell boundaries, and used to form an adjacency graph connecting the cells of the subdivision.
      Next, the cell-to-cell visibility is computed for each cell of the subdivision, by linking
      pairs of cells between which unobstructed sightlines exist.

      During an interactive walkthrough phase, an observer with a known position and view cone moves
      through the model.  At each frame, the cell containing the observer is identified, and the
      contents of potentially visible cells are retrieved from storage.  The set of potentially
      visible cells is further reduced by culling it against the observer's view cone, producing
      eye-to-cell visibility.  The contents of the remaining visible cells are then sent to a
      graphics pipleine for hidden-surface removal and rendering.

      Tests on moderately complex 2-D and 3-D axial models reveal substantially reduced rendering
      loads.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item They make the observation that the computation of exact visibility isn't necessary.  An
           algorithm which overestimates visibility is reasonable for fast hardware.

     \item Visibility estimation methods include:
	\begin{itemize}
	   \item View-frustum collision with scene overestimation, which potentially {\em vastly}
	         overestimates scene (for occluders near camera and complex hidden geometry behind).
	   \item Finding portals in otherwise opaque objects and treating them as light sources;
	         objects that live in shadow volumes with respect to these `lights' can be marked as
	         invisible -- not used, far to computationally expensive.
	   \item Discrete sampling / ray casting for visibility; can greatly underestimate
	         visibility, and even then large numbers of rays must be cast.
	\end{itemize}

     \item Teller's approach in a nutshell: divide the scene along major opaque features into cells,
           and then compute and store cell-to-cell visibility information.  Some additional culling
           techniques are presented for the case where the position and viewing direction of the
           observer are known.

     \item Two assumptions are made about input -- cell borders are axially aligned, and that
           coordinate data appears on a grid.  Neither assumption affects the algorithm
           conceptually, both merely ease implementation.

     \item They require the spacial subdivision scheme to consist of convex cells, and support point
           location, portal enumeration on cell boundaries, and neighbor finding.  Based on their
           assumptions, they choose a $k$-D tree for the spatial subdivision scheme.

     \item Finding visible cells is done via:\\
	{\tt
	findVisibleCells(Cell C, PortalSequence P, VisibleCellSet V)\\
	\verb#    # V = V $\cup$ C\\
	\verb#    # foreach N (neighbor(C))\\
	\verb#        # foreach p (portal(N,C))\\
	\verb#            # orient(p, from(N,C))\\
	\verb#            # P' = concatenate(P,p)\\
	\verb#            # if (stabbingLine(P'))\\
	\verb#                # findVisibleCells(N,P',V)
	}

     \item The recursive nature of the {\tt findVisibleCells} suggests a tree data structure, a {\em
           stab tree}, to represent a PVS (potentially visible set) from a cell.  Each node in the
           tree corresponds to a cell visible from the source cell, each edge a portal.

     \item Querying the existence of a stab line through a portal sequence can be done as a linear
           program, in $\mathcal{O}(m)$ time, where $m$ is the number of portals.

     \item Eye-to-cell visibility can be approximated or computed in a number of ways:
	\begin{itemize}
	   \item {\bf Disjoint cell}.  Collide view volume with PVS.  If it collides, draw it.
	   \item {\bf Connected component}.  Do a depth first search of the PVS, drawing (and
	         continuing the search from) cells interior to the view volume.
 	   \item {\bf Incident portals}.  Do a depth first search of the PVS, drawing (and
 	         continuing the search from) cells whose connecting portals are interior to the view
 	         volume.
	   \item {\bf Exact eye-to-cell}.  Phrase search as a linear program, with the additional
	         constraints that the stab line must pass through the viewer's position, and two
	         insisting that the stabbing ray lie inside the two halfspaces whose intersection
	         defines $C$ (em, what?).
	\end{itemize}


\end{itemize}

%================================================================
\pagebreak
\subsubsection{Management of Large Amounts of Data in Interactive\hfill{\tt Funkhouser.1992.MOL}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We describe techniques for managing large amounts of data during an interactive walkthrough of
      an architectural model.  These techniques are based on a spatial subdivision, visibility
      analysis, and a display database containing objects described at multiple levels of detail.
      In each frame of the walkthrough, we compute a set of objects to render, i.e. those
      potentially visible from the observer's viewpoint, and a set of objects to swap into memory,
      i.e. those that might become visible in the near future.  We choose an appropriate level of
      detail at which to store and to render each object, possibly using very simple representations
      for objects that appear small to the observer, thereby saving space and time.  Using these
      techniques, we cull away large portions of the model that are irrelevant from the observer's
      viewpoint, and thereby achieve interactive frame rates.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item To {\tt Teller.1991.VPF} (\ref{Teller.1991.VPF}), Funkhouser adds a couple of incremental
           improvements.  Cell-to-object visibility, and eye-to-object visibility.

     \item To the stab tree is added a list of potentially visible objects in the each cell.  The
           list is found by assembling a set of half-spaces during the recursion, and adding objects
           which live in the space bounded by the half-spaces.

     \item For eye-to-object visibility, half-spaces are again assembled, and objects in the
           potentially visible list are checked against them.  If within, they are drawn.

\end{itemize}


%================================================================
\subsubsection{Portals and Mirrors\hfill{\tt Luebke.1995.PAM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      We describe an approach for determining potentially visible sets in dynamic architectural
      models.  Our scheme divides the models into cells and portals, computing a conservative
      estimate of which cells are visible at render time.  The technique is simple to implement and
      can be easily integrated into existing systems, providing increased interactive performance on
      large architectural models.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The scheme first projects vertices of each portal onto screen-space and takes the axial
           2D bounding box of the resulting points.  The resulting box is called the {\em cull box},
           and represents a conservative bound for the portal.  Objects whose screen space
           projections fall outside the cull box can be safely culled.  As each successive portal is
           traversed, its cull box is intersected with the aggregate cull box.

     \item During the traversal, the objects in a cell are tested for visibility by comparing the
           screen-space projection of the object's bounding box with the cull box.  If the boxes
           intersect, the object must be drawn.  Objects can be tagged when drawn so that if they
           can be also seen through another portal, they are not redrawn.


\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Animation}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Principles and Concepts}

%================================================================
\subsubsection{Principles of Traditional Animation \hfill{\tt Lasseter.1987.POT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes the basic principles of traditional 2D hand drawn animation and their
      application to 3D computer animation.  After describing how these principles evolved, the
      individual principles are detailed, addressing their meanings in 2D hand drawn animation and
      their application to 3D animation.  This should demonstrate the importance of these principles
      to quality 3D computer animation.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{enumerate}
     \item {\bf Squash and Stretch}.  Defining the rigidity  and mass of an object by distorting its
           shape during an action
     \item {\bf Timing}.  Spacing actions to define the weight and size of objects and the
           personality of characters.
     \item {\bf Anticipation}.  The preparation for an action.
     \item {\bf Staging}.  Presenting an idea so that it is unmistakably clear.
     \item {\bf  Follow Through and Overlapping Action}.  The termination of an action and
           establishing its relationship to the next action.
     \item {\bf Straight Ahead Action and Pose-To-Pose Action}.  The two constrasting approaches to
           the creation of movement.
     \item {\bf Slow In and Out}.  The spacing of the inbetween frames to achieve subtlety of
           timing and movement.
     \item {\bf Arcs}.  The visual path of action for natural movement.
     \item {\bf Exaggeration}.  Accentuating the essence of  an idea via the design of the action.
     \item {\bf Secondary Action}.  The action of an object resulting from another action.
     \item {\bf Appeal}.  Creating a design or an action that the audience enjoys watching.
\end{enumerate}


%================================================================
\subsubsection{Computer Animation \hfill{\tt Hodgins.1999.CA}}

%================================================================
\subsubsection{Computer Animation \hfill{\tt Parent.2002.CA}}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Physical Simulation}

%================================================================
\subsubsection{Flocks, Herds, and Schools \hfill{\tt Reynolds.1987.FHA}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a
      beautiful and familiar part of the natural world.  But this type of complex motion is rarely
      seen in computer animation.  This paper explores an approach based on simulation as an
      alternative to scripting the paths of each bird individually.  The simulated flock is an
      elaboration of a particle system, with the simulated birds being particles.  The aggregate
      motion of the simulated flock is created by a distributed behavioral model much like that at
      work in a natural flock; the birds choose their own course.  Each simulated bird is
      implemented as an independent actor that navigates according to its local perception of the
      dynamic environment, the laws of simulated physics that rule its motion, and a set of
      behaviors programmed into it by the "animator".  The aggregate motion of the simulated flock
      is the result of the dense interaction of the relative simple behaviors of the individual
      simulated birds.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{Physically Based Modeling \hfill{\tt Witkin.2001.PBM}}


\paragraph{Notes}

\begin{itemize}
     \item This DiffEq course primarily is concerned with Initial Value Problems.

     \item A canonical ODE has the form $\dot{x} = f(x,t)$, which defines a vector field.
           If the an ODE depends on time, then the vector field will change with time.

     \item Physical simulation is primarily concerned with numerical solutions rather than symbolic
           solutions.

     \item Euler's method simply takes a step in the derivative direction:
	\[ x(t_0 +h) = x_0 + h\dot{x}(t_0) \]
	   Euler's method is equivalent to truncating the Taylor Series to the first two terms.

     \item The midpoint method:
        \[ x(t_0+h) = x(t_0) + h (f\left(x_0 + (h/2)f(x_0)\right)) \]
    	   This is also called Runga-Kutta of order two, and truncates the Taylor Series to the
    	   first three terms.

     \item Runga-Kutta of order four is the most popular

     \item Adaptive step sizes allow us to take as large of steps as possible within some error
          tolerance.

     \item Motion of a Newtonian particle is governed by the second order ODE $\ddot{x}=f/m$.  We
          deal with this by creating coupled first-order ODEs: $\dot{v}=f/m$, $\dot{x}=v$.

     \item The position / velocity vectors are concatenated into a 6-vector.  This position /
          velocity space is called {\em phase space}.

     \item A particle system is a high dimensional phase space formed by joining particle vectors
          together.

     \item Solver thinks of a system as a point in a high-dimensional space.  Simulation thinks of
          system as interacting components.

     \item {\tt Func EulerStep(float time):\\
	  \verb#      # ComputeForces();\\
	  \verb#      # ParticleDeriv();\\
	  \verb#      # SetAddStatePlusTimeScaledDeriv();\\
	  \verb#      # SetTime();}

     \item Unary Forces: Gravity, Drag\\
	   N-Ary Forces: Springs\\
	   Spatial Interaction Forces: $\mathcal{O}(n^2)$ number of particles

     \item  Certain types of constraints make ODEs ``stiff'', requiring extremely small timesteps in
            some situations to avoid instability ($2^{nd}$ order dynamics on particles attached by
            springs).

     \item There exists an implicit method for solving stiff ODEs, which amounts to approximating
           timesteps in reverse.  It requires more work per step, but generally allows much larger
           timesteps in stiff ODEs.

     \item To avoid penalty methods, one can directly compute forces needed to maintain constraints.
           Constraint forces must not add or remove energy from the system.

     \item Rigid bodies differ from particles in that they have rotation, volume, and shape.

     \item Rigid bodies have both linear velocity (how position changes with  time) and angular
           velocity (how orientation or rotation changes with time).

     \item Angular velocity, $\omega(t)$, is the axis of spin plus the rate of spin; a four-vector.
\end{itemize}

%================================================================
\subsubsection{Large Steps in Cloth Simulation \hfill{\tt Baraff.1998.LSI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      The bottle-neck in most cloth simulation systems is that time steps must be small to avoid
      numerical instability.  This paper describes a cloth simulation system that can stably take
      large time steps.  The simulation system couples a new technique for enforcing constraints on
      individual cloth particles with an implicit integration method.  The simulator models cloth as
      a triangular mesh, with internal cloth forces derived using simple continuum formulation that
      supports modeling operations such as local anisotropic stretch or compression; a unified
      treatment of damping forces is included as well.  The implicit integration method generates a
      large, unbanded sparse linear system at each time step which is solved using a modified
      conjugate gradient method that simultaneously enforces particles' constraints.  The
      constraints are always maintained exactly, independent of the number of conjugate gradient
      iterations, which is typically small.  The resulting simulation system is significantly faster
      than previous accounts of cloth simulation systems in the literature.
\end{minipage}}\end{quote}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Motion Capture and Editing}

%================================================================
\subsubsection{Real-Time Inverse Kinematics Techniques \hfill{\tt Tolani.2000.RIK}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      In this paper we develop a set of inverse kinematics algorithms suitable for an
      anthropomorphic arm or leg.  We use a combination of analytical and numerical methods to solve
      generalized inverse kinematics problems including position, orientation, and aiming
      constraints.  Our combination of analytical and numerical models results in faster and more
      reliable algorithms than conventional Jacobian and optimization-based techniques.
      Additionally, unlike conventional numerical algorithms, our methods allow the user to
      interactively explore all possible solutions using an intuitive set of parameters that define
      the redundancy of the system.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Inverse Kinematics Problem Definition: for a set of $n$ joint variables, find values such
           that the end effector is in a given position, or determine that no solution is possible.

     \item Broadly speaking, inverse kinematics algorithms can be characterized as {\em analytical}
           or {\em numerical}.  

     \item Analytical methods are said to be {\em complete}, since they find all possible
           solutions.  They can further be divided into {\em closed-form} and {\em
           algebraic-elimination-based} methods.
	\begin{itemize}
	   \item In a closed-form method, the solution to the joint variables can be directly
	         expressed as a set of closed-form equations.  In general, closed-form solutions can
	         only be obtained for 6-DOF systems with special kinematic structure.
	   \item Algebraic-elimination based methods express the joint variables as solutions to a
	         system of multivariate polynomial equations, or alternatively express a single joint
	         variable as the solution to a very-high-degree polynomial and determine the other
	         joint variables using closed form computations.  These methods will require
	         numerical subroutines, as the degree of the polynomials is greater than 4 (but are
	         still considered analytic methods, as all solutions can be found).
	\end{itemize}

     \item Numerical methods iteratively approach a single solution based on an initial guess.  Their
           main advantage is that they can be used in systems where the problem is ill-posed.
	\begin{itemize}
	   \item Newton-Raphson methods: The solution to an IK problem is the roots to a system of
	         nonlinear equations.  They are slow to converge, and singularities may cause them
	         to fail.
	   \item Pieper's methods: An adapted Newton-Raphson method.  
	   \item Methods based on differential equations-resolved motion rate control.
	   \item For redundant manipulators, the Jacobian is not square, but the above methods can
	         be adapted.
	   \item Control-theory-based-methods: these are based on casting the differential equation
	         into a control problem.  
	   \item Methods based on ${\bf J}^T$.
	   \item Optimization approaches: IK can be regarded as a nonlinear optimization problem.
	\end{itemize}
\end{itemize}


%================================================================
\subsubsection{Dealing with Ill-Conditioned Equations \hfill{\tt Maciejewski.1990.DWT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      Realistic motion simulation for articulated figures has generated a great deal of interest in
      recent years.  Whether the simulation is based on the kinematics or the dynamics of the
      figure, most formulations rely on the solution of linear systems of equations.  Sometimes
      solution of these equations presents a great deal of numerical difficulty, resulting in
      unrealistic or spurious motion for the figure or in excessive computation because of small
      integration intervals.

      This article shows the cause of the difficulty to be related to the physical structure of the
      figure, not the mathematical formulation.  It also shows how to determine the severity of ill
      conditioning and how to obtain physically meaningful solutions without excessive computations,
      even when dealing with extremely ill-conditioned configurations.
\end{minipage}}\end{quote}

%================================================================
\subsubsection{Retargetting Motion to New Characters \hfill{\tt Gleicher.1998.RMT}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      In this paper, we present a technique for retargeting motion: the problem of adapting an
      animated motion from one character to another.  Our focus is on adapting the motion of one
      articulated figure to another figure with identical structure but with different segment
      lengths, although we use this as a step when considering less similar characters.  Our method
      creates adaptations that preserve desirable qualities of the original motion.  We identify
      specific features of the motion as constraints that must be maintained.  A spacetime
      constraints solver computes an adaptive motion that re-establishes these constraints while
      preserving the frequency characteristics of the original signal.  We demonstrate our approach
      on motion capture data.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{enumerate}
     \item Annotate motion with constraint information

     \item Compute an initial estimate of a solution by scaling the translations of the motion, then
           adding a single translation to reposition the motion

     \item Choose the frequency of the b-spline displacement curve

     \item Solve for a displacement curve that satisfies constraints when added to the motion

     \item If solution is not sufficiently close to constraint satisfaction, increase displacement
           curve frequency and solve again, using most recent solution as a starting point
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Interfaces and Visualization}

Because no courses are currently offered in this area, our expectations of students are much lower
than in other areas.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagebreak
\section{Seminal Systems}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Sketchpad \hfill{\tt Sutherland.1963.SAM}}

\paragraph{Notes}
\begin{itemize}
     \item In the early sixties, most computers ran batches of jobs only, and did not run
           ``on-line''.  A notable exception to this was the TX-2 at MIT's Lincoln Laboratory.

     \item The TX-2 had 320Kb of fast memory, twice the capacity of the biggest commercial machines.
           It had magnetic tape storage, an on-line typewriter, the first Xerox printer, paper tape
           for program input, and a nine inch CRT.

     \item The display, a lightpen, and a bank of switches were the interface on which Ivan based
           the first interactive computer graphics. In 1963, his Ph.D. thesis, "Sketchpad: A
           Man-machine Graphical Communications System," used the lightpen to create engineering
           drawings directly on the CRT.

     \item Sketchpad pioneered the concepts of graphical computing, including memory structures to
           store objects, rubber-banding of lines, the ability to zoom in and out on the display,
           and the ability to make perfect lines, corners, and joints. This was the first GUI
           (Graphical User Interface) long before the term was coined.

\end{itemize}

\textcolor{red}{\bf Watch sketchpad video!}



%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{A Head Mounted Three Dimensional Display \hfill{\tt Sutherland.1968.AHT}}

\paragraph{Notes}

\begin{itemize}
     \item Major difficulties in creating the head-mounted display included solving:
	\begin{itemize}
	   \item the {\em windowing problem}, or how to do clipping
	   \item the {\em hidden line problem}, backface culling; they punted and showed wireframes
	         with the backfaces still in place
	\end{itemize}

     \item The display consisted of an elaborate arm contraption attached to the head, mounted on
           the ceiling, to both measure viewing parameters (position / rotation), and to feed
           information to the eye-facing CRTs.

     \item General purpose computers at the time were unable to do the matrix operations needed at a
           sufficient speed, so they built a special-purpose matrix multiplier which had a
           throughput of about 3 million multiplications per second.  The clipping divider operated
           at a similar speed, processing two end points in about 10ms (amortized speed; operation
           was data dependent).  The entire set up could drive the CRTs with 3000 lines at 30 fps.

     \item Line generator, clipping divider, and matrix multiplier processed data in a pipeline,
           taking about 10ms per line to process.

     \item The user had a 40 degree field of view, viewing a virtual display 18 inches from the
           face.

     \item Head position measurement could be made at a resolution of 1/100 of an inch and one part
           in 10,000 of rotation.  A finer resolution wouldn't have helped, because the
           digital-to-analog conversion in the display resulted in a ``grain'' about that size.

     \item In addition to measuring head position with the arm, they also used ultrasonic emitters
           and sensors for tracking.  It operated well enough over the span of several minutes,
           where upon cumulative sensor errors reached the point of being objectionable.

     \item The found that wireframe representations of geometry did not sufficiently convey 3D
           shape...shape was often ambiguous.

     \item They were surprised at how much a stereo display enhanced the experience.

\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{A System for Computer Generated Movies \hfill{\tt Catmull.1972.ASF}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      With the recent developments in fast hidden surface algorithms and a method for smooth shading
      half-tone pictures, it has become feasible to generate useful movies with the computer.  This
      paper describes a system used to make computer generated movies.  It also explains the methods
      used to attempt to solve the problems of the object representation, object manipulation, and
      ease of specifying motion.  The system was first used to make a movie of a hand that lasts for
      little more than a minute.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The system took advantage of recent advances in hidden surface removal and the newly
           created Gouraud shading.

     \item Models are structured as a hierarchy of polygon quads.  Transformations on polygons are
           done relative to their parent's transformations.

     \item Polygons are given symbolic names, and these names are used to express parental
           relationships.

     \item With their hand model, it takes 14 instructions to specify a pose.

     \item They define a ``Motion Picture Language'' called MOP.  Most statements in mop are of the
           form:

	\begin{quote}
	   {\tt <label> <frame period> <instruction> <parameters>}
	\end{quote}

	   The {\tt <label>} labels the instruction, not the target.  A frame period is of the form
	   {\tt <expr>,<expr>,<table name>}.  The expressions specify start and end times, and the
	   table dictates a rate of change.  Instructions are divided into two lists, {\em known},
	   if the begin and end times are known, and {\em unknown}, if not.  On each frame the known
	   list is walked, and statements are executed if the current time is during their frame
	   period.  Statements executed can shift items from the {\em unknown} list to the {\em
	   known} list.

\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{The Reyes Rendering Architecture \hfill{\tt Cook.1987.TRI}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      An architecture is presented for fast high-quality rendering of complex images.  All objects
      are reduced to common world-space geometric entities called micropolygons, and all of the
      shading and visibility calculations operate on these micropolygons.  Each type of calculation
      is performed in a coordinate system that is natural for that type of calculation.
      Micropolygons are created and textured in the local coordinate system of the object, with the
      result that texture filtering is simplified and improved.  Visibility is calculated in screen
      space using stochastic point sampling with a z buffer.  There are no clipping or inverse
      perspective calculations.  Geometric and texture locality are exploited to minimize paging and
      to support models that contain arbitrarily many primitives.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Their assumptions and goals:
	\begin{itemize}
	   \item {\bf Model complexity}. They expect the need for hundreds of thousands of geometric
	         primitives, each one which may be complex.
	   \item {\bf Model diversity}.  They wish to support a variety of primitives, including
	         procedural models, fractals, graftals, and particle systems.
	   \item {\bf Shading Complexity}.  They consider programmable shader, capable of working
	         with textures, environment maps, bump maps, displacement maps, shadows, and
	         refraction, a necessity.
	   \item {\bf Minimal Ray Tracing}.  They wish to approximate global illumination effects
	         with high quality local approximations whenever possible.
	   \item {\bf Speed}.  They must be able to render quickly to achieve the 24 fps for a 2
	         hour movie quantity of images in a reasonable (a year or so) length of time.
	   \item {\bf Image Quality}.  They will avoid aliasing artifacts.
	   \item {\bf Flexibility}.  The system must be extensible to accommodate new techniques.
	\end{itemize}

     \item They have a number of design principles:
	\begin{enumerate}
	   \item {\bf Natural coordinates}. Do calculations in the most natural coordinate system
	         for each calculation.
	   \item {\bf Vectorization}. The architecture should support parallelized computation.
	   \item {\bf Common Representation}. Convert all primitives to a common primitive.  They
	         chose {\em Micropolygons}, flat-shaded subpixel-sized quadrilaterals.
	   \item {\bf Locality}.  Minimize state changes.
		\begin{enumerate}
		   \item {\bf Geometric locality}. Calculations for a primitive should be calculated
		         once and not reference other primitives.
		   \item {\bf Texture locality}. Minimize texture memory usage and texture loading.
		\end{enumerate}
	   \item {\bf Linearity}.  Rendering time should grow $\mathcal{O}(n)$.
	   \item {\bf Large models}. No limit to number of primitives in model.
	   \item {\bf Back door}. There is a hook to allow external programs to render components.
	   \item {\bf Texture Maps}. Texture map usage will be extreme and must be very efficient.
	\end{enumerate}

     \item Micropolygons are flat-shaded quads approximately 1/2 a pixel on a side.  As 1/2 a pixel
           is the Nyquist limit for an image, flat-shading is appropriate.

     \item Primitives are diced into micropolygons in eye-space, using only an estimate of size in
           screen space.  The result of a dicing is a two-dimensional array of micropolygons called
           a {\em grid}.  All micropolygons in a grid are shaded together.

     \item Rendering algorithm:%
	\vspace{-0.15in}
	\begin{verbatim}
	Init(zBuffer);
	foreach primitive (model):
	   if (boundable(primitive)):
	      eyeBound(primitive);
	      cullIfNeeded(primitive);
	      if (crossesEyePlane(primitive)):
	         markNotDiceable(primitive);
	   if (canDice(primitive)):
	      grid = dice(primitive);
	      shade(grid);
	      foreach micropoly (grid):
	         cullIfNeeded(micropoly);
	         if (zSampleTest(micropoly)):
	            PixelAndZStore(micropoly);
           else
	      push(model, split(primitive))
	\end{verbatim}

     \item This approach has the advantages in that there are no inversion calculations (projecting
           pixel corners onto patches to find normals, texture coords), there are no clipping
           calculations (only micropoly cull), shading and normal calculations are vectorized, and
           texture thrashing is avoided.

\end{itemize}


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{High Performance Polygon Rendering \hfill{\tt Akeley.1988.HPR}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes a system architecture for realtime display of shaded polygons.
      Performance of 100,000 lighted, 4-sided polygons per second is achieved.  Vectors and points
      draw at the rate of 400,000 per second.  High-speed pan and zoom, alpha blending, realtime
      video input, and anti-aliased lines are supported.  The Architecture heavily leverages
      parallelism in several forms: pipeline, vector, and array processing.  It is unique in
      providing efficient and balanced graphics that support interactive design and manipulation of
      solid models.  After an overview of algorithms and computational requirements, we describe the
      details of the implementation.  Finally, the unique features enabled by the architecture are
      highlighted.
\end{minipage}}\end{quote}

\paragraph{Notes}

\begin{itemize}
     \item The goals of the architecture were: {\em 100,000 polygons per second}, {\em 10 frames per
           second}, and {\em window support}.

     \item The problem components are:
	\begin{enumerate}
	   \item {\bf Transfer vertex data from memory to graphics subsystem}.  Requires a bandwidth
	         of 10 MB/sec for 400,000 vertices.
	   \item {\bf Transform vertex coordinates}.  Requires 11 Mflops for standard homogeneous
	         data, or 9.5 Mflops in the case where homogeneous component is 1.0.
	   \item {\bf Transform vertex normals}.  Requires 9.5 Mflops, including normalization.
	   \item {\bf Light each vertex}.  Uses lighting model with a single, infinitely distant
	         light, an infinitely distant viewer, ambient, diffues, and specular components.
	         Requires 11 Mflops.
	   \item {\bf Clip each vertex}.  Requires 2.5 Mflops, properly optimized.
	   \item {\bf Project each vertex}.  Requires 4.5 Mflops.
	   \item {\bf Map vertex coordinates to the screen}.  Requires 3.5 Mflops.\\
		 \vspace{-0.15in}\begin{center}\shadowbox{Thats a total of 46.5 Mflops.}\end{center}
	   \item {\bf Fill the resulting screen-space polygons, interpolating color, depth}.  They
	         benchmark fill rate necessary at 10 pixel $\times$ 10 pixel polygons at 100,000
	         polygons per second.  For larger polygons, a higher fill rate would be necessary.
	   \item {\bf Clip all drawing against visible window boundaries}.
	   \item {\bf Be prepared to  quickly swap drawing contexts at any time}.
	   \item {\bf Continually scan frame buffer at screen refresh rate}.
	\end{enumerate}
\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\pagebreak
\subsection{An Object-Oriented 3D Graphics Toolkit \hfill{\tt Strauss.1992.AO3}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper presents an object-oriented toolkit for developers of interactive 3D graphics
      applications.  The primary goal of the toolkit is to make it easier for programmers to create
      3D graphics applications that employ direct manipulation techniques in addition to
      conventional 2D widgets.  Such techniques have generally been ignored in previous graphics
      packages and systems.

      The toolkit provides a general and extensible framework for representing 3D scenes so that
      applications can integrate their data with graphical objects rather than having duplicate
      copies.  A simple, integrated event model that enables direct interaction with 3D objects is
      included.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item The toolkit is based on three criteria:
	\begin{itemize}
	   \item {\bf Object representation}.  From an application point of view, graphical data
	         should be stored as editable objects and not as collections of drawing primitives.
	   \item {\bf Interactivity}.  The event model must be integrated with the object
	         representation.
	   \item {\bf Architecture}.  Applications should not have to adapt to the object
	         representation or toolkit interaction policies.  Toolkit mechanisms should instead
	         be used to implement desired policies.
	\end{itemize}

     \item The toolkit consists of three major components: the interaction component, the node kit
           component, and the scene database component.

     \item The scene database consists of a collection of nodes.  Nodes come in many types:
	\begin{itemize}
	   \item {\em shape nodes}, represent geometry
	   \item {\em property nodes}, describe properties of the geometry (color, material, light
	         model, normals, texture, transforms)
	   \item {\em group nodes}, which connect other nodes to form a graph
	   \item {\em light/camera nodes}
	\end{itemize}

     \item As nodes can be included in the graph more than once (via the group nodes), to specify a
           particular object, one must use the path to that object from the root to unambiguously
           specify it.

     \item {\em Actions} are objects which traverse the graph and in doing so perform some action,
           such as rendering, compute cumulative transformation matrix, compute a bounding box,
           perform picking, search, etc.

     \item {\em Sensors} are objects, either triggered or timed, which executes a user callback when
           either the timer goes off or a watched for event in the graph occurs.

     \item The event model allows the window system, then the render area, and then all nodes in the
           graph access in turn to a particular user event until some object handles the event, at
           which time the transversal stops.

     \item {Manipulators} are integrated into the graph to perform actions on subgraphs by handling
           user events.

     \item Node kits provide pre-structured collections of nodes for convenience and to encourage
           consistently structured graphs.

\end{itemize}

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Modeling and Rendering Architecture from Photographs \hfill{\tt Debevec.1996.MAR}}
See section~\ref{Debevec.1996.MAR}.


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{The Menv Modeling and Animation Environment \hfill{\tt Leffler.1990.TMM}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      This paper describes Menv, an environment for the development of interactive three-dimensional
      modeling and animation systems.  Menv supports both interactive and procedural techniques.
      Systems built upon Menv are implemented as a set of independent, cooperating tools operating
      upon a shared workspace.  Models are defined in a high-level procedural language with calls to
      graphical primitives.  Animation data is bound to the model through the use of time-varying
      articulated variables.
\end{minipage}}\end{quote}

\paragraph{Notes}
\begin{itemize}
     \item Menv, or ``Modeling Environment'', is a collection of tools used in many early Pixar
           films.

     \item In Menv, a model is not a database of geometric primitives; it is a program, written in
           an interpreted C-like language called ML.

     \item ML provides three powerful, high-level capabilities for modeling: {\em replication}
           (making many copies of the same primitive), {\em precision} (they align surfaces
           precisely using the language to calculate positions), and {\em parametrization} (they can
           create a range of different objects from the same parametric design).

     \item The link between modeling and animation is the {\em articulated variable}, a variable in
           ML which can be animated.

     \item The animation is based on a {\em cue sheet}, a set of keyframes for each articulated
           variable which are interpolated over time with some spline curve.  Cue sheets can be
           static, or can be controlled algorithmically with the animation subsystem or dynamics
           subsystem.

     \item Menv is implemented as a collection of individual programs called tools.  The tools have
           a shared memory segment through which they communicate, a semaphore daemon which handles
           access to the memory, and an event handler which monitors input / output devices.  Tools
           include:
	\begin{itemize}
	   \item {\em Input/output tool}, for disk I/O of shared data
	   \item {\em Display tool}, for examination and management of the display list
	   \item {\em Camera tool}, for displaying a scene on the display device; may be static or
	         animated.
	   \item {\em Object and articulated variable selection tool}, speaks for itself
	   \item {\em 3D digitizer tool}, captures point data from a 3D scanner
	   \item {\em Curve tool}, used to interactively specifying 3D spline curves
	   \item {\em Sweep tool}, used to generate surfaces of revolution and extrusion
	   \item {\em Articulated variable keyframe tool}, to edit the cue sheet
	   \item {\em Articulated variable spline tool}, a different way to edit the cue sheet
	   \item {\em Muscle-based animation tool}, primarily for facial animation
	   \item {\em Armature-based animation tool}, for skeletal animation
	   \item {\em Playback tool}, for previewing animation
	\end{itemize}

     \item The ML language itself procedurally specifies geometry, relative to input parameters to
           instance a model, and avars, used for animation.

     \item Three different hierarchies exist relative to a model, a {\em procedural hierarchy} which
           represents variable scope, an {\em object hierarchy} which is the scope for articulated
           variables, and a {\em transformation hierarchy}, which positions the geometry.  Geometric
           transformations can be specified relative to variables in the scene so that the effective
           transformation hierarchy can be changed (object can be relative to one object or another,
           based on an avar).

\end{itemize}


%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Walkthrough \hfill{\tt Brooks.1986.WAD}}

\paragraph{Abstract}
\begin{quote}\colorbox{abcolor}{\begin{minipage}{6in}
      As part of our graphics research into virtual worlds, we are building a tool for an architect
      and his client to use for rapid prototyping of buildings by visually "walking through" them to
      refine specifications.

      Our first prototype simulated the new UNC Computer Science building with some 8000 polygons.
      BSP-tree software on the Adage Ikonas gave a colored, shaded perspective view every 3-5
      seconds while the user moved a cursor in real-time over floorplans shown on the Vector-General
      3300.

      The current (third) version uses Pixel-Planes to generate 9 updates/second, view images shown
      $4' \times 6'$ by projector.

      Active short- and long-term research questions include speed-up, stereo, a 6-DoF interface
      with eye-level defaults, and an interactive model-building, model-changing system.
\end{minipage}}\end{quote}
\paragraph{Notes}
\begin{itemize}
     \item Actually, the abstract just about says it all...
\end{itemize}
%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Quicktime VR \hfill{\tt Chen.1995.QVI}}
See section~\ref{Chen.1995.QVI}.

%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
\subsection{Sketch \hfill{\tt Zeleznik.1996.S}}


\end{document}
