\section{Proposed Approach}

	The following sections present our out-of-core deformable terrain algorithm
	for preprocessing and rendering of large-scale terrain datasets.
	We start with an overview of the hierarchical representation of the terrain
	data and then describe the runtime algorithm for mesh refinement, rendering,
	memory management, and deformation. \Figure{flowchart} illustrates
	the flow of data through the system from program initialization to rendering.

	\jpgFigure{flowchart}{h!}{3in}
	{Block diagram demonstrating the flow of data through the system.}

	\subsection{Hierarchical Representation}\label{sec:HierarchicalRepresentation}

	The hierarchical representation of the original mesh is built during a preprocessing step.
	For a $n\times n$ input mesh, a quadtree is used to organize the
	data such that the root node defines a low-detail representation of
	the entire mesh. Each subsequent child contains more detail at the
	scale of one quarter of its parent's mesh, while the leaf nodes constitute
	the original mesh. Every node is of size $m\times m$, and therefore
	each node uses the same amount of vertices. The dimensions $n$ of the
	input mesh and $m$ of the nodes must be one greater than a power of two
	to allow for optimization of the construction and refinement algorithms.

	The quadtree is constructed using a simplification process similar
	to~\cite{Lindstrom96real-time-continuous}. First, the input mesh is
	partitioned into leaf nodes of size $m\times m$, where each node overlaps
	neighboring nodes by one row and one column. Nodes are combined into
	$2\times2$ blocks and upsampled by removing every other row and column
	vertex. This is repeated recursively until $2\times2$ blocks can no
	longer be made. Each node is given a bounding box that encapsulates the
	entire mesh, as shown in Figure~\ref{Fig:Partitioning}.

	\begin{figure}[h]
	\begin{tabular}{ccc}
		\includegraphics[width=1in]{images/original_heightmap.jpg}&
		\includegraphics[width=1in]{images/partitioned.jpg}& 
		\includegraphics[width=1in]{images/merged_and_simplified.jpg} \\
	(a) Original Mesh & (b) Child Nodes & (c) Parent Node
	\end{tabular}
	\caption{The simplification process to create a quadtree.  The original mesh (a) is separated into $m\times m$ nodes ($m=5$) (b), where each $2\times2$ block creates a parent node (c).\label{Fig:Partitioning}}
	\end{figure}

	The process of removing every other row and column vertex when creating
	parent nodes implies that the data for each node, except for the root, comprises
	its parent's data (the excluded rows and columns) and its own data.
	During terrain deformation, this property obviates the need to propagate changes
	through the tree. In addition to a node's individual data, it contains pointers to its parent's data.
	To guarantee this property holds true,
	when a node is loaded into memory all of its ancestors must be
	in memory as well. The memory layout for any given node is shown in
	Figure~\ref{Fig:MemoryLayout}.

	For example, the bottom left vertex of an underlying heightfield
	belongs to the root node. Child nodes receive a pointer
	to this vertex in order to access it. This is similar to
	the wavelet compression scheme from~\cite{IMEDLT:2004}.
	However, we do not encode the child data within the parent's
	node. Instead the individual data for each node is stored in a file that can be loaded on
	demand. This eliminates the need to decode node information at
	runtime and allows for deformation without encoding new vertices
	into the quadtree. In order to query a node's data, it must simply
	dereference the vertices it points to.

	\begin{figure}[ht]
	\begin{tabular}{c}
	\includegraphics[width=2in]{images/node_data.png} \\
	(a) Node data \\
	\includegraphics[width=3in]{images/memory_layout.png} \\
	(b) Memory layout
	\end{tabular}
	\caption{Node data shown in (a) represents the memory layout shown in (b).\label{Fig:MemoryLayout}}
	\end{figure}

