Geometry compression for graphics models and visualization datasets

We summarize in this dissertation our progress on lossless geometry compression for graphics models and visualization datasets.; First, the problem of large alphabet size is commonly found in compressing these datasets. We solve the problem of semi-adaptive entropy coding of large alphabets by a two-layer code where we formulate the underlying alphabet partitioning problem as an optimization problem. We give solutions to this optimization problem and show that the results are superior.; Next, we present our technique for lossless geometry compression of irregular-grid volume data represented as a tetrahedral mesh. We give a novel lossless compression technique that effectively predicts, models, and encodes geometry data for both steady-state (one scalar value per vertex) and time-varying (multiple time-step scalar values per vertex) data. Our experimental results show that this technique achieves excellent compression ratios.; Then, we develop a technique for lossless compression of point based 3D models, where there is no connectivity information to be used to assist the compression. We formulate the problem as the Minimum Entropy Tree problem which can be shown to be NP-hard. We give a heuristic solution to this problem and demonstrate by experiments that our approach achieves excellent compression ratios.; Finally, we give a novel geometry compression technique for 3D triangle meshes. We formulate the problem of optimally (traversing triangles and) predicting the vertices via the widely used Flipping operations as a combinatorial optimization problem of constructing a Constrained Minimum Spanning Tree. We present heuristic solutions for this problem and show that we can achieve significant improvements over previous techniques in the literature.