\section{Introduction}

Terrain rendering is a highly researched
area due to demand from the military, scientific visualization, and
computer gaming communities. Even as advances in graphics hardware
continue to be released, these applications will always push the
current technology to the limit such that a “brute force” method
will never be practical. Level-of-detail (LOD) rendering algorithms are one of
the applications which continue to be developed to give the best visual
representation of large-scale landscapes in real-time.

The size of datasets is one of the major problems in terrain rendering. First, brute force
rendering is not an option when dealing with large datasets, so a
LOD approach needs to be taken. Second, given a large heightmap,
quite a bit of memory can be taken up and thus out-of-core (outside of system memory) rendering
needs to be supported. The most common approach is to extract a
good view-dependent approximation of the mesh in real-time. This is
accomplished by storing data in a specific hierarchical structure, in
which terrain can usually be categorized. Terrain can be represented
in many different data structures such as a triangulated irregular
mesh (TIN)~\cite{Hoppe98smoothview-dependent}, which gives the best
approximation, a regular grid, which uses somewhat more triangles to
represent a surface, quadtrees~\cite{Rottger98real-timegeneration},
binary triangle trees~\cite{Duchaineau97roamingterrain:}, or directed
acyclic graphs~\cite{Lindstrom01visualizationof}.

Refinement may
take place on a per-triangle basis, or tessellate aggregates of
polygons. Some existing algorithms refine the terrain every frame, having
a ``split-only'' approach. Others may merge and split from previous
frames' work. Refinement can be accomplished using a nested-error bound
metric, or as in~\cite{1015799} solely the viewing position. Some
terrain algorithms only support in-core (inside of system memory)~\cite{Duchaineau97roamingterrain:},
while others support out-of-core
rendering~\cite{Lindstrom01visualizationof}
and dynamic addition of procedural detail~\cite{RVLVDT}.

Since terrain data can consume such a large memory footprint, out-of-core
algorithms often limit their datasets to be static (unchanging). Large
amounts of terrain data are usually processed in a way that leaves
the geometry optimal for video hardware and is not expected to ever
change. When dealing with an out-of-core terrain system that handles
dynamic updates of its height values, things aren't so trivial. For the
most part, the areas of the mesh that need to be rendered stay in memory,
while areas that aren't visible can be discarded to the hard-drive
until needed. With deformable terrain, updates to the mesh could be
made outside the viewing frustum, in which case those areas would need
to be loaded, updated, and cached back to disk. If a hierarchy of LOD
mesh representations were preprocessed, then updated data may need to
be propagated up through the tree or reprocessed altogether. The idea
of dealing with large amounts of data in a dynamic terrain algorithm can
quickly become unmanageable, thus when combined with the first problem,
a second problem of terrain rendering is presented: dynamic terrain.
Therefore, presented here is an out-of-core terrain algorithm which
supports dynamic updates to the heightfield in real-time, allowing for
deformable terrain.

\paragraph {Contribution:}
We present an out-of-core terrain LOD algorithm that supports
real-time deformation, building upon the features of several
algorithms discussed in Section~\ref{sec:SelectedPreviousWork}.
~\cite{RVLVDT} presents a LOD algorithm that combines the quadtree structure
of~\cite{ChunkedLOD} with the detail addition properties
of~\cite{FTRUGM}. We adapt this data structure to support terrain
deformation at any resolution throughout the terrain hierarchy
with large-scale data stored out-of-core.

\paragraph {Overview:}
After the previous work (Section~\ref{sec:SelectedPreviousWork}), this paper is arranged as follows:
A quadtree is constructed using a coarse-grained simplification (Section~\ref{sec:HierarchicalRepresentation}). During runtime, the refinement
algorithm determines the currently active regions of the terrain
based on view-dependent and deformation refinement criteria (Section~\ref{sec:RuntimeAlgorithm}). A separate thread is responsible for loading
and writing out-of-core portions of the quadtree (Section~\ref{sec:MemoryManagement}).  Finally, a brush is used to select a rectangular region
of the terrain at a particular resolution to be deformed (Section~\ref{sec:Deformation}), possibly extending the quadtree
by adding levels. The new data is treated the same as the rest of
the terrain mesh, and is paged in and out of main memory as needed.
Finally, we present out texturing scheme (Section~\ref{sec:Texturing}).


