直线生成算法——Bresenham法

直线生成算法——Bresenham法

最近的研究涉及在像素图上作直线，自己也不想花时间摸索，于是在网上找到了Bresenham的直线生成算法，有一篇博客讲得清晰明了，但是算法上有些问题，我进行了改进和移植，下面讲解Bresenham的直线生成算法时也是参考这篇博文。

1.算法简介

图1

算法思想：图1中，连接M点和N点的直线经过点B，由于是像素图，所以实际上B 点应该由A点或者C点代替。当B点更靠近A点时，选择点A（x+1,y+1）；当B点更靠近C点时，选择点C（x+1,y）。

因此，当ε+m < 0.5时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点，这里ε为累加误差，表达式为：

式中：表示在第n次计算时的值，表示在第n+1次计算时的值；m就是直线的

斜率。

由于斜率m的值有正有负，有可能为0，也可能为∞，为了避免分别讨论这些情况，

将上述公式两边都乘以dx, 并将ε*dx用ξ表示，则有

式中：表示在第n次计算时的值，表示在第n+1次计算时的值；dx为起

点和终点横坐标之差，dy为起点和终点纵坐标之差。

还需说明一点，由直线斜率的定义

故

值得注意的是，现在我们只考虑dx > dy，且x，y的增量均为正的情况，但实际上有8种不同的情况（但是算法思想不变），如图2所示

如图2

2.算法程序

前文提到的那篇博文提出了一种方法，能将这8种情况都考虑，很巧妙。但是实际应用时发现程序运行结果不是完全对，多次检查之后将程序进行了修改。

修改后的算法VB程序如下

‘**************************************************************************** Type mypos '自定义数据类型

x As Integer

y As Integer

End Type

‘**************************************************************************** Function Bresenham(arr() As mypos, x1, y1, x2, y2)

Dim x!, y!, dx!, dy!, ux%, uy%, eps!

Dim cnt%

ReDim arr(100)

dx = x2 - x1

dy = y2 - y1

If dx >= 0 Then ux = 1

If dx < 0 Then ux = -1

If dy >= 0 Then uy = 1

If dy < 0 Then uy = -1

x = x1

y = y1

eps = 0

dx = Abs(dx): dy = Abs(dy)

cnt = 0

If dx >= dy Then

For x = x1 To x2 Step ux

cnt = cnt + 1

If 2 * (eps + dy) < dx Then

eps = eps + dy

arr(cnt).x = x

arr(cnt).y = y

Else

eps = eps + dy - dx

If cnt >= 2 Then y = y + uy 'cnt大于2才执行y = y + uy，即排除起始坐标点，否则造成错误结果

arr(cnt).x = x

arr(cnt).y = y

End If

Next x

Else

For y = y1 To y2 Step uy

cnt = cnt + 1

If 2 * (eps + dx) < dy Then

eps = eps + dx

arr(cnt).x = x

arr(cnt).y = y

Else

eps = eps + dx - dy

If cnt >= 2 Then x = x + ux 'cnt大于2才执行x = x + ux，即排除起始坐标点，否则造成错误结果

arr(cnt).x = x

arr(cnt).y = y

End If

Next y

End If

arr(0).x = cnt’记录元素个数

End Function

如果大家有不同看法，还希望共同讨论

3.程序运行结果（VB+ OpenGL）

图3

图4

绘制y=x，0≤x≤10，图3是原程序运行结果，图4时修改后的程序运行结果，原程序运行得到的起点是（0,1），但实际应该是（0,0）

图5

图6

绘制直线[第1个坐标为起点，第2个坐标为终点]

（5,5）-（15,15）、（5,10）-（15,15）、（5,15）-（15,15）、（5,20）-（15,15）、（5,25）-（15,15）；

（25,5）-（15,15）、（25,10）-（15,15）、（25,15）-（15,15）、（25,20）-（15,15）、（25,25）-（15,15）；

（5,5）-（15,15）、（10,5）-（15,15）、（15,5）-（15,15）、（20,5）-（15,15）、（25,5）-（15,15）；

（5,25）-（15,15）、（10,25）-（15,15）、（15,25）-（15,15）、（20,25）-（15,15）、（25,25）-（15,15）；

