Topology preserving top-down compression of 2d vector fields using bintree and triangular quadtrees

Abstract

We present a hierarchical top-down refinement algorithm for compressing 2D vector fields that preserves topology. Our approach is to reconstruct the data set using adaptive refinement that considers topology. The algorithms start with little data and subdivide regions that are most likely to reconstruct the original topology of the given data set. We use two different refinement techniques. The first technique uses bintree subdivision and linear interpolation. The second algorithm is driven by triangular quadtree subdivision with Coons patch quadratic interpolation. We employ local error metrics to measure the quality of compression and as a global metric we compute Earth Mover's Distance (EMD) to measure the deviation from the original topology. Experiments with both analytic and simulated data sets are presented. Results indicate that one can obtain significant compression with low errors without losing topological information. Advantages and disadvantages of different topology preserving compression algorithms are also discussed in the paper.