一般多边形窗口的线裁剪.pdf

维普资讯 第 5卷 第 4期 计算机辅助设计与图形学学报 V01．5．No．4 1993年 10月 Chm．J CAD ＆ CG Oct．．1993 2 一 般多边形窗 口的线裁剪 弋甲 l、。I 刘勇奎 刘桂芳 ’P- _。_～ 。-’-- 。～ 沈阳工业大学计算机学院，沈阳，11(XI21 LINE CLⅡ’PING AGA ST A GENERALIZED POLYGoN Liu Yongkuiand Liu Guifang Compu~ E 9 ∞ 呻‘ Collie,Shen3amoPo icUalver~y,Shenya~,110021 Abst~et Existing lineclipping aglorithn~ aIealloffenxlbased oila rectangularwin- dow orac0nV polygonalwindow．No algorithm forlineclipping based on agencmlimd polygon (orGoncavcpolygon1isavailableintheliterature．It quitevaluabletodevelop suchalgodthn~，bccausctheyaIeofpracticall玛ejustlikethehiddenlineproblem．Inthis paper，a line clipping algorithm based oil a gencraliz~ polygon is presented． The calculation effortofthealgorithm issmal1． ICer~ als Computer graphics，Goric~ ． v~ polygonal window，line c~ppiug，n／teasoction calculating 摘要 已有 的线裁剪算法都是针对矩形窗口或凸多边形窗口的．对于一般的多边形 窗口(包括凹多边形)的线裁剪， 目前尚无有效的算法。 开发这种算法是很必要的，固为它 在计算机图形学中有很广泛的应用，如物体的消隐处理等。 固此，提 出一个对于一般 多 边形窗口的线栽剪算法 并给 出了最优实现。 关羹词芷箜垫里 堂，凹窆 垄查旦，： ，交点计算 一 、 引 言 线裁剪是计算机 图形学中的一个基本操作。目前，对于矩形窗 口的线裁剪 已得到人们 深入的研究，’并 盯现 狲 效的算法，如经典的Cohen—Sutherland算法[11，Spmull和 Sutherland提出的便于硬件实现的中点分割法 ，我国学者梁友栋与 Barsky提出的参数 方 法 ，还有较近期的Nicholl—Lee—Nicholl算法 及 Sobkow—Posps／il—Yang算法 ‘等。最 近，MichaelDorr对现有的一些线裁剪算法 (主要对梁 一Barsky算法)进行了 整型化一实现 。 既去掉算法中的除法运算而 由乘一个适当的参数来代替。这样可不用浮点运算，从而提高了 算法 的执行速度 。对于凸多边形窗 口的线裁剪，唯一著名的算法是 由Cyrus~Beck提出的n ． 车文于 1992