计算机图形学 实验 数值微分(DDA)法、中点画线法、Bresenham算法
计算机图形学实验指导书(vc++版)
实验指导书 刘文涛 2013
目录 第一章图形学实验环境和要求 (4) 1.1 VC++实验环境 (4) 1.1.1 基本环境 (4) 1.1.1 开发图形程序的一般流程 (7) 1.1.3 基本绘图函数介绍 (11) 1.2 OpenGL (22) 1.2.1 OpenGL介绍 (22) 1.2.2 OpenGL开发环境 (24) 1.2.3 OpenGL函数 (24) 1.2.4 回调函数 (25) 1.2.4 一个典型OpenGL例程 (26) 1.3 实验要求 (29) 1.3.1 实验内容 (29) 1.3.2 实验方法 (29) 1.3.3 实验效果 (30) 第二章直线生成算法 (30) 2.1 实验原理 (30) 2.1.1 DDA算法 (30) 2.1.2 Bresenham算法 (30) 2.2 实验内容 (30) 2.3 参考示例程序 (30) 第三章圆和椭圆生成算法 (32) 3.1 实验原理 (32) 3.2 实验内容 (32) 3.3 参考示例程序1 (32) 3.4 参考示例程序2 (33) 第四章裁剪算法 (35) 4.1 实验原理 (35) 4.2 实验内容 (35) 4.3 示例程序 (35) 4.3.1 参考例子1 (35) 4.3.2参考例子2 (38) 第五章二维变换 (40) 5.1 实验原理 (40) 5.2 实验内容 (40) 5.3 示例程序 (40) 5.3.1参考例子1 (40) 第六章三维变换 (44)
6.1 实验原理： (44) 6.2 实验内容 (45) 6.3示例程序 (45) 第七章填充算法 (47) 7.1 实验原理： (47) 7.2 实验内容 (47) 7.3示例程序 (47) 第八章曲线曲面 (50) 8.1 实验原理 (50) 8.2 实验内容 (50) 8.3示例程序 (51) 8.3.1 参考例子（1） (51) 8.3.2 参考例子（2） (52) 8.3.3 参考例子（3） (54) 8.3.4 参考例子（4） (56) 第九章真实感图形绘制 (59) 9.1 实验原理 (59) 9.2 实验内容 (59) 9.3示例程序 (59) 9.3.1参考例子（1） (59) 9.3.2参考例子（2） (61) 9.3.3参考例子（3） (63) 第十章动画 (66) 10.1 实验原理 (66) 10.2 实验内容 (66) 10.3示例程序 (66) 10.3.1 参考例子 (66) 参考文献： (72)
计算机图形学实验报告
计算机图形学 实验报告 学号： 姓名： 班级：计算机 2班 指导老师：何太军 2010.6.19
实验一、Windows 图形程序设计基础 1、实验目的 1）学习理解Win32 应用程序设计的基本知识（SDK 编程）； 2）掌握Win32 应用程序的基本结构（消息循环与消息处理等）； 3）学习使用VC++编写Win32 Application 的方法。 4）学习MFC 类库的概念与结构； 5）学习使用VC++编写Win32 应用的方法（单文档、多文档、对话框）； 6）学习使用MFC 的图形编程。 2、实验内容 1）使用WindowsAPI 编写一个简单的Win32 程序，调用绘图API 函数绘制若干图形。（可选任务） 2 ）使用MFC AppWizard 建立一个SDI 程序，窗口内显示"Hello,This is my first SDI Application"。（必选任务） 3）利用MFC AppWizard(exe)建立一个SDI 程序，在文档视口内绘制基本图形（直线、圆、椭圆、矩形、多边形、曲线、圆弧、椭圆弧、填充、文字等），练习图形属性的编程（修改线型、线宽、颜色、填充样式、文字样式等）。定义图形数据结构Point\Line\Circle 等保存一些简单图形数据（在文档类中），并在视图类OnDraw 中绘制。 3、实验过程
1）使用MFC AppWizard(exe)建立一个SDI 程序,选择单文档； 2）在View类的OnDraw（）函数中添加图形绘制代码，说出字符串“Hello,This is my first SDI Application”，另外实现各种颜色、各种边框的线、圆、方形、多边形以及圆弧的绘制； 3）在类视图中添加图形数据point_pp,pp_circle的类，保存简单图形数据，通过在OnDraw（）函数中调用，实现线、圆的绘制。 4、实验结果 正确地在指定位置显示了"Hello,This is my first SDI Application"字符串，成功绘制了圆，椭圆，方形，多边形以及曲线圆弧、椭圆弧，同时按指定属性改绘了圆、方形和直线。成功地完成了实验。 结果截图： 5、实验体会 通过实验一，了解了如用使用基本的SDI编程函数绘制简单的图
计算机图形学实验报告
计算机图形学 实验报告 实验一:二维线画图元的生成 实验目的：掌握直线段的生成算法，并用C/WIN-TC/VC++实现算法，包括中点法生成直线，微分数值法生成直线段等。 实验内容：用不同的方法生成斜率不同的直线段，比较各种方法的效果。 Bresenham 算法的思想 Bresenham 画法与中点法相似，都是通过每列象素中确定与理想直线最近的像素来进行直线的扫描的转换的。通过各行、各列的象素中心构造一组虚拟网格线的交点，然后确定该列象素中与此交点最近的像素。该算法的巧妙之处在于可以采用增量计算，使得对于每一列，只需要检查一个误差项的符号，就可以确定该列的所有对象。 1.1方法一：直线的中点算法 算法的主要思想： 讨论斜率k ∈[1,+∞)上的直线段的中点算法。 对直线01p p ，左下方的端点为0p （x0，y0），右上方的端点为1p （x1，y1）。直线段的方程为： y m x B =+ ?y y x B x y y x x B x ?= +??=?+?? (,)0F x y xy yx xB ?=?-?-?= 现在假定已求得像素（,,i r i x y ），则如图得
,,11(,]22 i 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 (,)2 i i x y ++右方时，取像素NE ，否则取像素E ，即 ,11,,1()()01()()0 i 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(0 i r i i r i r i x E d x x NE d +? ≤=? +>?点当点)当 计算i d 的递推公式如下： ,1 1,12[(2)()]012 2(,2)0 122[(2)(1)] 2 i 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() i i i i d x d d x y d +?≤?? +?-?>? 算法的初始条件为： 00,00,0(,)(0,0)1 2(,1)22 r r x y x y d F x y x y =? ? ?=++=?-??? 相应的程序示例： 建立成员函数： void MidPointLine4(CDC*pDC,int x0,int y0,int x1,int y1,int color) { /*假定x0 实验一OpenGL开发环境及扫描转换算法 1、实验目的与要求 1.通过实验掌握OpenGL中编程环境的设置，了解相关函数用途及设置步骤； 2.通过实验掌握基本图形元素的生成，给出相关代码和运行结果； 3.用WINDOWS GDI函数编写生成直线或区域填充的程序(选DDA或Bresenham直线算法，活 性边表算法填充多边形)，演示算法过程。 4.画矩形，调用一个函数画一个矩形。画椭圆，调用一个函数画一个椭圆。画Bezier 曲线。 2、实验方案 请描述为达到实验的需要完成哪些方面的实验，列举出实验的基本要点和重点。 在工程WinAPIEX加入void createLine(HDC tmpDC)和void Polyline (tmpDC) 在void createLine(HDC tmpDC)用DDA直线算法或Bresenham直线算法生成直线 在void Polyline (tmpDC)添加活泩边表填充算法，生成填充四边形和八边形 加入Rectangle(tmpDC,x0,y0,x1,y1);加入Ellipse (tmpDC, x0,y0,a,b) ;加入PolyBezier(tmpDC,arr_vertex,4) ; 3、实验结果和数据处理 1)生成直线的DDA直线算法 在createLine(tmpDC)中加入以下代码int x0,y0,x1,y1,color; //自定义直线的起点(x0,y0)和终点(x1,y1)，及颜色color float dx,dy,x,y; int length,i; x0=50; y0=160; x1=900; y1=200;//此处修改了 color=1000; color=1; if(abs(x1-x0)>=abs(y1-y0)) length=abs(x1-x0); else length=abs(y1-y0); dx=(x1-x0)/(float)length; dy=(y1-y0)/(float)length; i=1; x=(float)x0; y=(float)y0; while(i<=length) { SetPixel(tmpDC,int(x+0.5),int(y+0. 5),color); x+=dx; y+=dy; i++; } 2)区域填充的程序 在void Polyline (tmpDC) 添加活性边表填充 void Polyline (HDC tmpDC) //多边形边数. { const int POINTNUM=4;//或者是八边形8 /******定义结构体用于活性边表AET 计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中用屏幕显示图样是计算机绘图的重要内容。 计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳接近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域填充。 复杂的图形系统，都是由一些最基本的图形元素组成的。利用计算机编制图形软件时，编制基本图形元素是相当重要的，也是必需的。点是基本图形，本章主要讲述如何在指定的输出设备（如光栅图形显示器）上利用点构造其他基本二维几何图形（如点、直线、圆、椭圆、多边形域及字符串等）的算法与原理，并利用Visual C++编程实现这些算法。 1.1 直线 数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。 由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。 第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0,y0)、P1(x1,y1)的直线段为L(P0,P1)，则直线段L的斜率 L的起点P0的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L 的直线程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y i+1=kx i+1+b =k1x i+b+k?x =y i+k?x 所以，当 x =1;y i+ y i+k。也就是说，当x每递增1，y递增k(即直线斜 1= 率)。根据这个原理，我们可以写出DDA（Digital Differential Analyzer）画线算法程序。 DDA画线算法程序： void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0；dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示像素的颜色和灰度。 举例：用DDA法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 Bresenham算法是计算机图形学中常用的一种画直线的算法。它的原理是利用像素点在屏幕上的排列规律，从而高效地计算出直线上的像 素点。本文将以一个具体的例题来说明Bresenham算法的原理及应用。 1. 问题描述 假设我们需要在一个分辨率为800x600的屏幕上，画一条直线，起点坐标为(100, 200)，终点坐标为(400, 300)。请使用Bresenham算法 计算直线上的像素点，并用符号“*”表示出来。 2. Bresenham算法原理 Bresenham算法的核心思想是利用像素点的整数坐标值与直线的斜率之间的关系，从而逐个确定直线上的像素点。 具体步骤如下： - 计算直线的斜率k，即k = (y2 - y1) / (x2 - x1)，其中(x1, y1)为起 点坐标，(x2, y2)为终点坐标。 - 以起点坐标作为初始值，从左至右依次求解直线上各点像素的坐标。- 对于每一个x坐标，根据斜率k的大小确定y坐标的增长方向。 3. Bresenham算法应用 根据上述原理，我们来解决具体的例题。 计算直线的斜率k： k = (300 - 200) / (400 - 100) = 1/3 以起点坐标(100, 200)作为初始值，从左至右依次求解直线上各点像素的坐标。 当x坐标从100递增至400时，y坐标的增长方向由斜率k来确定。具体计算如下： - 当x=100时，y=200 - 当x=101时，y=200+1/3≈200 - 当x=102时，y=200+2/3≈201 - ... - 当x=400时，y=300 现在，我们可以得到直线上的像素点坐标，并用符号“*”表示出来。 4. 结果展示 根据上述计算，我们可以得到该直线上的像素点坐标，展示如下： (100, 200) * (101, 200) * (102, 201) * ... 分别解释直线生成算法dda法、中点画线法和 bresenham法的基本原理 DDA直线生成算法、中点画线法和Bresenham法都是计算机图形学中用于生成直线的算法。以下是这三种算法的基本原理： 1.DDA直线生成算法（Digital Differential Analyzer）： DDA算法是一种基于差分运算的直线生成算法。其基本原理是，通过计算直线起点和终点之间的差值（横向差值dx 和纵向差值dy），并根据步长来决定下一个像素点的位置。算法首先确定差值中绝对值较大的一方作为基准，步长设为1，另一方则按比例进行调整，以保持线段的斜率不变。在实现过程中，DDA算法需要遍历每一个像素点，根据差值的正负和大小来确定新像素点的位置。 2.中点画线法： 中点画线法的基本原理是，通过计算线段上当前像素点与相邻两个像素点构成的线段与理想直线的距离，来决定下一个像素点的位置。具体实现时，设定线段的中点为M，理想直线与线段的交点为Q。通过比较M和Q的位置关系来确定下一个像素点：若M在Q上方，则取上方的像素点为下一个点；若M在Q下方，则取下方的像素点为下一个点；若M与Q重合，则可任意选择上方或下方的像素点。中点 画线法以中点M作为判别标志，逐点生成直线。 3.Bresenham法： Bresenham算法的原理是基于直线的斜率和截距来计算每个像素点的位置。在计算机屏幕上，每个像素点都有一个坐标值。Bresenham算法通过计算直线上每个像素点的坐标值来绘制直线，避免了使用浮点数运算，从而提高了计算效率。在实现过程中，Bresenham算法根据直线的斜率以及当前像素点的位置，计算出下一个像素点的位置，并逐点绘制出直线。 注：1、实验报告的内容: 一、实验目的；二、实验原理；三、实验步骤；四、实验结果；五、讨论分析（完成指定的思考题和作业题）；六、改进实验建议。 2、各专业可在满足学校对实验教学基本要求的前提下，根据专业特点自行设计实验报告的格式，所设 计的实验报告在使用前需交实践教学管理科备案。 五、实验步骤 1、复习有关直线扫描转换算法的基本原理，明确实验目的和要求； 2、依据算法思想，绘制程序流程图； 3、设计程序界面，要求操作方便； 4、用C/C++语言编写源程序并调试、执行； 5、分析实验结果 6、对程序设计过程中出现的问题进行分析与总结； 7、打印源程序或把源程序以文件的形式提交； 8、按格式要求完成实验报告。 六、实验报告要求： 1、各种算法的基本原理； 2、各算法的流程图 3、实验结果及分析（比较三种算法的特点，界面插图并注明实验条件） 4、实验总结（含问题分析及解决方法） 七、实验原理 1、DDA算法(数值微分法) 数值微分法(DDA法，Digital Differential Analyzer)是一种直接从直线的微分方程生成直线的方法。给定直线的两端点P0(x0, y0)和P1(x1, y1)，得到直线的微分方程如下： DDA算法原理：由于直线的一阶导数是连续的，而且对于△x和△y是成正比的，故此可以通过在当前位置上分别加上二个小增量来求下一点的x，y坐标，如下图所示。 则有： 其中，ε=1/max(|△x|,|△y|) 分两种情况讨论如下： （1）max(|△x|,|△y|)=|△x|，即|k|≤1的情况： （2）max(|△x|,|△y|)=|△y|，此时|k|≥1： 注意：由于在光栅化的过程中不可能绘制半个像素点，因此对求出的xi+1，yi+1的值需要四舍五入。 2、中点Bresenham算法 给定直线的两个端点坐标，可以得到直线的方程为： 此时直线将平面分成三个区域：对于直线上的点，F(x, y)=0；对于直线上方的点，F(x, y)>0；对于直线下方的点，F(x, y)<0，如下图所示。 图5－2 直线将平面分为三个区域 3种画圆算法的优劣分析 画圆是计算机图形学中的基本操作之一，常用于绘制图形、实现图形 的填充和边界等。为了实现画圆操作，人们提出了许多不同的圆算法。本 文将对三种常见的画圆算法进行优劣分析，包括中点圆算法、Bresenham 圆算法和数值微分圆算法。 1.中点圆算法： 中点圆算法是一种基本的画圆算法，它使用了圆的对称性质来减少计 算量。该算法的基本思想是从圆心开始逐渐向外扩展，每次判断一个点是 否在圆上。相比于其他算法，它的计算量相对较小，适用于处理小半径的圆。优点如下： -算法简单易懂，实现简单，代码量少，计算效率较高。 -由于利用了圆的对称性，算法中的计算量较小，能够实现实时绘制。 -可以实现反锯齿效果。 然而，中点圆算法也存在一些不足之处： -由于该算法是基于对圆的对称性的判断，对于较大的圆，计算量会 变大，绘制速度较慢。 -由于绘制的是离散像素，所以在绘制大半径圆时，圆的边缘可能会 出现锯齿现象。 -在绘制一些不对称的图形时，需要进行额外的计算，而计算效率相 对较低。 2. Bresenham圆算法： Bresenham圆算法是一种以Bresenham直线算法为基础的算法，它克服了中点圆算法的对称性引起的效率问题。该算法的核心思想是利用差分思想求解圆上的点。优点如下： -算法简单易懂，实现简单，代码量少。 -算法的计算量与圆的大小无关，适用于绘制任意半径的圆。 -能够减少计算量和内存开销，提高绘制速度。 然而，相较于中点圆算法，Bresenham圆算法也存在一些不足之处：-该算法对于像素大小的选择要求较高，需要将圆心和半径放置在像素上才能绘制出良好的效果。 -在绘制一些复杂的图形时，需要进行额外的计算，计算的复杂性相对较高。 -在绘制大半径圆时，圆的边缘可能会出现锯齿现象。 3.数值微分圆算法： 数值微分圆算法是基于微分思想的一种算法，其核心思想是通过计算圆上两个相邻像素之间的差分来绘制圆。优点如下： -该算法计算精确，绘制出的圆形较为平滑。 -在绘制一些不规则图形时，该算法具有较高的适应性和灵活性。 -可以根据需要调整像素的密度，实现特定效果，如虚线圆。 然而，数值微分圆算法也存在一些不足之处： -算法相对复杂，实现难度较大，代码量较多。 #include 实验一: 直线 数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。 一. DDA（数值微分）算法 DDA算法原理：如图1-1所示，已知过端点的直线段；直线斜率为，从的左端点开始，向右端点步进画线，步长=1（个像素），计算相应的坐标；取像素点[ , round（y）] 作为当前点的坐标。计算，当，即当x每递增1，y递增k（即直线斜率）。 1的情形。在这种情况下，x每增加1, y最多增加1。当时，必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。 注意：上述分析的算法仅适用于k 二. 生成直线的中点画线法 中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下一个像素点有两种选择，点P1或P2。M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，应取P1为下一点。中点画线法的实现：令直线段为L[ p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0；点与L的关系如下。 在直线上，F(x, y)=0； 在直线上方，F(x, y)>0； 在直线下方，F(x, y)<0。 把M代入F（x, y），判断F的符号，可知Q点在中点M的上方还是下方。为此构造判别式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c。 当d < 0，L(Q点)在M上方，取P2为下一个像素。 当d > 0，L(Q点)在M下方，取P1为下一个像素。 当d=0，选P1或P2均可，取P1为下一个像素。 其中d是xp, yp的线性函数。 三. Bresenham算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个像素取右边点还是右上方点。 设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y = mx+b，其中b=y1–mx1，m = (y2–y1)/(x2–x1)=dy/dx；此处的讨论直线方向限于第一象限，如图1-3所示，当直线光栅化时，x每次都增加1个单元，设x像素为(xi，yi)。下一个像素的列坐标为xi+1，行坐标为yi或者递增1为yi+1，由y与yi及yi+1的距离d1及d2的大小而定。计算公式为 y = m(xi + 1) + b （1.1） d1 = y – yi （1.2） d2=yi+1–y （1.3） 如果d1–d2>0，则yi+1=yi+1，否则yi+1=yi。 式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式两边，并以Pi=(d1–d2)，dx代入上述等式，得 Pi = 2xidy–2yidx+2dy+(2b–1)dx （1.4） 《计算机图形学》模拟题 一．单项选择题 1．以下对DDA算法及Bresenham算法的描述中，错误的是（B） （A）DDA算法的本质是用数值方法解微分方程（数值微分法）。 （B）DDA算法效率低，但利于硬件实现。 （C）Bresenham算法只有加法和乘2计算，效率高。 （D）Bresenham算法的基本思想是借助于一个决策变量d的正负符号，来确定下一个该亮点的象素点。 2．下列对圆弧的生成算法中，可能造成所产生的圆是不封闭的算法是（B） （A）扫描法（B）DDA算法（C）Bresenham算法（D）正负法 3．计算机图形学与计算几何之间的关系是( B) (A）学术上的同义词(B）计算机图形学以计算几何为理论基础(C）计算几何是计算机图形学的前身(D）两门毫不相干的学科 4. 对直线的扫描转换算法中，下列说法正确的是（A） （A）Bresenham算法主要是通过借助于一个决策变量d的正负符号，来确定下一个该亮点的象素点。 （B）Bresenham算法中决策变量的计算式与上一次决策变量的正负无关。 （C）DDA算法主要利用整数进行计算，其效率较高。 （D）DDA算法不需要计算直线的斜率，但Bresenham算法需要。 5. 用中点法画线时，对坐标点P（x i,y i）,对M（x i+1,y i+0.5）有d i=F(M)=F(x i+1, y i+0.5)<0，此时下一个象素应选择（C） （A）P1(x i+1,y i) (B)P2(x i,y i+1) (C)P3(x i+1,y i+1) (D)P4(x i,y i) 6．对简单种子填充算法，其算法原理是将种子像素入栈，当栈非空时，将执行以下三个步骤：（1）栈顶像素点A出栈。（2）按某一顺序查出与A相邻的4个像素，若其中某个像素还是区域中原有颜色，或不为边界，则将该像素入栈。（3）将A置成填充色。 其正确步骤为（B） （A）（1）->（2）->（3）（B）（1）->（3）->（2） （C）（2）->（3）->（1）（D）（3）->（2）->（1） 7．曲线分为规则曲线和自由曲线，以下为自由曲线的是（D） （A）渐开线（B）双曲线（C）双曲线（D）等高线 8. 下列有关Bezier曲线性质的叙述语句中，错误的结论为（D） （A）Bezier曲线可用其特征多边形来定义。 （B）Bezier曲线不一定通过其特征多边形的各个顶点。 （C）Bezier曲线两端点处的切线方向必须与其特征折线集（多边形）的相应两端线段走向一致。 （D）n次Bezier曲线，在端点处的r阶导数，只与r个相邻点有关。 9．由M个控制顶点Pi(i=1,… k) 所决定的n次B样条曲线，由（D）段n次B样条曲线段光滑连接而成。 （A）k-n-2 （B）k-n-1 （C）k-n （D）k-n+1 10．在下列有关B样条曲线的叙述语句中，错误的叙述为（D ） （A）B样条曲线的形状和位置与坐标系的选择无关。 （B）B样条曲线的凸包区域比同一组控制顶点定义的Bezier曲线的凸包要小。 （C）由平面内n+1个控制点构成的B样条曲线p(t)的特征多边形，在该平面内的任意一条直线与p(t)的交点个数不多于该直线和特征多边形的交点个数。 2.1直线段的扫描转换算法 数值微分(DDA)法 设过端点P0(x0,y0)、P1(x1,y1)的直线段为L(P0,P1)，则直线段L的斜率 L的起点P0的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个象素)，用L的直线方程y=kx+b计算相应的y坐标，并取象素点(x,round(y))作为当前点的坐标。因为： y i+1 = kx i+1+b = k1x i+b+k∆x = y i+k∆x 所以，当∆x =1; y i+1= y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出DDA画线算法程序。 DDA画线算法程序 void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, k； dx = x1-x0； dy=y1-y0； k=dy/dx,；y=y0； for (x=x0；x< x1；x++) { drawpixel (x, int(y+0.5), color); y=y+k; } } 注意：我们这里用整型变量color表示象素的颜色和灰度。 举例：用DDA方法扫描转换连接两点P0 （0,0）和P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0. 5 图2.1.1 直线段的扫描转换 注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y 最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整，这使得它不利于硬件实现。 中点画线法 假定直线斜率k在0~1之间，当前象素点为（x p,y p），则下一个象素点有两种可选择点P1（x p+1,y p）或P （x p+1,y p+1）。若P1与P2的中点（x p+1,y p+0.5） 2 称为M，Q为理想直线与x=x p+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理。 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计算机图形学实验报告(一).doc
计算机图形学教程电子版
直线和圆弧的生成算法
bresenham算法画直线例题
分别解释直线生成算法dda法、中点画线法和bresenham法的基本原理
直线段的扫描转换_计算机专业_OpenGL实验_Exp
3种画圆算法的优劣分析
计算机图形学--Bresenham完整算法-画直线、椭圆和圆
直线的生成
计算机图形学模拟题
2.1 直线段的扫描转换算法
计算机图形学常用算法及代码大全