\section{Related Work}\label{sec:SelectedPreviousWork}
	\subsection{ROAM}
	ROAMing Terrain: Real-time Optimally Adapting
	Meshes~\cite{Duchaineau97roamingterrain:} is a well known level of
	detail algorithm utilizing a binary triangle tree (bintree) which
	stores all of the triangles for a given mesh. Instead of dealing
	with a complete terrain system that performs out-of-core paging
	for geometry, textures, and selection of LOD blocks, the authors
	focus on in-core geometry management. Given a bintree, split
	and merge operations are performed using a dual priority-queue
	system to achieve a LOD representation for the underlying data.

	ROAM starts with a preprocessing step that produces a nested
	view-independent error-bounds that works along side the
	bintree. When deciding to split or merge a specific triangle
	in a bintree, the pre-computed error bound is taken into
	consideration along with the view-dependent metric. The
	algorithm uses a metric based on nested world-space bounds,
	where a world-space volume (called a “wedgie”) contains the
	points of the triangle. World-space bounds are computed bottom-up,
	such that a node's error-bounds is the maximum of its children's
	world-space bounds.

	This algorithm also realizes that neighboring triangles could
	be at different resolutions, either coarser or finer by one
	level. In this case, before a split is made, neighboring triangles
	may be force-split to eliminate cracks or T-junctions in the
	mesh. This is done recursively until the base neighbor is at
	the same resolution level (i.e. a diamond is created). Doing this
	recursive step ensures a single continuous mesh.

	Top-down refinement of a terrain mesh is a simple and
	widely used concept where detail resolution can be added easily
	by extending the leaf nodes of the binary triangle tree with
	some adjustments to the nested error-bounds. The authors
	state that ROAM is suitable for dynamic terrain since the
	preprocessing of error-bounds computation is localized and
	fast. However, the algorithm only handles data that can fit
	into system memory. Reprocessing large amounts (more than can
	fit into memory) of terrain data is unacceptable for extremely
	large datasets, especially if many deformations are occurring
	and requiring error-bounds to be recomputed every frame.

	\subsection{Geomipmapping}
	With advances in graphics hardware, it is common to spend
	less work on the CPU to find a ``perfect'' mesh and send more
	triangles to the GPU, even if they aren't needed. Since
	sometimes it is faster (and easier) to render a triangle
	than determine if it should be culled, there is a balance
	between brute force and dynamic refinement
	algorithms. In 2000, de Boer wrote the paper \emph{Fast Terrain
	Rendering Using Geometrical MipMapping}~\cite{FTRUGM}, a new
	approach that exploits graphics hardware instead of computing
	perfect tessellation on the CPU.  De Boer states that the goal is
	to send as many triangles to the hardware as it can handle. Since
	terrain data can be represented as a 2-dimensional heightmap, the
	analogy of texture mipmapping was used and applied to geometry.

	Geomipmapping makes use of a regular grid of evenly spaced
	height values, that must have $2^{N} + 1$ samples on each side. A
	preprocessing step is performed that cuts the terrain into blocks,
	called GeoMipMaps, also with $2^{N} + 1$ vertices on each side (e.g. a
	$257\times257$ regular grid may be divided into $16\times16$ blocks
	of $17\times17$ vertices). Vertices on the edge are duplicated for
	each block where each block is given a bounding box and is suitable
	to be stored in a quadtree for quick frustum culling. Finally,
	a series of mipmaps are created by simplifying the
	mesh which is done by removing every other row and column
	vertex. The author suggests that out-of-core rendering could
	be supported by having only visible blocks or those near the
	camera in memory while others can be discarded to the hard disk
	until needed.

	Each geomipmap level has an associated geometrical error.
	For each vertex removed during the simplification step,
	a world space error is calculated as the distance between
	the vertex and the line of the interpolated simplified mesh.
	The maximum error of all vertices is assigned as the geometrical
	error to the block. Then, to decide which geomipmap to
	use, it is projected to screen pixel space and compared to a
	user-defined threshold. When the current geometrical error is
	too high, a higher detailed block is used.

	After each geomipmap block has been chosen, there will be several
	neighboring blocks that reside at a different LOD. As
	such, cracks will appear between these blocks since one patch
	holds more detail than the other. De Boer fixes this problem
	by omitting vertices on the edge of a higher detailed block to
	identically match its lower detailed neighbor.

	This algorithm is extremely easy to understand, implement,
	and also exploits the benefits of the graphics hardware. Adding
	detail is trivial by simply reversing the simplification
	step described in the algorithm. Deformation could be supported,
	but geomipmaps would have to be recreated and geometrical errors
	recalculated, which could hinder real-time deformation. The
	downside is that the number of geomipmaps increases quadratically
	($N^{2}$ ) based on the size of the terrain; therefore, possibly
	resulting in slow computation and rendering.

	\subsection{Chunked LOD}
	At \emph{SIGGRAPH'02} Ulrich presented a hardware friendly algorithm
	based on the concept of a chunked quadtree, which is described
	in~\cite{ChunkedLOD}. This algorithm, also referred to as Chunked
	LOD, is somewhat similar to GeoMipMapping; however, it scales much
	better due to the quadtree structure. There is often confusion
	of the differences between Chunked LOD and Geomipmapping since
	the algorithms are similar. However, Chunked LOD exploits a quadtree
	data structure of mipmapped geometry. Therefore the number of
	rendered nodes does not quadratically increase due to the size
	of the terrain.

	A requirement of this algorithm is to have a view-dependent LOD
	algorithm that refines aggregates of polygons, instead
	of individual polygons. As ROAM tessellates down to a single
	triangle, Chunked LOD refines chunks of geometry that have been
	preprocessed using a view-independent metric. Since chunks
	are stored in a quadtree, the root node is stored as a very
	low polygon representation of the entire terrain. Every node
	can be split recursively into four children, where each child
	represents a quadrant of the terrain at higher detail than
	its parent. Every node is referred to as a chunk, and can be
	rendered independent of any other node in the quadtree. Having
	such a feature allows for easy out-of-core support.

	In order to create the chunked quadtree, a non-trivial
	preprocessing step must first be performed. Given a large
	heightmap dataset, height samples are partitioned into a quadtree
	and simplified based on the properties of the mesh and not the
	viewer. This can be done using any per-triangle tessellation
	algorithm, such as binary tree tessellation as illustrated in
	ROAM~\cite{Duchaineau97roamingterrain:}. Depending on the depth
	of the chunk, more detail is given to the final mesh.

	Each chunk holds a list of renderable vertices, a bounding volume,
	and a maximum geometrical error. Starting with the root node
	of the quadtree, nodes are culled and recursively split based
	on the viewing position and its geometrical error. Neighboring
	chunks at different levels of detail are addressed by creating
	a “skirt” of extra geometry that eventually, with tweaks of
	texture coordinates, fills in the frame buffer so no artifacts
	are noticed. Utilizing skirts keeps chunks independent of each
	other, which makes out-of-core support trivial.

	The Chunked LOD quadtree structure is one of the best known
	hardware friendly LOD algorithms since it can be utilized
	for very large out-of-core terrain. Adding detail resolution
	requires extending the chunked quadtree, which could be easily
	done in a preprocessing step. However, deformation isn't
	trivial since the algorithm requires a static mesh;
	if any height samples were changed, it would require
	reprocessing the entire quadtree, which is unacceptable for
	real-time deformation.

