图形学之二维裁剪.ppt

《图形学之二维裁剪.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五讲二维裁剪基本目的：判断图形元素是否落在窗口区域之内。显示部分画面，指定图形内容，窗口系统。地图显示。图形编辑图形裁剪算法，直接影响图形系统的效率。2021/7/171GraphicsLab.PKU二维裁剪两个步骤：图元在窗口区域内外的判别；图形元素与窗口的求交；裁剪扫描转换:点阵图形在设备坐标系中进行，算法效率不高，适合求交难度大的图形。裁剪扫描转换:点、线、多边形等简单图形，在世界坐标系中进行。分析裁剪。2021/7/172GraphicsLab.PKU5.1直线段裁剪是基础。裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见

2、；(3)其它提高裁剪效率：快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。点裁剪。2021/7/173GraphicsLab.PKU5.1.2直接求交算法直线与窗口边都写成参数形式，求参数值。2021/7/174GraphicsLab.PKU5.1.3Cohen-SutherLand算法(编码算法)裁剪过程是递归的。由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码CtCbCrCl，上下右左；各位编码含义：上面：ify>ymax,Ct=1,else,0;下面：ify

3、e,0；右面：ifx>xmax,Cr=1,else,0;左面：ifx

4、种情形：大窗口场合；窗口特别小场合(光标拾取图形)，光标看作小的裁剪窗口。2021/7/178GraphicsLab.PKU5.1.4Nicholl-Lee-Nicholl算法消除C-S算法中多次求交的情况。基本想法：对2D平面的更细的划分。2021/7/179GraphicsLab.PKU假定P0点落在区域0，4，52021/7/1710GraphicsLab.PKU步骤：1.区域细分(9个区域)，只考察P0在0，4，5情形，其它类似。2.P0点向窗口的四角点引射线，把平面区域分成4个有意义的区域。判断P1所在区域位置，可判定P0、P1与窗口那

5、条边求交。3.用斜率判P1所在区域4.求交点，确定线段可见部分。特点：效率较高，但仅适合二维矩形窗口。2021/7/1711GraphicsLab.PKU2021/7/1712GraphicsLab.PKU5.1.5中点分割法想法：从P0点出发找出距P0最近的可见点，从P1点出发找出距P1最近的可见点。取中点Pm=(P1+P2)/2。（算法见框图）2021/7/1713GraphicsLab.PKU2021/7/1714GraphicsLab.PKU对分辩率为2N*2N的显示器，上述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现

6、。适合平行计算。2021/7/1715GraphicsLab.PKU5.1.6Liang-Barsky算法看作点集之间的交集，即为裁剪结果。Q0Q1为诱导窗口，一维窗口，二维裁剪简化成一维裁剪。2021/7/1716GraphicsLab.PKU一维裁剪问题P0P1至少部分可见的充要条件是Max(0,t0)<=min(1,t1)且可见部分的参数区间为[Max(0,t0),min(1,t1)]2021/7/1717GraphicsLab.PKU诱导窗口计算：假设直线l与窗口左、右、上、下四边的交点为L，R，T，BP0P1的可见部分VW=P0P1∩L

7、R∩TB这就是二维裁剪问题的解。2021/7/1718GraphicsLab.PKU用参数域方法定可见部分：始边，终边(对窗口边而言)由有向直线段方向定。诱导窗口与P0P1的交点可用直线的参数区间来表示。交点参数的简单确定：用X或Y坐标边的长度比。2021/7/1719GraphicsLab.PKU5.1.7参数化算法(Lyrus-Beck)算法考虑凸多边形区域R和直线段P1P2P1P2=(P2-P1)*t+P1凸多边形的性质：P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有N·(P(t)-A)>02021/7

8、/1720GraphicsLab.PKUAP1P2R2021/7/1721GraphicsLab.PKUk条边的多边形，可见线段参数区间