TY - JOUR

T1 - Calculating minimum distance between two NURBS objects

AU - He, P.

AU - Zhang, C.

AU - Zhou, J.

AU - Ma, Y.

PY - 2010/8

Y1 - 2010/8

N2 - The disadvantage of the most existing algorithms for computing the shortest distance between geometric objects is that it needs to do a lot of polygon detections, and the shortest distance computed is not precise enough sometimes. In this paper, a method is proposed to compute the minimum distance between NURBS objects (curve-curve, curve-surface and surface-surface). It firstly decompose both of the NURBS objects into their piecewise Bézier forms to form two sets, and the bounding spheres of each Bézier object are computed. Then, candidate pairs are extracted from the two sets based on a two-level selection process. The property of the new method is that the upper-lower bounds and 'four-points-condition' are used to chose the candidate pairs, which makes the candidate pairs as few as possible, and hence, the computation costs could be reduced greatly. At last, an iterative multidimensional Newton-Raphson method is applied to all candidate pairs in order to calculate the approximate local minimum distances. By comparing all local minimum distances between a pair of Bézier objects, we are able to find the global minimum distance. The experiments show the new method is a high-performance, accurate and robust. It can process two NURBS objects in real-time under the condition of machine accuracy.

AB - The disadvantage of the most existing algorithms for computing the shortest distance between geometric objects is that it needs to do a lot of polygon detections, and the shortest distance computed is not precise enough sometimes. In this paper, a method is proposed to compute the minimum distance between NURBS objects (curve-curve, curve-surface and surface-surface). It firstly decompose both of the NURBS objects into their piecewise Bézier forms to form two sets, and the bounding spheres of each Bézier object are computed. Then, candidate pairs are extracted from the two sets based on a two-level selection process. The property of the new method is that the upper-lower bounds and 'four-points-condition' are used to chose the candidate pairs, which makes the candidate pairs as few as possible, and hence, the computation costs could be reduced greatly. At last, an iterative multidimensional Newton-Raphson method is applied to all candidate pairs in order to calculate the approximate local minimum distances. By comparing all local minimum distances between a pair of Bézier objects, we are able to find the global minimum distance. The experiments show the new method is a high-performance, accurate and robust. It can process two NURBS objects in real-time under the condition of machine accuracy.

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-77956001108&partnerID=MN8TOARS

U2 - 10.3724/SP.J.1089.2010.11015

DO - 10.3724/SP.J.1089.2010.11015

M3 - Article

VL - 22

JO - Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics

JF - Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics

IS - 8

M1 - 1344-1351

ER -