An efficient, accurate approach to medial axis transforms of pockets with closed free-form boundaries

Abstract

Medial axis transform of a pocket with free-form closed boundaries is a completed, compact representation of the pocket geometric shape and topology. It is very useful to multiple cutters selection and their tool paths generation for CNC machining of complex pockets. In the past decades, much research has been successfully conducted on the topic of finding the medial axis of a shape domain bounded with a polygon or simple geometries, e.g., lines and circles. Currently, more pockets with free-form boundaries are adopted in mechanical parts; however, the prior medial axis generation methods cannot handle this type of pockets well, resulting in long computation time and low medial axis accuracy. To address this problem, an efficient, accurate approach to calculating the medial axis transforms of these pockets is proposed in this work. An original optimization model of bisectors is established, and a new optimization method—the hybrid global optimization method—is developed to efficiently and accurately solve the optimization model of bisectors. The new optimization model and solver have been applied to many examples, and the testing results have demonstrated the advantages of this innovative approach over the prior medial axis methods. It can be an effective solution to the medial axis transforms of complex pockets.

1 Introduction

As a new type of geometric feature, pockets with closed free-form boundary curves are often adopted in mechanical parts, and it is always in high demand to efficiently machine these pockets in industry. However, due to their complex shape, it is quite challenging to select appropriate cutters and plan tool paths for them to achieve high material removal rates [1]. Medial axis (MA) of the pockets can be an effective tool to solve this technical challenge. Basically, the medial axis of a planar domain is the locus of centers of all the largest circles that are bounded by the domain boundaries at the contact points and are scattered in the domain along its boundaries. In this paper, the medial axis transform (MAT) refers to these circles centers, radii, and contact points. Due to its wide applications, MA has been a topic under extensive research in the past decade. For pockets with polygon boundaries, many works adopted Voronoi diagrams of the pockets to easily and accurately find their MAs, and the results were acceptable. But, for free-form boundaries, they often encountered the problem of low accuracy of medial axis points. Then the analytical methods were proposed to find the bisector equations between two curves. However, these methods are very difficult to implement and computing time is long. The objective of this research is to develop a new approach to generating the medial axis transforms of free-form pockets, which include non-uniform rational B-spline (NURBS) boundary curves.

Among the accurate mathematical methods of finding MA [2–7], the differential and topological properties of the MAT were studied and the exact MATs of pocket boundaries with piecewise lines and circular arcs were constructed in an analytical way [2, 3]. A trimming procedure was proposed to identify parametric sub-segments of variable distance offsets that constitute true bisectors of point/curve and curve/curve [4, 5]. Elber and Kim [6] represented the correspondence between the foot points on two planar rational curves as a bi-variate B-spline function. Moreover, Culver et al. [7] developed a tracing algorithm to compute the exact medial axes of polyhedrons. The approaches are accurate; however, their solutions could be complicated and the computing time normally is quite long.

Many researchers have conducted research on generating Voronoi diagrams to approximate MAs. In computational geometry, the technique of computing the Voronoi diagram of a group of point sites is matured [8, 9], and several efficient algorithms of complexity $O\,(n \cdot \log n)$ are available together with their free source codes [10]. Brandt [11] found that the Voronoi diagram of a shape can properly converge if its boundary is continuous. Dey and Zhao [12] approximated a medial axis with a Voronoi diagram in a scale- and density-independent manner, and convergence of this approximation was guaranteed. Chou [13] developed a tracing algorithm to calculate Voronoi diagrams for closed planar shapes with boundaries of free-form curves. Ramamurthy and Farouki [14, 15] presented an approach for computing Voronoi diagrams by adding a single boundary segment in each step, based on point/curve and curve/curve bisectors. They clearly stated in [14] that “it might seem that an easy ‘practical’ approach to domains with free-form boundary curves is to first approximate the boundaries, within a prescribed tolerance, by polygonal or piecewise-linear/circular curves, and then invoke the currently available algorithms for such boundary curves. However, this approach yields qualitatively incorrect results.” Alt et al. [16] presented a randomized incremental algorithm to compute the Voronoi diagrams of curved objects by breaking up the curves into “harmless” pieces, which include line segments, circular arcs and spiral arcs. Unfortunately, the methods of approximating bisector curves with Voronoi diagrams are challenged for shape domains with free-form boundaries. Seong et al. [17] calculated the critical structures of the Voronoi diagrams by solving a system of nonlinear piecewise rational equations in the parametric space. However, this method is very complicated.

Besides the main stream MA methods mentioned above, Gursoy and Patrikalakis [18, 19] introduced a wave front propagation method by determining inward offset distances and the associated branch points at which the contour topology changes. Their method analytically defines the MA in terms of conic sections, and free-form boundary curves are approximated within a prescribed tolerance using line and circular arc segments. Likewise, Hassouna and Farag [20] rendered a wave front propagation method. The front propagates at each object point in a speed that is proportional to its Euclidean distance from the boundary. The motion of the front is governed by a nonlinear partial differential equation and is solved using level set methods. Then, the medial axis is computed by tracking the propagating front points of the maximal positive curvature. Aichholer et al. [21] approximated the boundary spline with spiral biarcs and found the medial axis based on the biarcs. Kosinka and Juttler [22] computed the medial surfaces of spatial boundary surfaces in the Minkowski space. However, a major problem of these methods is that the medial axis of the fitting biarcs could largely deviate from the ideal medial axis of the spline boundary even though they fit the boundary very well. The main reason is that the fitting arcs can be quite different from the boundary with regard to the tangent at two points on them, the corresponding medial axis points could be far from each other. This is an inherited problem of these methods and has not received much attention.

To address the technical challenge of the prior MA methods, an efficient, accurate approach to the medial axis transforms of pockets with closed free-form boundary curves is proposed. As the basics, the properties of the free-form boundary curves of pockets and terminologies and definitions of MAT are provided in Sect. 2. The optimization model of bisector point is formulated in Sect. 3, and a new global optimization method—a hybrid global optimization method—is developed in Sect. 4 to solve the optimization problem for bisector points of the MA. In Sect. 5, several examples are provided to compare the results of MAs found with a Voronoi diagram generation method and this new approach, in order to demonstrate advantages of this approach. This work is concluded in Sect. 6.

2 Medial axis transforms of pockets with closed free-form boundary curves

Since the main research objective is to generate medial axis transforms of pockets of mechanical parts for their CNC machining, the geometric properties and definitions of the pocket boundaries and their medial axis transforms are first rendered in this section.

2.1 Properties of the free-form boundaries of pockets of mechanical parts

To design pockets of mechanical parts with CAD software, composite curves including line, arc, and NURBS curve segments are often used to define the external boundaries of the recess domains and boundaries of the internal islands, if any [1]. The external boundary is closed with its component curves head-to-toe connected one-by-one. All component curves are regular curves, i.e., their first derivatives exist, and are represented in a parametric form. In this work, a pocket boundary generally includes external and internal boundaries, and it is defined in the following.

Definition 2.1

