Exact computation of the medial axis of a polyhedron

✍ Scribed by Tim Culver; John Keyser; Dinesh Manocha

• Book ID: 104006564
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 840 KB
• Volume: 21
• Category: Article
• ISSN: 0167-8396
• DOI: 10.1016/j.cagd.2003.07.008

✦ Synopsis

We present an accurate algorithm to compute the internal Voronoi diagram and medial axis of a 3-D polyhedron. It uses exact arithmetic and exact representations for accurate computation of the medial axis. The algorithm works by recursively finding neighboring junctions along the seam curves. To speed up the computation, we have designed specialized algorithms for fast computation with algebraic curves and surfaces. These algorithms include lazy evaluation based on multivariate Sturm sequences, fast resultant computation, culling operations, and floatingpoint filters. The algorithm has been implemented and we highlight its performance on a number of examples.