A Fast and Lossless Compression Algorithm for Point-Based Models Based on Local Minimal Spanning Tree

Point-based graphics has become one of the hottest topics in 3D computer graphics recently. Since point-based models are often too large to be stored and transferred in limited hardware and bandwidth easily, it is necessary to design effective compression methods. We propose an efficient and fast lossless geometry compression algorithm for point-based models. Firstly, point-sampled surface is split into many equal sized surface patches. Over the points of each patch, a minimal spanning tree is constructed and encoded in breadth first order. During this process, each point is predicted from its father in the spanning tree. Then both predicted and actual positions are broken into sign, exponent and mantissa, and their corrections are separately compressed by using arithmetic coding in the different contexts. The achieved bit-rate and time usage in our algorithm outperforms the previous lossless compression methods of point-based models. Our algorithm nicely complements those lossy compression algorithms of point-based models, and it can be used under the situation where lossy compression is not preferred.