高级检索
刘海霞, 李新. 几何区间裁剪算法收敛性分析和比较[J]. 计算机辅助设计与图形学学报, 2010, 22(12): 2250-2258.
引用本文: 刘海霞, 李新. 几何区间裁剪算法收敛性分析和比较[J]. 计算机辅助设计与图形学学报, 2010, 22(12): 2250-2258.
Liu Haixia, Li Xin. Convergence Analysis and Comparison for Geometric Interval Clipping[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(12): 2250-2258.
Citation: Liu Haixia, Li Xin. Convergence Analysis and Comparison for Geometric Interval Clipping[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(12): 2250-2258.

几何区间裁剪算法收敛性分析和比较

Convergence Analysis and Comparison for Geometric Interval Clipping

  • 摘要: 为了寻求简单、快速、稳定的求交算法来加速光线跟踪渲染三维场景,对一种快速计算2条平面曲线交点的方法——几何区间裁剪(GeoClip)算法进行了深入研究.严格证明了GeoClip算法在计算多项式的根以及计算2条平面曲线的交点中都具有三阶收敛性,该结果从理论上保证了GeoClip算法优于经典的曲线求交算法——Bézier Clipping算法;最后对GeoClip与二次裁剪(QuadClip)算法进行了比较,结果表明,虽然都是三阶收敛,但是GeoClip算法比QuadClip算法快30%左右.

     

    Abstract: In order to develop a simple, yet fast and robust algorithm to accelerate the intersection calculation of ray tracing, we make a deep study on the convergence of geometric interval clipping.We formally prove its 3rd order convergence for computing all roots of a given univariate polynomial and for calculating the intersections of two plane curves, which guarantees its better performance than Bézier clipping algorithm.We also provide the comparison against quadratic clipping.Although both algorithms exhibit the 3rd order convergence, the geometric interval clipping algorithm is about 30% faster than quadratic clipping algorithm.

     

/

返回文章
返回