A New Algorithm for View-Dependent Optimization of Terrain with Sub-Linear Time CPU Processing

Abstract

This paper presents new schemes for view-dependent continuous level-of-detail (LOD) rendering of terrain which update output meshes with sub-linear CPU processing. We use a directed acyclic graph (DAG) abstraction for the longest-edge-bisection based multiresolution model. The other component of our refinement framework is the saturated monotonic perspective-division based error function. We made the critical observation that, for a vertex, the difference between the reciprocals of this particular error function for two different viewpoints is bounded by the distance between the two viewpoints, times a per-vertex constant. We call this the bounded variation property. Utilizing this property, we introduce the distance deferral table, a circular array based structure that schedules deferred processing of DAG vertices according to viewpoint motion. We then use the distance deferral table to optimize the traditional threshold-based refinement algorithm and the dual-queue constrained optimization algorithm to allow sub-linear CPU run-time.