\subsection{Runtime Algorithm}\label{sec:RuntimeAlgorithm}
	\subsubsection{Mesh Refinement}
	The goal of any terrain rendering algorithm is to quickly
	create the best approximation mesh for each frame. Our approach
	uses a split-only top-down refinement. Previous algorithms
	use properties of the underlying geometry (e.g. nested error
	bounds) during refinement as in~\cite{ChunkedLOD} and~\cite{FTRUGM}. Deformation of the terrain requires
	recalculation and propagation of these properties throughout
	the tree. We take an approach similar to~\cite{1015799} and
	use only the view position and frustum as refinement criteria.
	Although this approach looks awkward for high-frequency data
	(e.g. a steep mountain consisting of a few vertices), natural
	terrain datasets often feature a smooth gradient.

	Refinement begins at the root node and proceeds recursively
	for each child node. A breadth-first traversal is required
	for linking neighboring nodes.
	For every node, if the node's bounding box is inside the view
	frustum and the center of the bounding box is closer than
	a predefined threshold, the node is refined by traversing
	its four children, otherwise it is prepared for rendering. A
	threshold should be chosen such that a nested regular grid
	surrounds the viewer. Since no other metrics are taken into
	account during refinement, this will yield the best visual
	fidelity. Note that the LOD of neighboring nodes is never
	limited, as in a restricted quadtree where nodes
	are forced to split based on the level of its neighbors as
	in~\cite{Pajarola98largescale}. \Figure{wireframe}
	shows bounding boxes of the hierarchy.

	\jpgFigure{wireframe}{h!}{2.5in}
	{A quadtree displaying the bounding boxes of each node.
	 Bounding boxes are culled against the viewing frustum to quickly eliminate nodes during refinement.}

	\subsubsection{Neighboring Nodes}
	Smooth transitions between nodes of different LOD must be
	rendered correctly, otherwise seams will be visible due to gaps
	in the rendered mesh or inconsistent shading from incorrect
	normal calculations.  Also, since each neighbor holds its own
	copy of edge vertices, care must be taken while deforming
	edges or edge boundaries.  To handle these variations, a node
	must be aware of its neighbors.  Since quadtree refinement isn't
	restricted, the difference between two nodes may be one level
	or more. Since a node's LOD may change from frame to frame,
	neighboring links are recreated during refinement.

	When linking nodes together, a node is only allowed to point to
	a neighbor of equal level or higher. Enforcing this rule allows
	each node to store no more than four neighbor references.  When a
	node is split during refinement, the node is responsible for
	updating its children with the correct neighborhood information.
	This cannot be accomplished with a depth-first traversal, commonly
	used in LOD algorithms. Instead, a breadth-first traversal is
	performed.

	Neighbor links
	play an important role for correct normal calculation. Normals
	are needed to simulate a realistic lighting model, and can also
	be used for collision response. The biggest
	problem of normal calculation presents itself on the
	seams of terrain patches. Vertices on an edge need the height
	values of neighboring nodes.

	The most common approach to calculate a normal is to
	compute a normal for each vertex in the heightfield by
	taking the average normal of all faces that contain
	the vertex~\cite{FANCFHLOANIG}. This process
	consists of several costly mathematical operations, such
	as square roots. Several optimizations can be made by exploiting properties of
	the heightfield. The
	method we use is described in~\cite{Shankel:2002}, which
	only requires the four neighboring heightsamples of a
	vertex. In order to create a smooth transition across a
	patch seam, neighboring vertices must be queried and the
	computed normal is then stored for each edge.
	
	\subsubsection{Detail Addition}\label{sec:DetailAddition}
	To improve the appearance of the terrain without increasing the
	size of the data on disk, procedural detail is added at runtime
	for leaf nodes that meet the refinement criteria. The detail is
	added to the hierarchy in the form of new leaf nodes that extend
	the quadtree until a user-specified level is reached.
	When creating a new node, a reverse process of adding rows and
	columns is performed and the new node is linked to its parent,
	which was previously a leaf node. The new vertices are then
	assigned procedural data.

	Linear interpolation is not sufficient for creating additional detail
	because the resulting data is uniform.
	Instead, fractals are used to give the data a non-uniform appearance.
	Each interpolated vertex is shifted a random amount such that
	it stays within the bounds of the surrounding vertices. Since
	detail addition is subtle, the process does not need to be
	deterministic, therefore detail can be randomized each time it
	is created.

	\subsubsection{Rendering}
	The result of refinement is
	a list of patches to be rendered. Before rendering, indices can
	be recalculated for nodes whose neighbor's LOD have changed and
	normals can be recalculated if deformation had occurred. Each
	node must then dereference its pointer data to create a vertex
	list. Finally, each node can be transformed into world space and
	the data sent across the bus to be rendered. The rendering
	process is decoupled from the updating and disk I/O methods,
	allowing for smooth loads of data and no hiccups in the system
	regardless of how fast the viewer is moving around the terrain.

		Stitching is
		accomplished by having the finer detail node omit vertices on its
		edge to match that of its coarser neighbor. This is done
		by rendering degenerate triangles.
		Geometrical skirts~\cite{ChunkedLOD} were not chosen since the
		size of the skirt may change after deformation.
		Recalculation of the skirt can become tedious
		and slow. Figure~\ref{Fig:Stitching} illustrates the
		removal of T-junctions by utilizing degenerate triangles.

		\begin{figure}[ht]
		\begin{tabular}{cc}
			\includegraphics[width=1.5in]{images/t-junction.jpg} &
			\includegraphics[width=1.5in]{images/degenerate.jpg} \\
			(a) T-Junction & (b) Degenerate Triangles
		\end{tabular}
		\caption{T-Junctions appear at the neighboring nodes of different levels of detail.  
			     Omitting vertices via degenerate triangles removes any possible cracks from the mesh.\label{Fig:Stitching}}
		\end{figure}

