The primary elements of visualization dealt with by this paper are three
  dimensional digital elevation maps (DEMs), stored using the BIL File
  Format~\cite{bil_format}, and two dimensional Geographical Information Systems
  (GIS) layers, stored using the ESRI{\texttrademark} Shapefile
  Format~\cite{shp_format}. It is common for both DEMs and GIS layers to be complex
  in terms of size and structure, thus requiring special methods for
  visualization.
  
  \subsection{Digital Elevation Map Manipulation}\label{subsec:dem_manip}
  
  Three-dimensional rendering APIs such as OpenGL~\cite{opengl} and
  Direct3D~\cite{direct3d} expect display primitives to be represented as
  collections of triangles. DEMs are easily represented using triangles, so
  rendering a DEM can be trivial. Figure~\ref{fig:dem_small} shows a DEM and all
  of the triangles used to approximate it. However, the size of modern DEMs are
  approaching the point that real-time rendering with modern graphics hardware
  is not possible. Also, this paper uses DEMs to assign an extra dimension to a
  GIS layer, not just for visualization.

  In order to efficiently deal with DEMs, this paper applies a lossy compression 
  technique to DEMs called Triangle   Decimation~\cite{tri_dec1,tri_dec2} and 
  Mesh Simplification~\cite{mesh_dec1,mesh_dec2,mesh_dec3}. Triangle 
  Decimation works by examining coincident triangles, and removing unnecessary 
  triangles. Figure~\ref{fig:tri_dec} shows a set of triangles that can  be 
  reduced and the possible effects of triangle decimation. Triangle decimation 
  is called lossy because once it is performed, it is not always possible to 
  regain the full representation of the DEM. However, the effects of the 
  decimation aim to   have little-to-no visual side effects. 
  Figure~\ref{fig:dem_small} shows a DEM that is a prime candidate for triangle 
  decimation since it has many coincident triangles that are nearly coplanar.
  
  \begin{figure}[!h]
    \begin{center}
      \includegraphics[width=3.75in]{images/tri_dec.eps}
    \end{center}
    \caption{Candidate triangles and the result of their decimation.  The small amount
             of height lost in the left area is barely noticeable in the right area.\label{fig:tri_dec}}
  \end{figure}
  
  \begin{figure}[!h]
    \begin{center}
      \includegraphics[width=3.0in]{images/approxDEMTrianglesShadow.eps}
    \end{center}
    \caption{Approximated Digital Elevation Map\label{fig:dem_small}}
  \end{figure}
  
  \subsection{GIS Layer Manipulation}\label{subsec:gis_manip}
  
  As mentioned previously, rendering APIs expect primitives to be broken into
  triangles. The GIS layers found in Shapefiles are represented using two-dimensional
  polygons. These polygons are clean, meaning they contain no
  self-intersecting lines. Examples for both clean and non-clean polygons are
  shown in Figure~\ref{fig:clean_and_unclean_poly}. Since there is no
  restriction on the   structure of the polygons beyond that of ``cleanness,''
  one cannot assume   anything of the convexity of the polygons in GIS layers.
  This paper uses   several techniques to triangulate the polygons in the GIS
  layer; ear-clipping~\cite{ear_clip_and_trap}, monotone
  decomposition~\cite{mon_decomp},   and
  trapezoidilization~\cite{ear_clip_and_trap}. The output of all these
  techniques is a   set of two-dimensional, non-intersecting triangles.
  
  \begin{figure}[!h]
    \begin{center}
      \includegraphics[width=5.0in]{images/clean_and_unclean_poly.eps}
    \end{center}
    \caption{Two clean (left, middle) polygons and a non-clean (right)
             polygon.\label{fig:clean_and_unclean_poly}}
  \end{figure}
  
  \subsection{Combining DEMs and GIS Layers}
  
  In order to combine the DEM and the GIS layer, a six step approach
  is proposed:
  \begin{enumerate}
    {\item Read and store the raw DEM and GIS layer }
    {\item Convert the GIS layer into sets of two-dimensional triangles }
    {\item Convert the DEM into triangles }
    {\item Perform triangle decimation on the DEM }
    {\item Add a third dimension to the GIS layer }
    {\item Add the DEM points to the GIS layer }
  \end{enumerate}
  
  Step 1 of the approach is trivial. Steps 2, 3, and 4 can be done using the
  algorithms discussed in~\ref{subsec:dem_manip}~and~\ref{subsec:gis_manip}.
  Step 5 can be accomplished using the $O(t_d$~$*$~$v_g)$ algorithm presented
  Figure~\ref{fig:comb_alg1}, where $t_d$ is the number of triangles in the DEM
  and $v_g$ is the number of vertices in the GIS layer. Step 6 can be computed
  using the $O(v_d$~$*$~$t_g)$ algorithm shown in Figure~\ref{fig:comb_alg2},
  where $v_d$ is the number of vertices in the DEM and $t_g$ is the number of
  triangles in the GIS layer.
  
  The algorithm relies on the ability to split a triangle into one, two, or
  three triangles new triangles. The algorithm, which we call {\bf SPLIT}, takes
  as parameters a triangle and a point. {\bf SPLIT} works by examining the
  location of the point; if the point lies on a vertex of the triangle, {\bf
  SPLIT} returns the original triangle. If the point lies on the perimeter of
  the triangles, but not on a vertex of the triangle, {\bf SPLIT} returns two
  new triangles with the point being a vertex on both triangles. Finally, if
  the point resides in the interior of the triangle, {\bf SPLIT} creates three
  new triangles using the vertices of the triangle and the new point. Examples
  for the three cases of {\bf SPLIT} can be seen in Figure~\ref{fig:tri_split}.
  In the figure, the dark dot represents the second parameter to {\bf SPLIT}.
  
    \begin{figure}
        \verb|                    |$T_0 \leftarrow $ Triangles in DEM                \\
        \verb|                    |$V_0 \leftarrow $ Vertices in GIS layer           \\
        \verb|                    |for all $t_0$ $\epsilon$ $T_0$                    \\
        \verb|                      |for all $v_0$ $\epsilon$ $V_0$                  \\
        \verb|                        |if $v_0$ has only two dimensions              \\
        \verb|                          |if $v_0$ is contained by $t_0$              \\
        \verb|                            |$v_1 \leftarrow v_0$ projected onto $t_0$ \\
        \verb|                            |$V_0 \leftarrow V_0 - \{ v_0 \}$          \\
        \verb|                            |$V_0 \leftarrow V_0 \cup \{ v_1 \}$       \\
      \caption{Algorithm for assigning height values to a GIS layer\label{fig:comb_alg1}}
    \end{figure}

    \begin{figure}
        \verb|                    |$V_0 \leftarrow $ Vertices in DEM                 \\
        \verb|                    |$T_0 \leftarrow $ Triangles in GIS layer          \\
        \verb|                    |for all $v_0$ $\epsilon$ $V_0$                     \\
        \verb|                      |for all $t_0$ $\epsilon$ $T_0$                   \\
        \verb|                        |if $v_0$ is contained by $t_0$                 \\
        \verb|                          |$T_1 \leftarrow $ {\bf SPLIT }($t_0$, $v_0$)\\
        \verb|                          |$V_0 \leftarrow V_0 - \{ v_0 \}$            \\
        \verb|                          |$T_0 \leftarrow T_0 - \{ t_0 \}$            \\
        \verb|                          |$T_0 \leftarrow T_0 \cup T_1$               \\
      \caption{Algorithm for incorporating DEM points with a GIS layer\label{fig:comb_alg2}}
    \end{figure}

  \begin{figure}
    \begin{center}
      \includegraphics[width=3.25in]{images/tri_split.eps}
    \end{center}
    \caption{Cases for {\bf SPLIT}: Splitting a triangle into (from left to right), 2
             triangles, 3 triangles, and 1 triangle.\label{fig:tri_split}}
  \end{figure}