A competition flow method for computing medial axis transform

摘要

Medial axis computation (MAC) has many applications in computer-aided design, computer graphics, automated mesh generation, solid modeling, CNC tool path generation, robotic motion planning, bioinformatics, and shape analysis. There are three key issues that need to be further addressed on MAC of a NURBS(Non-Uniform Rational B-Spline) curve boundary, namely (1) computation of regular medial axis points; (2) efficient detection of the existence of a branch point where two branches intersect; and (3) convergence and correctness on computing the position of a branch point. This paper presents a competition flow method for medial axis computation of a planar simply-connected NURBS boundary. Different from previous methods which trace a Voronoi Diagram Tree (VDT) in depth-first order from a terminal point, the competition flow method (CFM) traces the corresponding tree in breadth-first order. It has three main contributions. Firstly, it utilizes an optimized method based on previous state-of-art algorithms for computing regular medial axis points, which can achieve a higher computational efficiency. Secondly, it implements a divide-and-conquer method in a natural way by proposing a simple tree technique, in which a VDT is divided into several simple tree structures of level l, l=0,1,…, for competitive medial axis computation. Finally, by using the competition flow method, possible places where branch points are located, are intuitively and efficiently detected and bounded with high precision, which ensures the convergence and the correctness of the computation of the position of a branch point, and also ensures the correctness of the topological structure of the medial axis tree. Numerical examples show that the new method can achieve a better performance compared with several existing methods.