For a point X, we want to find the closest point on a polynomial surface patch p, and its parameter value. The closest point is always on the border on the domain or at a critical point (footpoint of X or singular point of p). Finding the closest point on the border is easy. Thus, if all singular points in the domain are found (there are ususally none), and all footpoints of X are found, then the problem is solved. We find all the footpoints in the domain by first constructing the equations of two moving ruled surfaces, using a technique from approximate implicitization. One moving surface follows the surface in the first parameter direction, and one follows the surface in the other parameter direction. Then we can find the footpoints by substituting X into these equations and solving the resulting univariate polynomials. The result is a method that is relatively fast when we need to compute many closest points for a single surface patch.
Ray tracing of algebraic surfaces is faster than ray racing of rational parametric surfaces as the algebraic represented surface can be intersected by a parametric represented straight line yielding one polynomial equation in one variable. While intersecting a rational parametric surface with a straight line represented as the intersection of two planes yields two polynomial equations in two variables. Thus provided sufficiently good approximations to parametric surfaces can be made, it will be attractive to ray trace an approximate implicit representation of rational parametric surfaces, rather than the parametric surface itself.
Published June 7, 2005