裁剪算法详解
在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。
(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中点 裁剪算法详解 在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (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 计算机科学与技术学院 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、简述图像处理、模式识别与计算机图形学的关系。 图像处理、模式识别与计算机图形学是计算机应用领域发展的三个分支学科，它们之间有一定的关系和区别，它们的共同之处就是计算机所处理的信息都是与图有关的信息。它们本质上是不同的：图像处理是利用计算机对原存在物体的映象进行分析处理，然后再现图像；模式识别是指计算机对图形信息进行识别和分析描述，是从图形到描述的表达过程；计算机图形学是研究根据给定的描述用计算机生成相应的图形、图像。 计算机图形系统主要具有哪些功能？ 答案：1. 计算功能 2. 存储功能 3. 输入功能 4. 输出功能 5. 交互功能多边形的顶点和点阵表示各有什么优缺点？ 答案：顶点表示是用多边形的顶点序列来描述多边形。该表示几何意义强、占内存少、几何变换方便；但它不能直观地说明哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来描述多边形。该方法虽然没有多边形的几何信息，但便于用帧缓存表示图形，可直接用于面着色。 为什么需要隐藏面消隐算法？ 答： 因为我们在用计算机生成三维物体的真实感图形，必须要做的是确定物体的可见部分，只有 确定了物体的可见部分，我们才能在计算机中真实地再现三维物体。因此，我们就需要一个隐藏面消隐算法来去掉物体的不可见部分，从而避免错误地将不可见部分显示出来，这样就可以在计算机中生成一个三维物体的真实感图形了。 z缓冲器算法是怎么判断哪个面应消隐的？ 答： z缓冲器算法设置了一个二维数组，类似于帧缓冲器。但是z缓冲器存放的是每个象素点的深 度值，而不是帧缓冲器中的颜色值。z缓冲器的初始值为某个大的数值，通常是后裁剪平面的距离。 在判断像素),(yx上的哪个平面更靠近观察者时，就可以简单地比较z缓冲器中的深度值和当前平面的深度值。如果当前平面的值比z缓冲器中的值小（即距视点更近），则用新值替换原z缓冲器中的值，像素的颜色值也变成新平面的颜色值。 颜色的基本特征是什么？ 答：颜色的基本特征是：波长、亮度和饱和度。 波长是依赖于物质的，可见光的波长范围大约是350nm~780nm。 图形裁剪算法 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 河南理工大学 万方科技学院 课程设计报告 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．光栅扫描显示器结构与工作原理。 第一章导论 1 计算机图形学是什么？主要应用领域有哪些？ 2 名词解释：参数法、点阵、图形、图像 4 计算机图形学，图像处理，模式识别这几门学科之间有何关系？ 5 Ivan E. Sutherland对计算机图形学主要有哪些贡献？ 6 阴极射线管主要由哪几部分组成？CRT的工作原理？ 7 名词解释：分辨率、像素、走样 8 名词解释：光栅、荫罩板、三枪三束、扫描线 9 帧缓冲器容量如何计算？若要在800╳600的屏幕分辨率下显示256种灰度图像，帧缓冲器的容量至少应为多少？ 10为什么要制定图形软件标准？经ISO批准的第一个图形软件标准是什么？ 第三章基本图形的扫描转换 1 什么是图形的扫描转换？ 2 简述直线的中点Bresenham算法原理 3 简述1/8圆的中点Bresenham算法原理 3 简述1/4椭圆的中点Bresenham算法原理 第四章多边形填充 1 名词解释：实面积图形、凸多边形、四连通域、八连通域 2 多边形有哪两种表示方法？多边形的扫描转换是什么？ 3 在多边形填充过程中，对边界像素的处理原则是什么？对极值点的处理原则是把它当作几个点计算？ 4 对一个多边形，如何写出每条扫描线的有效边表？ 5 简述多边形的有效边表填充算法中，每一条扫描线的填充步骤 5 简述四邻接点填充算法 第五章 1 规范化齐次坐标的含义 2 二维图形基本几何变换矩阵 3 计算复合变换矩阵（例1、2，习题5.1：1、2） 4 名词解释：窗口、视区、窗视变换 5 叙述Cohen-Sutherland直线段裁剪算法（编码原理、裁剪步骤）参考习题5.2：4 6 简述中点分割直线段裁剪算法 第六章 1 三维基本几何变换矩阵；会求简单的三维复合变换矩阵 2 名词解释：灭点、主灭点；理解一点透视、二点透视、三点透视的概念 第七章 1 简述：拟合、逼近、一阶参数连续性、一阶几何连续性 2 曲线的拟合：三次参数样条曲线、Hermite样条曲线 曲线的逼近：Bezier曲线、B样条曲线 简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、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) 1.计算机图形学的研究内容 什么是计算机图形学? (1/2) 什么是计算机图形学? (2/2) 什么是交互式计算机图形学? (1/3) 什么是交互式计算机图形学? (2/3) 什么是交互式计算机图形学? (3/3) 基本概念——图形 图形表示方法 相关学科 图像处理 图像分析 2.图形学发展历史 计算机图形学的发展历史 现代计算机图形学的发展 硬件的对比 现代计算机图形学的发展 模型与渲染 交互式图形学的概念框架 图形库 3.图形学应用领域 图形学的应用 设计 信息显示 仿真 Virtual Reality 用户界面 超媒体用户界面 4.相关知识 软件兼容性和图形标准 官方标准 APIs的嵌入标准 典型的图形系统 好的图形需要什么?（1/2） 好的图形需要什么? (2/2) ACM SIGGRAPH会议 资料查询作业 第二讲数字图像基础 1.基础概念 计算机图形系统 例子：一个简单程序（P23 code）图形系统的概念框架 图形处理器 Render farms 顶点（Vertex）着色 扫描线 刷新频率 分辨率 例子 纵横比 2.图形输入设备 输入设备 3D 输入设备 图形输入设备 3.图形输出设备 图形输出设备 硬拷贝设备 3D图形设备 CRT显示器 彩色CRTs 局限性 液晶显示器(Liquid Crystal Displays) LCDs 光栅显示 光栅显示器 内存映射 显存（帧缓冲存储器） 显存大小的计算 Avatar引发的3D浪潮（前沿) 三维电视 问题提出 3D显示技术原理 技术手段？ 立体显示技术分类 问题？ MIT “第六感” 涉及的技术 4.图形文件 图形文件 点阵图形及其表示 参数图形及其表示 作业 第三讲(第四章) 扫描转换 3.1 扫描转换直线 直线的扫描转换 寻找下一个像素 、计算机图形学中的图形是指由点、线、面、体等和明暗、灰度（亮度）、色彩等构成的，从现实世界中抽象出来的带有灰度、色彩及形状的图或形。 、一个计算机图形系统至少应具有、、输入、输出、等基本功能。 、常用的字符描述方法有：点阵式、和。 、字符串剪裁的策略包括、和笔划/像素精确度。 、所谓齐次坐标就是用维向量表示一个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的实现
计算机图形学全部知识点
《计算机图形学》试卷及答案
《计算机图形学》课程教学大纲
相关主题
文本预览