Calculating minimum distance between two NURBS objects

被引:1
作者
He P. [1 ]
Zhang C. [1 ]
Zhou J. [1 ]
Ma Y. [1 ]
机构
[1] School of Computer Science and Technology, Shandong University
来源
Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics | 2010年 / 22卷 / 08期
关键词
Control polygon; Minimum distance; Newton-Raphson method; NURBS curve/surface;
D O I
10.3724/SP.J.1089.2010.11015
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:1344 / 1351
页数:7
相关论文
共 20 条
  • [1] Lin M.C., Efficient collision detection for animation and robotics, (1993)
  • [2] Ho S., Sarma S., Adachi Y., Real-time interference analysis between a tool and an environment, Computer-Aided Design, 33, 13, pp. 935-947, (2001)
  • [3] Johnson D.E., Cohen E., A framework for efficient minimum distance computations, Proceedings of the IEEE International Conference on Robotics & Automation, pp. 3678-3684, (1998)
  • [4] Jimenez P., Thomas F., Torras C., 3D collision detection: A survey, Computers & Graphics, 25, 2, pp. 269-285, (2001)
  • [5] Liu D., Zhao H., Dong Y., Et al., Collision-free inspection path generation for coordinate measuring machines, Journal of Computer-Aided Design & Computer Graphics, 21, 6, pp. 804-811, (2009)
  • [6] Chen X., Yong J., Wang G., Computing the minimum distance between two planar algebraic curves, Journal of Computer-Aided Design & Computer Graphics, 20, 4, pp. 459-463, (2008)
  • [7] Liu H., Tang Y., Liao W., Minimum distance between two biquadratic NURBS surfaces, Journal of Computer-Aided Design & Computer Graphics, 15, 10, pp. 1298-1302, (2003)
  • [8] Turnbull C., Cameron S., Computing distances between NURBS-defined convex objects, Proceedings of IEEE Conference on Robotics & Automation, pp. 3685-3690, (1998)
  • [9] Xu J., Liu W., Bian H., Et al., Algorithm for minimum distance between Bézier curves, Journal of Computer-Aided Design & Computer Graphics, 21, 5, pp. 595-599, (2009)
  • [10] Thomas F., Turnbull C., Ros L., Et al., Computing signed distances between free-form objects, Proceedings of the IEEE International Conference on Robotics & Automation, pp. 3713-3718, (2000)