TY - JOUR

T1 - A High-Performance Method for Calculating the Minimum Distance between Two 2D and 3D NURBS Curves

AU - Ma, YingLiang

AU - Hewitt, W. T.

AU - Turner, Martin

PY - 2006/1

Y1 - 2006/1

N2 - We present a fast, accurate, and robust method to compute the minimum distance between two 2D and 3D NURBS curves. This is carried out by first decomposing both of the NURBS curves into their piecewise-Bézier forms. Candidate pairs, as a subset of all possible pairs, are extracted based on a two-level selection process. The first-level selection uses upper-lower bounds of Bézier subcurves to remove pairs. The second-level selection is based on the spatial relationship test between a pair of Bézier curves. An iterative multidimensional Newton-Raphson method is applied on all candidate pairs in order to calculate the approximate local minimum distances. Finally, by comparing all local minimum distances between a pair of Bézier subcurves, we are able to find the global minimum distance. The accuracy is improved by further use of the multidimensional Newton-Raphson method to give high accuracy. Source code is available online.

AB - We present a fast, accurate, and robust method to compute the minimum distance between two 2D and 3D NURBS curves. This is carried out by first decomposing both of the NURBS curves into their piecewise-Bézier forms. Candidate pairs, as a subset of all possible pairs, are extracted based on a two-level selection process. The first-level selection uses upper-lower bounds of Bézier subcurves to remove pairs. The second-level selection is based on the spatial relationship test between a pair of Bézier curves. An iterative multidimensional Newton-Raphson method is applied on all candidate pairs in order to calculate the approximate local minimum distances. Finally, by comparing all local minimum distances between a pair of Bézier subcurves, we are able to find the global minimum distance. The accuracy is improved by further use of the multidimensional Newton-Raphson method to give high accuracy. Source code is available online.

U2 - 10.1080/2151237X.2006.10129214

DO - 10.1080/2151237X.2006.10129214

M3 - Article

VL - 11

SP - 37

EP - 50

JO - Journal of Graphics Tools

JF - Journal of Graphics Tools

SN - 2165-347X

IS - 1

ER -