画图板--用DDA算法和Bresenham算法画直线

直线算法的技巧

直线算法的技巧直线算法是计算机图形学中最基本的算法之一，用于在屏幕上绘制直线。

本文将就直线算法的一些技巧进行详细讲解。

直线算法通常需要一个起始点（x1, y1）和一个终止点（x2, y2），然后在这两个点之间绘制一条直线。

最基本的直线算法是数字微分分析法（DDA）和中点画线法（Bresenham算法）。

这两种算法的核心思想都是利用直线的斜率来进行像素点的逼近。

在使用DDA算法绘制直线时，可以通过增加步长来减少精度损失。

DDA算法的步骤如下：1. 计算斜率：计算直线的斜率m = (y2 - y1) / (x2 - x1)。

2. 判断斜率：判断斜率的绝对值是否在0和1之间。

如果是，我们可以选择在x上递增逼近y或在y上递增逼近x。

3. 增加步长：计算递增的步长，对于长度较大的直线，可以通过增加步长来减少计算数量。

4. 开始绘制：从起始点开始，根据斜率和步长计算下一个要绘制的像素点的坐标。

5. 终止条件：当当前的坐标达到终止点时，终止绘制。

中点画线法（Bresenham算法）是一种更高效的直线算法，它通过使用整数运算和位移来避免了浮点数运算，提高了绘制速度。

Bresenham算法的步骤如下：1. 初始化：初始化起始点（x1, y1）和终止点（x2, y2），并计算dx = x2 - x1 和dy = y2 - y1 。

2. 计算斜率：判断斜率m = dy / dx，以决定使用什么方式增加x和y的值（水平递增或垂直递增）。

3. 计算误差：计算误差项E = -0.5，并对dx和dy进行判断，确定每个点移动时误差项的变化。

若dx > dy，则E += dy；否则，E += dx。

4. 绘制像素点：从起始点开始，每次根据误差项判断，决定是在y上递增还是在x上递增，并根据计算出的新的坐标绘制像素点。

5. 更新误差项：在每次绘制完成后，根据dx和dy更新误差项的值。

6. 终止条件：当当前的坐标达到终止点时，终止绘制。

计算机图形学直线DDA算法和Bresenham算法