A pocket boundary is defined as a composite parametric curve ${\mathbf{\rm B}}(u):{\mathbb{R}} \to {\mathbb{R}}^{2}$ consisting of $n$ component curves, ${\mathbf{B}}^{i} (u): = \left[ {\begin{array}{*{20}c} {Bx^{i} (u),} & {By^{i} (u)} \\ \end{array} } \right]^{\text{T}} , \, i = 1,2, \ldots ,n$, where their parameter $u \in \left[ {\begin{array}{*{20}c} {u_{\hbox{min} }^{i} ,} & {u_{\hbox{max} }^{i} } \\ \end{array} } \right]$. The boundary generally can be represented as ${\mathbf{B}}(u):= \bigcup\nolimits_{i = 1}^{n} {{\mathbf{B}}^{i} } (u)$. The component curves can be lines, circular arcs and NURBS curves with the following properties:

• ${\mathbf{B}}^{i} \left( {u_{\hbox{max} }^{i} } \right) = {\mathbf{B}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right), \, i = 1,2, \ldots ,\left( {n - 1} \right)$; and ${\mathbf{B}}^{1} \left( {u_{\hbox{min} }^{1} } \right) = {\mathbf{B}}^{n} \left( {u_{\hbox{max} }^{n} } \right);$

• The unit tangent vector of a component curve as ${\mathbf{T}}^{i} (u):= \left[ {\begin{array}{*{20}c} {Tx^{i} (u),} & {Ty^{i} (u)} \\ \end{array} } \right]^{\text{T}} ;$ and

• The unit normal vector of a component curve as ${\mathbf{N}}^{i} (u):= \left[ {\begin{array}{*{20}c} {Nx^{i} (u),} & {Ny^{i} (u)} \\ \end{array} } \right]^{\text{T}} ,$ and the vector ${\mathbf{N}}^{i} (u)$ pointing inside of the pocket.

For the external boundary of a pocket, its component curves and their directions are arranged counter-clockwise. For an internal boundary of the pocket, its component curves and their directions are arranged clockwise. Each of these boundaries is stored as an ordered list of the component curves.

Generally, at a point on a component curve, there exist infinite circles tangent to this curve and on the pocket side, which can be defined in the following way. First, for any point ${\mathbf{P}}$ with parameter $u_{\text{P}}$ on a component line ${\mathbf{B}}^{i} (u)$, $u_{\hbox{min} }^{i} \le u \le u_{\hbox{max} }^{i}$, its position vector ${\mathbf{B}}_{\text{P}}^{i}$ can be computed as ${\mathbf{B}}_{\text{P}}^{i} = {\mathbf{B}}^{i} \left( {u_{\text{P}} } \right)$, and the corresponding unit normal of ${\mathbf{B}}^{i} (u)$ is ${\mathbf{N}}_{\text{P}}^{i} := {\mathbf{N}}^{i} \left( {u_{\text{P}} } \right)$, where ${\mathbf{N}}^{i} (u)$ is the unit normal function. If the point ${\mathbf{P}}$ is the starting point ${\mathbf{B}}_{\text{S}}^{i}$ $\left( {u_{\text{P}} = u_{\hbox{min} }^{i} } \right)$, the unit normal vector at this point is on its right-hand side, denoted as ${\mathbf{N}}^{i} \left( {u_{\text{P}} } \right):= {\mathbf{N}}^{i} \left( {u_{\text{P}}^{ + } } \right):= {\mathbf{N}}^{i} \left( {u_{\hbox{min} }^{i} } \right)$; likewise, if the point ${\mathbf{P}}$ is the ending point ${\mathbf{B}}_{\text{E}}^{i}$ $\left( {u_{\text{P}} = u_{\hbox{max} }^{i} } \right)$, the unit normal at this point is on its left-hand side as ${\mathbf{N}}^{i} \left( {u_{\text{P}} } \right):= {\mathbf{N}}^{i} \left( {u_{\text{P}}^{ - } } \right):= {\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right)$. Therefore, the center of a tangent circle ${\varvec{\Uptheta}}_{\text{P}} (r)$ is represented as ${\mathbf{O}}^{{{{\Uptheta}}_{\text{P}} }} := {\mathbf{B}}_{\text{P}}^{i} + r \cdot {\mathbf{N}}_{\text{P}}^{i}$, where the circle radius $r > 0$. This type of tangent circles is defined as ${\varvec{\Uptheta}}_{\text{P}} \left( r \right): = \left\{ {\left( {u_{\text{P}} ,r} \right):{\mathbf{B}}_{\text{P}}^{i} ,{\mathbf{O}}^{{{{\Uptheta}}_{\text{P}} }} ,r} \right\}$.

Second, for a point ${\mathbf{P}}$ on a circular arc ${\mathbf{B}}^{i} (u)$ of center ${\mathbf{O}}^{{{\text{B}}^{i} }}$and radius $r^{{{\text{B}}^{i} }}$, the point parameter $u_{\text{P}}$ is within its domain, $u_{\hbox{min} }^{i} \le u_{\text{P}} \le u_{\hbox{max} }^{i}$. It is easy to understand that the largest circle tangent to the arc at this point ${\mathbf{B}}_{\text{P}}^{i}$ and inside the arc is the corresponding circle of the arc. Thus, the largest tangent circle ${\varvec{\Uptheta}}_{\text{P}}^{\hbox{max} }$ is the circular arc ${\mathbf{B}}^{i} (u)$, whose center ${\mathbf{O}}^{{{{\Uptheta}}_{\text{P}}^{\hbox{max} } }}$ is ${\mathbf{O}}^{{{\text{B}}^{i} }}$ and radius $r^{{{{\Uptheta}}_{\text{P}}^{\hbox{max} } }}$ is $r^{{{\text{B}}^{i} }}$. If the point ${\mathbf{P}}$ is at the starting point, the unit normal vector ${\mathbf{N}}_{\text{P}}^{i}$ can be calculated as

$$ {\mathbf{N}}_{\text{P}}^{i} : = {\mathbf{N}}^{i} \left( {u_{\text{P}}^{ + } } \right) = {\mathbf{N}}^{i} \left( {u_{\hbox{min} }^{i} } \right) = \left[ {\begin{array}{*{20}c} { - \cos \left( {u_{\hbox{min} }^{i} } \right)} \\ { - \sin \left( {u_{\hbox{min} }^{i} } \right)} \\ \end{array} } \right], $$

(1)

and if the point ${\mathbf{P}}$ is at the ending point, the unit normal vector ${\mathbf{N}}_{\text{P}}^{i}$ can be calculated as ${\mathbf{N}}_{\text{P}}^{i} : = {\mathbf{N}}^{i} \left( {u_{\text{P}}^{ - } } \right) = {\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right).$

Third, for a point ${\mathbf{P}}$ of parameter $u_{\text{P}}$ on a NURBS component curve ${\mathbf{B}}^{i} (u)$, its unit tangent vector ${\mathbf{T}}_{\text{P}}^{i} : = {\mathbf{T}}^{i} \left( {u_{\text{P}} } \right)$ and unit normal vector ${\mathbf{N}}_{\text{P}}^{i} : = {\mathbf{N}}^{i} \left( {u_{\text{P}} } \right)$ can be calculated. The curvature $\kappa_{\text{P}} : = \kappa \left( {u_{\text{P}} } \right)$ of this curve at this point can be found using the following equation,

