A classic problem in the fields of geometric modeling and computer graphics (GM-CG) is that of finding all intersections between a parametric surface and a line. What makes this paper different from similar contributions is that an emphasis is placed on advanced numerical analysis tools (in particular, the Kantorovich convergence test), leading to an algorithm of improved robustness and efficiency.
Sections 2 and 3 present introductory material: a review of the Kantorovich theorem, and the standard formulation of the line-surface intersection problem based on standard polynomial bases. Sections 4 and 5 discuss the proposed Kantorovich test subdivision (KTS) algorithm. Detailed convergence and time-complexity analysis are presented in Sections 6 and 7, which are confirmed by the numerical tests reported in Section 8.
The most impressive features of the KTS algorithm are: first, based on the Kantorovich test, the KTS starts Newton’s method only when quadratic convergence is assured; second, there is an upper bound on the number of subdivisions performed, depending only on the condition number of the problem instance; third, a theorem, proved in the paper, establishes that solutions located at the border of a subpatch are directly identified without any special treatment; and, fourth, the KTS algorithm is affine invariant.
I consider this paper a very valuable contribution to the fields of GM-CG. It emphasizes that, despite the impressiveness of the modern GM-CG tools, there is a lot to gain when these are combined with the vast body of knowledge offered by classical fields like approximation theory and numerical analysis.