Isosurface Extraction and View-Dependent Filtering from Time-Varying Fields Using Persistent Time-Octree (PTOT)

摘要

We develop a new algorithm for isosurface extraction andview-dependent filtering from large time-varying fields, by using anovel Persistent Time-Octree (PTOT) indexingstructure. Previously, the Persistent Octree (POT) was proposed toperform isosurface extraction and view-dependent filtering, whichcombines the advantages of the interval tree (for optimal searches ofactive cells) and of the Branch-On-Need Octree (BONO, forview-dependent filtering), but it only works for steady-state(i.e., single time step) data. For time-varying fields, a 4D versionof POT, 4D-POT, was proposed for 4D isocontour slicing, where slicingon the time domain gives all active cells in the queried timestep and isovalue. However, such slicing is not output sensitiveand thus the searching is sub-optimal. Moreover, it was notknown how to support view-dependent filtering in addition totime-domain slicing.In this paper, we develop a novel Persistent Time-Octree (PTOT) indexing structure, which has the advantages of POT and performs 4Disocontour slicing on the time domain with an output-sensitiveand optimal searching. In addition, when we query the sameisovalue q over m consecutive time steps, there is noadditional searching overhead (except for reporting the additionalactive cells) compared to querying just the first time step. Suchsearching performance for finding active cells is asymptoticallyoptimal, with asymptotically optimal space and preprocessing time aswell. Moreover, our PTOT supports view-dependent filtering in addition to time-domain slicing. We propose a simple and effectiveout-of-core scheme, where we integrate our PTOT with implicit occluders, batched occlusion queries and batched CUDA computingtasks, so that we can greatly reduce the I/O cost as well asincrease the amount of data being concurrently computed in GPU.This results in an efficient algorithm for isosurface extraction withview-dependent filtering utilizing a state-of-the-art programmable GPUfor time-varying fields larger t-nhan main memory. Our experiments ondatasets as large as 192GB (with 4GB per time step) having no morethan 870MB of memory footprint in both preprocessing and run-timephases demonstrate the efficacy of our new technique.