任洪海， 郭发军， 王艳娟

（大连交通大学软件学院数字媒体教研室，辽宁 大连 116052）

线裁剪是计算机图形学的一个基本操作，作为圆形窗口线裁剪求交过程较为复杂，快速确定线段是否与窗口相交以及交点计算是这类算法的关键。近年来很多学者提出了圆形窗口的线裁剪算法。如文献[1-2]直接将线段参数方程代入圆形窗口的代数方程，通过求解一元二次方程实现裁剪，效率较低。文献[3]经过矩形单侧排除预处理后，利用圆心到直线段距离以及从圆心向直线段所引的垂直射线来判别直线段与圆形窗口的位置关系，但点-线距离以及旋转矢量法的计算量都很大。文献[4]通过制备规范化交点表避免了二次方程的运算，但需要很大精力建立复杂的规范化交点表。文献[5]利用常规外切正方形一次编码及旋转外切正方形二次编码排除部分圆形窗口之外的线段，在线段位置不确定的情况下，需要进行多重编码，而事实上并未简化求交过程。文献[6]通过坐标变换使线段与圆的位置关系转化为x轴与圆的位置关系，其中坐标变换和其逆变换都很费时。文献[7]通过圆切线斜率与线段斜率的比较确定线段是否与圆形窗口相交，一定程度提高了裁剪效率，不过求圆切线斜率也涉及到开方等复杂计算。

本文提出一种基于线段在两坐标轴上截距的圆形窗口线裁剪算法。经过简单测试，排除两端点都在圆外切正方形某边界之外的线段，并确定两端点都在圆形窗口内或一端点在圆形窗口内而另一端在圆形窗口外这两种情况中线段与圆形窗口的位置关系。……