\subsection{Memory Management}\label{sec:MemoryManagement}
Our algorithm supports large datasets stored out of core, i.e.
data that resides outside of main memory ~\cite{RVLVDT}.
A separate loading and caching thread is fed patches to load or
write to disk. The patches to load are based on refinement,
while the patches to write are based on a least recently used (LRU) algorithm.

During refinement, if a parent cannot be split because the data for
its children is not in-core, a request for the data is made to the
loading and caching thread. The system never stops to wait for data
to load; until the data for the	children is loaded, the parent's data is rendered.

When the memory footprint exceeds a predefined threshold, LRU patches
are discarded to disk until the used memory falls below the threshold.
Each node is given a timestamp representing the last time the node was
either rendered or deformed.  A priority queue is used to efficiently
determine which nodes should be discarded.
Since every node
relies on its parent for some of its data, discarding a parent to disk
will invalidate memory references for its children,
therefore only leaf nodes of the
currently refined mesh are considered for caching.

Depending on the actions of the user (fast movement or several
deformations) and the current memory footprint, nodes may require
continuous allocation and deallocation.  Instead of using operators
such as new or delete which are notoriously slow for small and frequent
allocations, a freelist is used as in ~\cite{Glinker:2004}.

\subsection{Deformation}\label{sec:Deformation}
Real-time modifications are applied to the terrain by refining the 
currently active mesh based on a rectangular selection of the terrain, called a brush,
in addition to the view-dependent refinement criteria
described earlier. The vertex data for each refined node is modified
to fit the brush specification.

A brush defines the rectangular extent (defined by position, width,
and height) and the resolution of deformation (defined by a level in the
hierarchy, which may not exist). In addition, a brush holds an array of
pointers to vertices in the terrain, allowing deformations to cross node
boundaries. Nodes that intersect the brush are selected during refinement
and vertices from each node are given to the brush. Dereferencing
the brush gives access to vertex data which can be overwritten with
new data. Since vertices on edges are duplicated for each patch, care
must be taken for deformations across boundaries by syncing adjacent
vertices. This is done in a pre-rendering step that compares dirty flags
of neighboring nodes in the quadtree.

Refinement is based on brush extent and resolution as well as view-dependent criteria.
Therefore, a node may be refined even though it is
not sufficiently close to the viewer or inside the view frustum. Depending
on the resolution of the brush, data for nodes deep into the hierarchy
may be requested for loading.  Only when all of the data required by
the brush's resolution has been loaded can deformation be applied.

As described in Section \ref{sec:DetailAddition}, procedural detail is added for leaf nodes
that meet the view-dependent refinement criteria.  If a brush alters
a node with procedural data, disk space is allocated for the node and
it is allowed to be discarded to disk by the memory manager.

