计算机图形学之裁剪算法

基本图形生成算法原理(四)第三章本章内容一、点、直线段生成二、曲线的生成三、区域填充算法四、线宽与线型的处理五、字符及汉字生成六、二维图形裁剪六、二维图形裁剪图形坐标系统

点的裁剪直线线段的裁剪多边形的裁剪字符的裁剪

几何物体具有很多重要的性质，如大小、形状、位置、方向以及相互之间的空间关系等。为了描述、度量、分析上述特性，需要定义一个参考框架，该参考框架称为坐标系统。

计算机图形坐标系统建立了图形与数据之间的对应联系。（一）图形坐标系统设备坐标系（Devicecoordinatesystem--DC）

与图形设备相关联的坐标系叫设备坐标系。世界坐标系(用户坐标系）（WorldCoordinateSystem--WC）

世界坐标系通常为直角坐标系，一般由用户选定，与机器设备无关。用户在使用图形系统创建或定义图形时，都用自己熟悉的坐标系，即用户坐标系来描述图形数据。如常用的图幅坐标系、大地坐标系等。1、常用坐标系

局部坐标系又称为符号坐标系，是在定义图形时，采用相对于物体的坐标系，使图形描述简单。规格化设备坐标系(NormalDeviceCoordinatesSystem--NDC）

把各个设备坐标系的数据经过变换转化为统一的数据范围就得到规格化的设备坐标系。对于具有多种图形设备的图形处理系统，采用该坐标系是可以简化图形数据的处理。局部坐标系

(LocalCoordinatesSystem--LC）2、几个基本概念用户域----由用户定义的描述图形的整个自然空间。窗口区----由用户指定的用户域中的某个矩形区域。

用户域是指用户在世界坐标系中定义的描述图形区域，是连续无限的实数域；用户在用户域中指定的一个矩形范围称为窗口区或窗口。窗口区小于或等于用户域。屏幕域----设备输出图形的最大区域。视图区----设定的小于或等于屏幕域的矩形区域。

屏幕域是在设备坐标系中定义设备输出图形的最大区域，是有限的整数域；用户在屏幕域中指定的一个矩形范围称为视图区或视口。视口小于或等于屏幕域，是用设备坐标来定义的。

视图区一般为矩形。在一个屏幕上，可以定义多个视图区，作为不同的应用。如在交互式图形系统中，屏幕分为几个区，可分别用于图形显示、放置菜单、工具条、提示信息、备注等。12341、主菜单区2、工具条3、图形显示区4、提示信息区（xw1，yw1）ywxwLwHW窗口坐标Windowxvyv（xv1，yv1）LVHV视口坐标Viewport变换公式：3、窗口到视口的变换图形裁剪：

确定并提取出在指定区域（裁剪窗口）内部的图形对象（裁剪对象）的过程。即从数据集合中抽取部分数据（子集）的过程。裁剪过程：

判断图形对象与裁剪窗口之间的关系并找出其位于窗口内部（或外部）的部分。图形裁剪的概念裁剪窗口：1、矩形窗口：由上（Top）、下（Bottom）、左（Left）、右（Right）四条边界围成。用其左下角点（XL，YB）和右上角点（XR，YT）来定义。2、多边形窗口：由窗口多边形的顶点坐标串来定义。即

判断点P（x，y）在裁剪窗口(矩形)内（可见）、或在窗口外（不可见）。（二）点的裁剪判别式：≤≤≤≤（三）直线线段的裁剪直线段与窗口的位置关系：

完全可见完全不可见部分可见通过对线段端点的判别，确定线段与窗口的位置关系，并找出线段在窗口内（或外）的部分。裁剪方法：

编码裁剪法

中点裁剪法矢量裁剪法1、编码裁剪法(Cohen-Sutherland)100110000001010100001010001001000110区域编码：(四位代码)从左到右各位依次表示上、下、右、左。裁剪步骤：第一步计算直线段两端点的编码C1、C2；第二步C1=C2=0000，线段可见，在窗口内；第三步C1ΛC2≠0000，线段不可见，在窗口外；第四步否则，计算线段与窗口边线的交点（求交），将其分为两段，分别重复第一、二、三、四步重新判别，直至结束。100110000001010100001010001001000110求交：通过判断直线段端点的编码值（ClCtCrCb），确定与之相交的是哪条窗口边所在直线？计算交点。特点：1）用编码可快速判断线段--完全可见和显然不可见。2）特别适用两种场合：大窗口场合；窗口特别小的场合。2、中点裁剪法

中点分割裁剪法是将Cohen-Sutherland算法中求线段与窗口边界的交点的过程用折半查找（即求中点）的方法来代替。仍然采用对线段端点进行编码的方式判断完全可见和显然完全不可见的线段，对于与窗口有交点的线段，该算法分别求离两个端点最近（或最远）的可见点。这两个可见点之间的线段即是原线段的可见部分。只需解算不可见端点的最近的可见点。判断中点Pm1如果落在（接近）窗口边上，则确定该中点为最近可见点。裁剪结束。否则，P2P1P1P2（一）直线段P1P2的一个端点可见，另一个端点不可见。计算P1P2的最近可见点Pma和Pmb

：1）设P1不可见，计算P1P2的中点Pm1。如果Pm1可见，以Pm1取代P2，返回到1）计算P1Pm1的中点Pm2，判断Pm22）判断Pm1是否可见：如果Pm1不可见，以Pm1取代P1，返回到1）计算Pm1P2的中点Pm2，判断Pm2Yes,则P1P2为不可见线段，结束。No,将两线段中为非显然不可见的线段取代

P1P2，并返回到1）重新判别计算。P2P1P1P2（二）直线段P1P2的两个端点都不可见。计算P1P2的最近可见点Pma和Pmb

：1）计算P1P2的中点Pm。如果Pm可见，将P1P2分为两段：P1Pm和PmP2，分别按（一）中的方法解算出各自的最近可见点。2）判断Pm是否可见：如果Pm不可见，判断线段P1Pm和PmP2是否为显然不可见。两种线段裁剪算法的比较

Cohen-Sutherland算法是最早的、使用最广泛的线段裁剪算法之一。在裁剪窗口很大，大部分线段完全可见，或裁剪窗口很小，大部分线段完全不可见的情况下，该算法特别有效；在一般情况下，该算法有时要做不必要的求交运算，因而效率不是太高.

中点分割裁剪算法是Cohen-Sutherland算法的硬件版本。该算法只需要做加法和移位，不要做乘除法，用硬件实现既简单又有效。

平面多边形是由若干直线段围成的平面封闭图形。裁剪的结果，应仍是封闭的图形。（四）多边形的裁剪平面多边形和窗口之间的位置关系：

依次用窗口的四条边框所在的直线对多边形进行分步裁剪。逐边裁剪算法（Sutherland-Hodgman）将多边形表示为顶点表，即｛P1，P2，……

Pn-1，Pn

｝,并生成边表P1P2，P2P3，……Pn-1Pn，PnP1。(2)用窗口边裁剪原多边形，生成中间多边形(3)对中间多边形重复步骤(2)，直至被窗口所有边裁剪完为止关键：根据多边形的边表，逐次对每一段边与裁剪线(窗口边直线)比较，判别输入顶点的个数和坐标，并联结成封闭多边形。多边形边与裁剪线相对位置的四种情况与处理方法：(1)位于可见一侧：输出终点作为新多边形顶点(2)位于不可见一侧：不输出(3)由可见到不可见：输出与裁剪线的交点(4)由不可见到可见：输出与裁剪线的交点及终点可见侧不可见侧1423P1P2P3P4P5P6P7P8P’1P2P3P4P5P6P7P8P9P’1P2P’3P4P