% proposal.tex
% SC WEIRICH
% 1994 npac reu program
% June 1994

\documentstyle[leqno,twoside,11pt,ltexproc, psfig]{article}
\setlength{\oddsidemargin}{+1in}
\setlength{\evensidemargin}{+.6in}
\setlength{\topmargin}{+5mm}
\raggedbottom

\begin{document}
\cleardoublepage
\pagestyle{myheadings}


\title{\bf Real Time Rendering\\ for a Geographical Information 
System\thanks{
 Project conducted as part of the 1994 Research Experiences for 
 Undergraduates (REU) Program
 in High-Performance Computing conducted by the Northeast Parallel
 Architectures Center (NPAC) at Syracuse University.  The National
 Science Foundation provides primary funding for the 1994 NPAC REU
 Program, through NSF Grant CDA-9200577.  Additional funding is provided by
 the GE Foundation Faculty for the Future Program; the
 Vice President for Research and Computing, the Dean of the
 College of Engineering and Computer Science, the Dean of the
 College of Arts and Sciences, and NPAC, Syracuse University.}}
\author{Stephanie Weirich\thanks{Research Apprentice, 1994 NPAC REU Program;
email:{\it sweirich@npac.syr.edu}.
Computer Science Major, Rice University; email:{\it sweirich@owlnet.rice.edu}.}
\and Paul Coddington\thanks{Research Scientist, NPAC, Syracuse University; 
email:{\it paulc@npac.syr.edu}.}}
\date{\sc Proposal for a 1994 NPAC REU Project}
\maketitle
\markboth{Weirich \& Coddington}{Real Time Rendering for a Geographical
 Information System}

\begin{abstract}
This paper addresses the development of a real time rendering program to 
provide a ``flight simulator'' type of interface to information about
New York State, as part of the Living Textbook project. The project is 
discussed and broken into smaller problems. Finally, a project is proposed 
to explore the capabilities of various Silicon Graphics machines, both
alone and networked with high performance parallel computers, in regards to 
rendering terrain data. 
\end{abstract}

\section{The Living Textbook}
The Living Textbook Project is a joint project between the Northeas Parallel 
Architecture Center (NPAC), the School of Education at Syracuse University,
 NYNEX, and Columbia University to define
how new communication technologies will enhance the quality of teaching 
and learning. Several pilot projects are designing multimedia
educational applications and tools appropriate for high-speed computing and
communications networks, including interactive simulations. 

As a part of this project, we propose to create a ``flight simulator''  
interface to geographical data of New York state. Students 
will be able to ``fly'' around a rendered view of the  state and 
select landmarks 
and cities for more information. A realistic terrain for the simulator 
will come from a variety of geographically referenced data sources, 
making the renderer a veritable Geographical Information System (GIS).


\section{What is a Geographical Information System?}
The United States Geological Survey(USGS) answers the question,
``What is a GIS?'' with the following:
\begin{quotation}
\noindent
   ``In the strictest sense, a GIS is a computer system capable of
   assembling, storing, manipulating, and displaying geographically
   referenced information, i.e. data identified according to their
   locations. Practitioners also regard the total GIS as including
   operating personnel and the data that go into the system~\cite{usgs}.''
\end{quotation}
For this project, we intend to use the same geographically referenced data,
 considering in particular four types:

\begin{description}
\item[Elevation] data is found in the form of a Digital Elevation Model(DEM).
This will be the primary data used by the renderer to create the terrain. 
It can be broken into polygons, rendered and then shaded for a three 
dimensional effect. The data itself is 
gridded with a 30 m resolution. Standard data sets cover 7.5 arc-minute
by 7.5 arc-minute areas equivalent to United States Geological Survey
 (USGS) 1:24,0000 scale maps~\cite{gisfaq}.An example of rendered elevation
 data is in figure ~\ref{elv} of the Kissimmee River flood plain \cite{dem}.
\begin{figure}[htb]
\centerline{\psfig{figure=DEM.ps,width=3in}}
\caption{Digital Elevation Model (DEM)}
\label{elv}
\end{figure}



\item[Landsat] satellite data of vegetation and geography, as in figure 
~\ref{landsat} will provide colors and texture for the polygons.
\begin{figure}[htb]
\centerline{\psfig{figure=capecod.ps,width=3in}}
\caption{Landsat image of Cape Cod}
\label{landsat}
\end{figure}
 