When a node is chosen for rendering, it is possible that an ancestor
has previously been deformed. Time stamps are compared, and if a node's
last modification is older than its parent's, its data is adapted to
the parent mesh by creating procedural detail.

\subsection{Texturing}\label{sec:Texturing}
Textures are processed similarly to the terrain data. A large texture
can be cut into user-defined partitions and merged into ${2\times2}$
blocks before being mipmapped. This process continues until an entire
quadtree is built over the original texture data.

Nodes in the terrain quadtree directly map to nodes in the texture
quadtree. However, with modifications to the terrain quadtree
(deformation and procedural detail), it becomes impractical to create a
texture quadtree of the same depth. If a node in the terrain quadtree
cannot be mapped directly to a node in the texture quadtree, the parent's
texture and texture coordinates are used.  When a node is being loaded
or deleted it can also load or delete its texture.

Just as the terrain quadtree presented issues at seams, so does the
texture quadtree. This is due to the kind of texture filtering used
to generate the texture quadtree.  Although no seams are visible with
nearest filtering, this type of filtering is not visually appealing.
With linear filtering, seams appear at the texture edges because the
edge texels are not being blended with the correct neighbor texel.
This is solved by overlapping adjacent textures during texture quadtree
construction such that neighboring nodes have exact texels on shared
edges. Clamping the texture edges during rendering causes these texels
to blend, removing the seam. There is no perfect solution, and the amount
of pixels to overlap can vary.

\subsection{Supporting Large Scenes}

Extending terrain detail causes the terrain as a whole to be resized
to a different resolution. Instead of having a 1-meter resolution map,
detail can be added so now its a 1-millimeter map. In order to properly
represent detail, the entire terrain needs to be increased in scale.

As worlds get substantially bigger, the amount of precision to
reprensent world coordinates gets smaller and smaller. For example, if
units represent meters and our world is 100km square, at the farther
corner of the world a 32-bit number will allow us to represent 7.8mm
granularity~\cite{Freese04}. The larger the world coordinates, the less
accurate they will be at the farthest extent. Therefore floats usually
have to be converted to doubles since there are not enough bits to
represent a large number with high precision.

Unfortunately the graphics hardware only performs floating point
operations, so precision is lost during operations such as matrix
transformations. Traveling to the farthest extent of your terrain will
result in seams between patches or jittering movement when the camera
moves. It is best to partition the world into a user defined segment
space, where each node belongs to a segment and is given an offset.

Instead of transforming the camera and translating patches during
rendering, thus losing precision, transforms can be made in segment
space, such that the world now revolves around the camera within a
segment. This will solve any and all accuracy problems that large scenes
come with. Unfortunately, this doesn’t come without a burden. If this
method is used, then all objects need to be represented in segment space
which can prove difficult, especially when using a scenegraph.

Along with large world coordinates, precision is also an issue with the
depth buffer.  Ideally the user will want to see detail an inch from his
nose while also seeing the moon in the sky. Unfortunately a 24 or 32-bit
depth buffer can’t support such a task. Since the depth buffer is not
linear, there are many more bits allocated to the precision of objects
closer to the camera than further. Precision is gained exponentially
as you push out the near clipping plane. However, in our terrain we
will sometimes want to view millimeter resolution, without culling the
mountiains in the horizon.

Several methods can fix this problem, such as using
imposters~\cite{ONe07}, or a multipass rendering system that renders
the scene in sections, clearing the depth buffer while altering the
frustum each time. In our implementation we allow for multiple rendering
passes. \Table{newTable} shows the steps required to perform such a task.

\begin{table}[ht]
\begin{center}
	\begin{tabular}{|l|}
		\hline
		1. Set zFar to the maximum value needed.\\
		2. Set zNear = zFar / ratio. \\
		3. Clear z-buffer. \\
		4. Render scene and cull to the adjusted frustum. \\
		5. Set zFar = zNear. \\
		6. If zNear isn’t close enough yet go back to Step 2. \\
		\hline
	\end{tabular}
	\caption{Process for multipass rendering\label{tab:newTable}}
\end{center}
\end{table}
