next up previous contents index
Next: 11.3 Offset surfaces Up: 11.2 Planar offset curves Previous: 11.2.3 Computation of singularities   Contents   Index


11.2.4 Approximations

In general, an offset curve is functionally more complex than its progenitor curve because of the square root involved in the expression of the unit normal vector. If the progenitor is a NURBS curve, then its offset is usually not a NURBS curve, except for some special cases such as straight lines and circles etc. Lü [238] has shown that the offset of a parabola is a rational curve. However, this result has not been generalized to higher order curves. Farouki and Neff [101] have shown that the two-sided offsets of planar rational polynomial curves are high-degree implicit algebraic curves of potentially complex shape. These equations cannot typically be separated into two equations describing positive and negative offsets individually. The degree of this implicit offset curve is $ n_o = 4n-2-2m$ , where $ n$ is the degree of polynomial generator curve $ {\bf r}=(x(t),y(t))^T$ and $ m$ is the degree of $ \phi(t) = GCD(\dot{x}(t), \dot{y}(t))$ where $ GCD$ denotes the greatest common divisor. For example the degree of the two-sided offset curve of a parabola $ {\bf r}(t)=(t,t^2)^T$ is 6 and of a general polynomial cubic curve is 10 with $ \phi(t)$ a constant.

Because of the wide application of offset curves and the difficulty in directly incorporating such entities in geometric modeling systems, due to their potential analytic and algebraic complexity, a number of researchers have developed approximation algorithms for these types of geometries in terms of piecewise polynomial or rational polynomial functions. A literature survey on approximation of planar offset curves is compiled in [313,250]. A paper by Elber et al. [88] presented qualitative as well as quantitative comparisons for several plane offset curve approximation methods, namely the control polygon-based methods by Cobb [62], Tiller and Hanson [421], Coquillart [65], and Elber and Cohen [86], the interpolation methods by Klass [203], and Pham [312], the least square methods by Hoschek [174], the nonlinear optimization technique by Hoschek and Wissel [176], and the circle approximation method by Lee et al. [230]. They counted the number of control points of the approximated offset as a measure for efficiency, while the approximation error was within a prescribed tolerance. They found in general that the least square methods perform very well. However, when the progenitor curve is quadratic they showed that the simple method due to Tiller and Hanson [421], which translates each edge of the control polygon into the edge normal direction by an offset distance, outperforms the other methods. Therefore as an example we summarize the algorithm by Tiller and Hanson [421] with an illustration in Fig. 11.13:

  1. Let $ C$ be a rational B-spline progenitor curve with control vertices $ {\bf p}_{(1)}$ in homogeneous representation and knot vector $ {\bf T}_{(1)}$ . Set $ i=1$ .
  2. Offset each leg of the control polygon by $ d$ .
  3. Intersect consecutive legs of polygon to find new vertices $ \hat{\bf p}_{(i)}$ . Then the approximated offset $ \hat C$ is defined by $ \hat{\bf p}_{(i)}$ and $ {\bf T}_{(i)}$ .
  4. Check deviation of the approximate offset from the true offset.
  5. If the deviation is larger than the given tolerance subdivide $ {\bf p}_{(i)}$ and $ {\bf T}_{(i)}$ to obtain $ {\bf p}_{(i+1)}$ and $ {\bf T}_{(i+1)}$ . Then set $ i \leftarrow i+1$ and go back to step 2. Stop if the deviation is smaller than the given tolerance.

Figure 11.13: Offset curve approximation
\begin{figure}\centerline{ \psfig{file=fig/off_appr_curve.eps,height=1.5in}}\end{figure}

Sederberg and Buehler [375] approximate an offset of a Bézier curve using Hermite interpolation of any even degree not less than the degree of the initial Bézier curve. The representation of the offset is a special interval Bézier curve of even degree with only the middle control point as a rectangular interval. The size of the rectangular interval indicates the tightness of the approximation.

Most of the existing offset approximation schemes generate the approximate offset curve in terms of Bézier /B-spline format in an iterative manner based on a subdivision technique to improve the accuracy of the offset curve. If local and global self-intersections exist, they must be eliminated after the approximation. Elber and Cohen [85] identify the local loops by using the fact that a pair of cusps always exist within the local self-intersection loop of the offset curve. The tangent vector of the offset $ \hat{\bf t}(t)$ flips its direction at the cusps, and thus $ \omega(t) = {\bf t}(t)\cdot\hat{\bf t}(t)$ , where $ {\bf t}(t)$ is the tangent vector of the input curve, becomes negative at the regions bounded by the cusps. Consequently, the local loops can be identified by finding the zero set of $ \omega (t)$ . Once a local loop is identified the curve is split into three parts, the region before the first cusp, the region between the cusps and the region after the second cusp. The offset of the curve before the first cusp and the offset of the curve after the second cusp are intersected to find the self-intersection point. The region bounded by the parameters corresponding to the self-intersection point are trimmed off.

Lee et al. [230] eliminate the local and global self-intersections by approximating the input curve by discrete points and the connecting polygon. Then the offset curve is generated by offsetting these discrete points. The local redundant polygon edges can be detected by checking the dot product between the line segment and its corresponding offset line segment. If the dot product is negative, the offset segment is eliminated. The global self-intersections are detected by a plane sweep algorithm among the offset line segments. Once a valid boundary topology on the offset polygon is computed, the valid parameter intervals of the input curve are extracted. The intersection points of polygonal approximations may not provide accurate parameter values for the intersection points of the offset curve and hence they need to be refined using, for example Newton's method.

The method introduced by Kimmel and Bruckstein [201] generates offsets via wavefront propagation methods in fluid dynamics. The algorithm works on a square grid with a resolution chosen according to the desired accuracy. Finally the contour lines (offsets) are generated based on grid values. Gurbuz and Zeid [138] employ a different approach to avoid self-intersections. Instead of offsetting analytically, the offsetting process is carried out by filling the closed balls of radius $ d$ for each point on the object. The union of the closed balls is subtracted from the object to construct the offset. An offset of a point in space is considered as a sphere. They simplified the implementation by assuming that the shape of a point is a cube and its offset is also a cube. First the object to be offset and its enclosing space are divided into small cubic cells. Therefore the accuracy is governed by the size of the cell. The cells that are on the object are referred to as boundary cells. The boundary cells separate the original set of cells into two subspaces, in and out of the object. Offset operation is carried out for each boundary cell. Chiang et al. [55] also compute offsets without self-intersections using a technique developed in image processing. First the domain is discretized into a two-dimensional grid and the progenitor curve is assigned to the nearest grid point. For each grid point, the distance to the discretized curve is evaluated. By extracting the grid points whose distances are equal to the offset distance, an offset without self-intersection can be constructed. This approach also obviously involves a trade-off between accuracy achieved and memory required.

next up previous contents index
Next: 11.3 Offset surfaces Up: 11.2 Planar offset curves Previous: 11.2.3 Computation of singularities   Contents   Index
December 2009