{
Graphicsgraphics =this.CreateGraphics();
bmp =newBitmap(this.ClientRectangle.Width,this.ClientRectangle.Height);
DDAline(27, 19, 200, 183, bmp);
graphics.DrawImage(bmp,newRectangle(0, 0,this.ClientRectangle.Width,this.ClientRectangle.Height));
{
x++;
y = x + k;
}
else
{
y++;
x = y + (1 / k);
}
{
bmp.SetPixel(x, y,Color.Red);
}
}
}
privatevoidbutton1_Click(objectsender,EventArgse)
{
Graphicsgraphics =this.CreateGraphics();
④代码与运行结果;
usingSystem;
usingSystem.Collections.Generic;
ponentModel;
usingSystem.Data;
usingSystem.Drawing;
usingSystem.Linq;
usingSystem.Text;
③实验步骤:
1、在C#环境下，设计界面，添加4个文本框，三个命令按钮；
2、在代码编写窗口，编写DDA、中点直线生成算法、Bresenham直线生成算法子程序，子程序名分别设为DDALine,MidPointLine和BresenhamLine；

DDA、Bresenham、Midpoint算法画直线报告1

课程名称计算机图形学实验名称DDA、Bresenham、Midpoint算法画直线一、实验目的及要求（1）理解窗口到视区的变换（2）理解MFC创建工程实现动画的原理(3) 学习MFC类库的概念与结构（4）学习使用VC++编写Win32应用的方法（单文档，多文档，对话框）（5）学习使用MFC的图形编程软件环境：Microsoft studio visual C++ 6.0 MFC硬件：计算机二、实验内容（1）添加代码实现DDA算法画直线（2）添加代码实现Bresenham算法画直线（3）添加代码实现Midpointline画直线(4) 添加代码实现画圆三、实验步骤选择工作环境添加工程名选择程序类型前几步省略全选默认值选择resource-Menu添加不同函数画直线和圆为每个函数建立类向导在fileview中打开source filesview.cpp输入各函数代码并编译运行无误四、实验源码// 直线和圆View.cpp : implementation of the CMyView class//#include "stdafx.h"#include "直线和圆.h"#include "直线和圆Doc.h"#include "直线和圆View.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif///////////////////////////////////////////////////////////////////////////// // CMyViewIMPLEMENT_DYNCREATE(CMyView, CView)BEGIN_MESSAGE_MAP(CMyView, CView)//{{AFX_MSG_MAP(CMyView)ON_COMMAND(ID_DDALINE, OnDdaline)ON_COMMAND(ID_MIDPOINTLINE, OnMidpointline)ON_COMMAND(ID_BRESENHAMLINE, OnBresenhamline)ON_COMMAND(ID_MIDPOINTCIRCLE, OnMidpointcircle)//}}AFX_MSG_MAP// Standard printing commandsON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)END_MESSAGE_MAP()///////////////////////////////////////////////////////////////////////////// // CMyView construction/destructionCMyView::CMyView(){// TODO: add construction code here}CMyView::~CMyView(){}BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// the CREATESTRUCT csreturn CView::PreCreateWindow(cs);}///////////////////////////////////////////////////////////////////////////// // CMyView drawingvoid CirclePoints(int x,int y,int color ,CDC* pDC ){pDC->SetPixel(x,y,color);pDC->SetPixel(y,x,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(y,-x,color);pDC->SetPixel(x,-y,color);pDC->SetPixel(-y,x,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-y,-x,color);}void Midpointcircle(int r,int color,CDC* pDC){int x,y;float d;x=0;y=r;d=1.25-r;CirclePoints(x,y,color,pDC);pDC->SetViewportOrg(200,100);while(x<=y){if(d<0)d+=2*x+3;else{d+=2*(x-y)+5; y--;}x++;CirclePoints(x,y,color,pDC);}}void DDA(int x0,int y0,int x1,int y1,int color,CDC* pDC){int x;float dx,dy,y,k;dx=x1-x0;dy=y1=y0;k=dy/dx;y=y0;for(x=x0;x<=x1;x++){pDC->SetPixel(x,int (y+0.5), color);y=y+k;}}void Bresenhamline(int x0,int y0,int x1,int y1,int color,CDC* pDC) {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(int i=0;i<=dx;i++){pDC->SetPixel(x,y,color);x=x+1;e=e+k;if(e>=0){y++;e=e-1;}}}void Midpointline(int x0,int y0,int x1,int y1,int color,CDC* pDC) {int a,b,d1,d2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;pDC->SetPixel(x,y,color);while (x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}pDC->SetPixel(x,y,color);}}void CMyView::OnDraw(CDC* pDC){CMyDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);Midpointcircle(100,RGB(0,168,168),pDC) ;DDA(0,0, 250,300,RGB (255,0,255),pDC);Midpointline(0,0, 500,200,RGB (255,255,0),pDC);Bresenhamline(0,0, 150,600,RGB (168,200,168),pDC);// TODO: add draw code for native data here}///////////////////////////////////////////////////////////////////////////// // CMyView printingBOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo){// default preparationreturn DoPreparePrinting(pInfo);}void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/){// TODO: add extra initialization before printing}void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/){// TODO: add cleanup after printing}///////////////////////////////////////////////////////////////////////////// // CMyView diagnostics#ifdef _DEBUGvoid CMyView::AssertValid() const{CView::AssertValid();}void CMyView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CMyDoc* CMyView::GetDocument() // non-debug version is inline{ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));return (CMyDoc*)m_pDocument;}#endif //_DEBUG///////////////////////////////////////////////////////////////////////////// // CMyView message handlersvoid CMyView::OnDdaline(){// TODO: Add your command handler code here}void CMyView::OnMidpointline(){// TODO: Add your command handler code here}void CMyView::OnBresenhamline(){// TODO: Add your command handler code here}void CMyView::OnMidpointcircle(){// TODO: Add your command handler code here}五.实验结果六. 实验总结分析通过做这个实验学会了使用这个软件，也了解到指针的用法，在做之初由于对指针用法的不熟悉，所以遇到很多问题，从提示中弹出的CDC类，通过对它的学习，我将源码中的drawpixel改写成调用CDC类的pDC指针的用法，再插入pDC->SetViewportOrg(200,100);实现了圆心的移动，实现了对直线的绘制，现在对它的操作已基本掌握了。

使用DDA和Bresenham绘制直线

九、注意及特别说明：
1ɺ 凡使用 LineTo（）函数、Polyline（）函数绘制直线的，本次实验没有成绩。 2ɺ 如对 Visual C++的编译环境不熟悉，请课下提前参考 Visual C++的相关书籍和 MSDN。
int i; float dx,dy,length,x,y;
if (fabs(x1-x0)>=fabs(y1-ylse length=fabs(y1-y0);
dx=(x1-x0)/length; dy=(y1-y0)/length; i=1; x=x0; y=y0; while(i<=length) {
Bresenham 算法是 DDA 算法画线算法的一种改进算法。本质上它也是采取了步进的思想。不过它比 DDA 算法作了优化，避免了步进时浮点数运算，同时为选取符合直线方程的点提供了一个好思路。首先通过直线的斜率确定了在 x 方向进行单位步进还是 y 方向进行单位步进：当斜率 k 的绝对值|k|<1 时，在 x 方向进行单位步进；当斜率 k 的绝对值|k|>1 时，在 y 方向进行单位步进。
图3
图4 4ɺ 在函数体 void DDALine(int x0, int y0, int x1, int y1, COLORREF color)中，实现 DDA
算法。具体代码参考教材 P30~P31。需要注意的是，调用 Setpixel 函数之前需要得到设备上下文，即在函数体中加入如下代码：
CDC *pDC = this->GetDC(); 然后，用 pDC->SetPixel(int (x + 0.5), int (y + 0.5), color); 代替原来程序中的 SetPixel(int (x + 0.5), int (y + 0.5), color);即可。以后使用 Bresenham 绘制直线的算法中调用 SetPixel 函数的情况按同样的方法处理。 5ɺ 同步骤 3 类似，在 CGView.cpp 文件中（类 CCGView 中），添加函数 void Bresenham_Line(int x0, int y0, int x1, int y1, COLORREF color)。实现代码参考教材 P33 的 Bresenham 画线算法程序。参考步骤 4，注意对函数 Setpixel 的调用。

Bresenham快速画直线算法

Bresenham快速画直线算法现在的计算机的图像的都是⽤像素表⽰的，⽆论是点、直线、圆或其他图形最终都会以点的形式显⽰。

⼈们看到屏幕的直线只不过是模拟出来的，⼈眼不能分辨出来⽽已。

那么计算机是如何画直线的呢，其实有⽐较多的算法，这⾥讲的是Bresenham的算法，是光栅化的画直线算法。

直线光栅化是指⽤像素点来模拟直线，⽐如下图⽤蓝⾊的像素点来模拟红⾊的直线。

给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢，即是如何得到上图所⽰的蓝⾊的点。

假设直线的斜率0<k>0,直线在第⼀象限，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.结束算法的具体过程是怎样的呢，其实就是在每次画点的时候选取与实现直线的交点y坐标的差最⼩的那个点，例如下图：关键是如何找最近的点，每次x都递增1，y则增1或者不增1，由上图，假设已经画了d1点，那么接下来x加1，但是选d2 还是u点呢，直观上可以知道d2与⽬标直线和x+1直线的交点⽐较近即纵坐标之差⼩也即与(x+1, y+1)点纵坐标差⼤于0.5，所当然是选d2，其他点了是这个道理。

⼀、算法原理简介：算法原理的详细描述及部分实现可参考：假设以(x, y)为绘制起点，⼀般情况下的直观想法是先求m = dy /dx（即x每增加1， y的增量），然后逐步递增x, 设新的点为x1 = x + j,则y1 = round(y + j * m)。

可以看到，这个过程涉及⼤量的浮点运算，效率上是⽐较低的（特别是在嵌⼊式应⽤中，DSP可以⼀周期内完成2次乘法，⼀次浮点却要上百个周期）。

bresenham画线算法详解

给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢，即是如何得到上图所示的蓝色的点。

假设直线的斜率0<k>0,直线在第一象限，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;//乘2int dy2 = dy << 1;//乘2int 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;}}}。

DDA法,中点法,Bresenham法画直线

实验名称 DDA 法，中点法，Bresenham 法画直线一、实验目的学会用DDA 法，中点法，Bresenham 法这三种思想画直线，同时，对画直线的操作有一定的了解。

二、实验原理及内容1. DDA 法的基本思想如下：已知过端点P0(x0,y0) , P1(x1,y1)的直线段L ：y=kx+b ,直线斜率为k=(y1-y0)/x1-x0 ,从x 的左端点x0开始，向x 右端点步进。

步长=1(个象素)，计算相应的y 坐标y=kx+b ；取象素点(x, round(y))作为当前点的坐标。

2. 中点法的基本思想如下：当前象素点为(xp, yp) 。

下一个象素点为P1 或P2 。

设M=(xp+1, yp+0.5)，为p1与p2之中点，Q 为理想直线与x=xp+1垂线的交点。

将Q 与M 的y 坐标进行比较。

当M 在Q 的下方，则P2 应为下一个象素点；M 在Q 的上方，应取P1为下一点。

构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c ,其中a=y0-y1, b=x1-x0, c=x0y1-x1y0当d<0，M 在L(Q 点)下方，取右上方P2为下一个象素；当d>0，M 在L(Q 点)上方，取右方P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素；但这样做，每一个象素的计算量是4个加法，两个乘法。

采用增量算法改进如下：d 是xp, yp 的线性函数，因此可采用增量计算，提高运算效率。

若当前象素处于d 0情况，则取正右方象素P1 (xp+1, yp), 要判下一个象素位置，应计算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a ；增量为a ，若d<0时，则取右上方象素P2 (xp+1, yp+1)。

要判断再下一象素，则要计算d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为a ＋b画线从(x0, y0)开始，d 的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b 。

计算机图形学--Bresenham完整算法-画直线、椭圆和圆

#include<windows.h>#include<gl/glut.h>#include"stdio.h"int m_PointNumber = 0; //动画时绘制点的数目int m_DrawMode = 1; //绘制模式 1 DDA算法画直线// 2 中点Bresenham算法画直线// 3 改进Bresenham算法画直线// 4 八分法绘制圆// 5 四分法绘制椭圆//绘制坐标线void DrawCordinateLine(void){int i = -250 ;//坐标线为黑色glColor3f(0.0f, 0.0f ,0.0f);glBegin(GL_LINES);for (i=-250;i<=250;i=i+10){glVertex2f((float)(i), -250.0f);glVertex2f((float)(i), 250.0f);glVertex2f(-250.0f, (float)(i));glVertex2f(250.0f, (float)(i));}glEnd();}//绘制一个点，这里用一个正方形表示一个点void putpixel(GLsizei x, GLsizei y){glRectf(10*x,10*y,10*x+10,10*y+10);}/////////////////////////////////////////////////////////////////////DDA画线算法 //// //// //// /////////////////////////////////////////////////////////////////////void DDACreateLine(GLsizei x0, GLsizei y0, GLsizei x1, GLsizei y1, GLsizei num) {//设置颜色glColor3f(1.0f,0.0f,0.0f);//对画线动画进行控制if(num == 1)printf("DDA画线算法：各点坐标\n");else if(num==0)return;//画线算法的实现GLsizei dx,dy,epsl,k;GLfloat x,y,xIncre,yIncre;dx = x1-x0;dy = y1-y0;x = x0;y = y0;if(abs(dx) > abs(dy)) epsl = abs(dx);else epsl = abs(dy);xIncre = (float)dx / epsl ;yIncre = (float)dy / epsl ;for(k = 0; k<=epsl; k++){putpixel((int)(x+0.5), (int)(y+0.5));if (k>=num-1) {printf("x=%f , y=%f,取整后 x=%d,y=%d\n", x, y, (int)(x+0.5),(int)(y+0.5));break;}x += xIncre;y += yIncre;if(x >= 25 || y >= 25) break;}}/////////////////////////////////////////////////////////////////////中点Bresenham算法画直线(0<=k<=1) //// //// //// /////////////////////////////////////////////////////////////////////void BresenhamLine(GLsizei x0, GLsizei y0, GLsizei x1, GLsizei y1, GLsizei num){glColor3f(1.0f,0.0f,0.0f);if(num == 1)printf("中点Bresenham算法画直线各点坐标及判别式的值\n");else if(num==0)return;//画线算法的实现GLsizei p=0;GLfloat UpIncre,DownIncre,x,y,d,k,dx,dy;if(x0>x1){x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;}x=x0;y=y0;dx=x1-x0;dy=y1-y0;k=dy/dx;if(k>=0&&k<=1){d=dx-2*dy;UpIncre=2*dx-2*dy;DownIncre=-2*dy;while(x<=x1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;x++;if(d<0){y++;d+=UpIncre;}else d+=DownIncre;}}if(k>1){d=dy-2*dx;UpIncre=2*dy-2*dx;DownIncre=-2*dx;while(y<=y1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;y++;if(d<0){x++;d+=UpIncre;}else d+=DownIncre;}}if(k<0&&k>=-1){d=dx-2*dy;UpIncre=-2*dy;DownIncre=-2*dx-2*dy;while(x<=x1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;x++;if(d>0){y--;d+=DownIncre;}else d+=UpIncre;}}if(k<-1){d=-dy-2*dx;UpIncre=-2*dx-2*dy;DownIncre=-2*dx;while(y>=y1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;y--;if(d<0){x++;d+=UpIncre;}else d+=DownIncre;}}}/////////////////////////////////////////////////////////////////////改进的Bresenham算法画直线(0<=k<=1) //// //// x1,y1 终点坐标 //// /////////////////////////////////////////////////////////////////////void Bresenham2Line(GLsizei x0, GLsizei y0, GLsizei x1, GLsizei y1, GLsizei num) {glColor3f(1.0f,0.0f,0.0f);GLsizei x,y,dx,dy,e,k;if(num == 1)printf("改进的Bresenham算法画直线各点坐标及判别式的值\n");else if(num==0)return;//画线算法的实现GLsizei p=0;if(x0>x1){x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;}dx=x1-x0;dy=y1-y0;k=dy/dx;if(k>=0&&k<=1){e=-dx;x=x0;y=y0;while(x<=x1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;x++;e=e+2*dy;if(e>0){y++;e=e-2*dx;}}}if(k>1){e=-dy;x=x0;y=y0;while(y<=y1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;y++;e=e+2*dx;if(e>0){x++;e=e-2*dy;}}}if(k<0&&k>=-1){e=-dx;x=x0;y=y0;while(x<=x1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;x++;e=e+2*dy;if(e<0){y--;e=e+2*dx;}}}if(k<-1){e=-dy;x=x0;y=y0;while(y>=y1){putpixel(x,y);if (p>=num-1) {printf("x=%d,y=%d\n", x, y);break;}p++;y--;e=e-2*dx;if(e<0){x++;e=e-2*dy;}}}}///////////////////////////////////////////////////////////Bresenham算法画圆 //// //// //// ///////////////////////////////////////////////////////////void CirclePoint(GLsizei x,GLsizei y){ putpixel(x,y);putpixel(x,-y);putpixel(y,-x);putpixel(-y,-x);putpixel(-x,-y);putpixel(-x,y);putpixel(-y,x);putpixel(y,x);}void BresenhamCircle(GLsizei x, GLsizei y, GLsizei R, GLsizei num) {glColor3f(1.0f,0.0f,0.0f);GLsizei d;x=0;y=R;d=1-R;if(num == 1)printf("Bresenham算法画圆：各点坐标及判别式的值\n");else if(num==0)return;while(x<=y){CirclePoint(x,y);if (x>=num-1) {printf("x=%d,y=%d,d=%d\n", x, y,d);break;}if(d<0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;}}void Bresenham2Circle(GLsizei a,GLsizei b,GLsizei num){glColor3f(1.0f,0.0f,0.0f);if(num==1)printf("Bresenham算法画椭圆：各点坐标及判别式的值\n");else if(num==0)return;GLsizei x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.5);putpixel(x,y); putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);while(b*b*(x+1)<a*a*(y-0.5)){if (x>=num-1) {printf("x=%d,y=%d,d1=%d\n", x, y,d1);break;}if(d1<=0){d1+=b*b*(2*x+3);x++;}else{d1+=b*b*(2*x+3)+a*a*(-2*y+2);x++;y--;}putpixel(x,y); putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);}//while上半部分d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y>0){if (x>=num-1) {printf("x=%d,y=%d,d2=%d\n", x, y,d2);break;}if(d2<=0){d2+=b*b*(2*x+2)+a*a*(-2*y+3);x++;y--;}else{d2+=a*a*(-2*y+3);y--;}putpixel(x,y); putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);}}//初始化窗口void Initial(void){// 设置窗口颜色为蓝色glClearColor(0.0f, 0.0f, 1.0f, 1.0f);}// 窗口大小改变时调用的登记函数void ChangeSize(GLsizei w, GLsizei h){if(h == 0) h = 1;// 设置视区尺寸glViewport(0,0, w, h);// 重置坐标系统glMatrixMode(GL_PROJECTION);glLoadIdentity();// 建立修剪空间的范围if (w <= h)glOrtho (-250.0f, 250.0f, -250.0f, 250.0f*h/w, 1.0, -1.0);elseglOrtho (-250.0f, 250.0f*w/h, -250.0f, 250.0f, 1.0, -1.0);}// 在窗口中绘制图形void ReDraw(void){//用当前背景色填充窗口glClear(GL_COLOR_BUFFER_BIT);//画出坐标线DrawCordinateLine();switch(m_DrawMode){case 1:DDACreateLine(0,0,20,15,m_PointNumber);break;case 2:BresenhamLine(0,0,-20,15,m_PointNumber);break;case 3:Bresenham2Line(1,1,8,6,m_PointNumber);break;case 4:BresenhamCircle(0,0,20,m_PointNumber);break;case 5:Bresenham2Circle(10,8,m_PointNumber);default:break;}glFlush();}//设置时间回调函数void TimerFunc(int value){if(m_PointNumber == 0)value = 1;m_PointNumber = value;glutPostRedisplay();glutTimerFunc(500, TimerFunc, value+1);}//设置键盘回调函数void Keyboard(unsigned char key, int x, int y) {if (key == '1') m_DrawMode = 1;if (key == '2') m_DrawMode = 2;if (key == '3') m_DrawMode = 3;if (key == '4') m_DrawMode = 4;if (key == '5') m_DrawMode = 5;m_PointNumber = 0;glutPostRedisplay();}//void main(void)int main(int argc, char* argv[]){glutInit(&argc, argv);//初始化GLUT库OpenGL窗口的显示模式glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);glutInitWindowSize(600,600);glutInitWindowPosition(100,100);glutCreateWindow("基本图元绘制程序);glutDisplayFunc(ReDraw);glutReshapeFunc(ChangeSize);glutKeyboardFunc(Keyboard);//键盘响应回调函数glutTimerFunc(500, TimerFunc, 1);// 窗口初始化Initial();glutMainLoop(); //启动事件处理循环return 0;}。

Bresenham画线算法

以前看到Bresenham画线算法，直接拿来用，没有去推导它,近日,参考一些资料,特整理其算法推导过程如下。

各位大虾如果知道其细节，赶紧闪过，不用浪费时间了。

基本上Bresenham画线算法的思路如下:// 假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2).// 根据对称性,可推导至全象限内的线段.1.画起点(x1,y1).2.准备画下个点。

x坐标增1，判断如果达到终点，则完成。

否则，由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点.2.1.如果线段ax+by+c=0与x=x1+1的交点的y坐标大于M点(即中点)的y坐标的话,下个点为U(x1+1,y1+1)2.2.否则,下个点为B(x1+1,y1)3.画点(U或者B).4.跳回第2步.5.结束.这里需要细化的是怎么判断下个要画的点为当前点的右邻接点还是当前点的右上邻接点.设线段方程：ax+by+c=0(x1<x<x2,y1<y<y2)令dx=x2-x1,dy=y2-y1则：斜率-a/b = dy/dx.从第一个点开始，我们有F(x,1,y1) = a*x1+b*y1+c=0下面求线段ax+by+c=0与x=x1+1的交点:由a*(x1+1)+b*y+c = 0, 求出交点坐标y=(-c-a(x1+1))/b所以交点与M的y坐标差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) = -a/b-0.5，即Sub1的初始值为-a/b-0.5。

则可得条件当Sub1 = -a/b-0.5>0时候,即下个点为U.反之,下个点为B.代入a/b,则Sub1 = dy/dx-0.5.因为是个循环中都要判断Sub,所以得求出循环下的Sub表达式,我们可以求出Sub的差值的表达式.下面求x=x1+2时的Sub，即Sub2 1.如果下下个点是下个点的右上邻接点，则Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;2.如果下下个点是下个点的右邻接点，Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;于是，我们有了Sub的初始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表达式Dsub = dy/dx -1 （当Sub1 > 0）或dy/dx（当Sub1 < 0）.细化工作完成。

DDA算法、Bresenham算法和画家算法

Bresenham算法
记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)–yi，且 0≤d≤1 当d<0.5：下一个象素应取右光栅点(xi+1,yi) 当d≥0.5：下一个象素应取右上光栅点(xi+1,yi+1)
Bresenham算法
如果直线的（起）端点在整数点上，误差项d的初值：d0＝0， x坐标每增加1，d的值相应递增直线的斜率值k，即：d＝d + k。一旦d≥1，就把它减去1，保证d的相对性，且在0-1之间。
Bresenham算法
基本原理
假定直线斜率k在0~1之间。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。设直线当前点为(xi,y) 直线当前光栅点为(xi,yi) 则下一个直线的点应为(xi+1,y+k) 下一个直线的光栅点为右光栅点(xi+1,yi)（y方向递增量0）或为右上光栅点(xi+1,yi+1)（y方向递增量1）
Bresenham算法
1)Bresenham算法的实施——Rogers 版
通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；如果斜率小于0.5，则反之；当斜率等于0.5，没有确定的选择标准，本算法选择(1,1)
Bresenham算法
x=x1 y=y1 dx = x2 –x1 dy = y2 –y1 //initialize e to compensate for a nonzero intercept NError =2*dy-dx //Error =dy/dx-0.5; NError = 2*Error*dx //begin the main loop for i=1 to dx WritePixel (x, y) if (NError >=0) then y=y+1 NError = NError –2*dx //Error = Error -1 end if x=x+1 NError = NError +2*dy //Error = Error +dy/dx next i finish

bresenham算法画直线例题

bresenham算法画直线例题摘要：1.介绍Bresenham算法2.Bresenham算法的原理3.使用Bresenham算法画直线的步骤4.Bresenham算法的应用示例5.总结Bresenham算法在计算机图形学中的重要性正文：Bresenham算法是一种计算几何中用于画直线的算法，由英国计算机科学家Jack Bresenham于1965年提出。

该算法广泛应用于计算机图形学、视频游戏和各种嵌入式系统。

Bresenham算法的核心思想是使用简单的加法和减法运算，以及位运算来计算直线上的每个点的坐标，从而实现画直线的目标。

Bresenham算法的原理基于对直线方程y = mx + b的观察。

当m为正数时，直线是从左下到右上的；当m为负数时，直线是从左上到右下的。

根据这个特点，Bresenham算法将画直线的过程分为两个阶段：第一阶段是向上扫描，第二阶段是向下扫描。

在每一阶段，算法仅使用简单的加法和减法运算来更新当前点的坐标。

使用Bresenham算法画直线的步骤如下：1.初始化x和y坐标，以及直线的斜率m和截距b。

2.判断m的正负性。

如果m为正，进入第一阶段；如果m为负，进入第二阶段。

3.在第一阶段，每次将y坐标加b，然后将x坐标加m，直到x坐标达到最大值或y坐标达到最小值。

4.在第二阶段，每次将y坐标加b，然后将x坐标减m，直到x坐标达到最小值或y坐标达到最大值。

5.如果需要，可以将画直线的过程进行迭代，以获得更高的精度。

Bresenham算法在计算机图形学中具有重要应用价值。

它不仅计算简单、速度快，而且可以在各种不同的硬件平台上实现。

下面给出一个使用Bresenham算法画直线的示例：```pythondef bresenham_line(x0, y0, x1, y1):m = (y1 - y0) / (x1 - x0)b = y0 - m * x0x = x0y = y0e = 0if m < 0:y = y0while x < x1:put_pixel(x, y)e = e + abs(m)if e > abs(b):x = x + 1e = e - abs(m)y = y + 1else:x = x0while y < y1:put_pixel(x, y)e = e + abs(m)if e > abs(b):y = y + 1e = e - abs(m)x = x + 1bresenham_line(0, 0, 10, 5)```总之，Bresenham算法是一种简单而有效的计算几何画直线方法。

【OpenGL学习】四种绘制直线的算法

【OpenGL学习】四种绘制直线的算法我是⽤MFC框架进⾏测试的，由于本⼈也没有专门系统学习MFC框架，代码若有不⾜之处，请指出。

⼀，先来⼀个最简单的DDA算法DDA算法全称为数值微分法，基于微分⽅程来绘制直线。

①推导微分⽅程如下：②，dM时间步长的倒数的详解：可以看到当|k|<=1时dx=1或者-1，此时的x为计长⽅向当|k|>1时dy=1或者-1，此时的y为计长⽅向绘制时需要⽤dM来控制绘制的点数③绘制像素的问题：为了“⽅便”管理算法，我为不同的绘制函数新建了⼀个类了。

（其实可以写到⼀个类⾥⾯。

）④代码实现：MyDDA.cpp1 #include "stdafx.h"2 #include "MyDDA.h"345MyDDA::MyDDA()6{7}8910 MyDDA::~MyDDA()11{12}1314void MyDDA::SetDc(CDC * dc)15{16this->pdc = dc;17}1819void MyDDA::Moveline(CPoint start, CPoint end)20{21int x1, x2;22int y1, y2;23 x1 = start.x;24 x2 = end.x;25 y1 = start.y;26 y2 = end.y;27float dm = 0;28if (abs(x2 - x1) >= abs(y2 - y1))29 dm = abs(x2 - x1);30else31 dm = abs(y2 - y1);32float dx = (float)(x2 - x1) / dm;33float dy = (float)(y2 - y1) / dm;34float x = x1 + 0.5;35float y = y1 + 0.5;36int i = 0;37while (i<dm) {38this->pdc->SetPixel((int)x, (int)y, RGB(0, 0, 0));39 x += dx;40 y += dy;41 i += 1;42 }43总结：其实这个算法还算是挺简单的，就是要确定是X还算Y为计长⽅向，需要注意的是循环过程中计长⽅向⾃增1，另⼀个⽅向按照当直线在计长⽅向⾃增1时，直线在轴上的投影的⼤⼩⾃增就可以了。