$$ \frac{d}{du}\left[ {{\mathbf{T}}^{i} (u)} \right] = \kappa (u) \cdot \left| {\frac{d}{du}{\mathbf{B}}^{i} (u)} \right| \cdot {\mathbf{N}}^{i} (u),\quad{\text{ and}}\quad\,u = u_{\text{P}} . $$

(2)

When $\kappa_{\text{P}} > 0$, the largest circle ${\varvec{\Uptheta}}_{\text{P}}^{\hbox{max} }$ tangent to the NURBS curve at ${\mathbf{B}}_{\text{P}}^{i}$ is the osculating circle of the NURBS curve at this point, and its radius $r^{{{{\Uptheta}}_{\text{P}}^{\hbox{max} } }}$ is fixed at ${1 \mathord{\left/ {\vphantom {1 {\kappa_{\text{P}} }}} \right. \kern-0pt} {\kappa_{\text{P}} }}$, and the equation of the circle center is

$$ {\mathbf{O}}^{{{{\Uptheta}}_{\text{P}}^{\hbox{max} } }} : = {\mathbf{B}}_{\text{P}}^{i} + r^{{{{\Uptheta}}_{\text{P}}^{\hbox{max} } }} \cdot {\mathbf{N}}_{\text{P}}^{i} = {\mathbf{B}}_{\text{P}}^{i} + \frac{1}{{\kappa_{\text{P}} }} \cdot {\mathbf{N}}_{\text{P}}^{i} . $$

(3)

When $\kappa_{\text{P}} < 0$, the tangent circle ${\varvec{\Uptheta}}_{\text{P}} (r)$ is not unique, and the circle center is ${\mathbf{O}}^{{{{\Uptheta}}_{\text{P}} }} : = {\mathbf{B}}_{\text{P}}^{i} + r \cdot {\mathbf{N}}_{\text{P}}^{i}$, where the circle radius is $r > 0$.

As all the pocket component curves are regular curves, at an interior curve point, whose parameter is $u_{\text{P}}$, the unit tangent vectors on both sides of the point are the same, i.e., ${\mathbf{T}}^{i} \left( {u_{\text{P}}^{ - } } \right) = {\mathbf{T}}^{i} \left( {u_{\text{P}}^{ + } } \right)$. So there is only one unit normal vector ${\mathbf{N}}_{\text{P}}^{i}$ at this point. In this work, the composite curves of the pocket boundaries connect one by one with at least position continuity. Some pair of curves is smoothly connected, sharing the same tangent direction at their joint; while some pair is not smoothly connected, having different tangent directions at their joint. Thus, for the unit tangent vectors of the two curves at the left and the right of the joint are the same, i.e., ${\mathbf{T}}^{i} \left( {u_{\hbox{max} }^{i} } \right) = {\mathbf{T}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)$, there is only one unit normal vector, i.e., ${\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right) = {\mathbf{N}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)$. However, for the non-smooth link of two component curves, the joint is a cusp and the unit normal vector at the joint is defined here. If the tangent vectors of the two curves at the joint meet the following condition,

$$ \left[ {{\mathbf{T}}^{i} \left( {u_{\hbox{max} }^{i} } \right) \times {\mathbf{T}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)} \right]_{z} = \left| {\begin{array}{*{20}c} {Tx^{i} \left( {u_{\hbox{max} }^{i} } \right)} & {Ty^{i} \left( {u_{\hbox{max} }^{i} } \right)} \\ {Tx^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)} & {Ty^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)} \\ \end{array} } \right| > 0, $$

(5)

which means this joint is a concave corner, no unit normal vector at the joint is defined. Otherwise, the angle $\theta_{\hbox{min} }$ starting from ${\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right)$ to ${\mathbf{N}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)$ can be calculated as

$$ \theta_{\hbox{min} } = - \cos^{ - 1} \left[ {{\mathbf{T}}^{i} \left( {u_{\hbox{max} }^{i} } \right) \cdot {\mathbf{T}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)} \right], $$

(6)

where $- \pi < \theta_{\hbox{min} } < 0$. The valid unit normal vector at the joint can be defined as

$$ {\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} ,\theta } \right):= {\mathbf{N}}^{i + 1} \left( {u_{\hbox{min} }^{i} ,\theta } \right):= \left[ {\begin{array}{*{20}c} {\cos \theta } & { - \sin \theta } \\ {\sin \theta } & {\cos \theta } \\ \end{array} } \right] \cdot {\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right), $$

(7)

where $\theta \in \left[ {\theta_{\hbox{min} } ,0^{ \circ } } \right]$. Hence, any unit normal vector between ${\mathbf{N}}^{i} \left( {u_{\hbox{max} }^{i} } \right)$ and ${\mathbf{N}}^{i + 1} \left( {u_{\hbox{min} }^{i + 1} } \right)$ is a valid unit normal vector at the joint (see Fig. 1).

Fig. 1

An illustrative diagram for finding valid unit normal vectors at a cusp between two adjacent component curves

2.2 Terminologies and definitions of medial axis transform

The medial axis transform (MAT) of the domain of a pocket is a completed shape descriptor, which concisely represents the domain shape and is very useful to manipulate the complex pocket domain (see Fig. 2). The MAT is based on the medial axis (MA), which geometrically bisects the pocket domain and becomes the pocket skeleton. Although MA has been defined in the published articles, we update its definition in our work for clarity. For this purpose, locally inscribed circle (LIC) is first introduced. As before, the external and internal boundaries are denoted as ${\mathbf{B}}^{i} (u)$ with parameter u, and a locally inscribed circle at a boundary point u, its center and radius are denoted as $\mathcal{\Upphi }(u)$, ${\mathbf{O}}^{{{\Upphi}}}$, and $r^{{{\Upphi}}}$, respectively.

Fig. 2

Illustration of local inscribed circles and the basic elements of the MA of a pocket

Definition 2.2

Given a pocket domain ${\varvec{\Upomega}} \subset {\mathbb{R}}^{2}$ and its boundary ${\mathbf{B}}(u)$, at a boundary point P with parameter u, a locally inscribed circle ${\varvec{\Upphi}}(u)$ of center ${\mathbf{O}}^{{{\Upphi}}}$ and radius $r^{{{\Upphi}}}$ is defined if and only if a circle meets four conditions: (1) ${\varvec{\Upphi}}(u) \subseteq {\varvec{\Upomega}}$, (2) $\forall [{\mathbf{P}}_{1} ,{\mathbf{P}}_{2} , \ldots ,{\mathbf{P}}_{j} , \ldots ,{\mathbf{P}}_{m} ] :{ = }{\varvec{\Upphi}}(u) \cap {\mathbf{B}}(u),\quad m \ge 1$, $\left| {{\mathbf{O}}^{{{\Upphi}}} {\mathbf{P}}_{1} } \right| = \left| {{\mathbf{O}}^{{{\Upphi}}} {\mathbf{P}}_{2} } \right| = \cdots = \left| {{\mathbf{O}}^{{{\Upphi}}} {\mathbf{P}}_{j} } \right| = \cdots = \left| {{\mathbf{O}}^{{{\Upphi}}} {\mathbf{P}}_{m} } \right|$, (3) $\forall {\mathbf{P}}_{j} : = {\mathbf{B}}^{i} \left( {u_{j} } \right)$,${\mathbf{O}}^{{{\Upphi}}} {\mathbf{P}}_{j} \cdot {\mathbf{T}}^{i} \left( {u_{j} } \right) = 0$, $j = 1,2, \ldots ,m$, and (4) the radius $r^{{{\Upphi}}}$ is the maximum. Here, the locally inscribed circle (LIC) is represented as ${\varvec{\Upphi}}\left( u \right):= \left\{ {{\mathbf{O}}^{{{\Upphi}}} \left( u \right),r^{{{\Upphi}}} \left( u \right),{\varvec{\Upphi}}\left( {{\mathbf{O}}^{{{\Upphi}}} ,r^{{{\Upphi}}} } \right),\left[ {{\mathbf{P}}_{1} ,{\mathbf{P}}_{2} , \ldots ,{\mathbf{P}}_{m} } \right]} \right\}$ (see Fig. 2). At any boundary point, its LIC is the largest circle tangent to the boundary inside the pocket without any intersection with the boundary.

