下载文档原格式
实验题目：实验三图形裁剪算法1.实验目的：理解区域编码(Region Code，RC)设计Cohen-Sutherland直线裁剪算法编程实现Cohen-Sutherland直线裁剪算法2.实验描述：设置裁剪窗口坐标为：wxl=250;wxr=850;wyb=250;wyt=450;裁剪前如下图所示：裁剪后结果为：3.算法设计：Cohen-Sutherland 直线裁剪算法：假设裁剪窗口是标准矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边组成，如下图所示。
延长窗口四条边形成 9个区域。
根据被裁剪直线的任一端点 P(x，y)所处的窗口区域位置，可以赋予一组4位二进制区域码C4C3C2C1。
编码定义规则：第一位C1：若端点位于窗口之左侧，即 X<Wxl，则 C1=1，否则 C1=0。
第二位C2：若端点位于窗口之右侧，即 X>Wxr，则 C2=1，否则 C2=0。
第三位C3：若端点位于窗口之下侧，即 Y<Wyb，则 C3=1，否则 C3=0。
第四位C4：若端点位于窗口之上侧，即 Y>Wyt，则 C4=1，否则 C4=0。
裁剪步骤：1. 若直线的两个端点的区域编码都为0，即 RC1|RC2=0（二者按位相或的结果为0，即 RC1=0 且RC2=0），说明直线两端点都在窗口内，应“简取”。
2. 若直线的两个端点的区域编码都不为0，即 RC1&RC2≠0（二者按位相与的结果不为0，即 RC1≠0且 RC2≠0，即直线位于窗外的同一侧，说明直线的两个端点都在窗口外，应“简弃”。
3. 若直线既不满足“简取”也不满足“简弃”的条件，直线段必然与窗口相交，需要计算直线与窗口边界的交点。
交点将直线分为两段，其中一段完全位于窗口外，可“简弃”。
对另一段赋予交点处的区域编码，再次测试，再次求交，直至确定完全位于窗口内的直线段为止。
4. 实现时，一般按固定顺序左（x=wxl）、右（x=wxr）、下（y=wyb）、上（y=wyt）求解窗口与直线的交点。
实验2使用线段剪裁Cohen——sutherland算法一．实验目的及要求根据Cohen——sutherland算法，掌握直线剪裁的程序设计方法。
注意，不能使用语言库中的画圆函数。
二．理论基础将不需要裁剪的直线挑出，并删去其中在窗外的直线，然后对其余直线，逐条与窗框求交点，并将窗框外的部分删去。
采用Cohen-Sutherland直线剪裁的算法一区域编码为基础，将窗口及周围的八个方向以4位的二进制数进行编码。
4个位分代表窗外上，下，左右的编码值。
三、算法分析1. Cohen—SutherLand直线裁剪算法裁剪的实质，就是决定图形中那些点、线段、文字、以及多边形在窗口之内。
Cohen—SutherLand直线裁剪算法的基本大意是：对于每条线段P1P2，分为三种情况处理。
1) 若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之。
2) 若P1P2明显在窗口外，则丢弃该线段P1P2，简称“弃”之。
3) 若线段既不满足“取”的条件，也不满足“弃”的条件，则把线段分为两段。
其中一段完全在窗口外，可弃之。
然后对另一段重复上述处理。
为了使计算机能够快速地判断一条线段与窗口属何种关系，采用如下的编码方法。
延长窗口的边，把未经裁剪的图形区域分为9个区，每个区具有一个四位代码，即四位二进制数，从左到右各位依次表示上、下、左、右。
裁剪一条线段时，先求出端点P1P2所在的区号code1和code2。
若code1=0且code2=0，则说明P1和P2均在窗口内，那么整条线段也比在窗口内，应取之。
若code1和code2经按位与运算后的结果code1&code2不为0，则说明两个端点同在窗口的上方、下方、左方或右方。
若上述两种条件均不成立，则按第三种情况处理，求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。
再对另一段重复进行上述处理。
计算线段与窗口边界（或其延长线）的交点，属于线段与直线求交问题。
vatti裁剪算法Vatti裁剪算法是计算机图形学中非常重要的一种算法，它可以对图形进行裁剪以避免渲染过多无用区域，提高图形渲染效率。
下面，我将详细介绍Vatti裁剪算法的原理及其使用方法。
一、概述Vatti裁剪算法最初由Vatti在1984年提出，并在1992年得到了完整的形式化描述。
该算法主要用于多边形裁剪，它将多边形的裁剪视为一系列直线段的计算，从而避免了复杂的多边形运算，减少了计算量。
二、原理Vatti裁剪算法的原理可以简单概括为：将裁剪区域表示为一系列半平面的交集，将多边形表示为一系列线段的并集，然后对这两个集合进行运算，得到裁剪后的多边形。
具体来说，Vatti裁剪算法主要分为两个阶段：首先将裁剪区域表示为n个闭合的凸多边形的交集，然后将多边形分解为线段，并依次对每个线段进行裁剪运算。
1. 裁剪区域的表示a. 输入：在平面上给出n个凸多边形，表示为每个多边形的顶点。
b. 输出：一个表示裁剪区域的半平面集合。
c. 算法步骤：(1) 将每个凸多边形表示为一系列有向线段。
(2) 对每个有向线段Si，计算其左侧半平面：对于多边形中的每个顶点Vj，如果它在Si的左侧，则计算对应的另一个有向线段S'j，使得S'j与Si组成一个包含多边形的半平面。
(3) 重复步骤2，以便得到n个半平面。
(4) 对这n个半平面进行交集运算，得到裁剪区域。
2. 多边形裁剪a. 输入：一个表示多边形的线段集合，以及表示裁剪区域的半平面集合。
b. 输出：裁剪后的多边形。
c. 算法步骤：(1) 将多边形表示为一系列线段的并集。
(2) 对于每条线段Si，计算其与半平面集合的交集。
(3) 将线段的交集组成一个新的集合S'，作为裁剪后的多边形。
三、使用方法1. 准备工作在进行Vatti裁剪算法之前，需要准备好多边形的顶点和裁剪区域的半平面集合。
多边形的顶点可以通过手动或程序计算得到，而裁剪区域的半平面集合则需要根据具体需求进行计算。
计算机图形学的裁剪算法
计算机图形学的裁剪算法是图形学的一种重要算法，它的基本思想是将一个完整的几何图形（如线段、多边形、圆圈等）按照指定的裁剪窗口（矩形）进行裁剪，只保留在窗口内的部分，而把窗口外的部分抛弃掉。
由于裁剪算法的应用非常广泛，像图形显示系统、图形设备接口（GDI）和图形处理器（GPU）等都广泛使用裁剪算法。
计算机图形学的裁剪算法可以分为两种：2D裁剪算法和
3D裁剪算法。
2D裁剪算法是基于二维空间的，它将一个几何
图形投影到一个平面上，然后按照指定的窗口裁剪；而3D裁
剪算法是基于三维空间的，它将一个几何图形投影到一个三维空间，然后按照指定的窗口裁剪。
2D裁剪算法的基本步骤如下：首先，将要裁剪的几何图
形投影到平面上；其次，计算出投影后的几何图形以及裁剪窗口之间的交点；最后，将裁剪窗口内的部分保留，而把窗口外的部分抛弃掉。
3D裁剪算法的基本步骤如下：首先，将要裁剪的几何图
形投影到三维空间；其次，计算出投影后的几何图形以及裁剪窗口之间的交点；最后，将裁剪窗口内的部分保留，而把窗口外的部分抛弃掉。
计算机图形学的裁剪算法在图形处理中有着重要的作用，它不仅能够有效减少图形处理时间，而且还可以节约存储空间。
此外，它还可以有效提高图形处理效率，提高图形显示效果。
但是，它也存在着一定的局限性，比如，当几何图形的运动变得复杂时，它就会变得费时费力，这就对性能产生了一定的影响。
总之，计算机图形学的裁剪算法是图形学的重要算法，它的应用非常广泛，在图形处理中有着重要的作用。
虽然它也存在着一定的局限性，但是它仍然是一种有效的图形处理算法。
裁剪算法详解在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。
因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。
这个选择过程称为裁剪。
最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。
但那样太费时，一般不可取。
这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。
所以一般采用先裁剪再扫描转换的方法。
(a)裁剪前 (b) 裁剪后图1.1 多边形裁剪1直线段裁剪直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。
因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。
常用的线段裁剪方法有三种：Cohen-Sutherland,中点分割算法和梁友栋－barskey 算法。
1.1 Cohen-Sutherland裁剪该算法的思想是：对于每条线段P1P2分为三种情况处理。
（1）若P1P2完全在窗口，则显示该线段P1P2简称“取”之。
（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。
（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。
其中一段完全在窗口外，可弃之。
然后对另一段重复上述处理。
为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。
延长窗口的边，将二维平面分成九个区域。
每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下：图1.2 多边形裁剪区域编码图5.3线段裁剪裁剪一条线段时，先求出P1P2所在的区号code1,code2。
若code1=0,且code2=0，则线段P1P2在窗口，应取之。
若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。
可判断线段完全在窗口外，可弃之。
否则，按第三种情况处理。
求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。
在对另一段重复上述处理。
在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。
Cohen-Sutherland裁减算法#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8int encode(float x,float y){ int c=0;if(x<XL) c|=LEFT;if(x>XR) c|=RIGHT;if(x<YB) c|=BOTTOM;if(x<YT) c|=TOP;retrun c;}void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;//(x1,y1)(x2,y2)为线段的端点坐标，其他四个参数定义窗口的边界{ int code1,code2,code;code1=encode(x1,y1);code2=encode(x2,y2);while(code1!=0 ||code2!=0){ if(code1&code2 !=0) return;code = code1;if(code1==0) code = code2;if(LEFT&code !=0){ x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);}else if(RIGHT&code !=0){ x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);}else if(BOTTOM&code !=0){ y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);}else if(TOP & code !=0){ y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);}if(code ==code1){ x1=x;y1=y; code1 =encode(x,y);}else{ x2=x;y2=y; code2 =encode(x,y);}}displayline（x1,y1,x2,y2);}1.2 中点分割裁剪算法中点分割算法的大意是，与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。
对前两种情况，进行一样的处理。
对于第三种情况，用中点分割的方法求出线段与窗口的交点。
即从p0点出发找出距p0最近的可见点A和从p1点出发找出距p1最近的可见点B，两个可见点之间的连线即为线段p0p1的可见部分。
从p0出发找最近可见点采用中点分割方法：先求出p0p1的中点pm,若p0pm 不是显然不可见的，并且p0p1在窗口中有可见部分，则距p0最近的可见点一定落在p0pm上，所以用p0pm代替p0p1；否则取pmp1代替p0p1。
再对新的p0p1求中点pm。
重复上述过程，直到pmp1长度小于给定的控制常数为止，此时pm 收敛于交点。
由于该算法的主要计算过程只用到加法和除2运算，所以特别适合硬件实现，同时也适合于并行计算。
图5.4 A、B分别为距p0、p1最近的可见点，Pm为p0p1中点1.3梁友栋－Barskey算法梁友栋和Barskey提出了更快的参数化裁剪算法。
首先按参数化形式写出裁剪条件：这四个不等式可以表示为形式：其中，参数p k,q k定义为：任何平行于裁剪边界之一的直线p k=0，其中k对应于裁剪边界（k=1,2,3,4对应于左、右、下、上边界）如果还满足q k<0，则线段完全在边界外，舍弃该线段。
如果q k≥0，则该线段平行于裁剪边界并且在窗口。
当p k<0,线段从裁剪边界延长线的外部延伸到部。
当p k>0,线段从裁剪边界延长线的部延伸到外部。
当p k≠0，可以计算出线段与边界k的延长线的交点的u 值：u=q k/p k对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形的线段部分。
u1的值由线段从外到遇到的矩形边界所决定（p<0）。
对这些边界计算r k=q k/p k。
u1取0和各个r k值之中的最大值。
u2的值由线段从到外遇到的矩形边界所决定（p>0）。
对这些边界计算r k=q k/p k。
u2取1和各个r k值之中的最小值。
如果u1>u2，则线段完全落在裁剪窗口之外，被舍弃。
否则裁剪线段由参数u的两个值u1,u2计算出来。
void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;{ float dx,dy,u1,u2;tl=0;tu=1;dx =x2-x1;dy =y2-y1;if(ClipT(-dx,x1-Xl,&u1,&u2)if(ClipT(dx,XR-x1, &u1,&u2)if(ClipT(-dy,y1-YB, &u1,&u2)if(ClipT(dy,YT-y1, &u1,&u2){ displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy)return;}}bool ClipT(p,q,u1,u2)float p,q,*u1,*u2;{ float r;if(p<0){ r=q/p;if(r>*u2)return FALSE; else if(r>*u1){ *u1=r;return TRUE;}}else if(p>0){ r=p/q;if(r<*u1) return FALSE;else if(r<*u2){ *u2=r;return TRUE;}}else if(q<0) return FALSE;return TRUE;}2 多边形裁剪对于一个多边形，可以把它分解为边界的线段逐段进行裁剪。
但这样做会使原来封闭的多边形变成不封闭的或者一些离散的线段。
当多边形作为实区域考虑时，封闭的多边形裁剪后仍应当是封闭的多边形，以便进行填充。
为此，可以使用Sutherland-Hodgman算法。
该算法的基本思想是一次用窗口的一条边裁剪多边形。
算法的每一步，考虑窗口的一条边以及延长线构成的裁剪线。
该线把平面分成两个部分：一部分包含窗口，称为可见一侧；另一部分称为不可见一侧。
依序考虑多边形的各条边的两端点S、P。
它们与裁剪线的位置关系只有四种。
(1)S,P 均在可见一侧（2）S,P均在不可见一侧(3)S可见,P不可见(4)S不可见,P可见。
图1.3 S、P与裁剪线的四种位置关系每条线段端点S、P与裁剪线比较之后，可输出0至两个顶点。
对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。
对于每一条裁剪边，算法框图一样，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。
基于divide and conquer策略的Sutherland-Hodgman算法typedef struct{ float x; float y; }Vertex;typedef Vertex Edge[2];typedef Vertex VertexArray[MAX];SutherlandHodgmanClip（VertexArray InVertexArray, VertexArray OutVertexArray, edge ClipBoundary, int &Inlength, int &Outlength）{ Vertex s, p, ip;int j;Outlength = 0;S = InVertexArray [InLength -1];For (j = 0; j < Inlength; j++){P = InVertexArray [j];if(Inside (P, ClipBoundary)){ if(Inside (S, ClipBoundary)) //SP在窗口，情况1 Output(p, OutLength, OutVertex Array)else{ //S在窗口外, 情况4Intersect (S, P, ClipBoundary, &ip);Output (ip, OutLength, OutVertexArray);Output (P, OutLength, OutVertexArray);}}else if (Inside (S, WindowsBoundary)){ //S在窗口，P在窗口外,情况3Intersect (S, P, ClipBoundary, &ip);Output (ip, OutLength, OutVertexArray);} //情况2没有输出S = P;}}//判点在窗口bool Inside (Vertex &TestPt, Edge ClipBoundary){ if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边if(testpt.y>= ClipBoundary[0].y)return TRUE;else if(ClipBoundary[1].x< ClipBoundary[0].x) //裁剪边为窗口上边if(testpt.y<= ClipBoundary[0].y)return TRUE;else if(ClipBoundary[1].y> ClipBoundary[0].y) //裁剪边为窗口右边 if(testpt.x<= ClipBoundary[0].x)return TRUE;else if(ClipBoundary[1].y< ClipBoundary[0].y) //裁剪边为窗口左边 if(testpt.x>= ClipBoundary[0].x)return TRUE;Return FALSE;}//直线段SP和窗口边界求交，返回交点；void Intersect (Vertex&S,Vertex &P,Edge ClipBoundary,Vertex& IntersectPt){ if(ClipBoundary[0].y== ClipBoundary[1].y)//水平裁剪边{ IntersectPt.y = ClipBoundary[0].y;IntersectPt.x = S.x+( ClipBoundary[0].y -s.y)*(p.x - s.x) / (p.y - s.y);}else //垂直裁剪边{ Intersect.x = ClipBoundary[0].x;Intersect.y = s.y + (ClipBoundary[0].x - s.x)*(p.y - s.y) / (p.x. - s.x)；}}。
