计算机图形学扫描转换

计算机科学技术：计算机图形学题库三1、名词解释扫描转换答案：在矢量图形中，多边形用顶点序列来表示，为了在光栅显示器或打印机等设备上显示多边形，必须把它转换为点阵表示。

这种转换称为扫描转换。

2、单选下面对光栅扫描图形显示器描述正确的是（）A.荧光粉涂层均匀离散分布；B.是一种点画设备；C.电子束从顶到底扫描；D.通过控制电子束的强弱实现色彩的强弱；答案：A3、填空题计算机图形系统由（）系统和软件系统组成。

答案：硬件4、填空题在处理图形时常常涉及的坐标系有模型坐标系（），世界坐标系，观察坐标系，设备坐标系。

答案：局部坐标系5、单选计算机图形学与计算机图象学的关系是（）。

A.计算机图形学是基础，计算机图象学是其发展B.不同的学科，研究对象和数学基础都不同，但它们之间也有可转换部分C.同一学科在不同场合的不同称呼而已D.完全不同的学科，两者毫不相干答案：B6、问答题简述中点分割法进行裁剪的过程？答案：中点分割剪取法，主要是对线段不断地进行对分，并排除在区域外的部分，找出线段落在窗口内的部分。

其方法主要是通过求出离线段的一个端点最近并且在区域内的点的方法，来确定线段落在窗口内的端点。

7、问答题局部光照模型和全局光照模型的不同之处是什么？答案：局部光照模型主要是考虑光源发出的光对物体的直接影响。

另外，全局光照模型除了处理光源发出的光之外，还考虑其他辅助光的影响，如光线穿过透明或半透明物体，以及光线从一个物体表面反射到另一个表面等。

8、判断题彩色阴极射线管主要是由红绿蓝三个彩色电子束的亮度不同，进而组合形成各种色彩的。

答案：错9、问答题什么叫做走样？什么叫做反走样？反走样技术包括那些？答案：走样指的是用离散量表示连续量引起的失真。

为了提高图形的显示质量。

需要减少或消除因走样带来的阶梯形或闪烁效果，用于减少或消除这种效果的方法称为反走样。

其方法是①前滤波，以较高的分辨率显示对象；②后滤波，即加权区域取样，在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个像素的属性进行平均得到较低分辨率下的像素属性。

计算机图形学——多边形的扫描转换（基本光栅图形算法）⼀、多边形扫描转换在光栅图形中，区域是由【相连的】像素组成的集合，这些像素具有【相同的】属性值或者它们位于某边界线的内部1、光栅图形的⼀个基本问题是把多边形的顶点表⽰转换为点阵表⽰。

这种转换成为多边形的扫描转换。

2、多边形的扫描转换与区域填充问题是怎样在离散的像素集上表⽰⼀个连续的⼆维图形。

3、多边形有两种重要的表⽰⽅法：（1）顶点表⽰：⽤多边形的定点序列来表⽰多边形优点：直观、⼏何意义强、占内存少、易于进⾏⼏何变换缺点：没有明确指出那些象素在多边形内，故不能直接⽤于上⾊（2）点阵表⽰：是⽤位于多边形内的象素集合来刻画多边形缺点：丢失了许多⼏何信息（eg:边界、顶点等）但是【点阵表⽰是光栅显⽰系统显⽰时所需的表现形式。

】多边形的扫描转换就是把多边形的顶点表⽰转换为点阵表⽰，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜⾊。

实际上就是多边形内的区域的着⾊过程。

4、多边形分类⼆、X扫描线算法X扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再⽤要求的颜⾊显⽰这些区间的象素，即完成填充⼯作。

区间的端点可以通过计算扫描线与多边形边界线的交点获得。

如扫描线y=3与多边形的边界相交于4点（2,3）、（4,3）、（7,3）、（9,3）这四个点定义了扫描线从x=2到x=4，从x=7到x=9两个落在多边形内的区间，该区间内像素应取填充⾊。

算法的核⼼是按x递增顺序排列交点的x坐标序列。

