论文部分内容阅读
光线跟踪算法是真实感图形学中的主要算法之一,该算法具有原理简单、实现方便和能够生成各种逼真的视觉效果等突出优点。由于光线跟踪算法需要用到大量的求交运算,因此求交运算的效率对整个算法的效率影响很大,光线和物体的求交算法是光线跟踪算法的核心。
本文对一种快速求交的新方法–几何区间裁剪算法(GeoClip)进行了深入研究。首先研究了计算两条平面曲线的几何裁剪算法,严格证明了几何区间裁剪算法在计算多项式的根以及计算两条平面曲线的交点中都具有三阶收敛性,该结果从理论上保证了几何区间裁剪算法优于经典的曲线求交算法-B(e)zierClipping算法。最后对GeoClip与二次裁剪(QuadClip)算法进行了比较,结果表明,虽然都是三阶收敛,但是GeoClip算法比二次裁剪算法要快30%左右。然后将这种算法的优势推广到光线/三角曲面求交算法。首先构造了以光线为交线的两个垂直平面,将B(e)zier曲面投影到R2。投影后光线映射为坐标原点,两个平面分别映为x,y轴。从而,光线/曲面的求交问题转变为多项式的求根问题,再利用GeoClip求根算法求出交点所在的参数区域。最后给出了两种用于求光线/三角曲面交点的算法–几何区间裁剪算法和B(e)zier 裁剪算法的比较,结果表明,几何区间裁剪算法优于B(e)zier裁剪算法。