5.1 Overview of intersection problems

Intersections are fundamental in computational geometry, geometric modeling and design, analysis and manufacturing applications [276,19,175,295,300]. Examples of intersection problems include:

• Contouring of surfaces through intersection with a series of parallel planes or coaxial circular cylinders or cones for visualization (see Fig. 5.1).
• Numerical control machining (milling) involving intersection of offset surfaces with a series of parallel planes, to create machining paths for ball (spherical) cutters (see Fig. 5.2, and Sect. 11.1.2).
• Representation of complex geometries in the Boundary Representation (B-rep) scheme; for example, the description of the internal geometry and of structural members of automobiles, airplanes, and ships involves
  • Intersections of free-form parametric surfaces with low order algebraic surfaces (planes, quadrics, torii, cyclides [83]);
  • Intersections of low order algebraic surfaces (see Fig. 5.26);
  in a process called boundary evaluation, in which the Boundary Representation is created by evaluating a Constructive Solid Geometry (CSG) model of the object [343,261,56,167,342,344]. During this process, intersections of the surfaces of primitives (see Fig. 5.3) must be found during Boolean operations. Boolean operations on point sets , include (see Fig. 5.4) union , intersection , and difference .

Figure 5.1: A marine propeller is visualized through intersection with a series of parallel planes

Figure 5.2: Offset surface is intersected with a series of parallel planes to generate a tool path for 3-D NC machining (adapted from [223])

Figure 5.3: Primitive solids

Figure 5.4: Example of Boolean operations

All such operations involve intersections of surfaces to surfaces. In order to solve general surface to surface (S/S) intersection problems, the following auxiliary intersection problems need to be considered:

1. point/point (P/P)
2. point/curve (P/C)
3. point/surface (P/S)
4. curve/curve (C/C)
5. curve/surface (C/S)

All above six types of intersection problems are also useful in geometric modeling, robotics, collision avoidance, manufacturing simulation, scientific visualization, etc. When the geometric elements involved in intersections are nonlinear (curved), intersection problems typically reduce to solving systems of nonlinear equations, which may be either polynomial or more general functions.

Solution of nonlinear systems is a very complex process in general in numerical analysis and there are specialized textbooks on the topic [293,69,274]. However, geometric modeling applications pose severe robustness, accuracy, automation, and efficiency requirements on solvers of nonlinear systems. Therefore, geometric modeling researchers have developed specialized solvers to address these requirements explicitly using geometric formulations as we have seen in Chap. 4.

When studying intersection problems, the type of curves and surfaces that we consider can be classified as follows:

• Rational polynomial parametric (RPP)
• Procedural parametric (PP)
• Implicit algebraic (IA)
• Implicit procedural (IP)

where procedural curves and surfaces are defined by means of an evaluation method without explicit use of the specific analytical properties of the defining formula. For example, procedural curves include offsets and evolutes, procedural surfaces include offsets, evolutes, blends and generalized cylinders (e.g. pipe and canal surfaces). However, some of the above procedural curves and surfaces under special conditions can be expressed in the RPP or the IA form, in which case the corresponding methods can be used (see for example [101,241,256,238,239]).