Computing Minimum Distance Between NURBS Surfaces

This thesis, from different analytical points of view, proposes three algorithms for the minimum distances between convex NURBS surfaces and general NURBS surfaces respectively.Firstly, based upon analyzing the geometric constraint condition of the nearest points, a method is given to refine the approximated distance between two surfaces through Newton-Raphson iteration. At the same times, the cases of boundaries are all considered in detail.Secondly, according to convex geometric characteristics, a Common-perpendicular-line Algorithm is developed for the distance between the convex NURBS surfaces by making surfaces discrete, approximating the distance by one between convex hulls of discrete surfaces and solving a linear programming problem to get their vertical projective length on common perpendicular direction, that is, the original distance.Thirdly, from the idea of locally linear approximate, another Tangent-plane Algorithm is presented for the distance between the convex NURBS surfaces. The critical step is the construction of the support mapping by GJK and LC to search for nearest points, and emphases are laid on dealing with isotropic cases and choosing initial iterated points. It is also proved that no isotropism during iteration would take place if initial iterated points are positive points.Finally, a Split Algorithm is put forward to calculate the minimum distance between two general NURBS surfaces, in which the technique of splitting the NURBS surfaces and the convergence of control points are used, and spatial classification using the upper & lower bound and the convex hull property of the NURBS surfaces are applied to avoid unnecessary subdivisions.The programs of the above algorithms are developed. It is showed that the algorithms are robust and efficient by computation of many examples, and analyses and comparison of the experimental results. Figures and tables are also a telling story.