Multi-Resolution Indexing for Hierarchical Out-of-Core Traversal of Rectilinear Grids

摘要: The real time processing of very large volumetric meshes introduces specific algorithmic challenges due to the impossibility fitting input data in main memory a computer. basic assumption (RAM computational model) uniform-constant-time access each location is not valid because part stored out-of-core or external memory. performance most algorithms does scale well transition from in-core conditions. degradation high frequency I/O operations that may start dominating overall running time. Out-of-core computing [28] addresses specifically issues algorithm redesign and layout restructuring enable patterns with minimal processing. Results this area are also valuable parallel distributed where one has deal similar issue balancing migration solution problem typically divided into two parts: (i) analysis understand its and, when possible, maximize their locality; (ii) storage secondary consistent amortize cost operation over several operations. In case hierarchical visualization for 3D hierarchy traversed build derived geometric models adaptive levels detail. shape output then modified dynamically incremental updates level parameters govern continuous modification geometry dependent on runtime user interaction making it impossible determine priori what detail going be constructed. For example they can like viewpoint current display window internal isovalue an isocontour position orthogonal slice. structure pattern summarized points: by so same resolution adjacent at within mostly regions geometrically close. paper I introduce new static indexing scheme induces satisfying both requirements traversal n-dimensional regular grids. particular implementation exploits way recursive construction Z-order space filling curve. standard maps nD onto 1D sequence curve based simple bit interleaving merges n indices index times longer. This helps grouping proximity but only show how transformed alternative allows group per first proximity. yields appropriate