Musings On "Intersections"

Intersection of geometric entities has been a highly researched topic. Having worked with several geometric modeling systems and consulted with a number of esteemed colleagues, I have come to some conclusions about the subject and the various approaches utilized.

Tolerances

Any intersection routine worth its salt will allow the input of a 3D tolerance. The intersector should return all intersections where the geometry comes within this tolerance. What this says is the intersector needs not only to intersect but to compute "closest points" between objects.

Analytical Intersections - Equation Solving

Determining intersections by solving implicit and parametric equations can be very efficient. There are a couple problems. The first problem is that they only work when there is an actual intersection. They typically fail to capture intersections which are "close" to within some geometric tolerance. The simplest example of intersection of a line and a circle fails if the line is close to the circle but not actually intersecting it. The second problem is that for higher order intersections the equations tend to have very high order and tend to be very unstable. Round off errors can actually change the topology of the intersection. My preference for using equations to use them only after the topology of the intersection has already been determined. This limits it to fairly simple intersections, i.e. curves and surfaces of degree two or less.

Geometric Intersection

There are many intersections which can be determined or partially determined by virtue of geometric computations. For example, in the case of a circle and line we can compute the distance between the center of the circle and the line. We can often utilize geometric computation this distance to then determine the topology of the intersection. In the line circle example there are four possible topologies:

1. Distance > circle radius and distance < radius + tolerance - one "closest point" type intersection.
2. Distance == radius - one "real" tangent intersection.
3. Distance < circle radius and distance > radius - tolerance - three intersection points - two "real" intersections and one "closest point".
4. Distance < radius - tolerance - two "real" intersections

We can do a lot of geometric intersection computation with lines, arcs, conics, planes, cylinders, cones, spheres, surfaces of revolution, surfaces of extrusion and several others. Often one can utilize geometric information as the basis for starting a numerical intersection or an analytical intersection.

Numerical Intersection

The nice thing about numerical intersection is that you are typically dealing with real geometry in 3D. The not so nice things about numerical intersections are as follows:

1. You need to have good start points to converge.
2. When two intersections are very "close" numerical techniques often miss one of the intersections.
3. Tangent intersections cause convergence problems because of nearly parallel tangents or tangent planes.

These problems can be overcome. These problems can be addressed utilizing geometric properties of NURBS, differential geometry, and smart solvers.