图5是原程序运行结果，图6是修改后的程序运行结果

DDA直线生成算法

实验报告 课程名称计算机图形学 实验名称DDA直线生成算法编程的实现实验类型验证型 实验地点计通学院304实验日期2010-03-29指导教师 专业 班级 学号 姓名 成绩 辽宁石油化工大学计算机与通信工程学院

实验报告说明 1、封面内容 （1）课程名称：实验所属的课程的名称。 （2）实验名称：要用最简练的语言反映实验的内容。要求与实验指导书中相一致。 （3）实验类型：说明是验证型实验、设计型实验、创新型实验还是综合型实验。 2、正文内容 实验报告的正文内容须包括以下内容： （1）实验目的：目的要明确，要抓住重点，符合实验指导书中的要求。 （2）实验内容：说明本实验的主要内容。 （3）实验原理：简要说明本实验项目所涉及的理论知识。 （4）实验环境：实验用的软硬件环境（配置）。 （5）实验方案：对于验证性型实验，写明依据何种原理、操作方法进行实验；对于设计型和综合型实验，写明依据何种原理、操作方法进行实验，并画出硬件组成图、软件流程图、设计思路和设计方法，再配以相应的文字说明；对于创新型实验，除符合设计型和综合型实验要求外，还应注明其创新点、特色。（6）实验步骤：写明实验的实施步骤，包括实验过程中的记录、数据。 （7）实验结果与分析：写明实验的最终结果，并对结果进行分析，做出结论。（8）实验中遇到的问题及解决方法：写明实验过程中遇到的问题及所采取的解决方法。 （9）实验总结（在封底上）：写出对本次实验的心得体会、思考和建议。

实验原理：已知线段的起点坐标()11x y ，终点坐标()22x y ，直线的点斜 式方程为：y m x b =?+，斜率和截距分别为：2121y y m x x -= - ， 11b y m x =-? 。沿x 的增量为x ?，沿y 的增量为y ?，即： 1x y m ?= ??，y m x ?=??。当1m ≤时，取x 为一个像素单位长，即x 每次增加一个像素，然后利用公式计算相应的y 值：1k k k y y y y m x -=+?=+??，相反1m >时，可以通过质量y ?来计算相应的x 值：1k k k x x x x m y -=+?=+??。 实验内容：新建一个Win32 Application 的典型“Hello World ”程序，工程 命名为：DDA 直线生成算法，打开DDA 直线生成算法.cpp 文件， 在里面加入代码： void DDA_line(HDC hdc) { double x,y,dx,dy,L,x1=100,x2=400,y1=100,y2=400; if(abs(x2-x1)>=abs(y2-y1)) L=abs(x2-x1); else L=abs(y2-y1); dx=(x2-x1)/L; dy=(y2-y1)/L; x=x1,y=y1; for(int k=1;k<=L;k++) { SetPixel(hdc,x,y,RGB(255,0,255)); x=x+dx; y=y+dy; Sleep(10); } } 实验结果：调用程序运行得出一下结果：

一种椭圆曲线快速生成算法

一种椭圆曲线参数生成的快速算法 谷勇浩 刘勇 （北京邮电大学通信网络综合技术研究所） 摘要：椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法，给出了一种生成参数a 、b 的快速算法。这种算法利用了Jacobi 符号和二次剩余的理论，并且用matlab 计算出利用这种算法生成一个椭圆曲线的平均时间，最后我们分析了今后椭圆曲线密码系统的研究方向和重点。 关键词：椭圆曲线；离散对数问题；Jacobi 符号；二次剩余；阶 1976年Diffie 和Hellman 提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为：基于大整数分解问题（IFP ），如RSA 体制和Rabin 体制；基于有限域离散对数问题（DLP ），如Diffie-Hellman 体制和ElGamal 体制；基于椭圆曲线离散对数问题（ECDLP ），如椭圆密码体制。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller 在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET(Secure Electronic Transaction)协议的制定者已把它作为下一代SET 协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 1建立椭圆曲线公钥密码体制 1.1椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363标准中，定义其参数为一个七元组：T=(q,FR,a,b,G,n,h)，其中q 代表有限域GF(q)，q 为素数或 2 m ;FR 为域表示法，如f(x)为 2 m F 域元素的不可约 多项式的表示法；曲线的方程，当q 为素数时，方程为2 3 ax b y x =++，当q 为2m 时， 方程为 2 32 xy a b y x x +=++，a,b 是方程中的系数；G 为基点；n 为大素数并且等于点G 的阶，h 是小整数称为余因子且#()/q h E n F =。主要的安全性参数是n ，因此ECC 密钥 的长度就定义为n 的长度。 1.2椭圆曲线密码的密钥 选取了基域 q F 和椭圆曲线后，得到了在有限域 q F 上的曲线E 确定的具体形式，即 上述的椭圆曲线域参数的一个七元组。每个用户选取一个整数d(1≤d ≤n-1) 作为其私钥，而以点Q=dG(G 为基点)作其公钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体的曲线，基域 q F ，基点G 及其阶n ，以及每个用户的公钥都是该系统的公开参

