\chapter{Viewing Characteristics of Terrain}
\label{viewing-characteristics}

We envision that the user starts out in the solar system, where Mars, Earth
and Venus are visible.  Then the user chooses to visit one of the three planets.

        This journey can be broken into four main viewing stages: stage one,
from solar orbit to high planetary orbit; stage two, from high planetary orbit
to lower planetary orbit; stage three, from lower planetary orbit to high
altitude flight path; and stage four, from high altitude flight path to low
altitude fly-by.  Each of these stages has
distinct viewing characteristics that the terrain viewer must respect.  As a
result, multiple rendering techniques and data sets are needed to generate the
images.  In the following sections, the viewing characteristics,
data requirements and rendering techniques of each stage are investigated.

\section{From Solar Orbit to High Planetary Orbit}

\begin{figure}
\begin{picture}(432,432)
\psfig{figure=earth.ps,width=432pt,height=432pt}
\end{picture}
\caption{This image is taken on the Apollo 17 mission
(NASA Photo ID: AS17-148-22727, File Name: 10075945.jpg,
Film Type: 70mm, Date Taken: 12/07/72,
Title: View of the Earth seen by the Apollo 17 crew traveling toward the
moon). The description of the image said, ``View of the Earth as seen by the
Apollo 17 crew traveling toward the moon. 
This translunar coast photograph extends from the Mediterranean Sea area
to  the Antarctica south polar ice cap. This is the first time the Apollo 
trajectory made it possible to photograph the south polar ice cap. Note the 
heavy cloud cover in the southern hemisphere. Almost the entire coastline
of  Africa is clearly visible. The Arabian Peninsula can be seen at the 
northeastern edge of Africa. The large island off the coast of Africa is
the  Malagasy Republic. The Asian mainland is on the horizon toward the
northeast.''\label{earth}}
\end{figure}

        At this stage, the user is deciding which planet to visit.  Hence, the
basic viewing requirement is to provide enough visual cue to distinguish the
planets.  As the user moves closer to a specific planet, we would like to show
the most striking features of the planet, for example, the continents and
oceans on Earth (figure~\ref{earth}) and the polar caps of Mars.  This
information is intended to
help the user properly orient to the viewer's 3D coordinate system.

\subsection{Data Requirement}

  The data required for this stage is a collection of progressively refined
pixel maps of the planets.  These pixel maps need to correct for spherical
projection to minimize the distortion during the rendering phase.
The pixel maps can be derived from any source as long as ``correct'' colors
are used for the major planetary features.

\subsection{Rendering Technique}
\label{texture-alg}

        We can render the planetary images by mapping the planetary pixel
maps onto the surfaces of the spherical objects (figure~\ref{map}).  Since the
pixel map is constructed to
cover the entire surface area of the sphere, the size of the sphere is not
important. For simplicity, we use the unit sphere.

\begin{figure}
\begin{center}
\begin{picture}(300,300)
\psfig{figure=map.eps,width=300pt,height=300pt}
\end{picture}
\end{center}
\caption{An rendered image of the earth generated by mapping an image
of a world map image onto a computer graphics sphere. \label{map}}
\end{figure}

We use the following mapping functions to map a 2D image onto a 3D
spherical surface (as shown in figure~\ref{texture1}).  The simplicity of the
mapping functions can be exploited to reduce computation
requirement by using look-up tables
and linear interpolation for various values of $\phi$ and $\theta$.

\begin{displaymath}
\begin{array}{lcll}
u & = & \frac{\cos (\phi) + 1}{2}, & \mbox{where } 0^{\circ}
\leq \phi < 180^{\circ} \\
v & = & \frac{\theta}{360^{\circ}}, & \mbox{where } 0^{\circ} \leq \theta <
360^{\circ} \\
\end{array}
\end{displaymath}

\begin{figure}
\begin{picture}(400,244)
\psfig{figure=texture1.eps,width=400pt,height=244pt}
\end{picture}
\caption{Mapping a 2D plane onto a 3D spherical surface. \label{texture1}}
\end{figure}

\begin{figure}
\begin{picture}(400,158)
\psfig{figure=texture2.eps,width=400pt,height=158pt}
\end{picture}
\caption{Compressed and elongated regions of the 2D plane. \label{texture2}}
\end{figure}

