Zhu, Yuanchen2016-01-072008Zhu, Yuanchen. 2008. A New Algorithm for View-Dependent Optimization of Terrain with Sub-Linear Time CPU Processing. Harvard Computer Science Group Technical Report TR-07-08.http://nrs.harvard.edu/urn-3:HUL.InstRepos:24019789This 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.en-USViewing algorithmsvirtual realityvisualization techniquescontinuous level-of-detailview-dependent optimizationdeferred processingmultiresolution representationResearch Paper or Report2016-01-07