Bresenham的直线生成算法和整圆生成算法完整代码

以下是Bresenham的直线生成算法和整圆生成算法，已调试过，没有任何问题。Bresenham直线生成算法 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy, i; float k,e; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=-0.5; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+k; if(e>=0) { y++;e=e-1;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); } 当取e=2*dy-dx时，可以消除浮点和除法运算 #include "stdio.h" #include "graphics.h" Bresenham_line(x0,y0,x1,y1,color)

int x0,y0,x1,y1,color; { int x,y,dx,dy, i,e; float k; dx=x1-x0;dy=y1-y0; k=(dy*1.0)/dx; e=2*dy-dx; x=x0; y=y0; for (x=x0; x<=x1; x++) { putpixel(x,y,color); e=e+2*dy; if(e>=0) { y++;e=e-2*dx;} } } int main() { int x0,y0,x1,y1,c; int driver=DETECT,mode=0; initgraph(&driver,&mode,"c:\\tc"); setbkcolor(BLUE); setcolor(YELLOW); printf("input x0,y0,x1,y1,c"); scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&c); Bresenham_line(x0,y0,x1,y1,c); getch(); closegraph(); }

计算机图形学 直线的生成算法的实现

实验二 直线的生成算法的实现 班级 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(),(

案例2-直线中点Bresenham算法

课程实验报告

步骤 为了规范颜色的处事，定义了CRGB类，重载了“+”，“-”、“*”、“\”、“+=”、“-=”、“*=”、“/=”运算符。成员函数Normalize()将颜色分量red,green,blue规范到[0,1]闭区间内。 RGB.h #pragma once class CRGB { public: CRGB(); CRGB(double, double, double); ~CRGB(); friend CRGB operator + (const CRGB&, const CRGB&); friend CRGB operator - (const CRGB&, const CRGB&); friend CRGB operator * (const CRGB&, const CRGB&); friend CRGB operator * (const CRGB&, double); friend CRGB operator * (double, const CRGB&); friend CRGB operator / (const CRGB&, double); friend CRGB operator += (const CRGB&, const CRGB&); friend CRGB operator -= (const CRGB&, const CRGB&); friend CRGB operator *= (const CRGB&, const CRGB&); friend CRGB operator /= (const CRGB&, double); void Normalize(); public: double red; double green; double blue; }; RGB.cpp #include"stdafx.h" #include"RGB.h" CRGB::CRGB() { red = 1.0; green = 1.0; blue = 1.0;

(1)直线生成算法.doc

课程名称：计算机图形学指导教师：罗晓辉 上机实践名称：基本图形（直线）生成算法 年级：2008 姓名：孔广波 学号：312008********* 上机实践成绩： 上机实践日期：2011-4-10 实验一: 直线生成算法 上机实践报告 一、实验目的 理解直线生成的基本原理，掌握儿种常见的直线生成算法，利用Microsoft Visual C++6.0实现直线生成的DDA算法。 二、实验内容： 1）了解直线的生成原理。 2）掌握儿种基本的直线生成算法：DDA画线法、Bresenham画线法、中点画线法。 3）利用Microsoft Visual C++6.0实现直线生成的DDA算法，在屏幕上任意生成一条直线。 三、实验步骤： 1）预习教材关于直线的生成原理。 2）仿照教材关于直线生成的DDA算法，使用Microsoft Visual C++6.0实现该算法。 3）调试、编译、运行程序。 四、实验分析、源程序和结果： （1.1）中点算法分析： 中点画线算法原理示意图

直线斜率：k属于[0, 1] 线段的隐式方程：F(x,y) = ax + by + c = 0 ((x0 , y0), ( xl , yl )为两端点，式中a = yO - yl , b = xl - xO , c = xO * yl - xl * yO) 直线上方的点：F(x , y) > 0 直线下方的点：F ( x , y ) < 0 构造判别式：d = F(M) = F(Xp+l,Yp + 0.5) 由d>0, V0 可判定下一个象素，d 的初始值：d0 = F( X0 + 1 , Y0 + 0.5 ) = F( X0 , Y0 ) + a + 0.5b 因(X0, YO)在直线上，F(X0 , YO ) = 0,所以，dO = a + 0.5b (1.2)具体实现代码： void CGView::Line_DDA(long plxjong ply,long p2x,long p2y,CDC *pDC)〃画直线算法实现 ( int a,b,del 1 ,del2,d,x,y; b=p2x-plx; a=ply-p2y; d=2*a+b; dell=2*a; del2=2*(a+b); x=plx; y=piy； pDC->SetFixel(x,y,mJPenColor)； while(xSetPixel(x,y-2,m_lPenColor); pDC->SetPixel(x,y-1 ,m_lPenColor); pDC->SetPixeI(x,y,m_lPenColor); pDC->SetPixel(x,y+1 ,m_IPenColor); pDC->SetPixel(x,y,m_lPenColor);

Bresenham算法

Course Page
Page 1 of 6
课程首页 > 第二章 二维图形的生成 > 2.1 直线的生成 > 2.1.2 生成直线的Bresenham算法
全部隐藏
2.1.2 生成直线的Bresenham算法
从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。 在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。 一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一 个象素。 我们首先讨论m=△ y/△x，当0≤m≤1且x1有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。 二、直线Bresenham算法思想之一： 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设 m<1），如下图所示。那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。
由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2：
d1=y-yi=m(xi+1)+b-yi d2=(yi+1)-y=(yi+1)-m(xi+1)-b 这两个距离差是 d1-d2=2m(xi+1)-2yi＋2b-1
(2－8) (2－9)
(2－10)
我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。 (2)当此值为负时，d1mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht
2011-7-12

OpenGL-实验2直线生成算法实现教学文案

实验2 直线生成算法实现 1.实验目的 理解基本图形元素光栅化的基本原理, 掌握一种基本图形元素光栅化算法, 利用0penGL 实现直线光栅化的DDA算法。 2.实验内容 (1)根据所给的直线光栅化的示范源程序, 在计算机上编译运行, 输出正确结果。 (2)指出示范程序采用的算法, 以此为基础将其改造为中点线算法或Bresenham算法,写 入实验报告。 (3)根据示范代码,将其改造为圆的光栅化算法,写入实验报告。 (4)了解和使用OpenGL的生成直线的命令,来验证程序运行结果。 3.实验原理 示范代码原理DDA算法。下面介绍OpenGL画线的一些基础知识和glutReshapeFunc（）函数。 (1)数学上的直线没有宽度,但0penGL的直线则是有宽度的。同时, OpenGL的直线必须是有限长度,而不是像数学概念那样是无限的。可以认为, OpenGL的“直线”概念与数学上的“线段”接近,它可以由两个端点来确定。这里的线由一系列顶点顺次连接而成, 有闭合和不闭合两种。 前面的实验已经知道如何绘“点”,那么OpenGL是如何知道拿这些顶点来做什么呢? 是依次画出来,还是连成线? 或者构成一个多边形? 或是做其他事情? 为了解决这一问题, OpenGL要求:指定顶点的命令必须包含在glBegin函数之后, glEnd函数之前(否则指定的顶点将被忽略),并由glBegin来指明如何使用这些点。 例如: glBegin(GL P0INTS) , glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES,则两个点将被认为是直线的两个端点, OpenGL将会画出一条直线。还可以指定更多的顶点, 然后画出更复杂的图形。另一方面, glBegin支持的方式除了GL_POINTS和GL_LINES,还有GL LINE STRIP、GL LINE L0〇P、GL TRIANGLES、GL TRIANGLE STRIP、GL TRIANGLE_FAN等几何图元。 (2) 首次打开窗口、移动窗口和改变窗口大小时, 窗口系统都将发送一个事件, 以通知程序员。如果使用的是GLUT,通知将自动完成,并调用向glutReshapeFunc注册的函数。该函数必须完成下列工作: ①重新建立用作新渲染画布的矩形区域。 ②定义绘制物体时使用的坐标系。 如: void Reshape(int w, int h) { glViewport(0, 0, (GLsizei) w, (GLsizei) h);

直线和圆弧的生成算法

第3章直线和圆弧的生成算法 3.1直线图形的生成算法 数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。 3.1.1逐点比较法 3.1.2数值微分(DDA)法 设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为L(P0 ,P1)，则直线段L的斜率 L的起点P 的横坐标x0向L的终点P1的横坐标x1步进，取步长=1(个像素)，用L 的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round(y))作为当前点的坐标。因为： y = kx i+1+b i+1 = k1x i+b+k x = y i+k x 所以，当x =1; y i+1 = y i+k。也就是说，当x每递增1，y递增k(即直线斜率)。根据这个原理，我们可以写出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）的直线段。 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 图3.1.1 直线段的扫描转换 注意：上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y 进行四舍五入后取整，这使得它不利于硬件实现。

CG_实验2_基本图形元素(直线)生成算法的实现

实验二基本图形元素（直线）生成算法的实现 1．实验目的： 理解基本图形元素光栅化的基本原理，掌握一种基本图形元素光栅化算法，利用OpenGL实现直线光栅化的DDA算法。 2．实验内容： （1）根据所给的直线光栅化的示范源程序，在计算机上编译运行，输出正确结果； （2）指出示范程序采用的算法，以此为基础将其改造为中点线算法或Bresenham算法，写入实验报告； （3）根据示范代码，将其改造为圆的光栅化算法，写入实验报告； （4）了解和使用OpenGL的生成直线的命令，来验证程序运行结果。 3．实验原理： 示范代码原理参见教材直线光栅化一节中的DDA算法。下面介绍下OpenGL画线的一些基础知识和glutReshapeFunc()函数。

（1）数学上的直线没有宽度，但OpenGL的直线则是有宽度的。同时，OpenGL的直线必须是有限长度，而不是像数学概念那样是无限的。可以认为，OpenGL的“直线”概念与数学上的“线段”接近，它可以由两个端点来确定。这里的线由一系列顶点顺次连结而成，有闭合和不闭合两种。 前面的实验已经知道如何绘“点”，那么OpenGL是如何知道拿这些顶点来做什么呢？是一个一个的画出来，还是连成线？或者构成一个多边形？或是做其它事情呢？为了解决这一问题，OpenGL要求：指定顶点的命令必须包含在glBegin函数之后，glEnd函数之前（否则指定的顶点将被忽略），并由glBegin来指明如何使用这些点。 例如： glBegin(GL_POINTS); glVertex2f(0.0f, 0.0f); glVertex2f(0.5f, 0.0f); glEnd(); 则这两个点将分别被画出来。如果将GL_POINTS替换成GL_LINES，则两个点将被认为是直线的两个端点，OpenGL将会画出一条直线。还可以指定更多的顶点，然后画出更复杂的图形。另一方面，glBegin 支持的方式除了GL_POINTS和GL_LINES，还有GL_LINE_STRIP，GL_LINE_LOOP，GL_TRIANGLES，GL_TRIANGLE_STRIP，

直线中点Bresenham算法

实验一基本图形生成算法 实验目的： 掌握中点Bresenham绘制直线的原理 设计中点Bresenham算法 编程实现中点Bresenham算法 实验描述： 使用中点Bresenham算法绘制斜率为0≤k≤1的直线。 算法设计： 直线中点Bresenham算法 1. 输入直线的起点坐标P0（x0，y0）和终点坐标P1（x1，y1）。 2. 定义直线当前点坐标x，y、定义中点偏差判别式d、定义直线斜率k、定义像素点颜色 rgb。 3. x=x0，y=y0，计算d=0.5-k，k=(y1-y0)/(x1-x0)，rgb＝RGB(0,0,255)。 4. 绘制点（x，y），判断d的符号。若d<0，则（x，y）更新为（x＋1，y＋1），d 更新为 d＋1－k；否则（x，y）更新为（x＋1，y），d更新为d－k。 5. 如果当前点x 小于x1，重复步骤4，否则结束。 源程序： 1)// TestView.h #include "InputDlg.h"//对话框头文件 #define ROUND(a) int(a+0.5) class CTestView : public CView { ….. } 2)//TestView.cpp void CTestView::OnMENUMbline()//菜单函数 { InputDlg dlg; if(dlg.DoModal()==IDOK) { AfxGetMainWnd()->SetWindowText(":直线中点Bresenham算法"); RedrawWindow(); Mbline(dlg.m_x0, dlg.m_y0, dlg.m_x1, dlg.m_y1); } } void CTestView::Mbline(double x0, double y0,double x1,double y1) //直线中点Bresenham函数 { CClientDC dc(this); COLORREF rgb=RGB(255,0,0); //定义直线颜色为红色 double x,y,d,k; x=x0;y=y0;k=(y1-y0)/(x1-x0);d=0.5-k;

bresenham画线算法详解

给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢，即是如何得到上图所示的蓝色的点。假设直线的斜率00,直线在第一象限，Bresenham算法的过程如下： 1.画起点(x1, y1). 2.准备画下一个点，X坐标加1，判断如果达到终点，则完成。否则找下一个点，由图可知要画的点要么为当前点的右邻接点，要么是当前点的右上邻接点。 2.1.如果线段ax+by+c=0与x=x1+1的交点y坐标大于(y+*y+1))/2则选右上那个点 2.2.否则选右下那个点。 3.画点 4.跳回第2步 5.结束 具体的算法如下，原理就是比较目标直线与x+1直线交点的纵坐标，哪个离交点近就去哪个void Bresenhamline(int x0, int y0, int x1, int y1, int color) { int x, y, dx, dy; float k, e; dx = x1 - x0; dy = y1 - y0; k = dy / dx; e = -0.5; x = x0; y = y0; for (x= x0;x < x1; x++) { drawpixel(x, y, color);//这个是画点子函数

e = e + k; if (e > 0) { y++; e = e - 1; } } } 上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。等式两边同时乘以2*dx，得到2*e*dx = 2*e*dx + 2dy, 2*e*dx = 2*e*dx - 2*dx.由于算法中只用到误差项的符号，因此可作如下替换：2*e*dx.改进的Bresenham画线算法程序：将e统一乘以2*dx即变成了整数的Bresenhan算法了，^_^ void InterBresenhamline (int x0, int y0, int x1, int y1, int color) { int dx = x1 - x0； int dy = y1 - y0； int dx2 = dx << 1;//乘2 int dy2 = dy<< 1;//乘2 int e = -dx; int x = x0； int y = y0; for (x = x0; x < x1; x++) { drawpixel (x, y, color); e=e + dy2; if (e > 0) { y++; e = e - dx2; } } }

直线生成算法的实现

实验二：直线生成算法 班级 13软件+道铁1班学号 20132110050115姓名丁益 1.实验目的 a)通过实验，进一步理解直线段扫描转换的DDA算法、中点画线自算法 及bresenham算法的基本原理，掌握以上算法生成直线段的基本过程。 b)通过编程，掌握在C/C++环境下完成用DDA算法、中点画线算法及 bresenham算法对任意直线段的扫描转换，以及在C/C++环境下完成用中 点画圆及椭圆的绘制方法。 2.实验内容 c)阅读《openGL三维程序设计》（电子书）第二部分第四章，掌握OpenGL 基本建模方法，并调试其中程序。 d)参考教材第6章，编程实现整数DDA算法、中点画线法和Bresenham 画线法，绘制直线（直线宽度和线型可自定）。 2.1 DDA直线生成 2.1.1算法原理 已知过端点P0（x0,y0），P1（x1,y1）的直线段L(P0,P1)，斜率为k=(y1-y0)/(x1-x0)，画线过程从x的左端点x0开始，向x右端点步进，步长为1个像素，计算相应的y坐标为y=kx+B。计算y i+1 = kx i+B =kx i +B+kx =y i +kx 当x=1,y i+1=y i+k，即当x每递增1，y递增k。由计算过程可知，y与k可能为浮点数，需要取y整数，源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。 2.1.2 算法流程

