Compressed Piecewise Circular Approximation of 3D Curves

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/3317

Title: Compressed Piecewise Circular Approximation of 3D Curves
Author: Safanova, Alla ; Rossignac, Jaroslaw R.
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.
Type: Technical Report
URI: http://hdl.handle.net/1853/3317
Date: 2001
Relation: GVU Technical Report;GIT-GVU-01-05
Publisher: Georgia Institute of Technology
Subject: Compression
3D
Curves

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
01-05.pdf 683.9Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record