The characteristics of this mapping are the elongation and compression of
the 2D pixel map regions as shown in figure~\ref{texture2}.
The compression in the $v$ direction is due to the reduction of the
circumference of the circles, which are on the surface of the sphere and
are parallel to $x-y$ plane.  The compression in the
$u$ direction is caused by mapping half of the pixel map onto the region
bounded by $60^{\circ} \leq \phi \leq 120^{\circ}$ and
$0^{\circ} \leq \theta < 360^{\circ}$.  The rest of the pixel map forms the two
elongated regions.

        This distortion, if applied to a planar Earth image, will shorten
all land mass between the Tropic of Cancer and Tropic of Capricorn and lengthen
all the land mass from these lines to the polar region in the $u$ direction.
Meanwhile, all land mass located away from the equator is compressed in the $v$
direction.  All continents will be distorted beyond recognition.
Consequently, correctly prepared pixel maps are essential.

        As the user moves closer to a planet, the user expects to see more
detailed features of the planet.  The rendering program can fulfill this
expectation by using a higher resolution pixel map as the user gets closer to a
planet.  The exact relationship between distance and the resolution of the
pixel map used will depend on the quality of the pixel map and the output
screen resolution.  Furthermore antialiasing can be accomplished easily, since
the pixels are already loaded in core.

Combining the low computation requirement of this rendering algorithm with
the low maintenance and low storage requirement of the pixel maps, we have an
option to implement the first stage of the terrain
rendering program on the client.  This reduces the training equipment cost for
the student to learn to use the terrain rendering program.  Moreover, the
first stage can also serve as a gateway to other related information
server.

\section{From High Planetary Orbit to Lower Planetary Orbit}
\label{earth-bump-map}

\begin{figure}
\begin{picture}(432,414)
\psfig{figure=texture.ps,width=432pt,height=414pt}
\end{picture}
\caption{This image (NASA Photo ID: STS066-129-005, File Name: 20180586.jpg,
Film Type: 70mm, Date Taken: 11/14/94, Title: ATLAS-3 payload in the payload bay
of STS-66 shuttle Atlantis in orbit) shows recognizable landmarks from orbit.
The description of the photo said, ``Clouds over the Atlantic Ocean serve
as a backdrop for this 70mm scene of the Atmospheric Laboratory for Applications
and Science (ATLAS-3) payload in the cargo bay of the Earth-orbiting Space
Shuttle Atlantis.''\label{landmarks}}
\end{figure}

\begin{figure}
\begin{picture}(432,432)
\psfig{figure=shadow.ps,width=432pt,height=432pt}
\end{picture}
\caption{This image of Salton Sea, California, which is submitted by Brad
Rundquist (Photo ID: STS078-754-93), shows that shadows provide the
necessary visual cue to
distinguish the mountain range from the plan.   The description of the
photo said, ``The Salton Sea is the largest lake in California (360 square
miles). The ecological problems facing the Salton Sea, mainly the deposition of
agricultural chemicals and rising salinity levels, are due to the fact that it
is a closed basin.  Water only leaves the sea by evaporation, leaving the salt
and chemicals behind.''\label{shadow}}
\end{figure}

\begin{figure}
\begin{picture}(432,322)
\psfig{figure=sunrise.ps,width=432pt,height=322pt}
\end{picture}
\caption{This image (NASA Photo ID: STS047-54-018, File Name: 10064973.jpg,
Film Type: 70mm, Date Taken: 09/20/92, Title: Sunrise, Earth Limb, SW Pacific
Ocean) shows a speculator image of sun light shining at a low angle is not
suitable for viewing terrain information.  In addition, it also
demonstrates the difference reflectivity of the ocean and land.
The description of the photo said, ``The colors of this sunrise/sunset scene
provide insights into the relative density of the Earth's atmosphere (15.5S,
158.5E).  This scene captures the silhouette of several thunderstorms with their
cirrus anvil tops spreading out against the tropopause - the top of the lowest
layer of atmosphere, the troposphere which is also the most dense and refracts
light at the red end of  the spectrum while the blues refract in the
stratosphere, the highest layer.''\label{sunrise}}
\end{figure}

