Adaptive geometry compression based on four-point interpolatory subdivision schemes with labels

Abstract

We propose an adaptive geometry compression method with labels based on four-point interpolatory subdivision schemes. It can work on digital curves of arbitrary dimensions. With the geometry compression method, a digital curve is adaptively compressed into several segments with different compression levels. Each segment is a four-point subdivision curve with a subdivision step. Labels are recorded in data compression to facilitate merging the segments in data decompression. We provide high-speed four-point interpolatory subdivision curve generation methods for efficiently decompressing the compressed data. For an arbitrary positive integer k, formulae for the number of resultant control points of a four-point subdivision curve after k subdivision steps are provided. Some formulae for calculating points at the kth subdivision step are also presented. The time complexity of the new approaches is O(n), where n is the number of points in the given digital curve. Examples are provided to illustrate the efficiency of the proposed approaches.

Keywords:

• Geometry compression
• Subdivision scheme
• Four-point subdivision
• Interpolatory subdivision
• High-speed curve generation

Acknowledgements

This research was supported by the Chinese 973 Programme (2004CB719400) and the National Science Foundation of China (60403047, 60533070). The second author was supported by a project sponsored by the Foundation for the Author of National Excellent Doctoral Dissertation of PR China (200342), and a Programme for New Century Excellent Talents in University (NCET-04-0088).