由此可得到扫描线算法步骤如下：算法步骤：1.确定多边形所占有的最⼤扫描线数，得到多边形定点的最⼩最⼤值（y min和y max）；2.从y min到ymax每次⽤⼀条扫描线进⾏填充；3.对⼀条扫描线填充的过程分为四个步骤：a)求交点；b)把所有交点按递增顺序排序；c)交点配对（第⼀个和第⼆个，第三个和第四个）；d)区间填⾊。

描述多边形扫描转换的扫描线算法的基本步骤多边形扫描转换是计算机图形学中一种常用的算法，用于将输入的多边形进行转换和填充。

其基本步骤包括初始化，活性边表的生成，活性边表的更新和扫描线的处理。

1.初始化首先，需要根据输入的多边形构造一个扫描线填充的边表。

这包括对多边形顶点的排序、计算多边形中的水平线交点，并将边表中的数据初始化为初始值。

2.活性边表的生成活性边表是用来存储和管理与扫描线相交的边的数据结构。

生成活性边表的过程包括两个步骤：-遍历多边形的每一条边，将边与当前扫描线的位置进行比较，如果两者相交，则将这条边添加到活性边表中。

-对活性边表中的边按照交点的水平位置进行排序。

这里可以使用插入排序等算法。

3.活性边表的更新活性边表需要在每次扫描线移动时进行更新。

这包括对活性边表中的边进行更新，以反映新的交点或边的状态的变化。

-对于与当前扫描线相交的边，需要计算其交点，并更新到活性边表中。

-对于已经处理完的边或超出当前扫描线范围的边，从活性边表中移除。

4.扫描线的处理在每次扫描线移动时，需要对当前的活性边表进行处理。

这包括两个子步骤：-将活性边表中的边按照两两成对的方式遍历，找到当前扫描线和这两条边所定义的三角形的上顶点和下顶点。

-将这个三角形的内部填充，并进行显示或存储等处理。

5.继续扫描线的移动在处理完一条扫描线后，需要将扫描线的位置向上移动一个单位，并继续执行第3步和第4步，直到所有的扫描线都被处理完毕。

总结：多边形扫描转换的基本步骤包括初始化、活性边表的生成、活性边表的更新和扫描线的处理。

这个算法通常用于实现对多边形的填充。

在每次扫描线移动时，活性边表需要进行更新，以反映新的交点或变化的边的状态。

扫描线的处理包括遍历活性边表中的边，并根据扫描线和这两条边所定义的三角形的顶点来进行填充。

最后，重复执行扫描线的移动和对活性边表的更新和处理，直到所有的扫描线都被处理完毕。

多边形的扫描转换算法概述多边形的扫描转换算法是计算机图形学中用于将多边形转换为像素的常用算法。

它通过扫描线的方式来确定多边形与像素的相交关系，并将多边形的内部区域填充为指定的颜色。

本文将详细介绍多边形的扫描转换算法的原理、步骤和应用。

原理多边形的扫描转换算法基于扫描线的概念，将多边形的边界线与一条水平线或垂直线进行比较，从而确定多边形的内部和外部区域。

算法的关键在于边界线的处理和内部区域的填充。

步骤多边形的扫描转换算法一般包括以下步骤：1.初始化扫描线的位置和内部区域的填充颜色。

2.遍历多边形的边界线，将其与扫描线比较，确定内部和外部区域。

3.根据内部区域的状态，进行填充颜色。

4.更新扫描线的位置，继续扫描下一条线段，直至完成对所有边界线的处理。

算法详解初始化扫描线在开始进行多边形的扫描转换之前，需要初始化扫描线的位置和内部区域的填充颜色。

一般情况下，扫描线的位置可以从多边形的最低点开始，逐渐向上扫描。

内部区域的填充颜色可以根据具体需求进行选择。

边界线处理多边形的边界线可以由多个线段组成，需要按照一定的顺序进行处理。

一种常用的处理方式是按照边界线的上端点的纵坐标从小到大排序，然后依次处理每条线段。

