5.8.2.3 Marching methods

Marching methods involve generation of sequences of points of an intersection curve branch by stepping from a given point on the required curve in a direction prescribed by the local differential geometry [17,19,20,210,454], as we have studied in tracing the planar algebraic curve in Sect. 5.8.1. However, such methods are by themselves incomplete in that they require starting points for every branch of the solution. In order to identify all connected components of the intersection curve, a set of important points on the intersection curve (characteristic points) can be defined. As seen in Sect. 5.8.1, such a set may include border, turning and singular points of the intersection and provides at least one point on any connected intersection segment and identifies all singularities. For a 3-D RPP/RPP intersection case a more convenient set of such points sufficient to discover all connected components of the intersection, includes border and collinear normal points between the two surfaces. Collinear normal points provide points inside all intersection loops and all singular points.

Border points are points of the intersection at which at least one of the parametric variables takes a value equal to the border of the - or - parametric domain. To compute border points, a piecewise rational polynomial curve to piecewise rational polynomial surface intersection capability is required, e.g., , which we discussed in Sect. 5.7.2. Müllenheim [278] addressed a local method to find starting points for two parametric surfaces. Abdel-Malek and Yeh [1] introduced two local methods, iterative optimization and the Moore-Penrose pseudo-inverse method to determine starting points on the intersection curve between two parametric surfaces.

Sederberg et al. [376] first recognized the importance of collinear normal points in detecting the existence of closed intersection loops in intersection problems of two distinct parametric surface patches. These are points on the two parametric surfaces at which the normal vectors are collinear. Collinear normal points are a subset of parallel normal points first used by Sinha et al. [396] in surface intersection loop detection methods.

To simplify the notation, we replace by and by . Then the collinear normal points satisfy the following equations [376]

Equations (5.100) form a system of four nonlinear polynomial equations that can be solved using the robust methods of Chap. 4. Now we split the patches in (at least) one parametric direction at these collinear normal points. Consequently, starting points are only border points on the boundaries of all subdomains created. Grandine and Klein [133] follow a systematic approach for topology resolution of B-spline surface intersections. In this process, they determine the structure of the intersection curves including closed loops prior to numerical tracing (following a marching method based on numerical integration of a differential algebraic system of equations). Topology resolution in this context relies on an extension of the PP algorithm (see Sect. 4.4) to the B-spline case implemented in floating point (with normalization of the equations in the range [-1,1] and normalization of the knot vector in each subdomain in the range [0,1] at each iteration step of the process to capitalize on the higher density of floating point numbers in this range, thereby improving numerical robustness of the algorithm). An alternate way to detect closed intersection loops is to use topological methods [236,53,264,210,245,244,436,435]. Also bounding pyramids [209,382] can be used effectively to assure the nonexistence of closed surface to surface intersection loops. These earlier methods need to be implemented in exact or RIA for robustness.

In order to trace the intersection curve, starting points must be located prior to tracing. An intersection curve branch can be traced if its pre-image starts from the parametric domain boundary in either parameter domain [19]. The marching direction coincides with the tangential direction of the intersection curve which is perpendicular to the normal vectors of both surfaces. Therefore, the marching direction can be obtained as follows:

where the normalization forces to be arc length parametrized and

are the normal vectors of and , respectively. When the two surfaces intersect tangentially, we cannot use (5.101) since the denominator vanishes. In such cases we must find the marching direction in an alternate way which will be discussed in Sect. 6.4.

The intersection curve can also be viewed as a curve on the two intersecting surfaces. A curve , in the -plane defines a curve on a parametric surface , as well as a curve in the -plane defines a curve on a parametric surface . We can derive the first derivative of the intersection curve as a curve on the parametric surface using the chain rule:

Since we know the unit tangent vector of the intersection curve from (5.101), we can find and as well as and by taking the dot product on both hand sides of the first equation of (5.103) with and and the second equation with and , which leads to two linear systems [178]. The solutions are immediately obtained as

where denotes the determinant.

The points of the intersection curves are computed successively by integrating the initial value problem for a system of nonlinear ordinary differential equations (5.104) and (5.105) using numerical techniques such as the Runge-Kutta or adaptive stepping methods [69,126]. Figure 5.24 presents the intersection of a rational quadratic-linear B-spline patch (representing a cylinder) with a biquadratic Bézier patch representing an elliptic paraboloid [208]. Figure 5.25 presents the intersection between two biquartic Bézier patches (nearly coincident surfaces) [210].

Figure 5.24: Cylinder - elliptic paraboloid intersection (adapted from [208])

Figure 5.25: Intersection of two biquartic Bézier patches forming four small loops (adapted from [210])