基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法

路 通， 苏 丰， 杨若瑜

（南京大学计算机软件新技术国家重点实验室，江苏 南京 210093）

裁剪算法是计算机图形学的基础性方法，速度更快的算法一直是研究者的不断追求。在经典的Cohen-Sutherland线段裁剪算法提出之后又出现了许多好的裁剪方法，它们在本质上有两个共同点：一是尽量避免无效的操作，二是尽量用简单快捷的加、减等基本操作代替复杂、耗时的乘、除及开方等操作。例如，Liang-Barsky[1]方法通过正确选择相对于待裁剪线段的窗口矩形始、终边来简化判定；Nicholl–Lee-Nicholl[2]方法通过比较待裁剪线段的斜率和始点到矩形窗口各顶点连线斜率，来确定需求交的窗口边，以便避免无效的求交操作；Devai[3]方法对 Nicholl–Lee-Nicholl方法作了一定的改进；Duvanenko-Robbins-Gyurcsik[4]方法通过优化算法、减少冗余比较与浮点数运算等来提高裁剪效率；Wang-Wu-Cai[5]方法通过将待裁剪线段简单变换，使其始点位于特定区域，从而明确应求交的窗口边来加速处理；Lu-Wu-Peng[6]提出了基于待裁剪线段位置和方向的排除方法；针对圆形窗口也提出了一些裁剪方法[7-10]。但对于圆形窗口如何在排除性测试和线-圆求交等环节避免或减少大量的复杂操作，仍然是有待进一步研究的问题。

圆形窗口对线段的裁剪有众多应用需求，如在智能CAD系统的交互式图形界面中，需要实时移动“圆形放大镜”或“鹰眼”作快速图元检查或检索；在图形识别与理解等复杂图形应用系统中，需要快速计算圆与其它各图元间的精确几何或拓扑约束；以及在实时绘制时需对图元进行消除隐藏线的处理等。……