对于每条线段，通过比较线段的上端点和下端点的纵坐标与扫描线的位置，可以确定线段与扫描线的相交关系。

根据线段的斜率可以进一步确定线段与扫描线的交点。

内部区域填充确定了线段与扫描线的相交关系后，就可以确定内部和外部区域。

一般情况下，内部区域被定义为线段上方的区域，而外部区域被定义为线段下方的区域。

根据内部区域的状态，可以进行填充颜色。

如果内部区域是连续的，则可以使用扫描线的颜色进行填充。

如果内部区域有间隙，则需要采用其他填充算法，如边界填充算法或种子填充算法。

更新扫描线处理完当前线段后，需要更新扫描线的位置，继续扫描下一条线段。

一般情况下，扫描线的位置会逐渐向上移动，直至到达多边形的最高点。

应用多边形的扫描转换算法在计算机图形学中有广泛的应用。

计算机图形学——圆的扫描转换（基本光栅图形算法）与直线的⽣成类似，圆弧⽣成算法的好坏直接影响到绘图的效率。

本篇博客将讨论圆弧⽣成的3个主要算法，正负法、Bresenham 法和圆的多边形迫近法，在介绍算法时，只考虑圆⼼在原点，半径为R的情况。

⼀、正负法1、基本原理假设已选取Pi-1为第i-1个像素，则如果Pi-1在圆内，就要向圆外⽅向⾛⼀步；若已在圆外就要向圆内⾛⼀步。

总之，尽量贴近圆的轮廓线。

2、正负法的具体实现1）圆的表⽰：设圆的圆⼼为(0,0),半径为R，则圆的⽅程为：F(x,y)=x2+y2–R2=0当点(x,y)在圆内时，F(x,y)<0。

当点(x,y)在圆外时，F(x,y)>0。

2）实现步骤第1步：x0=0，y0=R第2步：求得Pi(x i,y i)后找点P i+1的原则为：当P i在圆内时(F(xi,yi)≤0)，要向右⾛⼀步得P i+1，这是向圆外⽅向⾛去。

取x i+1= x i+1, y i+1= y i当P i在圆外时(F(xi,yi)>0)，要向下⾛⼀步得P i+1，这是向圆内⽅向⾛去，取x i+1= x i, y i+1= y i-1⽤来表⽰圆弧的点均在圆弧附近且 F(xi, yi)时正时负假设已经得到点（x i, y i），则容易算出F(x i, y i)，即确定了下⼀个点（x i＋1, y i＋1），则如何计算F(x i+1, y i+1)，以确定下下个点（x i＋2, y i＋2）？分为两种情况：右⾛⼀步后：x i+1=x i+1，y i+1=y i，此时：F(x i+1, y i+1)=x i+12+y i2-R2=x i2+y i2-R2+2x i+1 = F(x i, y i)+2x i+1下⾛⼀步后：x i+1=x i，y i+1=y i-1， 此时：F(x i+1, y i+1)=x i2+（y i-1)2-R2= F(x i, y i)-2y i+1由此可得：确定了F(xi+1, yi+1)之后，即可决定下⼀个点(xi+2, yi+2)，选择道理同上。

多边形扫描转换算法多边形扫描转换算法是一种计算机图形学中常用的算法，用于将一个多边形转换为一组水平线段，以便进行填充或渲染。

该算法的基本思想是将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点，并将这些交点按照从左到右的顺序进行排序，最终得到一组水平线段。

多边形扫描转换算法的实现过程可以分为以下几个步骤：1. 找出多边形的顶点首先需要找出多边形的顶点，这些顶点可以通过遍历多边形的边来得到。

在遍历边的过程中，需要注意将相邻的边进行合并，以便得到多边形的完整轮廓。

2. 找出多边形与水平线段的交点在进行扫描转换时，需要将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点。

这些交点可以通过遍历多边形的边来得到，对于每条边，需要判断其是否与当前扫描线相交，如果相交，则计算出交点的坐标。

3. 对交点进行排序得到多边形与水平线段的交点后，需要将这些交点按照从左到右的顺序进行排序。

这可以通过对交点的x 坐标进行排序来实现。

