高级检索
陆洋, 施侃乐, 雍俊海. 细分法求解点投影问题时的剪枝算法[J]. 计算机辅助设计与图形学学报, 2014, 26(4): 617-622.
引用本文: 陆洋, 施侃乐, 雍俊海. 细分法求解点投影问题时的剪枝算法[J]. 计算机辅助设计与图形学学报, 2014, 26(4): 617-622.
Lu Yang, Shi Kanle, Yong Junhai. A Clipping Method Applied in Subdivision to Solve Point Projection Problems[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(4): 617-622.
Citation: Lu Yang, Shi Kanle, Yong Junhai. A Clipping Method Applied in Subdivision to Solve Point Projection Problems[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(4): 617-622.

细分法求解点投影问题时的剪枝算法

A Clipping Method Applied in Subdivision to Solve Point Projection Problems

  • 摘要: 点到NURBS曲线/曲面的投影是CAD中的基础问题.为了避免数值迭代法陷入局部最优,通常把曲线/曲面细分为多段.文中提出排除无用曲线段/曲面片的剪枝算法,以提高细分求解投影的运行效率.在投影算法中将曲线/曲面递归细分,分别计算测试点到各个曲线段/曲面片的投影值;在递归过程中,对当前曲线段/曲面片计算测试点到控制点凸包距离的近似距离,如果该距离大于投影距离上界值,根据NURBS曲线/曲面的凸包性,测试点到当前曲线段/曲面片的投影距离也一定大于上界值,无需计算投影结果,直接排除该曲线/曲面.最后通过测试实例验证了该算法的有效性.

     

    Abstract: Point projection to a NURBS curve/surface is an essential operation in CAD. When computing the projection result, the curve/surface is usually subdivided into several patches to avoid being trapped in the local optima.In this paper, in order to improve the efficiency of the subdivision, a clipping method is proposed to eliminate the patches which are irrelevant to the result.In our projection algorithm, the curve/surface is subdivided recursively and the projection distance to the current curve/surface patch is computed in each step.We approximate the distance between the source point and the convex hull of the control points.If it is larger than the upper bound of the projection result, according to the convex hull property of NURBS curves/surfaces, the current projection distance is also larger than the upper bound and the current curve/surface patch can be ignored. Examples illustrate the performance improvement of the corresponding projection algorithms.

     

/

返回文章
返回