Bézier曲线/曲面间最近距离的几何裁剪算法

Geometric Pruning Method for Computing Minimum Distance between a Bézier Curve and a Bézier Surface

曲线、曲面间距离的计算问题在CAD/CAM、计算机图形学中有着广泛的应用.为了精确计算Bézier曲线/曲面间的最近距离,结合稳定的曲线、曲面分裂技术提出一种基于offset滚动球裁剪的几何算法.首先给出判定条件来裁剪去落在曲面的滚动球外的曲线段,或者落在曲线的滚动球外的曲面片,以摒弃大部分不包含最近点的曲线段或曲面片,为后续可能的Newton方法提供较好的初始点;然后给出判定最近点是否落在曲线的端点或曲面的边界曲线上的条件,将曲线/曲面间的距离计算问题转化为点/曲面或曲线/曲线间的距离计算问题,简化了问题的复杂度,提高了计算效率.实例结果表明,文中算法具有较好的稳定性和较高的效率.

The minimum distance computation problem has wide applications in CAD/CAM and computer graphics. This paper presents a sweeping sphere pruning based method for computing the minimum distance between a Bezier curve and a Bezier surface. Firstly, we provide a sufficient condition whether a curve is outside of the sweeping sphere of a surface, or whether a surface is outside of the sweeping sphere of a curve, which can prune most of sub-curves or surface patches which contain no closest poin1. Then we provide conditions whether the closest point is an end point of the curve or on a boundary curve of the surface, this turns the curve/surface case into a curve/curve or point/surface case, and leads to lower computation complexity and better efficiency. Examples illustrate the efficiency and the robustness of the new method.