如果有多个交点具有相同的 x 坐标，则需要按照其 y 坐标进行排序。

4. 将交点组成线段将交点按照从左到右的顺序进行排序后，就可以将它们组成一组水平线段。

对于相邻的两个交点，可以将它们之间的部分作为一条水平线段。

如果两个交点之间没有其他交点，则可以将它们之间的部分作为一条水平线段。

5. 进行填充或渲染得到一组水平线段后，就可以进行填充或渲染。

对于填充操作，可以使用扫描线算法来实现。

对于渲染操作，可以将每条水平线段转换为一组像素点，并将这些像素点进行绘制。

多边形扫描转换算法的优点是可以处理任意形状的多边形，并且可以得到一组水平线段，方便进行填充或渲染。

但是该算法的缺点是需要进行大量的计算，特别是在多边形较复杂时，计算量会非常大，导致性能下降。

为了提高多边形扫描转换算法的性能，可以采用一些优化技术。

例如，可以使用空间分割技术来减少计算量，将多边形分割成多个小块进行处理。

另外，可以使用并行计算技术来加速计算过程，将多个处理器或计算机同时进行计算。

计算机图形学实验报告班级计算机工硕班学号2011220456姓名王泽晶实验一:直线段扫描转换实验目的通过本次试验，学生可以掌握直线段的扫描转换算法及其程序设计方法。

实验内容1. 绘制20*20的网格线，格子X 和Y 方向间隔均为20像素，网格起始坐标在(20,20)。

我们使用此网格模拟像素矩阵（019,019x y ≤≤≤≤），格子交叉点是像素中心。

2. 输入直线段两端点，可使用以下两种方法之一：a) 对话框输入b) 鼠标在网格内以鼠标左键按下-拖动-抬起方式输入。

注意：直线段两端点要自动取整到模拟的像素中心位置3. 进行直线段扫描转换，通过点击鼠标右键调用方式或者菜单调用的方式执行。

计算完成后，将扫描转换结果，在模拟的像素矩阵中，使用圆形显示出来。

方法一：直线的中点算法算法的主要思想：讨论斜率k ∈[1,+∞)上的直线段的中点算法。

对直线01p p ，左下方的端点为0p （x0，y0），右上方的端点为1p （x1，y1）。

直线段的方程为：y mx B =+⇔y y x B xy yx xB x∆=+⇔∆=∆+∆∆ (,)0F x y xy yx xB ⇔=∆-∆-∆=现在假定已求得像素（,,i r i x y ），则如图得,,11(,]22i i r i r x x x ∈-+ 由于直线的斜率k ∈[1,+∞)，故m=1/k ∈(0,1],则1,,13(,]22i i r i r x x x +∈-+ 在直线1i y y =+上，区间,,13(,]22i r i r x x -+内存在两个像素NE 和E 。

