基于直线斜率的凸多边形线裁剪算法.docVIP

基于直线斜率的凸多边形线裁剪算法 第22卷第8期 2005年8月 计算机应用与软件 ComputerApplicationsandSoftware Vo1.22,No.8 Aug.2005 基于直线斜率的凸多边形线裁剪算法 唐棣单会秋 (辽宁师范大学计算机科学系辽宁大连116029) 摘要凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,现在的许多领域均有很重要的应用.本文提出了一种 非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较.结果表明:本算法更加简单,高效. 关键词凸多边形斜率线裁剪法矢量 LINECLIPPlNGALGoRITl1[ToNCONVEXP0LYGoNBASEDoNLINE’SSLoPE TangDiShanHuiqiu (DepartmentofComputerScanCe.LiaoningNormalUniversit),DalianLiaoning116029,China) AbstractThelineclippingonconvexpolygonhasanimportantstatusinComputerGraphics,andisbeingusedinmanyfields.Thistext putsforwardaveryeffectiveclippingalgorithmbasedonline’Sslope,andcomparesitwithCyrus—BerkAlgorithmTheresultindicatesthatit issimplerandmoreeffective. KeywordsConvexpolygonLineslopeLineclippingNormalvector 1引言 裁剪是计算机图形学的重要内容,是在指定区域内识别图 形内外部分的一个过程.计算机图形学的许多重要操作以它作 为基础.裁剪主要应用在:从定义的场景中抽取出用于观察的 部分;在三维视图中标志需要的可见面;清晰各个对象之问的模 糊边界;用实体造型来创造对象;显示多窗口的环境等等方面. 目前对于二维的矩形窗口的线裁剪已经得到了人们深入的 研究,端点编码算法,Cohen—Suhenerland线段细分裁剪算法以 及中点分割等算法都比较成熟.然而,在许多应用中,裁剪窗口 并非规则矩形.因此,上面所述算法无一适用.对于一般凸多 边形窗口的线裁剪,目前也已有几种算法.其中最着名,最有效 的算法是由Cyrus和Berk提出的Cyrus—Berk算法. 2Cyrus—Berk算法 c,邢一Berk算法通过判断直线段的方向矢量与窗口边法 矢量的点积是否为零而将所有交点分为上下两组.然后,分别 取上组中的最小交点与下组中的最大交点,即为线段可见部分 的端点. 考虑一个凸多边形区域月,被裁 剪线段P.Pz.设/是R边界上的一 点,而,z是该点所处边界的内法线矢 量,如图1所示.线段的参数方程 为: P(t):PI+(P2一P1)}t(0≤￡≤1) 魉图1内法线 矢量的方向 这时连接线段上一点到边界上其它任一点的矢量与内法线 矢量的点积为: n.?[P(t)一]i=1,2,… 当所取参数直线段上的点位于区域之内,区域边界上或区域之 外时,点积的值分别为大于零,等于零和小于零,这一关系式适 用于区域的任意边界.则直线与窗口交点的条件为: n?[P1+(—P1)}t一/=]=0 即:n.?(P1一)+n?(P2一P1)}t=0 设D=P2一P1;W=P1一/= 则:t=.?ni/D?niD≠O,i=1,2,… 若所得的t值位于0≤t≤1之外,则可抛弃.把剩余的t值分为 两组,一组为下限组,分布于线段起始点一侧;另一组为上限组, 分布于线段终点一侧.找出下限组中的最大t值和上限组中的 最小￡值.若D?n.gt;0,侧求下限组中的最大值￡P(￡);相反, 若D?n.lt;0,则求上限组中的最小值t,从P(tL)到P(t)位于 窗口内,是可见线段. 3基于直线斜率的裁剪算法 该算法通过对被裁剪线段所在直线的斜率和凸多边形窗口 各边的斜率之问进行比较,并通过找出线段与凸多边形边界的 真实交点,快速有效地判断出线段对于凸多边形窗口的位置关 系,而裁剪出线段在凸多边形区域内的部分. 3.1算法的基本原理 多边形与线段的基本位置关系只有四种:线段在凸多边形 外,如图2(a);线段在凸多边形内,如图2(b);线段与凸多边形 有一个交点,如图2(C);线段与凸多边形有两个交点如图2 (d). 收稿日期:2004—06—16.唐棣,教授,主研领域:计算ULIE形学的 科研与教学工作. 116计算机应用与软件2005丘 图2线段与凸多边形的基本位置关系 假设凸多边形窗口的顶点为{P}(0≤≤,1),P.=(P,