Exact medial axis computation for triangulated solids with respect to piecewise linear metrics. (English) Zbl 1345.65008

Aichholzer, Oswin; Aigner, Wolfgang; Aurenhammer, Franz; Jüttler, Bert

Boissonnat, Jean-Daniel (ed.) et al., Curves and surfaces. 7th international conference, Avignon, France, June 24–30, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-27412-1/pbk). Lecture Notes in Computer Science 6920, 1-27 (2012).

Summary: We propose a novel approach for the medial axis approximation of triangulated solids by using a polyhedral unit ball \(B\) instead of the standard Euclidean unit ball. By this means we compute the exact medial axis \(\text{MA}(\Omega)\) of a triangulated solid \(\Omega \) with respect to a piecewise linear (quasi-) metric \(d_B\). The obtained representation of \(\Omega \) by the medial axis transform \(\text{MAT}(\Omega)\) allows for a convenient computation of the trimmed offset of \(\Omega \) with respect to \(d_B\). All calculations are performed within the field of rational numbers, resulting in a robust and efficient implementation of our approach. Adapting the properties of \(B\) provides an easy way to control the level of details captured by the medial axis, making use of the implicit pruning at flat boundary features.
For the entire collection see [Zbl 1229.65002].

MSC:

65D17	Computer-aided design (modeling of curves and surfaces)
65D18	Numerical aspects of computer graphics, image analysis, and computational geometry

Keywords:

medial axis; piecewise linear metric; mesh boundary; trimmed offset

Software:

CGAL