The user is selecting a Earth's continent size region for the journey.
The user can either enter a coordinate or select a recognizable
land mark as the starting point.  A journey starting at a specified coordinate
can be trivially accommodated.  On the other hand, for the user to rely on
recognizable landmarks will require the ability to distinguish mountain ranges,
canyons, ice caps and large bodies of water.  Figure~\ref{landmarks} provides
an view of the ocean and the land-mass from orbit.  For most
of these features, a pixel map contains enough information for the user to
recognize the feature's characteristics.  However, the user requires shadow to
distinguish mountain ranges and canyons.  The shadow
of the mountain ranges in figure~\ref{shadow} enhances the visual que for their
height, but when the sun is shining at a low angle as in figure~\ref{sunrise},
the terrain features are obscured.   Shadow computation is quite
involved~\cite{CPS713_lec}~\cite{REU_1}.  At this altitude, the mountain
ranges and canyons are just abnormalities (bumps) on the sphere surface.
Since bumps do not cast very long shadows under most favorable lighting
condition for viewing, we can replace the full shadow
calculation by a shading computation without significant lost of image quality.
The lost image quality is caused by the shading calculation's failure
to properly account for shadow casting (figure~\ref{shading1}).  
A point is in shadow, if there is an object blocking the light rays from the
light source to the point.  The computation required to determine if a
point is in shadow or not involves searching part of the database for the light
blocking object.  Although this process is not particular challenging, it is
CPU intensive.  On the other hand, shading computes the brightness of a point
according to the direction of the light source, the surface normal of the
point, the viewer direction, and various adjustable parameters.  Since no
other object is considered, no shadow is generated.  As a result, the
shaded area is smaller than
a properly calculated shadow and the error is proportional to the height of
the shadow casting object and the angle of the light source.
        The shading of the terrain can be accomplish by using a displacement map
(also known as bump map).  In section~\ref{bump-alg}, we will
describe the algorithm to shade with a bump map.

\begin{figure}
\begin{picture}(400,238)
\psfig{figure=shading1.eps,width=400pt,height=238pt}
\end{picture}
\caption{Difference in shadow calculation and shading calculation.
\label{shading1}}
\end{figure}

        In the terrain rendering program, the light source remains
constant both in intensity and in location.  The shading cannot be precalculated
because the rotational rate of the planet does not remain constant as the user
drops into the planet's gravity well.  However, we will most likely to violate
some physical laws to avoid disorienting the user.  As a result, the shaded
area has to brighten as the terrain features rotate
toward the sun and to darken as they rotate away from the sun.  In addition,
experience has shown that continuously varying viewing parameters can help users
to grasp the depth cue more easily~\cite{Foley}.

\subsection{Data Requirement}

   The data required for this phase is one high resolution pixel map and one
bump map of the planet.  Both of these maps are corrected
for the spherical projection.

\begin{figure}
\begin{picture}(388,219)
\psfig{figure=normal.eps,width=388pt,height=219pt}
\end{picture}
\caption{The construction of bump map \label{normal}}
\end{figure}

        The displacement map can be constructed from the height field of the
planet.  Each entry of the displacement map consists of a small perturbation,
$\bigtriangleup N$, of the sphere's surface normal, $N_{\mbox{S}}$.
$\bigtriangleup N$ is computed by
$N_{\mbox{HF}} - N_{\mbox{S}}$, where $N_{\mbox{HF}}$ is the surface normal of
the terrain (as show in figure~\ref{normal}).
The directional information of $N_{\mbox{HF}}$ is encoded with respected to
the global coordinate system for a specific orientation of the sphere.  The
$\bigtriangleup N$ is in the local coordinate of each surface normal of the
sphere.  During the shading calculation, $N'_{\mbox{HF}}$ is reconstructed 
by combining the perturbation with the surface normal of a view oriented sphere,
$N'_{\mbox{S}}$.  Consequently, the transformation to put $N_{\mbox{HF}}$ in the
viewer's perspective is avoided.

\subsection{Rendering Algorithm}
\label{bump-alg}
        The rendering techniques used in this phase are texture mapping and
Phong shading.  The texture mapping algorithm remains the same as in
section~\ref{texture-alg}.

        The basic concept of the shading is to multiply an intensity factor,
$I$, to the RGB color value of each pixel. The intensity factor is computed by

