GVU Technical Report Number: GIT-GVU-01-05

Title: Compressed Piecewise Circular Approximation of 3D Curves

Authors: Alla Safonova, Jarek Rossignac

Abstract:
We propose a compact approximation scheme for 3D curves. Consider a polygonal curve P, whose n vertices have been generated through adaptive (and nearly minimal) sampling, so that P approximates some original 3D curve, O, withing tolerance e0. We present a practical and efficient algorithm for computing a continuous 3D curve C that approximates P within tolerance e1 and is composed of a chain of m circular arcs, whose end-points coincide with a subset of the vertices of P. We represent C using 5m+3 scalars, which we compress within a carefully selected quantization error e2. Our approximation uses a total of less than 7.5n bits, when O is a typical surface/surface intersection and when the error bound e1+e2 is less than 0.02% of the radius of a minimal sphere around O. For less accurate approximations, the storage size drops further, reaching for instance a total of n bits where e1+e2 is increased to 3%. The storage cost per vertex is also reduced when e0 is decreased to force a tighter fit for smooth curves. As expected, the compression deteriorates for jagged curves with a tight error bound. In any case, our representation of C is always more compact than a polygonal curve that approximate O with the same accuracy. To guarantee a correct fit, we introduce a new ereror metric for e1, which prevents discrepancies between P and C that are not detected by previously proposed Hausdorff or least-square error estimates. We provide the details of the algorithms and of the geometric constructions. We also introduce a conservative speed-up for computing C more efficiently and demonstrate that it is sub-optimal in only 2% of the cases. Finally, we report results on several types of curves and compare them to previously reported polygonal approximations, observing compression ratios that vary between 15:1 and 36:1.

Keywords: compression

You can access this technical report via: PDF