Definition 2.3

The MA definition is that the MA of a pocket domain ${\varvec{\Upomega}}$ is the locus of the center of the locally inscribed circle (disk) ${\varvec{\Upphi}}\left( u \right)$ moving along the pocket boundary ${\mathbf{B}}\left( u \right)$ to cover the whole domain, which is represented as ${\mathbf{MA}}: = \left\{ {{\mathbf{O}}^{{{\Upphi}}} :{\mathbf{O}}^{{{\Upphi}}} \in {\varvec{\Upphi}}\left( u \right), \cup {\varvec{\Upphi}}\left( u \right) = {\varvec{\Upomega}}} \right\}$ (see Fig. 2).

Remarks

The LIC varies in size at different locations as it best fits the local area bounded by the pocket boundary at any location. The MA is a “middle” axis bisecting the pocket domain. In this work, the pocket MA is represented with a set of end and branch points connected by bisector curves, which are defined in the following.

Definition 2.4

The definition of end point ${\mathbf{V}}^{\text{E}}$ is that the center of the LIC ${\varvec{\Upphi}}\left( u \right)$ is an end point if and only if it meets one of the three conditions: (1) the component curve ${\mathbf{B}}^{i} \left( u \right)$ that the LIC ${\varvec{\Upphi}}\left( u \right)$ touches is a circular arc, (2) at a concave corner, the radius $r^{{{\Upphi}}}$ of the LIC is zero at ${\mathbf{P}}_{1}$, where the unit normal vector is invalid, and (3) $\forall {\mathbf{P}}_{1} :\in {\varvec{\Upphi}}\left( u \right) \cap {\mathbf{B}}\left( u \right)$ and ${\mathbf{P}}_{1} : = {\mathbf{B}}_{{{\text{P}}_{1} }}^{i}$, its curvature $\kappa_{{{\text{P}}_{1} }}$ is positive and maximal in the local region of ${\mathbf{P}}_{1}$ (see Fig. 3).

Fig. 3

Diagram of end points in three conditions: a for the first and the second conditions, and b for the third condition

Remarks

The three conditions in the definition of end point infer to three special cases of LIC. These special circles are the circle of a component arc, the degenerated circle—a point—at the joint of two component curves forming a sharp concave corner, and the osculating circle of a NURBS component curve at a point having the maximum curvature in its neighborhood.

Definition 2.5

The definition of branch point ${\mathbf{V}}^{\text{B}}$ is that the center of an LIC ${\varvec{\Upphi}}\left( u \right)$ is a branch point if and only if this circle touches the pocket boundary at more than two points (see Fig. 4).

Fig. 4

Diagram of the branch point definition

Remarks

If an LIC contacts the boundary n times $\left( {n > 2} \right)$, the circle center is a branch point where n bisectors are connected (see Fig. 4). Generally, the LIC at a branch point touches the pocket boundary at three discrete points (Fig. 5).

Fig. 5

Diagram of the bisector point definition

Definition 2.6

The definition of bisector point is that the center ${\mathbf{O}}^{{{\Upphi}}}$ of the LIC ${\varvec{\Upphi}}\left( u \right)$ is a bisector point if and only if this circle contacts the pocket boundary ${\mathbf{B}}\left( u \right)$ at two points $\left[ {{\mathbf{P}}_{1} ,{\mathbf{P}}_{2} } \right]$. Thus, the bisector curve ${\mathbf{O}}^{{{\Upphi}}} \left( u \right)$ is a set of bisector points and connects a pair of end-and-branch or branch points.

Definition 2.7

The medial axis transform (MAT) refers to the MA, the radii and centers of the LICs and the contact points between these circles and the boundaries. Thus, the MAT is defined as ${\mathbf{MAT}}: = \left[ {{\varvec{\Upphi}}\left( u \right)\left| { \cup {\varvec{\Upphi}}\left( u \right) = {\varvec{\Upomega}}} \right.} \right]$, and it can be simply represented as $\cup \left[ {\left( {{\mathbf{V}}^{\text{E}} ,{\mathbf{V}}^{\text{B}} } \right),{\mathbf{O}}^{{{\Upphi}}} \left( u \right)} \right]$.

To find the MAT of a pocket, it is crucial to calculate the LIC of a bisector point accurately and efficiently. This work proposes a new mathematical model of the LIC.

3 A mathematical model of LIC

The essential element of the MAT is the LICs, and an innovative mathematical model of LIC is established in the section.

3.1 The maximal tangent circle

At a point of the pocket boundary where various tangent circles ${\varvec{\Uptheta}}$ exist, the LIC ${\varvec{\Upphi}}$ is unique among the circles. These circles ${\varvec{\Uptheta}}$ can be found using the equations rendered in Sect. 2. To facilitate finding the LIC ${\varvec{\Upphi}}$, the maximal tangent circle is defined.

Definition 3.1

For a point ${\mathbf{P}}_{1}$ on a boundary component curve ${\mathbf{B}}^{i} \left( u \right)$ with parameter $u_{{{\text{P}}_{1} }}$, the unit normal at this point is valid and the boundary curve is not a circular arc. The normal vector intersects the opposite boundary ${\mathbf{B}}\left( u \right)$ first at point ${\mathbf{Q}}_{1}$ with parameter $u_{{{\text{Q}}_{1} }}$. Sometimes, the opposite boundary ${\mathbf{B}}\left( u \right)$ could be the curve ${\mathbf{B}}^{i} \left( u \right)$ itself. The tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }} \left( r \right)$ determined with the diameter line ${\mathbf{P}}_{1} {\mathbf{Q}}_{1}$ is defined as the maximal tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } : = {\varvec{\Uptheta}}_{{{\text{P}}_{1} }} \left( {\tfrac{1}{2}\left| {{\mathbf{P}}_{1} {\mathbf{Q}}_{1} } \right|} \right)$ in this work. If the component curve ${\mathbf{B}}^{i} \left( u \right)$ is a circular arc of radius $r^{{{\text{B}}^{i} }}$, the arc circle is the maximal tangent circle, ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } \left( {r^{{{\text{B}}^{i} }} } \right) = {\mathbf{B}}^{i} \left( u \right)$.