\begin{displaymath}
\begin{array}{lcl}
I & = & I_{P}k_{d} N'_{HF} \cdot L \\
\end{array}, \label{full-light-intensity-formula}
\end{displaymath}
where $I_{P}$ is the maximum intensity value, $k_{d}$ is a diffuse reflection
coefficient, $N'_{HF}$ is the surface normal and $L$ is the vector pointing
toward the light source.  The turnable parameters are $I_{P}$ and $k_{d}$.
$I_{P}$ governs the brightness of the white light source.  $k_{d}$ control the
reflectivity of the surface.  By relating $k_{d}$ with terrain type, we
can make oceans and lakes be a bit more reflective than land to enhance the
photo realism of the image. The image in figure~\ref{reflective_ocean}, which
had been taken on the Apollo 7 mission, shows the reflective properties of the
ocean. An example of a bump map is shown in figure~\ref{bump}.

\begin{figure}
\begin{picture}(300,300)
\psfig{figure=bump.eps,width=300pt,height=300pt}
\end{picture}
\caption{Mandelbrot set is rendered as bumps on sphere. \label{bump}}
\end{figure}

\begin{figure}
\begin{picture}(432,367)
\psfig{figure=reflective_ocean.ps,width=432pt,height=367pt}
\end{picture}
\caption{This image is taken on the Apollo 7 mission
(NASA Photo ID: AS07-08-1933, File Name: 10074899.jpg, Film Type: 70mm,
Date Taken: 10/20/68,
Title: Morning sun on Gulf of Mexico as seen from the Apollo 7 spacecraft).
The description reads ``The morning sun reflects on the Gulf of Mexico and the
Atlantic Ocean as seen  from the Apollo 7 spacecraft during its 134th revolution
of the earth.  Photographed from an altitude of 120 nautical miles, at ground
elapsed time  of 213 hours and 10 minutes.'' This shows the ocean surface is
reflective.\label{reflective_ocean}}
\end{figure}

For this rendering phase, the computation and the storage requirement are
substantially more than
the previous stage.  As a result, the image will be generated on a high
performance workstation and shipped across a fast network.

\section{From Lower Planetary Orbital to High Altitude Flight Path}

        The user is further refining the tour destination by selecting 
a region approximately the size of a nation state.
Terrain features reveal considerable details at this
altitude.  Planetary curvature is still noticeable, but much less pronounce
than the
previous two stages.  The curvature of the terrain model should be reduced
smoothly as the user moves closer to the planet. This will permit the user to
adapt to the flat projected terrain model for the next stage.
A transformation function is needed for the smooth transition
between spherical projection and flat projection.

\subsection{Data Requirement}

   The data needed in this stage is the lowest resolution of the terrain data
sets.  A terrain data set consists of vertices list, edges list,
polygons list and texture maps for the polygons.
The low resolution terrain data set has a significantly smaller number of
vertices and the texture map resolution is much lower than the original
digital elevation data and satellite image; however, the vertices are chosen
to retain the details of the
terrain features (see section~\ref{future} for more information).
Furthermore, this data is prepackaged into subblocks.  The size of the blocks
are chosen to maximize the performance of the rendering phase.

\subsection{Rendering Algorithm}
\label{visible-calculation}

Although the low resolution terrain data set is considerably smaller than the
full data set, the low resolution data still has significant size due to
the redundant information in the vertices, edges and polygons list.
Consequently, only part of the data can be loaded in core.  An efficient
method to determine which part of the data is visible to the user is
essential to achieve our goal of constructing a real-time interactive viewing
environment.  Identifying the visible data
can be easily accomplished by using the information given by the viewer's
field of view and the curvature of the planet (figure~\ref{data-dis1}). 

\begin{figure}
\begin{picture}(400,181)
\psfig{figure=data-dis1.eps,width=400pt,height=181pt}
\end{picture}
\caption{Finding visible data \label{data-dis1}}
\end{figure}

   Since the terrain rendering program is generating images for a fly-by
without any fantastic maneuvers, the viewing location and direction at every
time step is very similar to the previous and to the next.
To exploit the locality of these viewing parameters, the 
terrain data is first mapped onto a 2D grid and then the visibility
identification is applied to the grid as presented in figure~\ref{data-dis1}.
Thus, only the visible data blocks are loaded from the secondary storage and
processed in the rendering pipeline.

   The visible calculation is essentially rendering a polygon, which bounds
