Fast and Accurate Methods for Computing the Distance Function and the Newton Solver

Richard Tsai
Princeton University
PACM & Mathematics

I will start by describing a fast way for computing the distance function to a given configuration of isolated points. We then generalize the algorithm to compute the distance to piecewise linear interfaces. Finally,we describe a fast way of computing Newton's iteration for computing the distance to parametrized surfaces such as NURBS. The algorithms presented are purely algebraic, though they are motivated by the PDE idea of following the characteristics.


Back to Geometrically Based Motions Tutorials