5.9 Overlapping of curves and surfaces

So far we have focused mainly on transversal intersection problems of regular curves and surfaces. However, in real engineering problems we may encounter curve/curve (see Fig. 5.28), curve/surface or surface/surface overlapping of curves and surfaces.

We will illustrate the curve/curve overlapping case using two planar cubic Bézier curves ( ) and ( ) whose control points are given by (0,0), (0.8,0.8), (1.6,0.32), (2.4,0.608) and (0.6,0.392), (1.4,0.68), (2.2,0.2), (3,1) (see Fig. 5.28). If we use the IPP algorithm to compute the intersections of the two curves, the rate of convergence of the solver drops significantly due to an extensive amount of binary subdivision [179]. In such cases we may run the IPP solver with a fairly coarse level of accuracy, for example or . If we observe a number of boxes overlap to one another, as shown in Fig. 5.29, it is very likely that overlap exists. Figure 5.29 shows the boxes of roots of the intersection points of two curves computed with . We can observe that the curve overlaps with curve from to and the curve overlaps with curve from to .

Figure 5.28: Two cubic Bézier curves AB and CD overlapping each other at CB (adapted from [179])

Figure 5.29: The coarse boxes that contain roots of intersection of two overlapping curves (adapted from [179])

Hu et al. [179,178] discuss the treatment of curve/curve, curve/surface as well as surface/surface overlapping problems based on interval polynomial curves and surfaces with the IPP solver. They also introduced the following theorem which can be used to find the starting and end points of the overlapping segment.

Theorem 5.9.1. If two curve segments and overlap along a finite part of their length, they must overlap everywhere. Otherwise, they end at boundary points.

This theorem means it is impossible that two curves, such as two parametric polynomial curves, overlap along a finite part of their length and separate from each other at one point, as illustrated in Fig. 5.30. This theorem can be proven contrapositively.

Figure 5.30: Overlap of two curves along a finite segment. (a) is an impossible configuration, and (b) and (c) are the two possible configurations (adapted from [178])

Proof: Assume that there exist two curves and which overlap partially. This means that there is an interior point (referred to as separation point) that ends the overlapping segment of and , as illustrated in Fig. 5.30. Let and be the parameters of and at , respectively. Suppose further that the two curves are arc length parametrized, and have the same orientation. Since the two curves are , their overlapping segment should be also , i.e.,

where superscript denotes derivative of order valid for all nonnegative integers . Therefore, from the Taylor expansion theorem, we have

From (5.107), (5.108) and (5.109), we have , which means that cannot be an interior point. Hence, Theorem 5.9.1 is proven.

Further discussions on curve/surface and surface/surface overlapping problems can be found in [178].