all visible data blocks, onto a very low resolution ``screen,'' the 2D grid.
The bounding polygon is formed by first projecting the user's 3D view volume
onto the 2D grid.  This gives us the left and right boundaries in 
figure~\ref{data-dis1}.  Then, by calculating the intersection points
of the left and right boundaries with the 2D grid's boundary, we find the
bounding polygon for all the visible data blocks.  Finally, we apply a
polygon scan conversion algorithm to mark the visible data blocks
(refer to~\cite{Foley}~\cite{CPS713_lec} for more information on the polygon
scan conversion algorithm).  If the planetary curvature is in effect, then the
distance from the viewer to each data block is computed.  The data block is not
visible if it is too far away with respect to the viewer's altitude. 
Since there is only one polygon with known shape being scan converted,
the scan conversion subroutine can be optimized to reduce the
computation cost.

   The benefit of the visibility calculation is demonstrated in
figure~\ref{data-dis2}.  The grey squares in the figure represent the
visible data blocks and only these data blocks are rendered.
Although only a tiny fraction of some of the visible data blocks are displayed,
no special rendering techniques are performed to avoid loading these data blocks
because they have a high probability for contributing more to the next image.
After the viewer turned 4 degrees to the right (figure~\ref{data-dis2}b) with
turning rate 240 degree per minutes
(40 revolutions per hour),  the visibility calculation subroutine determined
that two data blocks went out of view and three new data blocks come into view.
As a result, choosing an optimal grid size can effectively
cache the data blocks.  Further, improvement can be made by predicting the
viewer's movement.

\begin{figure}
\begin{picture}(400,257)
\psfig{figure=data-dis2.eps,width=400pt,height=257pt}
\end{picture}
\caption{Viewer has turned $4^{\circ}$ to the right.\label{data-dis2}}
\end{figure}

   After the data is loaded into the memory, the standard polygon rendering
pipeline, which consists of transformation, clipping, hidden surface removal
and rasterization, is used (see~\cite{CPS713_lec} for more information).
The rendered image is than compressed (see section~\ref{future}) and
delivered via a height speed network to the client.

\section{From High Altitude Flight Path to Low Altitude Flight Path}
\label{high2low-flight}

    By now, the user is examining a county size region at a relatively low
altitude.  The planetary curvature is not noticeable.  Furthermore, the 
skyline is often masked by terrain features.  At a result, we can use flat
projected terrain data sets without significant compromising of the image
quality.

The user's field of view can be divided into far, mid and near field regions.
The far field provides the viewer reference points to determine the relative
special location and headings with respected to the planet.  The mid field
shows the relative location and heading of the user with respect to the
impending target.
The user can then line up the flight path for closer examination.
The near field is for detailed examination of an area.

\subsection{Data Requirement}
\label{model-joining}
   The terrain renderer uses three different resolution terrain data sets to
deal with the different viewing regions.  The far region uses the previous
low resolution terrain data, but the data is in flat projection.  A medium
resolution data set is used to generate the mid region image.  This medium
resolution data also passes through the data optimization treatment, but
it uses more vertices to capture more terrain traits.
The near region uses the finest resolution height field data and satellite
image.  A 2D grid is imposed onto the three data sets.
Each data set is prepackaged into subblocks as in the previous stage.
Because three data sets are used, we need to guarantee that the data sets merge
seamlessly.  By using the highest resolution data as the boundary points
for all subblocks of the three data sets, we have the perfectly matched
subblocks across all resolution data.  The trade off is the increase of
the number of vertices in the lower resolution data sets.
The data optimization for the low and mid resolution is done within each
of the subblocks but excluding the boundary points.

\subsection{Rendering Algorithm}

The rendering algorithm is essentially the same as for the previous stage.
However, after the 
visibility identification procedure is done, the resolution of the data is
selected according to the distance of the data block from the viewer.
The far away squares will use the low resolution data.  The near squares will
use the high resolution data.  Although the data are in different resolutions,
the same rendering pipeline is used to render each subblock.  The final image
is then delivered to the client by a high speed network.
Since this stage demands the highest computation capability for the
server, it is best performed in parallel.

