一般多边形窗口的线裁剪

《一般多边形窗口的线裁剪》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第5卷第4期计算机辅助设计与图形学学报V01．5．No．41993年10月Ch'm．JCAD＆CGOct．．19932一般多边形窗口的线裁剪弋甲l、。I刘勇奎刘桂芳’P-_。_～。-’--。～沈阳工业大学计算机学院，沈阳，11(XI21LINECLⅡ’PINGAGASTAGENERALIZEDPOLYGoNLiuYongkuiandLiuGuifangCompu~E9∞‘呻Collie,Shen3amoPoicUalver~y,Shenya~,110021Abst~etExistinglineclippingalgorithn~aIeall

2、ofenxlbasedoilarectangularwin-doworac0nVpolygonalwindow．Noalgorithmforlineclippingbasedonagencmlimdpolygon(orGoncavcpolygon1isavailableintheliterature．Itquitevaluabletodevelopsuchalgodthn~，bccausctheyaIeofpracticall玛ejustlikethehiddenlineproblem．Inthispaper，alineclippingalgorithmbasedoilagencrali

3、z~polygonispresented．Thecalculationefortofthealgorithmissmal1．ICer~alsComputergraphics，Goric~．v~polygonalwindow，linec~ppiug，／nteasoctioncalculating摘要已有的线裁剪算法都是针对矩形窗口或凸多边形窗口的．对于一般的多边形窗口(包括凹多边形)的线裁剪，目前尚无有效的算法。开发这种算法是很必要的，固为它在计算机图形学中有很广泛的应用，如物体的消隐处理等。固此，提出一个对于一般多边形窗口的线栽剪算法并给出了最优实现。关羹词芷箜垫里堂，凹窆垄查旦，：，交

4、点计算一、引言线裁剪是计算机图形学中的一个基本操作。目前，对于矩形窗口的线裁剪已得到人们深入的研究，’并盯现狲效的算法，如经典的Cohen—Sutherland算法[11，Spmull和Sutherland提出的便于硬件实现的中点分割法，我国学者梁友栋与Barsky提出的参数方法，还有较近期的Nicholl—Lee—Nicholl算法及Sobkow—Posp／sil—Yang算法‘等。最近，MichaelDorr对现有的一些线裁剪算法(主要对梁一Barsky算法)进行了整型化一实现。既去掉算法中的除法运算而由乘一个适当的参数来代替。这样可不用浮点运算，从而提高了算法的执行速度。对于凸多边

5、形窗口的线裁剪，唯一著名的算法是由Cyrus~Beck提出的n．车文于1992年5月收到．羽爵童．1961年生，硬士，讲师主要研究方向：计算机田形学．图象赴理盈CAD等．捌桂芳，1943年生，讲师，主要研究方向：计算机图形学、算法分析与设计厦管理系统研究等．、维普资讯http://www.cqvip.com270计算机辅助设计与图形学学报1993担它通过判断直线段的方向矢量与窗I：1边法矢量的点积是否大于零而将所有交点分为上、下两组，然后，分别取上组中的最小交点和下组中的最大交点，即为线段可见部分的端点。但对于凹多边形窗I：1，这样的分组是没有意义的，它不能说明任何问题，所以Cyrus—

6、Beck算法只适用于凸多边形窗I：1的线裁剪。对于凹多边形窗I：1的线裁剪，目前尚未出现有效的算法．但就其意义及作用来说却是很重要的，有广泛的应用前景，如处理图形的反走样、真实感图形显示中阴影及纹理的产生等。而最典型的应用是在图形的消隐处理中，如被一个带内孔物体遮挡的另一物体的显示或被若干物体遮挡的另一物体的显示。其实，对被一个不带内孔的物体遮挡的另一物体的显示也同样属于裁剪问题，只不过是外裁剪。但是，所有的内裁剪(通常所称的裁剪)算法几乎都可用于外裁剪，只是这时在窗I：1外的图形是可见的，而在窗I：1内的图形是不可见的。正如T．Pavlidis在参考文献【9]中所指出的那样：由于实际应

7、用中所遇到的多顶点多边形中大多数不是凸的，因此，这方面的高效率的算法只有当它们可应用于非凸多边形窗I：1时才有意义。对于这个问题的解决，理论上可行的途径是将凹多边形分解成多个凸多边形，然后逐一进行裁剪。但是，这个过程非常复杂并且计算量大，因此其速度慢，效率低。目前尚未在文献中发现这种方法的典型应用．本文提出一个适用于一般多边形窗口(包括凹多边形窗口)的线裁剪算法。它无需将凹多边形分解，也不需进行窗I：1的凸凹性检查。也就是说，对于矩