Lemma 3.2

At a point ${\mathbf{P}}_{1}$ with parameter $u_{{{\text{P}}_{1} }}$ on a component curve ${\mathbf{B}}^{i} (u)$, its LIC ${\varvec{\Upphi}}_{{{\text{P}}_{1} }} : = {\varvec{\Upphi}}\left( {u_{{{\text{P}}_{1} }} } \right)$ is within or, in some special cases, is its maximal tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} }$ (see Fig. 6).

Fig. 6

Diagram of the maximal tangent circle and its relationship with the LIC

Proof

The proof covers two cases: the first case is that the component curve ${\mathbf{B}}^{i} (u)$ of the pocket boundary ${\mathbf{B}}(u)$ is not a circular arc, while the second case is that curve ${\mathbf{B}}^{i} (u)$ is a circular arc. For the first case, at the point ${\mathbf{P}}_{1}$ on curve ${\mathbf{B}}^{i} (u)$ with parameter $u_{{{\text{P}}_{1} }}$, its unit normal vector ${\mathbf{N}}_{{{\text{P}}_{1} }}^{i}$ and its tangent circles ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }} (r)$ in different size can be found. Suppose the unit normal vector intersects the boundary at point ${\mathbf{Q}}_{1}$, the maximal tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} }$ is determined with diameter ${\mathbf{P}}_{1} {\mathbf{Q}}_{1}$. Assume the boundary traverses the maximal tangent circle once with two intersection points ${\mathbf{Q}}_{1}$ and ${\mathbf{Q}}_{2}$, leaving a boundary segment within the circle and bounded by these points. By continuously reducing radius $r$ of the tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }} (r)$ at the point ${\mathbf{P}}_{1}$ to shrink it, the intersection points ${\mathbf{Q}}_{1} (r)$ and ${\mathbf{Q}}_{2} (r)$ gradually come closer and the boundary segment inside the circle becomes shorter (see Fig. 6). By doing this, it is guaranteed that the radius $r$ can reach a critical value $r^{{{\Upphi}}}$ so that the points ${\mathbf{Q}}_{1} (r)$ and ${\mathbf{Q}}_{2} (r)$ converge to one point ${\mathbf{P}}_{2}$ and the boundary touches the tangent circle. According to Definition 2.2, this circle is the LIC ${\varvec{\Upphi}}_{{{\text{P}}_{1} }}$, $\left( {\left\{ {{\mathbf{O}}^{{{\Upphi}}} \left( {u_{{{\text{P}}_{1} }} } \right),r^{{{\Upphi}}} \left( {u_{{{\text{P}}_{1} }} } \right),{\varvec{\Upphi}}\left( {{\mathbf{O}}^{{{\Upphi}}} ,r^{{{\Upphi}}} } \right),\left[ {{\mathbf{P}}_{1} ,{\mathbf{P}}_{2} } \right]} \right\}} \right)$. Therefore, it is within the maximal tangent circle (see Fig. 6). If the boundary traverses the maximal tangent circle m times, there are m pairs of intersection points, $\left( {{\mathbf{Q}}_{1} ,{\mathbf{Q}}_{2} } \right)$, $\left( {{\mathbf{Q}}_{3} ,{\mathbf{Q}}_{4} } \right)$, …, $\left( {{\mathbf{Q}}_{2m - 1} ,{\mathbf{Q}}_{2m} } \right)$. For each pair of the intersection points, a critical circle of radius $r^{j} , \, j = 1,2, \ldots ,m$ can be found. Among them, if only one circle is the minimal, it is the LIC and within the maximal tangent circle. The center of this circle is a bisector point of the MA. In some special cases, several circles are the same and in the minimal size; thus, this minimal circle is the LIC whose center is a branch point of the MA. Occasionally, if the maximal tangent circle contacts the boundary right at the point ${\mathbf{Q}}_{1}$ without any boundary crossing, this maximal circle itself is an LIC. The center of this circle is a bisector point of the MA.

For the second case that the component curve is a circular arc, the maximal tangent circle of a point on this curve is the arc circle. Similarly, if the boundary traverses this circle, an LIC can be found by reducing the radius of the tangent circle. It is evident that the LIC is within the maximal tangent circle (see Fig. 6). Otherwise, the maximal tangent circle is the LIC, whose center is an end point of the MA. $\square$

Remarks

The maximal tangent circle can facilitate finding the LIC. By checking the boundary segments inside the maximal tangent circle, the LIC can be efficiently found, instead of exhaustively searching the whole boundary.

3.2 Optimization model of calculating a bisector point

A mathematical model of LIC is very important for the accuracy and efficiency of computing the MA of a pocket. In general, a MA consists of a set of end and branch points and a group of bisector curves, and each curve connects a pair of end and branch points or two branch points. Since closed-form equations of the bisector curves cannot be derived, discrete bisector points should be computed to represent the bisector curves. Thus, a new and accurate model of calculating a bisector point is proposed in this section, in which an innovative idea of formulating the LIC at a boundary point is to shrink the maximal tangent circle until the tangent circle touches the boundary.

To formulate this model, assuming a point ${\mathbf{P}}_{1}$ of parameter $u_{{{\text{P}}_{ 1} }}$on the component curve ${\mathbf{B}}^{i} (u)$ of the boundary ${\mathbf{B}}(u)$, the position vector is ${\mathbf{P}}_{1} = \left[ {Bx^{i} \left( {u_{{{\text{P}}_{ 1} }} } \right),By^{i} \left( {u_{{{\text{P}}_{ 1} }} } \right)} \right]^{\text{T}}$, and the unit normal vector ${\mathbf{N}}_{{{\text{P}}_{ 1} }}^{i} = \left[ {Nx^{i} \left( {u_{{{\text{P}}_{ 1} }} } \right),Ny^{i} \left( {u_{{{\text{P}}_{ 1} }} } \right)} \right]^{\text{T}}$ can be found using the equations in Sect. 2. The first intersection point ${\mathbf{Q}}_{1}$ between the unit normal and the boundary ${\mathbf{B}}(u)$ can be easily calculated; its parameter is $u_{{{\text{Q}}_{ 1} }}$ and the position vector is ${\mathbf{Q}}_{1} = \left[ {Bx\left( {u_{{{\text{Q}}_{ 1} }} } \right),By\left( {u_{{{\text{Q}}_{ 1} }} } \right)} \right]^{\text{T}}$. Therefore, the diameter of the maximal tangent circle is ${\mathbf{P}}_{1} {\mathbf{Q}}_{1}$, and the center is ${\mathbf{O}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } }} = \tfrac{1}{2}\left( {{\mathbf{P}}_{1} + {\mathbf{Q}}_{1} } \right)$. The maximal tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } \left( {\tfrac{1}{2}\left| {{\mathbf{P}}_{1} {\mathbf{Q}}_{1} } \right|} \right)$ is found (see Fig. 7). For a bisector point, the simple, general situation is that the boundary traverses the maximal tangent circle once with a segment inside the circle. Based on Lemma 3.2, the LIC is within the maximal tangent circle.

Fig. 7

Diagram of formulating the mathematical model of calculating a bisector point

