A Practical Algorithm for Surface/Surface Intersection

Ling Huang   Xinxiong Zhu

（School of Mechanical Engineering & Automation,

Beijing University of Aeronautics & Astronautics, Beijing, 100083）

 

Abstract:  A practical solution to the surface/surface intersection is presented. This algorithm combines the techniques of loop detection, point marching and curve approximation, etc. Given a set theoretical curves constrained by surface/surface intersection equations, the algorithm can get all the intersection branches, and construct spline curves to approximate every theoretical curve with least data in terms of the given tolerance.

1.  Introduction

The problem of computing the surface/surface intersection (SSI) curves is a fundamental one in CAD/CAM. It arises from a broad spectrum of tasks, ranging from solid topology operation to manufacturing processes.

Given two surfaces  and , there would possibly be a parametric equation  which exactly expresses the theoretical intersection curves of those two surfaces:

                                                   (1)

However, algebraic degree and genus of the intersection curves are so high that even an SSI curve of two bicubic patches cannot be expressed precisely by using rational polynomial parametric equations, for only curves with genus being zero have an exact parametric equation. In general, numerical solutions are necessary and SSI curves can be approximated by using parametric curves, for example, by NURBS.

For surface/surface intersection, the divide-and-conquer algorithm and the marching algorithm are commonly used. In subdivision based algorithms, the surfaces are subdivided into a great number of facets and the intersection of surfaces is approximated by the intersection of the facet pairs. Marching algorithms begin by finding one starting point on the intersection curve and marching along the curve to get the successive points. But they are inefficient to deal or incapable to dealing with the singular cases (for example, tangent or overlap of two surfaces). Hence, it is very hard, if not impossible, to obtain all the intersection segments (for example, the small intersection loops) in an SSI algorithm.

In commercial CAD/CAM systems, an SSI algorithm should be able to obtain all the intersection curve(s) steadily and exclusively. And, the result curve(s) approximated by NURBS should be within the given tolerance. The practical solution for surface/surface intersection should be the combination of many techniques.

This memorandum presents a practical solution to the surface/surface intersection which combines the techniques of loop detection, point marching, curve approximation, etc. Given a set theoretical curves constrained by surface/surface intersection equations, the goal of the algorithm is to get all the intersection branches, and constructs a NURBS curve to approximate every theoretical curve with least numbers of segments in terms of the given tolerance. All the curves can be found by obtaining an initial marching point for every branch and all the points and tangent vectors on every curve can be calculated.

 

2.  Strategy

2.1  Procedure

The main steps of our surface/surface intersection algorithm can be summarized as follows:

l       Step1: Obtain a starting point for every intersection curve by exploiting the plane vector field method.

l       Step2: March along every intersection curve steadily to get the successive intersection points with an adaptive step length calculated by taking advantages of the local curvature of the curve.

l       Step3: Calculate the significant points on every intersection curve in the marching process and partition the curve to a number of monotonic intervals.

l       Step4: Construct a NURBS curve fitting the sample points (including significant points and all the marching points) and get a candidate approximation curve for every theoretical intersection curve.

l       Step5: Estimate the deviation between the candidate NURBS curve and the theoretical curve in every interval and check if the deviation is within the given tolerance.

l       Step6: If all the deviations are within the given tolerance, the candidate NURBS is accepted. Otherwise, add new marching point(s) into the sample points array in the interval(s) where the deviation exceeds the given tolerance. Go to step 4.

2.2  Obtaining Starting Points

The most difficult problem in surface/surface intersection is to find all the intersection curves without missing any one. The intersection of two surfaces may include two types of curves: (1) closed loops and (2) open branches, as shown in Fig.1.

 

Fig.1  Types of intersection curves.

It is easy to locate a starting point on an open branch by simply intersecting all the boundary curves of each patch with the opposing patch. On the other hand, if closed loops exist, there is a major challenge in surface intersection algorithm. There are many different ways to solve this problem, including patch subdivision and loop detection.

      In our method an algorithm based on the theory of plane vector field is exploited to obtain the starting points of all the intersection curves. The key of intersection finding is relevant to the global searching and local positioning of intersection area. And, the theories of topology and differential geometry provide the base to solve the problem. It is convenient to express an intersection curve as a set of points on the two surfaces with zero distance which results in the oriented distance function of one surface from the other. The gradient of the oriented distance function defines a vector field that is useful in solving the parametric surfaces intersection problems. An adaptive method in terms of Poincare index was developed that invoked the rotation number of vector fields to find the critical points of the oriented distance function between two parametric surfaces. This approach allows the development of a global method for identifying the areas enclosing small loops and significant points of the intersection set. Many papers discussed this method in detail and can be exploited.

