
\documentstyle[12pt,lslide]{article}

\input{psfig}

% Page orientation
\landscape  % or portrait

% Tune page lengths
\addtolength{\topmargin}{0.3in}
% \addtolength{\textwidth}{1in}
\verttop

% Subsection headings
\underlinesecframe

% \smallerfonts

% Tune the paragraph and list parameters
\parskip=10pt
\parsep=0pt
\topsep=0pt
\partopsep=0pt
\itemsep=0pt
\listparindent=0pt

% Change default footer parameters
\lfoot{Paul Coddington, NPAC, paulc@npac.syr.edu}
\rfoot{Oct 94, CPS-PR-\thepage}

\begin{document}

\title[CPS 713 Parallel rendering]%
      {CPS 713 \\ 
       \vspace{1cm}
       Parallel Rendering}

\author{Paul Coddington and Alvin Leung}
\organization{Northeast Parallel Architectures Center}
\date{October 1994}

\titlepage

\section{Computer graphics background}

\subsection{Introduction}

\begin{slide}
  The goal of computer graphics is to see a virtual world.
  This virtual world is composed of one of many different objects.
  The virtual world in this talk consists of two milk cartons.
\end{slide}

\subsection{Object representation}

\begin{slide}
  How the objects are
  represented in the object database have serious impact on the rendering
  performance, quality of the generated image and the time needed to
  construct the virtual world database.

  The milk cartons can represented in two ways.  The first method,
  the milk cartons are represented as a milk carton object.
  The scene designer only need to specified the dimension,
  the texture map and the color.  Each object in turns are composed of
  number of rectangular and triangular 3D subobjects.  These objects are
  analytically
  defined, so there is no limit on resolving the details of the object.
  The resolution of the object is bounded by the surface texture map, instead.
  Also, the subobject is position relatively to a anchor point of the object.

  The second method on modeling the milk cartons is by polygons.
  Generally, 3 or 4 vertex polygons are used.  Triangle is more often used
  because all vertices of a triangle are coplanar.  Hence, the polygon will
  have only one normal. The scene designer will need to construct
  a milk carton one polygon at a time.  Then define the surface texture
  and the color for each of the polygon. 
  The motivation of defining an object by polygons is literary flexibility of
  the object.  Each polygon is represented by a fixed set of point and edges.
  These point can be arbitrary in 3D space and the edges joins the points.
  Consequently, deforming an object is relative simple task.  In this case,
  a filled milk carton's side slightly warped.

  A high quality scene rendering program uses a combination of two methods.
  In addition, polygons usually be replaced by surface patches,
  which use control points to define the surface.  As a result, the warped
  side of a fill milk carton can have a smoother curvature.  This is important
  because the accurate shadow computation requires accurate representation.

\end{slide}

\subsection{Transformation}

\begin{slide}
  Once the scene designer defined all the objects.  The objects will be place
  at a specific location.  In this example, the two objects is placed side by
  side.  The placement of the object can be done by
  transformation.  The transformation process includes translation,
  rotation and scaling, etc.  Transformation is represented as 4x4 matrices.
  These matrices can be multiplied together to form one 4x4 matrix.  Then the
  finally matrix is applied to transform the objects.

  Transformation also used to place the virtual world in a viewer's
  perspective, so that the image can be generated in the viewer's
  perspective.

  Back to the previous examples, an analytically defined object is placed by
  transforming the anchor point of the object.  
  As a result, transformation can be done to the object as a whole.  As a
  result, transformation process can be done in O(object).

  However, Transformation of a polygon based object requires computation at
  each vertex.  The transformation process requires O(all vertices).

  Finally, window to viewport transformation is used to correctly scale and
  place the generated image on screen.
\end{slide}

\subsection{clipping}

\begin{slide}
  Clipping is done to eliminated some of the objects
  or part of a object base on some user defined view volume.

  The purpose of clipping are
\begin{itemize}
\item eliminate of some objects, so that the resulting image will be more
     pleasing.

     This is generally done to prevent a viewer, who is located too close
     or inside an object, to see a very uninteresting picture after a "long"
     wait.

\item reduce computation need.

     Clipping speed up the rendering process by eliminating object, which is
     outside the field of view.  The object that are eliminated do not need
     any further processing.
     For example, A person resided in a close environment will not be able to
     see every object within the environment.  Clipping, for example, can 
     eliminate the objects behind the viewer.
\end{itemize}
\end{slide}


\subsection{hidden surface or object removal}

\begin{slide}
  Even when a object is located within the field of view, the object may still
  not be 
  visible to the viewer, for example, a object located behind a closed door.
  This object have to be eliminated form the object rendering list, in order
  for the image to be correctly rendered.  In addition, rendering an object
  requires considerable of computation effort.  As a result, further speed
  up can be realized, if an object can be eliminated form the rendering list
  with considerable low cost.  Hidden surface removal can also be done during
  rasterization.  However, this process incurs considerable computing
  resources.
\end{slide}

\subsection{Rasterization}

\begin{slide}
  Rasterization is done to transform the data represented by the object
  database into a image.  Texture mapping, color computation
  and anti-aliasing are done at this stage.  For a polygon based object,
  scanline algorithm is commonly used to render the finial image.   
