Traversal on DAG-based Multiresolution Mesh Hierarchy

Traversal algorithm on the multiresolution hierarchy is critical for the view-dependent level of detail system. In this paper, we study multire solution hierarchy traversal for a DAG hierarchy of vertex-split/edge-collapse operations, in the context of a client-server based system. We present a general traversal management strategy that is beneficial for interactive frame rate and triangle-budget control, and is also favorable for the client-server based system. We adapt two commonly used traversal algorithms, linear traversal and priority-oriented traversal, to work under the management strategy. And we also propose a constant-time traversal algorithm. Extensive experiments on these three traversal algorithms are done and the comparison results can be used as a guide to choose the most appropriate traversal algorithm for different system requirements