2.3  Point Refinement

       Initial approximated points, either starting points or marching points should relax onto the intersection curve by Newton-Raphson iteration.

      Given an approximate intersection point , and candidate parameter pairs of surfaces  and  of . In general, point  will not lie on either surface. The method for point refinement is first to obtain surface “near points”, which are the points on surface and  with a minimum distance from , as shown in Fig.2.

 

Fig.2  Point refinement

As shown in Fig.2, projecting the midpoint of the surface near points  and  onto the intersection line of the tangent planes can get the next iterative point. With  and  as the normals at the near points on surface  and , and with  as the third one, the point  for next iteration can be calculated by Equation (2):

                                             (2)

Then, the Newton-Raphson iterative equation set follows:

(3)

This process continues iteratively until it converges.

       Alternately, the equation set of intersection  can be handled directly by specifying a constant domain parameter as an additional constraint. This idea can be used to relax boundary points onto surface boundaries. For example, at  or  boundary on surface , it would be possible to incorporate the  constraint directly into the system and a new iteration being a 4 by 4 system with 4 unknowns can obtained. For example, at  boundary the system is:

               (4)

In trimmed-surface intersection, iteration on trimmed boundaries should be dealt with. This becomes a problem of curve/surface intersection. For example, on trimmed boundaries of surface  denoted by parametric curve , the iterative equation set is:

           (5)

2.4  Marching along Intersection Curves

      After finding out a point on every intersection curve, successive intersection points can be generated by going a step in the direction defined by the local differential geometry of the curve. It is also necessary to determine the step length at which a new approximative point is obtained. If a step length is too big the intersection approximations may be wrong and the point refinement may not converge; if it is too small, the efficiency of the algorithm decreases. We use an adaptive step length approach based on local curvature at the intersection point.

For the tangent planes of two surfaces are not parallel, step vector directions can be calculated by the cross product of the surface normals. If surface tangent planes are coincide, the normal curvature is employed to calculate the marching direction. In this case, marching direction is the direction where two normal curvatures of the surfaces are equal and can be calculated by Euler formula.

       With a step direction known, an adaptive step length is calculated based on the approximate curvature and chord tolerance . An osculating circle is approximated at a given point  to obtain the radius of curvature. The circle is defined by  and its precedent , and the unit step vectors  and on them. The approximated radius of curvature is:

                                                         (6)

As shown in Fig.3, the step length can  be calculated by Equation (7):

where                                                                                          (7)

 

 

Fig.3  The step length

Then, the next approximate intersection point , and the candidate parameter pairs () and () of surfaces  and , can be calculated in terms of current point  with  parameter pairs and  by Equation (8):

                           (8)

where  is the step vector  and is step length. By Equation (3), point  can be relaxed onto the intersection curve and the “real” intersection point can be obtained. If the Newton-Raphson  iteration  for  does not converge, the step length  should be reduced until the iteration converges (It is always possible to make it converging by making sufficiently small).

2.5  Calculating Significant Points

The significant points on intersection curves, such as Border_Points, Turning_Points and Cusp_Points, subdivide the curves into many monotonic intervals and reflect the overall shape of the curves, as shown in Fig.4. These points are crucial to the marching process and keeping consistency of the topology of the intersection curves. Also the significant points are important and helpful to the processing of curves approximated by NURBS.

The significant points on surface  can be defined as follows:

l       Turning_Points conditions in u-direction:

 and                          (9)

l       Turning_Points conditions in v-direction:

 and                    (10)

l       Cusp_Points conditions:

                                                                   (11)

where  is the normal vector on surface . Similarily the significant points on surface  can be defined. Assume that current intersection is , the next marching point is  and the domain value tuples of  and  are  and , respectively.

Fig.4  Significant points on intersection curves

      The significant points can be detected in the marching process as follows:

       If ( or