next up previous contents index
Next: 11.2.4 Approximations Up: 11.2 Planar offset curves Previous: 11.2.2 Classification of singularities   Contents   Index

11.2.3 Computation of singularities

Using (2.25) with $ {\bf e}_z=(0,0,1)^T$ , $ \dot{\bf r}(t) = (\dot{x}(t), \dot{y}(t))^T$ and $ \ddot{\bf r}(t) = (\ddot{x}(t), \ddot{y}(t))^T$ , (11.9) for finding the locations of isolated points and cusps of planar offset curve reduces to [254]
$\displaystyle d\left[\ddot{x}(t)\dot{y}(t) - \dot{x}(t)\ddot{y}(t)\right] - \sqrt{\dot{x}^2(t) + \dot{y}^2(t)}\left[\dot{x}^2(t) + \dot{y}^2(t)\right] = 0\;.$     (11.11)

Consequently, if $ {\bf r}(t)$ is a polynomial curve, locations of irregular points can be obtained by solving the above univariate irrational function involving polynomials and square roots of polynomials, which can be transformed into two equations with two unknowns using the auxiliary variable method introduced in Sect. 4.5. The additional equation and variable result from replacing the square root involved in (11.11) leading to:
$\displaystyle d\left[\ddot{x}(t)\dot{y}(t) - \dot{x}(t)\ddot{y}(t)\right] -\varrho^3 =0\;,$     (11.12)
$\displaystyle \varrho^2 - \left[\dot{x}^2(t) + \dot{y}^2(t)\right] = 0\;.$     (11.13)

By substituting the expression for the normal vector for the planar parametric curve (2.24) (see Fig. 3.7 (b) and Table 3.2) into (11.10) yields the following system for locating the self-intersections of the offset of the planar curve:

$\displaystyle x(\sigma) + \frac{\dot{y}(\sigma)d}{\sqrt{\dot{x}^2(\sigma) + \do... ...^2(\sigma)}} = x(t) + \frac{\dot{y}(t)d}{\sqrt{\dot{x}^2(t) + \dot{y}^2(t)}}\;,$      
$\displaystyle y(\sigma) - \frac{\dot{x}(\sigma)d}{\sqrt{\dot{x}^2(\sigma) + \do... ...^2(\sigma)}} = y(t) - \frac{\dot{x}(t)d}{\sqrt{\dot{x}^2(t) + \dot{y}^2(t)}}\;.$     (11.14)

If $ {\bf r}(t)$ is a polynomial curve, (11.14) are two simultaneous bivariate irrational functions involving polynomials and square root of polynomials. Using the auxiliary variable method, system (11.14) can be transformed into four polynomial equations with four unknowns $ \sigma$ , $ t$ , $ \omega$ , $ \varrho$ as follows [254]:
$\displaystyle \omega\varrho\left[x(\sigma) -x(t)\right] + d\left[\varrho\dot{y}(\sigma) - \omega\dot{y}(t)\right] = 0\;,$      
$\displaystyle \omega\varrho\left[y(\sigma) -y(t)\right] + d\left[-\varrho\dot{x}(\sigma) + \omega\dot{x}(t)\right] = 0\;,$      
$\displaystyle \omega^2 -\left[\dot{x}^2(\sigma) + \dot{y}^2(\sigma)\right] = 0\;,$      
$\displaystyle \varrho^2 - \left[\dot{x}^2(t) + \dot{y}^2(t)\right] = 0\;.$     (11.15)

The trivial solution $ \sigma=t$ can be avoided by factoring out $ \sigma-t$ from the above equations. It is apparent that the two additional equations obtained through the auxiliary variables do not contain the factor $ \sigma-t$ . However, the original two equations, where the square roots of polynomials have been replaced by the auxiliary variables, possess the factor $ \sigma-t$ as can been seen after some algebraic manipulations [254]. Once the division operations are completed, we obtain a system of four polynomial equations with four unknowns without the trivial solution $ \sigma=t$ .

Similarly to (11.14), intersections of the normal offsets at distance $ d$ of two distinct planar curves $ {\bf r}^A(\sigma)$ and $ {\bf r}^B(t)$ can be computed by solving the following system:

$\displaystyle x^A(\sigma) + \frac{\dot{y}^A(\sigma)d}{\sqrt{(\dot{x}^{A})^2(\si... ...^B(t) + \frac{\dot{y}^B(t)d}{\sqrt{(\dot{x}^{B})^2(t) + (\dot{y}^{B})^2(t)}}\;,$      
$\displaystyle y^A(\sigma) - \frac{\dot{x}^A(\sigma)d}{\sqrt{(\dot{x}^{A})^2(\si... ...^B(t) - \frac{\dot{x}^B(t)d}{\sqrt{(\dot{x}^{B})^2(t) + (\dot{y}^{B})^2(t)}}\;.$     (11.16)

Note that for (11.14) we need to find a method to eliminate the trivial solution $ \sigma=t$ , while for (11.16) $ \sigma=t$ can be a solution. When the input curve is a B-spline curve, we can always split it into Bézier (polynomial) segments by a knot insertion algorithm [34,63]. In such cases not only the self-intersection in the offset of each split polynomial segment but also the intersections among the offsets of different split segments must be checked.

A system of nonlinear polynomial equations can be robustly and efficiently solved by the subdivision-based Interval Projected Polyhedron algorithm [254,179], which was introduced in Chap. 4. A remarkable feature of this algorithm when applied to the system (11.15) is that both local and global self-intersections can be found by the same algorithm without any initial approximations (see Figs. 11.10, 11.11, 11.12).

Figure 11.11: Global self-intersections of offsets: (a) degree six Bézier curve and its offset with $ d = -0.05$ , (b) offset curve self-intersects forming a tacnode with $ d \simeq -0.03141$ (adapted from [254])
\begin{figure}\centerline{\psfig{figure=fig/off_bot1.ps,height=3.5in}}\end{figure}

Figure 11.12: (a) Trimmed offset of degree six Bézier curve with $ d = -0.05$ , (b) tool path along the trimmed offset (adapted from [254])
\begin{figure}\vspace*{10mm} \centerline{\psfig{figure=fig/off_bot2.ps,height=3.5in}}\end{figure}

next up previous contents index
Next: 11.2.4 Approximations Up: 11.2 Planar offset curves Previous: 11.2.2 Classification of singularities   Contents   Index
December 2009