To attain a smaller tangent circle at point ${\mathbf{P}}_{1}$, select a test point ${\mathbf{P}}$ with parameter $u$ on the boundary segment inside the maximal tangent circle; ${\mathbf{P}} = \left[ {Bx(u),\,By(u)} \right]^{\text{T}}$ and $\left| {{\mathbf{PO}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } }} } \right| < \tfrac{1}{2}\left| {{\mathbf{P}}_{1} {\mathbf{Q}}_{1} } \right|$. Here, the test point ${\mathbf{P}}$ cannot be the point ${\mathbf{P}}_{1}$, so $u \ne u_{{{\text{P}}_{ 1} }}$. A tangent circle of point ${\mathbf{P}}_{1}$ and passing though point ${\mathbf{P}}$ can be constructed after finding its center in two steps: (1) connecting the two points with ${\mathbf{PP}}_{1}$, and (2) drawing the mid-section line of ${\mathbf{PP}}_{1}$ and intersecting ${\mathbf{P}}_{1} {\mathbf{Q}}_{1}$ at point ${\mathbf{O}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }} }}$. Thus, the center of the tangent circle ${\varvec{\Uptheta}}_{{{\text{P}}_{ 1} }} \left( {r(u)} \right)$ is ${\mathbf{O}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }} }}$, and the circle radius $r(u)$ can be calculated as

