高级检索

空间NURBS曲线间最近距离的高效计算方法

An Efficient Method for Computing the Minimum Distance between NURBS Curves

  • 摘要: 针对自由曲线间最近距离计算中传统细分方法存在的组合计算耗时高、初始值敏感等问题,提出一种基于竞争流加速匹配与准控制多边形控制点映射的高效方法。首先通过层次化细分将非均匀有理B样条(NURBS)曲线分割为Bézier曲线段集合,构造紧致包裹曲线的准控制多边形并计算误差上界,实现不包含最近点对区域的快速剪枝;然后引入竞争流遍历策略显著减少距离计算的时间复杂度,即在局部最近点对个数固定的情况下能得到线性时间复杂度;最后通过准控制多边形控制点到曲线的比例映射获取高精度初始值,结合牛顿迭代法实现全局最近距离的快速收敛。在多组不同复杂度曲线上的实验结果表明,与其他方法相比,所提方法在距离计算耗时上的优势明显,且保持给定的精度和结果鲁棒性。

     

    Abstract: Aiming at the problems of high combinatorial computation time consumption and initial value sensitivity in traditional subdivision methods for shortest distance calculation between NURBS curves, this paper proposes an efficient algorithm based on competitive flow matching and quasi-polygon control point mapping. Firstly, hierarchical subdivision is used to split NURBS curves into Bézier curve segments, construct quasi-polygons tightly wrapping curves and calculate error upper bounds for rapid invalid region pruning. And then, a competitive flow traversal strategy is introduced, significantly reducing the time complexity of distance calculation; that is, linear time complexity is achievable when the number of local nearest point pairs is fixed. Finally, high-precision initial values are obtained via proportional mapping from quasi-polygon control points to curves, and Newton’s iteration method achieves the global closest distance. Compared with prevailing methods, this approach consistently outperforms in computation time for complex curves while maintaining the given precision and robustness.

     

/

返回文章
返回