5.10 Self-intersection of curves and surfaces

So far we have focused mainly on intersection problems of regular curves and surfaces without self-intersections. In this section we will show how to compute self-intersections of curves and surfaces.

Self-intersection of a planar rational polynomial parametric curve can be formulated as finding pairs of distinct parameter values such that

or in terms of components as

where

Lasser [225] presents an algorithm to find all the self-intersection points of a Bézier curve by subdividing the Bézier polygon instead of the curve itself. Finally the self-intersection points are approximated by straight line intersections of the refined Bézier polygon.

Here we introduce a method to find all the self-intersection points of a planar rational polynomial parametric curve based on the IPP algorithm introduced in Chap. 4. Multiplying by the denominators of (5.111), we obtain

These equations can be rewritten as

which form a system of two nonlinear polynomial equations in and . Since

we can easily factor out from (5.114) and (5.115) to exclude the trivial solutions .

Self-intersections of a rational polynomial parametric surface are defined by finding pairs of distinct parameter values such that

Barnhill et al. [19] compute surface self-intersections by their procedural surface/surface intersection algorithm. Also Lasser [224] introduces a method to compute all the self-intersection curves of a Bézier surface patch by subdividing the Bézier control net instead of the surface patch itself. Finally the self-intersection curves are approximated by the polygons resulting from the plane/plane intersections of the refined Bézier control net. Andersson et al. [6] provide necessary and sufficient conditions to preclude self-intersections of composite Bézier curves and patches.

Unlike the curve self-intersection case, it is inefficient to solve surface self-intersection problems with the IPP solver (see Chap. 4). The key difficulty arises in the removal of the trivial solutions. We cannot divide out factors and from the system directly, since terms , and do not necessarily exactly involve the factors and . A technique to remove such trivial solutions is given in [253] and in Sect. 11.3.5.

Self-intersections of offsets of curves and surfaces, which are more difficult to compute, are discussed fully in Chap. 11.