\end{slide}

\section{Terrain rendering}

\subsection{Introduction}

\begin{slide}
   A terrain object is defined by a height field and a image.
   A height field, as the name suggest, encode information as height for a
   specific (x, y) coordinate.  The image is the additional information for
   the specific (x, y) coordinate and is rendered by color.
   For example, a digital evaluation model and a settlate image of a land
   landscape shows the relationship between the land use and terrain evaluation.
   Since height field of a terrain surface is closed (ie no disjointed section),
   a terrain object can be manipulated as a 2D object with third dimension as
   special case.
\end{slide}


\subsection{Terrain object representation}

\begin{slide}
   The terrain data set is stored as two dimensional data grids.  Each grid
   element contains a subsection of the terrain data set. A grid element
   can further subdivided to employ locality for better cache performance.
   A triangle is formed by three adjacent data points as show in figure.
   We choose polygon representation because interpolation of the evaluation
   and color within the polygon can provide more realistic landscape during
   close examination.

   The terrain object will also have multi resolution data.  This is motivated
   by further reducing the computational requirement, so that real time
   fly through can be done.


   The terrain data can have four or more resolutions.

\begin{itemize}

\item Quart the number of evaluation data by interpolation (as show in figure).
      This will achieve the best resolution on polygon based terrain renderer.
      This data set is only use to very close examination.  This may employ
      under special saturation.

\begin{minipage}{4.25in}
\begin{picture}(288,288)
\psfig{figure=grid1.eps,height=288pt,width=288pt}
\end{picture}
\end{minipage}
\
\begin{minipage}{4.25in}
\begin{picture}(225,225)
\psfig{figure=mesh1.eps,height=225pt,width=225pt}
\end{picture}
\end{minipage}

\item evaluation data at off the self accuracy.

\begin{minipage}{4.25in}
\begin{picture}(288,288)
\psfig{figure=grid2.eps,height=288pt,width=288pt}
\end{picture}
\end{minipage}
\
\begin{minipage}{4.25in}
\begin{picture}(225,225)
\psfig{figure=mesh2.eps,height=225pt,width=225pt}
\end{picture}
\end{minipage}

      The number of pixel covered by a line drop off linearly with respect
      to the distance.  Hence, the area of a polygon on screen is reduce
      proportional to distance square.  As show in the table, at a distance of
      20000 feet, a triangle at most occupied 48 pixel, where 1 square in on the
      screen have approximate 10 000 pixel.  As a result, when rendering terrain
      data further than 30000 with this data resolution is a complete waste
      of computational power.

\begin{tabular}{|c|c|c|} \hline
Distance (ft) & number of pixel & length on screen \\ \hline
1000 & 193.8  & approx 2 in \\ \hline
5000 & 39.0  &  approx 1/3 in \\ \hline
5280 (1 mi) & 37.0 & apporx 1/3 in\\ \hline
10000 & 19.5 & less than a 1/4 in \\ \hline
20000 & 9.8 & approx 1/10 in \\ \hline
40000 & 4.8 & aprrox 1/20 in (a big dust on screen) \\ \hline
80000 & 2.4 & aprrox 1/40 in (a medium dust on screen) \\ \hline
\end{tabular}

\item Evaluation data at medium accuracy.

      The resolution of the data is reduced, but higher resolution is
      maintained for special terrain features.

\item Evaluation data at course accuracy.

      The resolution of the data is further reduced, but maintained accuracy
      representation of large terrain features.
\end{itemize}

\end{slide}

\subsection{The terrain rednering process}

\begin{slide}
\begin{itemize}
\item Clipping (course)

\begin{picture}(320,343)
\psfig{figure=clipping.eps,width=320pt,height=343pt}
\end{picture}

   Since the goal of this terrain rendering project is allows high school
   teachers and students to do fly-bys on the terrain data set,
   we can assume the world view volumn of the user is bounded by
   simple flight characteristic.  In other words, the user will most often be
   looking level and have a level flight path.  By projecting the view volumn
   onto a 2D plane, we can identify a number of grid point that may been seen
   by the viewer.
   
   As show in the following figures, a viewer
   turned 4 degree to the right.  The turning rate is 240 degree per minutes,
   40 revolutions per hour.

\begin{minipage}{4.46in}
\begin{picture}(321,344)
\psfig{figure=image1a.ps,width=321pt,height=344pt}
\end{picture}
\end{minipage}
\
\begin{minipage}{4.46in}
\begin{picture}(321,344)
\psfig{figure=image5a.ps,width=321pt,height=344pt}
\end{picture}
\end{minipage}

   The two pictures shows that two of the squares are deactivated on the right
   side and two new squares are activated on the left side.
   As a result, the locality of the viewer position can be exployed to
   elliminate the unseen polygons.  Furthermore, with a coarse grid, we can
   determine, which part of the data is needed in core.

\item Transformation
\item Clipping (fine)
\item Hidden surface removal (back facing cull)
\item rasterization (scanline, Zbuffer, anti-aliasing)
\end{itemize}
\end{slide}

\section{Parallel terrain rednering}

\begin{slide}
   The grid data structure will be scatter decomposed across all processors.
   The redering pipeline remains the same as
\end{slide}


\end{document}

