裁剪算法详解
在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。
(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 8
int encode(float x,float y)
{ int c=0;
if(x if(x>XR) c|=RIGHT; if(x if(x 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在窗口外, 情况4 Intersect (S, P, ClipBoundary, &ip); Output (ip, OutLength, OutVertexArray); Output (P, OutLength, OutVertexArray); } } else if (Inside (S, WindowsBoundary)) { //S在窗口，P在窗口外,情况3 Intersect (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)； } } 裁剪算法详解 在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (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 名词解释 将图形描述转换成用像素矩阵表示的过程称为扫描转换。 1．图形 2．像素图 3．参数图 4．扫描线 5．构造实体几何表示法 6．投影 7．参数向量方程 8．自由曲线 9．曲线拟合 10．曲线插值 11．区域填充 12．扫描转换 三、填空 1．图形软件的建立方法包括提供图形程序包、和采用专用高级语言。 2．直线的属性包括线型、和颜色。 3．颜色通常用红、绿和蓝三原色的含量来表示。对于不具有彩色功能的显示系统，颜色显示为。 4．平面图形在内存中有两种表示方法，即和矢量表示法。 5．字符作为图形有和矢量字符之分。 6．区域的表示有和边界表示两种形式。 7．区域的内点表示法枚举区域内的所有像素，通过来实现内点表示。 8．区域的边界表示法枚举区域边界上的所有像素，通过给赋予同一属性值来实现边界表示。 9．区域填充有和扫描转换填充。 10．区域填充属性包括填充式样、和填充图案。 11．对于图形，通常是以点变换为基础，把图形的一系列顶点作几何变换后， 连接新的顶点序列即可产生新的变换后的图形。 12．裁剪的基本目的是判断图形元素是否部分或全部落在之内。 13．字符裁剪方法包括、单个字符裁剪和字符串裁剪。 14．图形变换是指将图形的几何信息经过产生新的图形。 15．从平面上点的齐次坐标，经齐次坐标变换，最后转换为平面上点的坐标，这一变换过程称为。 16．实体的表面具有、有界性、非自交性和闭合性。 17．集合的内点是集合中的点，在该点的内的所有点都是集合中的元素。 18．空间一点的任意邻域内既有集合中的点，又有集合外的点，则称该点为集合的。 19．内点组成的集合称为集合的。 20．边界点组成的集合称为集合的。 21．任意一个实体可以表示为的并集。 22．集合与它的边界的并集称集合的。 23．取集合的内部，再取内部的闭包，所得的集合称为原集合的。 24．如果曲面上任意一点都存在一个充分小的邻域，该邻域与平面上的（开）圆盘同构，即邻域与圆盘之间存在连续的1-1映射，则称该曲面为。 25．对于一个占据有限空间的正则（点）集，如果其表面是，则该正则集为一个实体（有效物体）。 26．通过实体的边界来表示一个实体的方法称为。 27．表面由平面多边形构成的空间三维体称为。 28．扫描表示法的两个关键要素是和扫描轨迹。 29．标量：一个标量表示。 30．向量：一个向量是由若干个标量组成的，其中每个标量称为向量的一个分量。 四、简答题 1. 什么是图像的分辨率？ 《计算机图形学》实验报告 学院：理学院专业：信息与计算科学班级：姓名学号指导教师实验时间 4. 实验地点计算机实验室成绩实验项目名称裁剪 实 验 环 境 VC++ 6.0 实 验内容 （1）理解直线裁剪的原理（Cohen-Surtherland算法、梁友栋算法） （2）利用VC+OpenGL实现直线的编码裁剪算法，在屏幕上用一个封闭矩形裁剪任意一条直线。 （3）调试、编译、修改程序。 实验原理编码裁剪算法的主要思想是：对于每条线段，分为三种情况处理。（1）若线段完全在窗口之内，则显示该线段，称为“取”；（2）若线段明显在窗口之外，则丢弃该线段，称为“弃”；（3）若线段既不满足“取”的条件，也不满足“舍”的条件，则把线段分割为两段。其中一段完全在窗口之外，可弃之；对另一段则重复上述处理 实验过程#include } struct Rectangle { float xmin,xmax,ymin,ymax; }; Rectangle rect; int x0,y0,x1,y1; int CompCode(int x,int y,Rectangle rect) { int code=0x00; if(y 实验二图形的几何变换的实现算法 班级 08 信计 学号 59 姓名 _____ 分数 _____ 一、 实验目的和要求： 1、 掌握而为图形的基本几何变换，如平移，旋转，缩放，对称，错切变换；＜ 2、 掌握OpenG 冲模型变换函数，实现简单的动画技术。 3、 学习使用OpenGL 生成基本图形。 4、 巩固所学理论知识，加深对二维变换的理解，加深理解利用变换矩阵可 由简单图形得到复杂图形。加深对变换矩阵算法的理解。 编制利用旋转变换绘制齿轮的程序。编程实现变换矩阵算法，绘制给出形体 的三视图。调试程序及分析运行结果。要求每位学生独立完成该实验，并上传实 验报告。 二、 实验原理和内容： .原理： 图像的几何变换包括：图像的空间平移、比例缩放、旋转、仿射变换和图像插值。 图像几何变换的实质：改变像素的空间位置，估算新空间位置上的像素值。 图像几何变换的一般表达式：［u,v ］=［X （x, y ）,Y （x, y ）］，其中，［u,v ］为变换后图像 像素的笛卡尔坐标， ［x, y ］为原始图像中像素的笛卡尔坐标。这样就得到了原始图像与变 换后图像的像素的对应关系。 平移变换：若图像像素点（x, y ）平移到（x x 。，y ■ y 。），则变换函数为 u = X （x, y ） =x 沟， v 二丫（x, y ） = y ■ y 。，写成矩阵表达式为: 比例缩放：若图像坐标 （x,y ）缩放到（S x ，s y ）倍，则变换函数为: S x ,S y 分别为x 和y 坐标的缩放因子，其大于1表示放大, 小于1表示缩小。 旋转变换：将输入图像绕笛卡尔坐标系的原点逆时针旋转 v 角度，则变换后图像坐标为: u COST 内容： :u l :Sx k ；0 其中，x 0和y 0分别为x 和y 的坐标平移量。 其中, 实验二 直线的生成算法的实现 班级 08信计2班 学号 59 姓名 分数 一、实验目的和要求 1.理解直线生成的基本原理。 2.掌握几种常用的直线生成算法。 3.利用Visual C++实现直线生成的DDA 算法。 二、实验内容 1.了解直线的生成原理，尤其是Bresenham 画线法原理。 2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。 3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。 三、实验步骤 1.直线的生成原理： （1）DDA 画线法也称数值微分法，是一种增量算法。是一种基于直线的微分方程来生成直线的方法。 （2）中点画线法原理 以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01 之间。中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最近者已经确定为(,)p p P x y ，用小实心圆表示。那么，下一个与直线最近的像素只能是正右方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。又假设Q 是理想直线与垂直线1p x x =+的交点。显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。 （3）B resenham 画线法原理 直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。 给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为： 0b kx y y)F(x,=--= （3-1） 构造中点偏差判别式d 。 b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),( 计算机科学与技术学院 2013－2014学年第一学期《计算机图形学》实验报告 班级： 学号： 姓名： 教师： 成绩： 实验项目（3、二维裁剪） 一、 实验目的与要求 （1） 掌握线段裁剪算法原理，并实现其算法。 （2） 理解多边形裁剪、字符裁剪算法思想，能编程实现其算法。 二、 实验内容 设计菜单程序，利用消息处理函数，完成以下要求： （1） 实现直线段的标号法（Cohen-Sutherland ）、矩形窗口裁剪算法。 （2） 参考教材中的算法，用矩形窗口实现多边形的Sutherland-Hodgman 裁剪算法。 三、 重要算法分析 以下分析Cohen-Sutherland 和Sutherland-Hodgma n 两个算法，其中Cohen-Sutherland 算法的基本思想通过编码的方法快速实现对直线段的裁剪；Sutherland-Hodgman 算法基本思想是用窗口的四条边所在的直线依次来裁剪多边形。 （一） Cohen-Sutherland 算法 该算法的基本思想是：对于每条待裁剪的线段P 1,P 2分三种情况处理： (1) 若P 1P 2完全在窗口内，则显示该线段。 (2) 若P 1P 2完全在窗口外，则丢弃该线段。 (3) 若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段。 1. 编码原则 具体编码过程为将延长线窗口的四条边线（y T 、y B 、x R 、x L ），将二维平面分成九个区域，全为0的区域是裁剪窗口，其中各位编码的定义如下： {T y y other T C >= 10 {B y y other B C <=10 {R x x other R C >= 10 {L x x other L C <=10 按照如上定义，相应区域编码如图1所示。 计算机图形学报告 前言 计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。 其从狭义上是来说是一种研究基于物理定律、经验方法以及认知原理，使用各种数学算法处理二维或三维图形数据，生成可视数据表现的科学。广义上来看，计算机图形学不仅包含了从三维图形建模、绘制到动画的过程，同时也包括了对二维矢量图形以及图像视频融合处理的研究。由于计算机图形学在许多领域的成功运用，特别是在迅猛发展的动漫产业中，带来了可观的经济效益。另一方面，由于这些领域应用的推动，也给计算机图形学的发展提供了新的发展机遇与挑战。 计算机图形学的发展趋势包括以下几个方面： 1、与图形硬件的发展紧密结合，突破实时高真实感、高分辨率渲染的技术难点； 2、研究和谐自然的三维模型建模方法； 3、利用日益增长的计算性能，实现具有高度物理真实的动态仿真； 4、研究多种高精度数据获取与处理技术，增强图形技术的表现； 5、计算机图形学与图像视频处理技术的结合； 6、从追求绝对的真实感向追求与强调图形的表意性转变。 1、三维物体的表示 计算机图形学的核心技术之一就是三维造型三维物体种类繁多、千变万化，如树、花、云、石、水、砖、木板、橡胶、纸、大理石、钢、玻璃、塑料和布等等。因此，不存在描述具有上述各种不同物质所有特征的统一方法。为了用计算机生成景物的真实感图形，就需要研究能精确描述物体特征的表示方法。根据三维物体的特征，可将三维物体分为规则物体和非规则物体两类。 图形裁剪算法 1.实验目的： 理解区域编码 设计直线裁剪算法 编程实现直线裁剪算法 2.实验描述： 设置裁剪窗口坐标为：wxl=250;wxr=850;wyb=250;wyt=450;裁剪前如下图所示： 裁剪后结果为： 3.算法设计： 直线裁剪算法： 假设裁剪窗口是标准矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边组成，如下图所示。延长窗口四条边形成9个区域。根据被裁剪直线的任一端点P(x，y)所处的窗口区域位置，可以赋予一组4位二进制区域码C4C3C2C1。 编码定义规则： 第一位C1：若端点位于窗口之左侧，即X 《计算机图形学实验报告》样例 实验名称：圆周画法的实现 1.实验内容 1.画出圆心坐标为(75,90)和半径为50的红色圆周 2.画出圆心坐标为(‐40,‐80)和半径为60的蓝色圆周 2.程序的基本思路和功能 先用MFC构建界面外观，然后在相应位置分别用Bresenham和DDA编辑画圆的程序然后编译运行。 3.关键代码及说明 void Circle::circleMinPoint(CDC* pDC) { xCenter = (float)(400 + x); yCenter = (float)(300 - y); //绘制圆心 drawCenter(pDC); //r = 50; //设置颜色 color = RGB(red,green,blue); float m_x = 0; float m_y = r; float d = 1.25 - r; circlePoint(m_x,m_y,pDC); while(m_x <= m_y){ if(d<=0){ d = d + 2 * m_x + 3; }else{ d = d + 2 * ( m_x - m_y ) + 5; m_y = m_y - 1; } m_x = m_x + 1; circlePoint(m_x,m_y,pDC); } } void Circle::circleBresenham(CDC* pDC) { //确认圆心坐标 xCenter = (float)(400 + x); yCenter = (float)(300 - y); //绘制圆心 drawCenter(pDC); //r = 50; //设置颜色 color = RGB(red,green,blue); float m_x = 0; float m_y = r; 河南理工大学 万方科技学院 课程设计报告 2011 — 2012学年第二学期 课程名称计算机图形学 设计题目计算机图形学基本算法 演示系统设计 学生姓名 学号 专业班级网络11升—1班 指导教师徐文鹏 2012 年5 月28 日 目录 第1章设计内容与要求 (1) 1.1 总体目标和要求 (1) 1.2内容与要求 (1) 1.2.1 直线的生成 (1) 1.2.2 圆弧的生成 (1) 1.2.3 线段裁剪 (2) 1.2.4 多边形裁剪 (2) 1.2.5 综合 (2) 第2章总体设计 (3) 2.1 Bresenham算法画直线 (3) 2.1.1 Bresenham算法画直线理论基础 (3) 2.1.2 Bresenham算法画直线原理 (3) 2.2 Bresenham算法画圆 (4) 2.2.1 Bresenham算法画圆理论基础 (4) 2.2.2 Bresenham算法画圆原理 (5) 2.3 梁友栋-Barsky算法进行线段裁剪 (6) 2.3.1梁友栋-Barsky算法进行线段裁剪基本原理 (6) 2.4 Sutherland-Hodgman算法进行多边形裁剪 (8) 2.4.1 Sutherland—Hodgman多边形裁剪算法思想 (8) 2.4.2 点在边界内侧的判断方法 (8) 2.4.4 Sutherland-Hodgeman多边形裁剪算法特点 (8) 第3章详细设计 (9) 3.1 Bresenham算法画直线 (9) 3.1.1 Bresenham 算法画线算法具体实现过程 (9) 3.2 Bresenham算法画圆 (9) 3.2.1 Bresenham 算法画圆核心代码 (9) 2.1.1 生成直线的DDA算法 数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。 一、直线DDA算法描述： 设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得 可通过计算由x方向的增量△x引起y的改变来生成直线： 也可通过计算由y方向的增量△y引起x的改变来生成直线： 式(2－2)至(2－5)是递推的。 二、直线DDA算法思想： 选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(x i+1，y i+1)经取整后送到显示器输出，则得到扫描转换后的直线。 之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。 另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。 三、直线DDA算法实现： 1、已知直线的两端点坐标：(x1，y1)，(x2，y2) 2、已知画线的颜色：color 3、计算两个方向的变化量：dx=x2－x1 dy=y2－y1 4、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|) 5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i<=steps；i++) { putpixel(x，y，color)；/*在(x，y)处，以color色画点*/ x=x+xin； y=y+yin； } 五、直线DDA算法特点： 该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 //@brief 浮点数转整数的宏 实现代码 #define FloatToInteger(fNum) ((fNum>0)?static_cast 《计算机图形学》思考练习题 第一章计算机图形学概论 1．比较计算机图形学与图象处理技术相同点和不同点。 计算机图形学是研究怎样用数字计算机生成、处理和显示图形的一门学科。 图像处理技术研究如何对连续图像取样、量化以产生数字图像，如何对数字图像做各种变换以方便处理，如何滤去图像中的无用噪声，如何压缩图像数据以便存储和传输，图像边缘提取，特征增强和提取。 2．列举三个计算机图形的应用实例。 勘探、绘制地形地貌，系统模拟，虚拟现实。辅助教学设计。 3．简述计算机图形学发展动向。 造型技术—真实图形生成技术—人机交互技术—基于网络的图形技术 第二章计算机图形系统概述 1．叙述计算机图形系统的基本功能。 输入、输出、计算、存储、对话 他的基本功能是帮助人们设计、分析、采集、存贮图形、视频甚至音乐等信息。 2．输入设备可有哪几种逻辑功能？请举出各自对应的物理设备。 .定位(locator): 指定一个坐标点。对应的物理设备有鼠标器、键盘、数字化仪、触摸屏等。.笔划(stroke): 指示一个坐标点系列, 如指定一条曲线的控制点等。主要物理设备有数字化仪。.送值(valuator): 输入一个数值。最常用的物理设备是键盘的数字键。 .字符串（string）：输入一个字符串。键盘字母键 .拾取(pick)：各种定位设备 .选择(choise): 鼠标器，数字化仪，键盘功能键等 3．画出图形软件的层次结构及主要组成。 ------------------------------------ | 应用程序| | ---------------------------- | | 图形支撑软件| | | ------------------- | | | 高级语言| | | | ------------ | | | | 操作系统| ------------------------------------ 主要部分：图形核心系统GKS 计算机图形元文件CGM 计算机图形设备接口CGI 程序员层次结构图形系统PHIGS 4．颜色查找表的概念及实现原理。 颜色查找表是一维线性表，其每一项的内容对应一种颜色，它的长度由帧缓存单元的位数决定。实现原理：把颜色码放在一个独立的表中，帧缓存存放的是颜色表中各项的索引值，这样在帧缓存单元的位数不增加的情况下，具有了大范围挑选颜色的能力。 5．光栅扫描显示器结构与工作原理。 简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。 三、新算法设计 1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。 2、主要数据结构 多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示， 一、实验目标 1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想； 2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现； 二、实验内容 本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。 Cohen-sutherland线段裁剪算法思想： 该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。 对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。 Cohen-sutherland线段裁剪算法步骤： 1、分区编码 延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。 四位二进制代码的编码规则是： (1)第一位置1：区域在左边界外侧 (2)第二位置1：区域在右边界外侧 (3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧 裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。 设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。 2、判别 根据C1和C2的具体值，可以有三种情况： （1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。 3、求交点 假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。 为了规范算法，令线段的端点P 1为外端点，如果不是这样，就需要P 1 和P 2 交换端点。 当条件(C1&0001≠0)成立时，表示端点P1位于窗口左边界外侧，按照求交公式，进行对左边界的求交运算。 依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。 求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。 Liang-Barsky线段裁剪算法思想： 我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示： x= x1+ u·（x2-x1）= x1+ u·Δx y= y1+ u·（y2-y1）= y1+ u·Δy0≤u≤1式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xw min， 1、计算机图形学的相关学科有哪些？它们之间的相互关系怎样？ 与计算机图形学密切相关的几门学科有：图像处理、模式识别、计算几何。它们研究的都是与图形图象处理有关的数据模型、图象再现的内容，它们相互结合、相互渗透。 2、图形系统的任务是什么？ 图形系统的任务是：建立数学模型、视像操作、图形显示。 3、计算机图形学的主要研究内容是什么？ 计算机图形学是研究通过计算机将数据转换为图形，并在专门的设备上输出的原理、方法和技术的学科。 4、举出六种你所知道的图形输出设备。 光栅扫描显示器、随机扫描显示器、直视存储管显示器、激光打印机、笔绘仪、喷墨绘图仪、静电绘图仪等。 5、什么叫刷新？刷新频率与荧光物质的持续发光时间的关系如何？ 屏幕上的荧光涂层受到电子束打击后发出的荧光只能维持很短的时间，为了使人们看到一个稳定而不闪烁的图形，整个画面必须在每秒钟内重复显示许多次，这也称为屏幕刷新。 刷新频率与荧光物质的持续发光时间成反比，即荧光物质的持续发光时间越长，刷新频率可以低一些；否则，荧光物质的持续发光时间越短，刷新频率必须高。 6、随机扫描显示器和光栅扫描显示器显示图形有什么不同？它们各自依靠什么对屏幕图形进行刷新的？ 随机扫描显示器显示图形时，电子束的移动方式是随机的,电子束可以在任意方向上自由移动，按照显示命令用画线的方式绘出图形，因此也称矢量显示器。而光栅扫描显示器显示图形时，电子束依照固定的扫描线和规定的扫描顺序进行扫描。电子束先从荧光屏左上角开始，向右扫一条水平线，然后迅速地回扫到左边偏下一点的位置，再扫第二条水平线，照此固定的路径及顺序扫下去，直到最后一条水平线，即完成了整个屏幕的扫描。 随机扫描显示器依靠显示文件对屏幕图形进行刷新；光栅扫描显示器则依靠帧缓存实现对屏幕图形的刷新。 7、光栅扫描显示系统为什么要采用彩色表？隔行扫描的优点是什么？ 对于光栅扫描显示系统，为了显示很多种颜色，帧缓存的容量就要很大。但实际上对一幅具体的画面而言，其使用的颜色数目并不多（几百至几千种）。为了解决帧缓存容量不能过大而又满足实际需要，产生了彩色表。采用彩色表后，一幅画面实际使用的颜色值放入彩色表，而帧缓存各单元保存的不再是相应象素的颜色值，而仅是该象素颜色的一个索引，它是彩色表的某个入口地址。 隔行扫描只需用逐行扫描一半的时间就能看见整个屏幕显示，因此隔行扫描技术用于较慢的刷新频率。 实验六二维裁剪算法Cohen_Sutherland的实现 一、实验目的： 理解并掌握直线裁剪算法。使用Visual C++实现二维直线的裁剪的Cohen_Sutherland算法。对窗口进行编码，并实现相应的裁剪函数。 二、实验内容及要求： 1、要求用消息映射的方式，绘制出一个裁剪窗口，大小为200×150象素； 2、按照例程的步骤画出3条典型线段，分别对应于完全在裁剪窗口内、完全在裁剪窗口外、穿过 裁剪窗口三种情况，并按照本实验例程的方法用颜色分别表示出裁剪后的情况； 3、按要求撰写实验报告，写出实验心得，并在实验报告中附上程序的核心算法代码。 三、实验设备： 微机，Visual C++6.0 四、实验内容及步骤： 1、打开VC，新建一个MFC Appwizard项目，选择创建单文档工程（SDI工程）。假设工程名为Clip。 如图1和图2所示。 图1 图2 2、在图2的界面上点击Finish，完成工程的创建。 3、在视图类ClipView中定义变量CRect rect; 用于记录裁剪窗口的位置； 4、在ClipView.cpp文件中定义四个宏，记录裁剪窗口的上下左右四个位置： #define LEFT 100 #define RIGHT 300 #define TOP 150 #define BOTTOM 310 5、在视图类的构造函数中为rect赋值； CClipView::CClipView() { // TODO: add construction code here rect = CRect(LEFT, TOP, RIGHT, BOTTOM); } 6、在视图类（类CFillView中）的OnDraw()函数中绘制裁剪矩形，OnDraw函数的代码如下： void CClipView::OnDraw(CDC* pDC) { CClipDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc); // TODO: add draw code for native data here pDC->Rectangle(&rect); } 7、在视图类（类CFillView中）添加成员函数int Encode(int x, int y)，该函数用于对线段的两个顶点 进行Cohen_Sutherland编码。函数体如下： int CClipView::Encode(int x, int y) { int nCode = 0; if(x < LEFT) nCode = nCode | 0x01; if(x > RIGHT) nCode = nCode | 0x02; if(y > BOTTOM) 、计算机图形学中的图形是指由点、线、面、体等和明暗、灰度（亮度）、色彩等构成的，从现实世界中抽象出来的带有灰度、色彩及形状的图或形。 、一个计算机图形系统至少应具有、、输入、输出、等基本功能。 、常用的字符描述方法有：点阵式、和。 、字符串剪裁的策略包括、和笔划/像素精确度。 、所谓齐次坐标就是用维向量表示一个n维向量。 、投影变换的要素有：投影对象、、、投影线和投影。 、输入设备在逻辑上分成定位设备、描画设备、定值设备、、拾取设备和。 、人机交互是指用户与计算机系统之间的通信，它是人与计算机之间各种符号和动作的。 、按照光的方向不同，光源分类 为：，，。 10、从视觉的角度看，颜色包含3个要素：即、和亮度。 二、单项选择题（每题 2分，共 30 分。请将正确答案的序号填在题后 的括号内） 1、在CRT显示器系统中，（）是控制电子束在屏幕上的运动轨 迹。 A. 阴极 B. 加速系统 C. 聚焦系统 D. 偏转系统 2、分辨率为1024×1024的显示器需要多少字节位平面数为16的帧缓存（） A. 512KB B. 1MB C. 2MB D. 3MB 3、计算机图形显示器一般使用什么颜色模型（） A. RGB B. CMY C. HSV D. HLS 4、下面哪个不属于图形输入设备（） A. 键盘 B. 绘图仪 C. 光笔 D. 数据手套 5、多边形填充算法中，错误的描述是（）。 A. 扫描线算法对每个象素只访问一次，主要缺点是对各种表的维持和排序的耗费较大 B. 边填充算法基本思想是对于每一条扫描线与多边形的交点，将其右方象素取补 C. 边填充算法较适合于帧缓冲存储器的图形系统 D. 边标志算法也不能解决象素被重复访问的缺点 6、 在扫描线填色算法中，扫描线与顶点相交时，对于交点的取舍问题，下述说法正确的是（ ）。 A. 当共享顶点的两条边分别落在扫描线的两边时，交点只算2个 B. 当共享交点的两条边在扫描线的同一边时，若该点是局部最高点取1个 C. 当共享交点的两条边在扫描线的同一边时，若该点是局部最低点取2个 D. 当共享顶点的两条边分别落在扫描线的两边时，交点只算0个 7、在多边形的逐边裁剪法中，对于某条多边形的边(当前处理的顶点为P ，先前已处理的多边形顶点为S)与某条裁剪线(窗口的某一边)的比较结果共有以下四种情况，分别需输出一些顶点。请问哪种情况下输出的顶点是错误的（ ） A. S 和P 均在可见的一侧，则输出点P B. S 和P 均在不可见的一侧，则输出0个顶点 C. S 在可见一侧，P 在不可见一侧，则输出线段SP 与裁剪线的交点和点S D. S 在不可见的一 侧，P 在可见的一侧，则输出线段SP 与裁剪 线的交点和P 8、使用下列二维图形变换矩阵：，将产生变换的结果为（ ）。 A. 图形放大2倍 B. 图形放大2倍，同时沿X 、Y 坐标轴方向各移动1个绘图单位 C. 沿X 坐标轴方向各移动2个绘图单位 ?? ??? ?????=111010002T 《计算机图形学》课程教学大纲 一、课程基本信息 课程代码：110053 课程名称：计算机图形学 英文名称：Computer Graphics 课程类别：专业课 学时：72 学分：3.5 适用对象：信息与计算科学专业本科生 考核方式：考试（平时成绩占总成绩的30%） 先修课程：高级语言程序设计、数据结构、高等代数 二、课程简介 中文简介： 计算机图形学是研究计算机生成、处理和显示图形的学科。它的重要性体现在人们越来越强烈地需要和谐的人机交互环境：图形用户界面已经成为一个软件的重要组成部分，以图形的方式来表示抽象的概念或数据已经成为信息领域的一个重要发展趋势。通过本课程的学习，使学生掌握计算机图形学的基本原理和基本方法，理解图形绘制的基本算法，学会初步图形程序设计。 英文简介： Computer Graphics is the subject which concerned with how computer builds， processes and shows graphics. Its importance has been shown in people’s more and more intensively need for harmony human-machine interface. Graphics user interface has become an important part of software. It is a significant trend to show abstract conception or data in graphics way. Through the learning of this course, students could master Computer Graphics’basic theories and methods，understand graphics basic algorithms and learn how to design basic graphics program. 三、课程性质与教学目的 《计算机图形学》是信息与计算科学专业的一门主要专业课。通过本课程的学习，使学生掌握基本的二、三维的图形的计算机绘制方法，理解光栅图形生成基本算法、几何造型技术、真实感图形生成、图形标准与图形变换等概念和知识。学会图形程序设计的基本方法，为图形算法的设计、图形软件的开发打下基础。 四、教学内容及要求 第一章绪论 (一)目的与要求计算机图形学裁剪算法详解
计算机图形学试题附答案完整版
计算机图形学裁剪
计算机图形学图形的几何变换的实现算法
计算机图形学 直线的生成算法的实现
计算机图形学实验报告-二维裁剪
计算机图形学课程总结
计算机图形学_实验报告三_图形裁剪算法
计算机图形学 圆周算法的实现
梁友栋-Barsky直线裁剪算法计算机图形学课程设计
计算机图形学常用算法及代码大全
计算机图形学
计算机图形学(简单多边形裁剪算法)
计算机图形学裁剪算法
计算机图形学复习题
计算机图形学 二维裁剪算法Cohen_Sutherland的实现
《计算机图形学》试卷及答案
《计算机图形学》课程教学大纲
相关主题
文本预览