根据取整原则，当11(,)i i x y ++在中点M 11(,)2i i x y ++右方时，取像素NE ，否则取像素E ，即 ,11,,1()()01()()0i r i i r i r i x E F M x x x NE F M x +++⎧⇔≤=⎨+⇔>⎩i i 点当(,y +1)在左方时点当(,y +1)在右方时若取2()i d F M =，则上式变为,1,,()01(0i r i i r i r i x E d x x NE d +⎧≤=⎨+>⎩点当点)当计算i d 的递推公式如下：,11,12[(2)()]0122(,2)0122[(2)(1)]2i i r i i i i i i i r x y y x xB d d F x y d x y y x xB ++⎧∆+-∆+-∆⎪≤⎪=++=⎨>⎪∆+-∆++-∆⎪⎩ =202()0i i i i d x d d x y d +∆≤⎧⎨+∆-∆>⎩算法的初始条件为：00,00,0(,)(0,0)12(,1)22r r x y x y d F x y x y =⎧⎪⎨=++=∆-∆⎪⎩ 相应的程序示例：public function drawLine(pixelDrawer:Function, x0:int,y0:int,x1:int,y1:int):void{var dx:Number = x1 - x0;var dy:Number = y1 - y0;var x:Number;var y:Number;if ((dx == 0) && (dy == 0) ){// 两点重合时，直接绘制重合的点pixelDrawer( x0, y0 );return;}else if ( dx==0 ){// 第二点落在X轴上，直接绘制直线上的点var step:Number = dy / Math.abs(dy);for (y=y0; y!=y1; y+=step )pixelDrawer( x0, y );}else if ( dy==0 ){// 第二点落在Y轴上，直接绘制直线上的点step = dx / Math.abs(dx);for (x=x0; x!=x1; x+=step )pixelDrawer( x, y0 );var stepX:Number = dx / Math.abs(dx);var stepY:Number = dy / Math.abs(dy);x = x0, y = y0;pixelDrawer( x, y ); // 绘制起点var k:Number = dy / dx;if ( Math.abs(k)<1.0 ) // 斜率<1的情形，以X为自变量递增{var a:Number = -Math.abs(dy);var b:Number = Math.abs(dx);var d:Number = 2 * a + b;var d1:Number = 2 * a;var d2:Number = 2 * (a + b);while ( x!=x1 ){if ( d<0 ) { x += stepX; y += stepY; d += d2; }else { x += stepX; d += d1; }pixelDrawer( x, y );}}else// 斜率>=1的情形，以Y为自变量递增a = -Math.abs(dx);b = Math.abs(dy);d = 2 * a + b, d1 = 2 * a, d2 = 2 * (a + b);while ( y!=y1 ){if ( d<0 ) { x += stepX; y += stepY; d += d2; }else { y += stepY; d += d1; }pixelDrawer( x, y );}}pixelDrawer( x1, y1 ); // 绘制终点}编译运行程序得到如下结果：方法二：直线的数值微分法算法的主要思想：由于课本上已经给出了斜率m ∈[-1,1]上的算法，故此处给出斜率m ∈[1，+∞〕上的算法，m ∈(-∞,-1]上的可同理推导。

实验二：基本图元扫描转换一、实验目的1、掌握图形扫描转换的基本概念；2、掌握直线的绘制算法及程序设计；3、掌握圆弧的绘制算法及程序设计。

二、实验要求1. 在MFC单文档应用程序中，利用MFC应用程序向导生成完整的应用程序基本框架，添加“直线”菜单，在“直线”菜单下添加“DDA画线”子菜单，如图1.1所示，对应DDA 算法绘制直线，直线端点为（100，100），（300，200），颜色为红色，如图1.2所示。

图1.1 菜单示例图图1.2 DDA画线2. 在上题基础上，在“直线”菜单下再添加一个“中点画线”子菜单，如图2.1所示，利用中点画线算法画线，实现鼠标按下抬起绘制直线段的功能，颜色为黑色，如图2.2所示。

图2.1菜单示例图图2.1绘制矩形制作动画图3. 在上题基础上，添加“圆形”菜单，如图3.1所示，利用Bresenham算法编程实现圆的扫描转换，绘制半径为200的黑色圆，如图3.2所示。

图3.1菜单示例图图3.2 Bresenham画圆三、实验内容○1“直线”菜单，“DDA画线”子菜单，“中点画线”子菜单的构建○2DDA画线void CMainFrame::OnDda(){// 获得设备指针CDC *pDC=GetDC();// 定义直线两端点和直线颜色（红色）int x0=100,y0=100,x1=300,y1=200,c=RGB(255,0,0);float x,y,i;float dx,dy,k;dx=(float)(x1-x0);dy=(float)(y1-y0);k=dy/dx;y=y0; x=x0;if(abs(k)<1){ for(;x<=x1;x++){pDC->SetPixel(x,int(y+0.5),c);y=y+k;}}if(abs(k)>=1){for(;y<=y1;y++){pDC->SetPixel(int(x+0.5),y,c);x=x+1/k;}}ReleaseDC(pDC); //释放设备指针}○3中点画线0≤k≤1时中点画线算法的算法步骤为：1.输入直线的两端点P0(x0,y0)和p1(x1,y1)。