\item[DLG] or Digital Line Graphs can include roads, city, county, and country
borders. An example of a road graph from the USGS  is in figure ~\ref{dlg}.
These will be used to add city boundaries and major roads to the terrain.
\begin{figure}[htb]
\centerline{\psfig{figure=dlg.ps,width=3in}}
\caption{Digital Line Graph of Roads}
\label{dlg}
\end{figure}


\item[Orthographic] data is made from pictures taken from about 20,000 feet
above ground. Then elevation data is used to remove perspective errors to
create a flat picture as in figure ~\ref{ortho} from the USGS \cite{orthobib}.
This type of data, though 
limited in availability, can provide the highest amount of detail for the 
renderer. It will be most useful inside cities for adding buildings and 
famous monuments.
\begin{figure}[htb]
\centerline{\psfig{figure=ortho.ps,width=4in}}
\caption{Orthographic image}
\label{ortho}
\end{figure}
\end{description}

 
\section{Examination of Project}
The rendering project can  be divided into four separate problems. 
\begin{enumerate}
\item{How to make the renderer run on a variety of platforms.\\
The renderer should maintain the same number of frames per second 
no matter what machine it is run on. Current goals are twenty frames per 
second though available public domain flight simulators currently run closer 
to two seconds per frame and make no effort to keep this consistent. 
This problem of portability and speed is discussed in more detail in
the next section.}

\item{How to take advantage of the format of the data. \\
A large number of optimization techniques can be successfully applied to 
rendering terrain. 
Because the format of the data is known, shortcuts in the rendering pipeline
should be explored. Of particular note is preprocessing the data to include
more/less detail as necessary. }

\item{How to incorporate different types of GIS data together.\\
Digital Elevation Models can be initially used with ease, but some method 
of adding the vegetation, road and city information must be used. This added
detail must also not prevent the renderer from running in real time, so
the amount of detail added must vary  depending on the platform 
used.
}
\item{How to create the user interface appropriate for a textbook.\\
Since this program is meant to be operated by a child, the access to 
information must be simple and intuitive. }
\end{enumerate}
Each of these must be solved in the process of creating a useful learning 
tool. Furthermore, some of these can be further subdivided to give a focus 
of effort for the project.

\section{Projects involving Portability of Renderer}
Making a totally portable renderer is a huge endeavor, and sevaral smaller
REU sized chunks can be divided out as follows:\\
\begin{itemize}
\item{ Port Jet Propulsion Lab (JPL) code for parallel terrain rendering
 to work on NPAC  machines. JPL currently uses it to render scenes of Mars and
Venus.  }
\item {Examine the capabilities of various Silicon Graphics(SGI) workstations
 both alone and if possible networked by Asynchronous Transfer Mode (ATM)
 networking to other high performance parallel computers.}
\item { Benchmark NPAC computers for speeds in rendering. }
\end{itemize}

\section{Proposed Work}
As part of my participation in the 1994 Northeast Parallel Architecture 
Center Research Experience for Undergraduates program, I propose to 
concentrate on the second project involved with making the code portable.
I will explore the capabilities of various Silicon Graphics workstations 
in conjunction with available public domain rendering programs.
NPAC currently has two Indy workstations and an SGI Challenge, a parallel
processing graphic workstation currently with two processors, but scalable 
up to thirty six. More information on this architecture is available from
 ~\cite{sgi}. 
 

If  time permits I will try to use parallel computers such as Thinking 
Machine's CM-5 or a cluster of DEC Alphas to perform
some of the computations, and send the results back to an SGI for display via 
fast Asynchronous Transfer Mode (ATM) networking. A major consideration 
here is what computation should be done by the parallel computer and what 
by the SGI's specialized hardware. 

\begin{thebibliography}{99}
\bibitem{usgs}
United States Geological Survey HTTP server, currently available
at http://info.er.usgs.gov/.
\bibitem{orthobib}
United States Geological Survey, {\em Digital Orthophotos}
 factsheet, November 1993.
\bibitem{gisfaq}
Geographical Information System Frequently Asked Questions 
list currently available via anonymous ftp from dg-rtp.dg.com(128.222.1.2) in 
the file /gis/faq.
\bibitem{sgi}
Galles and Williams, {\em Performance optimizations, implementation, and verification of the SGI Challenge multiprocessor}. Available from 
http://www.sgi.com.
\bibitem{dem}
Bob Brown, ``GIS Rechannels Water Planning Strategies,'' {\em GIS World}
 May 1994, pg 41.

\end{thebibliography}
\end{document}