$$ r(u) = \frac{1}{2} \cdot \frac{{\left[ {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right]^{2} + \left[ {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right]^{2} }}{{\left[ {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot Nx^{i} \left( {u_{{{\text{P}}_{1} }} } \right) + \left[ {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot Ny^{i} \left( {u_{{{\text{P}}_{1} }} } \right)}}. $$

(17)

By changing the point ${\mathbf{P}}$ along the boundary segment inside the maximal tangent circle, the radius of the tangent circle can gradually be reduced. Ultimately, when point ${\mathbf{P}}$ reaches a special point ${\mathbf{P}}_{2}$, the radius is the minimum, and, besides point ${\mathbf{P}}_{1}$, the tangent circle only contacts the boundary at this point. Therefore, this tangent circle is the LIC ${\varvec{\Upphi}}_{{{\text{P}}_{1} }}$ of point ${\mathbf{P}}_{1}$. The optimization model of the LIC is

$$ \begin{gathered} \begin{array}{*{20}c} {\text{Minimize}} & {r(u) = \frac{1}{2} \cdot \frac{{\left( {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right)^{2} + \left( {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right)^{2} }}{{\left( {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right) \cdot Nx^{i} \left( {u_{{{\text{P}}_{1} }} } \right) + \left( {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right) \cdot Ny^{i} \left( {u_{{{\text{P}}_{1} }} } \right)}}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\text{Subject to}} & {\left\{ \begin{gathered} u \ne u_{{{\text{P}}_{1} }} \hfill \\ \left| {{\mathbf{PO}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } }} } \right| < \tfrac{1}{2}\left| {{\mathbf{P}}_{1} {\mathbf{Q}}_{1} } \right| \hfill \\ \end{gathered} \right.} \\ \end{array} . \hfill \\ \end{gathered} $$

(18)

However, in many cases, the boundary traverses the maximal tangent circle several times and leaves several segments inside the circle (see Fig. 8). According to Lemma 3.2, the LIC is within the maximal tangent circle and touches one of the boundary segments, without the boundary traversing inside the circle. As the test point ${\mathbf{P}}$ moves along the boundary segments, the radius of the tangent circle changes in a highly non-linear way. It is clear that in this case the LIC model is a difficult global optimization problem. To solve this problem efficiently and consistently, the hybrid global optimization method is developed and introduced in the next section.

Fig. 8

Diagram of the discrete particle swarm optimization method in this work

4 The hybrid global optimization method

For the LIC at a boundary point ${\mathbf{P}}_{1}$, solving the above optimization problem actually is to search the boundary for point ${\mathbf{P}}_{2}$ that the circle contacts the boundary. However, due to the complex pocket shape, finding point ${\mathbf{P}}_{2}$ can take a long time and result in non-consistent solutions by using either a prior global or a local optimization method. With regard to the current global optimization methods, their salient feature is that they can intelligently and efficiently search for the region of the exact solution; however, it often takes intolerably long time to pin-point the solution. As comparison, the local optimization methods are not able to globally search the solution; while, if the solution region is initially provided, they can converge at the solution in very short time. To take the advantages of the global and local optimization methods, this work develops an effective hybrid optimization method that integrates a global and a local optimization method. In the first step, the discrete particle swarm optimization (PSO) method is employed to narrow down the solution region from the whole boundary; and in the second step, Newton’s gradient method is applied to locate the exact solution.

4.1 The discrete particle swarm optimization method

The problem of locating point ${\mathbf{P}}_{2}$ on the boundary for the LIC at point ${\mathbf{P}}_{1}$ actually is to search for ${\mathbf{P}}_{2}$ in the 1-D continuous range of the boundary parameter. As an outstanding feature, the population-based intelligent search of the present PSO method is to have a swarm of particles scattering across the problem domain, searching and sharing the objective function values in an iterative process, in order to efficiently find out the global solution [23, 24]. Thus, the PSO method is an effective tool to solve the problem. To push the limit of searching efficiency in this work, an improvement is to represent the whole continuous domain with a fairly large number of discrete points and modify the current PSO method to search among these points for the finite boundary piece around point ${\mathbf{P}}_{2}$.

To find out the finite boundary piece where point ${\mathbf{P}}_{2}$ lies, a large number of sample points (the number is $N_{\text{S}}$) are taken on the pocket boundary ${\mathbf{B}}(u), \, u \in \left[ {u_{\hbox{min} } ,u_{\hbox{max} } } \right]$. For example, the points are evenly distributed along the boundary with the same parameter interval $\Updelta u = {{\left( {u_{\hbox{max} } - u_{\hbox{min} } } \right)} \mathord{\left/ {\vphantom {{\left( {u_{\hbox{max} } - u_{\hbox{min} } } \right)} {\left( {N_{\text{S}} - 1} \right)}}} \right. \kern-0pt} {\left( {N_{\text{S}} - 1} \right)}}$, and the point parameters are $\left[ {u_{1} ,u_{2} , \ldots ,u_{j} , \ldots u_{{N_{\text{S}} }} } \right]$ where $u_{j} = u_{\hbox{min} } + \left( {j - 1} \right) \cdot \Updelta u$. In this work, the points are sampled on the boundary with approximately the same arc length between two adjacent points. The points are denoted as ${\mathbf{B}}_{j} : = {\mathbf{B}}\left( {u_{j} } \right)$ where $j = 1,2, \ldots ,N_{\text{S}}$. The finite boundary piece around point ${\mathbf{B}}_{j}$ is denoted as ${\mathbf{B}}_{j}$. In this problem, due to the constraint that only the boundary points within the maximal tangent circle are the candidates of the solution in this step, all the points ${\mathbf{B}}_{j}$ are checked against the in-equation, $\left| {{\mathbf{B}}_{j} {\mathbf{O}}^{{{{\Uptheta}}_{{{\text{P}}_{1} }}^{\hbox{max} } }} } \right| < \tfrac{1}{2}\left| {{\mathbf{P}}_{1} {\mathbf{Q}}_{1} } \right|$. Then, the boundary points inside the maximal tangent circle define the problem sub-domains ${\mathbb{R}}_{1} = \left[ {u_{{{\mathbb{R}}_{1} }}^{s} , \ldots ,u_{{{\mathbb{R}}_{1} }}^{e} } \right], \ldots ,{\mathbb{R}}_{l} = \left[ {u_{{{\mathbb{R}}_{l} }}^{s} , \ldots ,u_{{{\mathbb{R}}_{l} }}^{e} } \right], \ldots ,{\mathbb{R}}_{{N_{\text{D}} }} = \left[ {u_{{{\mathbb{R}}_{{N_{\text{D}} }} }}^{s} , \ldots ,u_{{{\mathbb{R}}_{{N_{\text{D}} }} }}^{e} } \right]$, for example, $\left[ {u_{1} ,\underbrace {{u_{2} ,u_{3} ,u_{4} }}_{{{\mathbb{R}}_{1} }}, \ldots ,\underbrace {{u_{j - 1} ,u_{j} ,u_{j + 1} , \ldots }}_{{{\mathbb{R}}_{l} }}, \ldots ,\underbrace {{ \ldots ,u_{{N_{\text{S}} - 1}} ,u_{{N_{\text{S}} }} }}_{{{\mathbb{R}}_{{N_{\text{D}} }} }}} \right]$. In order to quickly find the piece of the solution point ${\mathbf{P}}_{2}$, a discrete particle swarm optimization (PSO) method is developed in this work (see Fig. 8).

Here, the discrete PSO method is introduced. Given the boundary ${\mathbf{B}}(u)$ in non-continuous sub-domains as ${\mathbb{R}}_{1} , \ldots ,{\mathbb{R}}_{l} , \ldots {\mathbb{R}}_{{N_{\text{D}} }}$, and many discrete points ${\mathbf{B}}_{j}$ in the sub-domain are calculated (see Fig. 8). At beginning of the search, a swarm of particles with a number of $N_{\text{P}}$ is randomly selected among the discrete points in the domains. The particles are denoted as ${\mathbf{B}}_{s\left( k \right)}$ and their parameters are denoted as $u_{s\left( k \right)}$ where $k = 1,2, \ldots ,N_{\text{P}}$ refers to the particles and $s\left( k \right)$ refers to the sequence number of the sample points. The initial velocity $v_{k}$ of each particle is also determined with a random number. In the searching iteration, the velocity of each particle $v_{k}$ and a parameter value for this particle $u$ are computed using the equation below,

$$ \left\{ \begin{gathered} v_{k} = w \cdot v_{k} + c_{1} \cdot rand \cdot \left( {u_{k}^{ * } - u_{s(k)} } \right) + c_{2} \cdot rand \cdot \left( {u^{ * } - u_{s(k)} } \right) \hfill \\ u = u_{s(k)} + v_{k} \hfill \\ \end{gathered} \right., $$

(19)

where the inertia weight $w$ is 0.9, the acceleration coefficients $c_{1}$ and $c_{2}$ are 0.2 and 2.0, respectively, and $r\,and$ is the uniform distribution function that can generate random numbers between 0 and 1. If the in-equation

$$ u \in {\mathbb{R}}_{l} \quad {\text{and}}\quad\frac{{u_{j - 1} + u_{j} }}{2} < u \le \frac{{u_{j} + u_{j + 1} }}{2} $$

(20)

is true, $s(k) = j$ and $u_{s(k)} = u_{j}$. If the in-equation

$$ u_{s(k)} \in {\mathbb{R}}_{l} \quad{\text{and}}\quad u_{{{\mathbb{R}}_{l} }}^{e} \le u \le u_{{{\mathbb{R}}_{l + 1} }}^{s} $$

(21)

is true, $s(k)$ is the sequence number of the point with parameter $u_{{{\mathbb{R}}_{l + 1} }}^{s}$, and $u_{s(k)} = u_{{{\mathbb{R}}_{l + 1} }}^{s}$. If the in-equation

$$ u_{s(k)} \in {\mathbb{R}}_{l} \quad{\text{and}}\quad u_{{{\mathbb{R}}_{l - 1} }}^{e} \le u \le u_{{{\mathbb{R}}_{l} }}^{s} $$

(22)

is true, $s(k)$ is the sequence number of the sample point with parameter $u_{{{\mathbb{R}}_{l - 1} }}^{e}$, and $u_{s\left( k \right)} = u_{{{\mathbb{R}}_{l - 1} }}^{e}$. Then, by using Eq. 18, the radii $r\left( {u_{s\left( k \right)} } \right)$ of the tangent circles for all the particles are calculated. For each particle, if the radius is less than $r\left( {u_{k}^{ * } } \right)$ in the previous iteration, the best parameter value of the particle $u_{k}^{ * } = u_{s(k)}$. If the radius is less than $r\left( {u^{ * } } \right)$, the best parameter value of the swarm $u^{ * } = u_{s(k)}$, where $k = 1,2, \ldots ,N_{\text{P}}$. After many iterations, the particles will converge to point ${\mathbf{B}}_{j}$ with parameter $u_{j}$ in the sub-domains.

Since the boundary domain is divided into several sub-domains with discrete sample points based on the constraint, the search range of the particles has been significantly reduced, thus, it is very quick to find out the solution point ${\mathbf{P}}_{2}$. The finite boundary piece of this point is the piece where the exact solution lies, and this point is the input for searching with Newton’s gradient method.

4.2 Accurate Newton’s optimization method

By using the discrete PSO method, the finite boundary piece of the exact solution can be found. Because the piece is very short, the objective function in the region of this piece is in a uniform concave shape, and the Newton’s gradient method can guarantee converge to the solution. The first derivative of the objective function in terms of the parameter $u$ is

$$ \begin{gathered} r^{\prime}(u) = \frac{{\left[ {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot Bx(u)^{\prime } + \left[ {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot By(u)^{\prime } }}{{\left[ {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot Nx^{i} \left( {u_{{{\text{P}}_{1} }} } \right) + \left[ {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right] \cdot Ny^{i} \left( {u_{{{\text{P}}_{1} }} } \right)}} - \hfill \\ \, \frac{{\left[ {\left( {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right)^{2} + \left( {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right)^{2} } \right] \cdot \left[ {Nx^{i} \left( {u_{{{\text{P}}_{1} }} } \right) \cdot Bx(u)^{\prime } + Ny^{i} \left( {u_{{{\text{P}}_{1} }} } \right) \cdot By(u)^{\prime } } \right]}}{{2 \cdot \left[ {\left( {Bx(u) - Bx^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right) \cdot Nx^{i} \left( {u_{{{\text{P}}_{1} }} } \right) + \left( {By(u) - By^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right) \cdot Ny^{i} \left( {u_{{{\text{P}}_{1} }} } \right)} \right]^{2} }} \hfill \\ \end{gathered} $$

(23)

With the closed-form equation of the first derivative of the objective function, the linear search method is applied, and the solution can be found in several steps.

To show the super efficiency of this new optimization solver, the NURBS boundary curve shown in Fig. 8 is employed as an example, and our method and a related program of commercial geometric kernel software [25] are applied to this example to find the LICs at 1,000 locations on the boundary. The commercial program takes 4,286 ms to compute all the LICs. In our optimization method, 2,000 sample points are taken from the boundary. It takes 1,919 ms to compute 1,000 LICs at the same locations. Although we do not know the algorithm used in the commercial program, the testing result shows that the hybrid optimization method is more efficient than this program.

This newly proposed hybrid global optimization method uses the discrete PSO method to globally search for the local region of the solution in the large problem domain, and feed the search result to the Newton’s local optimization method for the exact solution. This method takes the advantages of the global and local optimization methods and gets rid of their weakness. It is very efficient to solve highly non-linear optimization problems, including the problem in this work.

5 Medial axis approximation

By using this new approach, a bisector point of an LIC at a boundary point can be accurately found; which is the main contribution of this work. Now, to generate the MA with high accuracy, a practical method is proposed, which includes (1) a large number of bisector points are computed and are fit with a curve to approximate the MA, and (2) a number of different bisector points are calculated and are compared to the MA approximation for the MA errors; if an error is larger than the tolerance, these bisector points, together with the previous bisector points, are used to re-generate the MA approximation. This is a numerical way to globally bind the error of the MA approximation. Since the MA equations cannot be established, this problem is very difficult to address, and further study is needed.

6 Applications

This new approach has been implemented into our in-house software by using the C++ programming language. A Windows PC with an AMD Athlon 2.7 GHz CPU is used. To demonstrate that it is more efficient and accurate than the prior MA methods, this new approach is applied to a thin, long pocket with a closed free-form boundary shown in Fig. 9. Among the current MA methods, the most popular MA method, the Voronoi diagram generation method, is selected to find the MA of the pocket. The results by using the two methods are explained in detail and are compared to confirm the advantage of our approach.

Fig. 9

a A group of accurate bisector points calculated with this new approach and an approximated bisector curve fitting these points, and b the error between the approximate bisector curve and the true bisector curve

By using the new approach to finding the bisector of the pocket, 40 points are sampled on the pocket boundary, and 40 bisector points are accurately calculated, at which the location errors are less than 1.0e−7. Then, a curve is fit to the bisector points to represent the bisector curve of the pocket shown in Fig. 9a. So, the location error of the bisector curve with regard to every boundary points, instead of at the 40 sample points, can be calculated. The error graph is plotted in Fig. 9b, and the maximum error is 5.84e−3 mm. Since the location errors at the 40 discrete bisector points are much less than the maximum error, the new approach to calculating bisector points is accurate, and the bisector curve error mainly is the bisector fitting error. Therefore, when more boundary points are sampled, more bisector points are attained, and the bisector curve is more accurate.

Here, a group of tests has been conducted by using this new approach. In each test, by sampling a different number of points on the boundary, their corresponding bisector points are computed, and the bisector curve is found. Then, the maximum error of the bisector curve is calculated. The results are listed in Table 1. When 390 points are sampled, the 390 bisector points are very accurate, thus, the bisector curve accuracy (8.11e−7 mm) is quite high and the computing time (359 ms) is very quick.

Table 1 Results of a group of tests by using this new approach

In this work, the Voronoi diagram generation method is employed to find the MA of the pocket. First, 82 points are sampled on the pocket boundary to form a polygon as its new discrete representation, and the Voronoi diagram is then found with 136 Voronoi points. In Fig. 10, the pocket boundary points and the corresponding Voronoi diagram points are plotted. Among all the Voronoi points, 80 bisector points inside the pocket can be found and shown in this diagram.

Fig. 10

The Voronoi diagram of the polygon approximating the pocket boundary

However, the 80 computed Voronoi points, which are used to approximate 80 bisector points, deviate from their corresponding true “middle” points (true medial axis points), so the distance between a computed Voronoi point and its corresponding true medial axis point is defined as a Voronoi location error. To show this problem with the Voronoi diagram, four Voronoi points and their errors are closely examined as shown in Fig. 11. At Voronoi point ${\mathbf{O}}_{1}^{{{\Upphi}}}$, the distances from this point to the boundary curves are not equal, and no circle centered at this point can be drawn to contact the boundary at two points. In Fig. 11, the location error is 0.176617 mm. Similarly, Voronoi points ${\mathbf{O}}_{2}^{{{\Upphi}}}$, ${\mathbf{O}}_{3}^{{{\Upphi}}}$ and ${\mathbf{O}}_{4}^{{{\Upphi}}}$ are off their true medial axis points, and their errors are 0.18392, 0.230038, and 0.183921 mm, and shown in Fig. 11, respectively. As a consequence, the location errors of the Voronoi points in terms of the true bisector points are large, and the maximum error of the bisector curve fitting these Voronoi points are large. Unfortunately, these bisector curves cannot be used for high precision tool path planning.

Fig. 11

The bisector point errors by using the Voronoi diagram and their detailed illustrations

To fully represent the bisector curve, a group of discrete Voronoi points are computed to approximate bisector points, and then a B-spline curve is fit to these points as the result. Thus, the bisector error is defined as the maximum deviation between the calculated and the true bisector curves. Eight tests with a different number of bisector points, which are extracted from the Voronoi points, are carried out; unfortunately, the bisector errors are quite large, which are listed in Table 2. For example, when the number of the bisector points is 41, the bisector error is 0.922 mm, while the error of the bisector curve that is fit to 40 bisector points found with our approach is 0.00584 mm. It is evident that the error of the bisector calculated with the Voronoi method is much greater than that of the bisector found with our approach. Since the curve fitting method is the same, the main reason for the large errors of the bisector points generated with the Voronoi method is that the Voronoi points are not accurate and the bisector points computed with our method are accurate, with regard to the true bisector points. It is easy to see that the computing time by using our new approach is much less that the time needed by using a MATLAB program of the Voronoi diagram method.

Table 2 Results of a group of tests by using the Voronoi diagram generation method

By using our in-house software, the MATs of three pockets with very complex shape are calculated and shown in Fig. 12, and the results are listed in Table 3. The above examples demonstrate the robustness and effectiveness of the proposed algorithms when dealing with complex shapes.

Fig. 12

The MAs of a group of testing examples with closed free-form pocket boundaries

Table 3 Data of finding the MAs of the three pockets by using our in-house software

7 Conclusions

In this work, an efficient, accurate approach to medial axis transforms of pockets with closed free-form boundary has been proposed. Compared to the prior medial axis generation methods, this new approach is able to handle pocket domains bounded with lines, circular arcs, and B-spline curves. It does not need to identify and eliminate curve/curve intersections, thus, it takes less time to compute MATs, compared to the analytical MA methods. It uses accurate boundary curves information to achieve much higher accuracy, compared to the Voronoi diagram approximation methods. The main contributions of this work include (1) an innovative optimization model of bisector points, which is able to accurately calculate any bisector point, and (2) a new global optimization method, a hybrid optimization method of the particle swarm optimization and the gradient optimization methods, which is able to efficiently pin-point any bisector point. This approach substantially improves the technique of computing the medial axis transforms of pockets. It can be directly used to multiple cutters selection and their path generation for aggressive rough machining of pockets.