Show simple item record

dc.contributor.authorSafanova, Alla
dc.contributor.authorRossignac, Jaroslaw R.
dc.date.accessioned2004-10-06T16:41:18Z
dc.date.available2004-10-06T16:41:18Z
dc.date.issued2001
dc.identifier.urihttp://hdl.handle.net/1853/3317
dc.description.abstractWe 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.en
dc.format.extent700415 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen
dc.relation.ispartofseriesGVU Technical Report;GIT-GVU-01-05
dc.subjectCompressionen
dc.subject3Den
dc.subjectCurvesen
dc.titleCompressed Piecewise Circular Approximation of 3D Curvesen
dc.typeTechnical Reporten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record