Seed polytopes for incremental approximation

O. Aichholzer, F. Aurenhammer, T. Hackl, B. Kornberger, S. Plantinga, G. Rote, A. Sturm, and G. Vegter

Abstract:

Approximating a three-dimensional object in order to simplify its handling is a classical topic in computational geometry and related fields. A typical approach is based on incremental approximation algorithms, which start with a small and topologically correct polytope representation (the seed polytope) of a given sample point cloud or input mesh. In addition, a correspondence between the faces of the polytope and the respective regions of the object boundary is needed to guarantee correctness. We construct such a polytope by first computing a simplified though still homotopy equivalent medial axis transform of the input object. Then, we inflate this medial axis to a polytope of small size. Since our approximation maintains topology, the simplified medial axis transform is also useful for skin surfaces and envelope surfaces.



Reference: O. Aichholzer, F. Aurenhammer, T. Hackl, B. Kornberger, S. Plantinga, G. Rote, A. Sturm, and G. Vegter. Seed polytopes for incremental approximation. In Proc. $24^{th}$ European Workshop on Computational Geometry EuroCG '08, pages 13-16, Nancy, France, 2008.