2.1.3 算法实现关键代码 #include #include void Init() { glClearColor(1.0,1.0,1.0,0.0); glMatrixMode(GL_PROJECTION); gluOrtho2D(0.0,200.0,0.0,150.0); } void lineDDA(int x0,int y0,int xEnd,int yEnd) { int dx=xEnd-x0,dy=yEnd-y0,steps,k; float xIncrement, yIncrement, x=x0, y=y0; if(fabs(dx)>fabs(dy)) steps=fabs(dx); else steps=fabs(dy); xIncrement=float(dx)/float(steps); yIncrement=float(dy)/float(steps); for(k=0;k

实验1：Bresenham算法

实验1：Bresenham算法 实验题目： Bresenham直线扫描算法的实现 实验内容及要求： 实现绘制各种情况直线的Bresenham算法，并将实现的算法应用于任意多边形的绘制，要求多边形的顶点由键盘输入或鼠标拾取，绘制的多边形顶点要准确，图形应该封闭。要求掌握Bresenham算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者VC++实现算法，并演示。 实验原理： 1、Bresenham基本算法： 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。 设直线方程为： 其中k=dy/dx。因为直线的起始点在象素中心，所以误差项d的初值d0＝0。 X下标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦d≥1， 就把它减去1，这样保证d在0、1之间。 当d≥0.5时，最接近于当前象素的右上方象素（） 当d<0.5时，更接近于右方象素（）。 为方便计算，令e＝d-0.5，e的初值为-0.5，增量为k。 当e≥0时，取当前象素（x i，y i）的右上方象素（）； 而当e<0时，更接近于右方象素（）。 可以改用整数以避免除法。 d d d d k y x x k y y i i i i i + = - + = + + ) ( 1 1 1 1 , + +i i y x i i y x, 1+ 1 1 , + +i i y x i i y x, 1+

Bresenham算法代码如下： void Bresenhamline(int x1, int y1, int x2, int y2,CDC *pDC) { //对于所有直线均按照从左至右的方向绘制 int x,y,d,dx,dy,right,rightleft; if(x1>x2){ int tempx,tempy; tempx=x1;x1=x2;x2=tempx; tempy=y1;y1=y2;y2=tempy; } //根据斜率的情况不同而绘制 if(y1==y2){//斜率为0的情况 for(x=x1;x<=x2;x++) pDC->SetPixel(x,y1,2); } else if(x1==x2){//直线为垂直的情况 if(y1>y2){ //使直线按从下往上画 int tempy=y1; y1=y2;y2=tempy; } for(y=y1;y<=y2;y++) pDC->SetPixel(x1,y,2); } else{ dy=y2-y1; dx=x2-x1; if(abs(dy)==abs(dx)){////斜率为1或-1时 x=x1;y=y1; if(dy<0){//斜率为1 for(;y>=y2;y--){ x++; pDC->SetPixel(x,y,2); } }//斜率为1 else{//斜率为-1 for(;y<=y2;y++){ x++; pDC->SetPixel(x,y,2); } }//斜率为-1 } else if(abs(dy)0&&dx>0){//斜率为正时 right=-2*dy; rightleft=2*dx-2*dy; d=dx-2*dy; x=x1;y=y1; while(x<=x2){ pDC->SetPixel(x,y,2); x++; if(d<0){ y++; d=d+rightleft; }else{ d=d+right; } } }//斜率为正时 else {//斜率为负时 right=2*dy; rightleft=2*dy-2*dx; d=2*dy-dx; x=x1;y=y1; while(x<=x2){ pDC->SetPixel(x,y,2); x++; if(d<0){ y++;

直线生成算法——Bresenham法

直线生成算法——Bresenham法 最近的研究涉及在像素图上作直线，自己也不想花时间摸索，于是在网上找到了Bresenham的直线生成算法，有一篇博客讲得清晰明了，但是算法上有些问题，我进行了改进和移植，下面讲解Bresenham的直线生成算法时也是参考这篇博文。 1.算法简介 图1 算法思想：图1中，连接M点和N点的直线经过点B，由于是像素图，所以实际上B 点应该由A点或者C点代替。当B点更靠近A点时，选择点A（x+1,y+1）；当B点更靠近C点时，选择点C（x+1,y）。 因此，当ε+m < 0.5时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点，这里ε为累加误差，表达式为： 式中：表示在第n次计算时的值，表示在第n+1次计算时的值；m就是直线的 斜率。 由于斜率m的值有正有负，有可能为0，也可能为∞，为了避免分别讨论这些情况， 将上述公式两边都乘以dx, 并将ε*dx用ξ表示，则有 式中：表示在第n次计算时的值，表示在第n+1次计算时的值；dx为起 点和终点横坐标之差，dy为起点和终点纵坐标之差。 还需说明一点，由直线斜率的定义 故

值得注意的是，现在我们只考虑dx > dy，且x，y的增量均为正的情况，但实际上有8种不同的情况（但是算法思想不变），如图2所示 如图2 2.算法程序 前文提到的那篇博文提出了一种方法，能将这8种情况都考虑，很巧妙。但是实际应用时发现程序运行结果不是完全对，多次检查之后将程序进行了修改。 修改后的算法VB程序如下 ‘**************************************************************************** Type mypos '自定义数据类型 x As Integer y As Integer End Type ‘**************************************************************************** Function Bresenham(arr() As mypos, x1, y1, x2, y2) Dim x!, y!, dx!, dy!, ux%, uy%, eps! Dim cnt% ReDim arr(100) dx = x2 - x1 dy = y2 - y1 If dx >= 0 Then ux = 1 If dx < 0 Then ux = -1

Bresenham直线算法与画圆算法

Bresenham直线算法与画圆算法 文章分类:Java编程 计算机是如何画直线的？简单来说，如下图所示，真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。 （上图来自于互联网络，《计算机图形学的概念与方法》柳朝阳，郑州大学数学系） 接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。 Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。 (引自wiki百科布雷森漢姆直線演算法) 这个算法的流程图如下：

可以看到，算法其实只考虑了斜率在 0 ~ 1 之间的直线，也就是与 x 轴夹角在 0 度到 45 度的直线。只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。 下面是一个C语言实现版本。 Java代码 1.view sourceprint? 2. // 交换整数 a 、b 的值 3. 4.inline void swap_int(int *a, int *b) 5.{ 6. *a ^= *b; 7. *b ^= *a; 8. *a ^= *b;

9.} 10. 11.// Bresenham's line algorithm 12. 13.void draw_line(IMAGE *img, int x1, int y1, int x2, int y2, unsi gned long c) 14.{ 15. // 参数 c 为颜色值 16. int dx = abs(x2 - x1), 17. dy = abs(y2 - y1), 18. yy = 0; 19. 20. if(dx < dy) 21. { 22. yy = 1; 23. swap_int(&x1, &y1); 24. swap_int(&x2, &y2); 25. swap_int(&dx, &dy); 26. } 27. 28. int ix = (x2 - x1) > 0 ? 1 : -1, 29. iy = (y2 - y1) > 0 ? 1 : -1, 30. cx = x1, 31. cy = y1, 32. n2dy = dy * 2, 33. n2dydx = (dy - dx) * 2, 34. d = dy * 2 - dx; 35. 36.// 如果直线与 x 轴的夹角大于45度 37. if(yy) 38. { 39. while(cx != x2) 40. { 41. if(d < 0) 42. { 43. d += n2dy; 44. } 45. else 46. { 47. cy += iy; 48. d += n2dydx; 49. } 50. 51. putpixel(img, cy, cx, c);