完整Bresenham算法画直线

#include

#include

#include

void lineBre(int x0,int y0,int xEnd,int yEnd) {

int dx=fabs(xEnd-x0),dy=fabs(yEnd-y0);

int p=2*dy-dx;

int twoDy=2*dy,twoDyMinusDx=2*(dy-dx);

int x,y;

if(x0 > xEnd)

{

x=xEnd;

y=yEnd;

xEnd=x0;

}

else

{

x=x0;

y=y0;

}

//setPixel(x,y);

glBegin(GL_POINTS);

glVertex2i(x,y);

glEnd();

while (x

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyMinusDx;

}

//setPixel(x,y);

glBegin(GL_POINTS);

glVertex2i(x,y);

glEnd();

glFlush();

}

}

void init(void)

{

glClearColor(1.0,1.0,1.0,0.0);

glMatrixMode(GL_PROJECTION);

gluOrtho2D(0.0,200.0,0.0,150.0);

}

void lineSegment(void)

{

glClear(GL_COLOR_BUFFER_BIT);

glColor3f(1.0,0.0,0.0);

lineBre(20,10,150,90);

glFlush();

}

void main(int argc,char** argv)

{

glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); glutInitWindowPosition(50,100); glutInitWindowSize(400,300); glutCreateWindow("Xjiao");

init();

glutDisplayFunc(lineSegment); glutMainLoop();

}

案例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;

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

实验1 中点画线和Bresenham画线算法的实现

计算机图形学实验报告 实验1 使用画线算法，绘制直线段 一．实验目的及要求 （1）掌握图形学中常用的三种画线算法：数值微分法、中点画线法和Bresenham画线算法。 （2）掌握绘制直线的程序设计方法。 （3）掌握使用文件来保存直线段的方法。 （4）掌握从文本文件中恢复出直线的方法。 二．实验内容 使用VC++ 6.0开发环境，分别实现中点画线算法和Bresenham画线算法，绘制直线（注意，不能使用VC中已有的绘制直线的函数），并以文本文件的形式保存绘制的结果，可以从文本文件中恢复出以前绘制过的直线。 三．算法设计与分析 Bresenham算法绘制直线的程序（仅包含整数运算）。 void MidBresenhamLine(int x0,int y0,int x1,int y1,int color) { int dx,dy,d,UpIncre,DownIncre,x,y; 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; d=dx-2*dy; UpIncre=2*dx-2*dy;DownIncre=-2*dy; while(x<=x1){ putpixel(x,y,color); X++; if(d<0){ y++; d+=UpIncre; } else d+=DownIncre; } } 四．程序调试及运行结果的自我分析与自我评价 // testView.cpp : implementation of the CTestView class #include "stdafx.h" #include "test.h" #include "testDoc.h" #include "testView.h" #include // ifstream、ofstream等位于其中 #include #include // string类型需要 #include "DlgInput.h" //CDlgInput类的头文件 using namespace std; #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif // CTestView IMPLEMENT_DYNCREATE(CTestView, CView) BEGIN_MESSAGE_MAP(CTestView, CView) //{{AFX_MSG_MAP(CTestView) ON_COMMAND(ID_MENUITEM32771, OnMenuitem32771) ON_COMMAND(ID_MENUBRESENHAMLINE, OnMenubresenhamline) ON_COMMAND(ID_MENUCLEARVIEW, OnMenuclearview) ON_COMMAND(ID_FILE_OPEN, OnFileOpen) ON_COMMAND(ID_FILE_SA VE, OnFileSave) //}}AFX_MSG_MAP // Standard printing commands ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint) ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)

直线中点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;

DDA算法 中点画线算法 Bresenham算法

实验1直接绘制实验 (提示：#表示Project的编号，##表示Project题目) 学号姓名上交时间 1.问题描述 如何利用OpenGL实现直线光栅化的DDA算法、中点画线算法和Bresenham算法2.算法描述 DDA算法：据直线公式y = kx + b来推导出来的，其关键之处在于如何设定单位步进，即一个方向的步进为单位步进，另一个方向的步进必然是小于1。 中点划线法：在画直线段的过程中，当前像素点为（xp ,yp )，下一个像素点有两种可选择点P1(xp +1,yp )或P2(xp +1,yp +1)。若M=(xp +1,yp +0.5)为P1与P2之中点，Q 为P理想直线与x=xp +1垂线的交点。当M在Q的下方，则P2应为下一个像素点； M在Q的上方，应取P1为下一个像素点。 Bresenham算法：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近 的像素。 实验结果 成功运行三个算法，并且能转换出通用Bresenham算法。 3.分析与评论 (分析每个算法的运行时间，对你的本实验的工作进行评论，同时也可以对老师提出建议。) 附录: Source Code(in C)

#include //需要正确安装GLUT，安装方法如预备知识中所述void myDisplay(void) { glClearColor(0.0, 0.0, 0.0, 0.0); glClear(GL_COLOR_BUFFER_BIT); glColor3f (1.0f, 1.0f, 1.0f); glRectf(-0.5f, -0.5f, 0.5f, 0.5f); glBegin (GL_TRIANGLES); glColor3f (1.0f, 0.0f, 0.0f); glVertex2f (0.0f, 1.0f); glColor3f (0.0f, 1.0f, 0.0f); glVertex2f (0.8f, -0.5f); glColor3f (0.0f, 0.0f, 1.0f); glVertex2f (-0.8f, -0.5f); glEnd (); glColor3f(1,0,0); glBegin(GL_LINE_LOOP); glVertex2f (0.0f, 0.5f); glVertex2f (0.4f, -0.25f); glVertex2f (-0.4f, -0.25f); glEnd (); glPointSize(3); glBegin (GL_POINTS); glColor3f (1.0f, 0.0f, 0.0f); glVertex2f (-0.4f, -0.4f); glColor3f (0.0f, 1.0f, 0.0f); glVertex2f (0.0f, 0.0f); glColor3f (0.0f, 0.0f, 1.0f); glVertex2f (0.4f, 0.4f); glEnd (); glFlush(); } int main(intargc, char *argv[]) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);

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; } } }

实验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++;

计算机图形学 实验 数值微分(DDA)法、中点画线法、Bresenham算法

XXXXXXXX 大学（计算机图形学）实验报告 实验名称 数值微分（DDA ）法、中点画线法、Bresenham 算法 实验时间 年 月 日 专 业 姓 名 学 号 预 习 操 作 座 位 号 教师签名 总 评 一、实验目的： 1.了解数值微分（DDA ）法、中点画线法、Bresenham 算法的基本思想； 2.掌握数值微分（DDA ）法、中点画线法、Bresenham 算法的基本步骤； 二、实验原理： 1.数值微分(DDA)法 已知过端点 的直线段L ：y=kx+b,直线斜率为 从x 的左端点 开始，向x 右端点步进。步长=1(个象素)，计算相应的y 坐标y=kx+b ；取象素点(x, round(y))作为当前点的坐标。 2.中点画线法 当前象素点为(x p , y p ) 。下一个象素点为P 1 或P 2 。 设M=(x p +1, y p +0.5)，为p 1与p 2之中点，Q 为理想直线与x=x p +1垂线的交点。将Q 与 M 的y 坐标进行比较。 当M 在Q 的下方，则P 2 应为下一个象素点； 当M 在Q 的上方，应取P 1为下一点。 构造判别式:d=F(M)=F(x p +1,y p +0.5)=a(x p +1)+b(y p +0.5)+c ，其中a=y 0-y 1, b=x 1-x 0, c=x 0y 1-x 1y 0。 当d<0，M 在L(Q 点)下方，取右上方P 2为下一个象素； 当d>0，M 在L(Q 点)上方，取右方P 1为下一个象素； 当d=0，选P 1或P 2均可，约定取P 1为下一个象素； 但这样做，每一个象素的计算量是4个加法，两个乘法。 d 是x p , y p 的线性函数，因此可采用增量计算，提高运算效率。 若当前象素处于d ≥0情况，则取正右方象素P 1 (x p +1, y p), 要判下一个象素位置，应计算 d 1=F(x p +2, y p +0.5)=a(x p +2)+b(y p +0.5)=d+a ； 增量为a 。 若d<0时，则取右上方象素P 2 (x p +1, y p +1)。要判断再下一象素，则要计算 d 2= F(x p +2, y p +1.5)=a(x p +2)+b(y p +1.5)+c=d+a+b ；增量为a ＋b 。 3.Bresenham 算法 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂 ),(),,(111000y x P y x P 0101x x y y k --=0x

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);

计算机图形学实验报告-直线中点bresenham算法的实现资料

计算机图形学实验报告 实验内容直线中点Bresenham算法的实现专业计算机科学与技术 班级 学号 姓名 指导教师刘长松 年月日

一、实验题目 直线中点Bresenham算法的实现 二、实验要求 学习Visual C++ 6.0集成编程环境的使用、图形设备接口和常用图形程序设计、鼠标编程以及菜单设计等基础知识，从而掌握利用Visual C++进行图形程序设计的方法以及简单的图形画法，并编程实现Bresenham直线扫描转换程序，得出相应的输出图形。 三、实验内容 1．学习Visual C++ 6.0集成编成环境的使用； 2．掌握Visual C++ 6.0图形设备接口和常用图形程序设计、菜单设计等方法； 3．编程实现Bresenham直线扫描转换程序，得出相应的输出图形；

四、实验过程 1、实验原理 Bresenham 算法思想： 0≤d≤1 当d<0.5：下一个象素应取右光栅点(xi+1，yi) 当d≥0.5：下一个象素应取右上光栅点(xi+1，yi+1) e=d-0.5 假定直线斜率|k|≤1。e0= -0.5，x每次加1，e = e + k；e<0时，下一像素取(xi+1，yi)，e = e + k ；e>0时，下一像素取(xi+1，yi+1)； e = e + k -1 ；e=0时，可任取上、下光栅点显示。 当斜率|k|>1时，同理，只是y每次加1，x是否变化取决于增量e。 中点算法 d =2F(M)=2F(Xp+1,Yp+0.5)=2(a(Xp+1)+b(Yp+0.5)+c) 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 当d<0，M在L(Q点)下方，取右上方T为下一个象素； 此时再下一个象素的判别式为： d’= 2F(Xp+2,Yp+0.5)=2(a(Xp+2)+b(Yp+0.5)+c) = 2(a(Xp+1)+b(Yp+0.5)+c) +2a = d + 2a; 当d>0，M在L(Q点)上方，取右方B为下一个象素； 此时下一个象素的判别式为： d’= 2F(Xp+2,Yp+1.5)=2(a(Xp+2)+b(Yp+1.5)+c) = 2(a(Xp+1)+b(Yp+0.5)+c) +2(a +b) = d + 2(a + b); 当d=0，选T或B均可，约定取B为下一个象素；d0 = 2F(X0+1,Y0+0.5) = 2(a(X0+1)+b(Y0+0.5)+c) = 2(F(X0,Y0)+a+0.5b) 2、案例分析 MFC提供的CDC类的成员函数MoveTo()和LineTo()函数用于绘制傻

DDA算法 中点画线算法 Bresenham算法

实验1 直接绘制实验 (提示：#表示Project的编号，##表示Project题目) 学号姓名上交时间 1.问题描述 如何利用OpenGL实现直线光栅化的DDA算法、中点画线算法和Bresenham算法2.算法描述 DDA算法：据直线公式y = kx + b来推导出来的，其关键之处在于如何设定单位步进，即一个方向的步进为单位步进，另一个方向的步进必然是小于1。 中点划线法：在画直线段的过程中，当前像素点为（xp ,yp )，下一个像素点有两种可选择点P1(xp +1,yp )或P2(xp +1,yp +1)。若M=(xp +1,yp +为P1与P2之中点，Q为P理想直线与x=xp +1垂线的交点。当M在Q的下方，则P2应为下一个像素点；M在Q 的上方，应取P1为下一个像素点。 Bresenham算法：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近 的像素。 实验结果 成功运行三个算法，并且能转换出通用Bresenham算法。 3.分析与评论 (分析每个算法的运行时间，对你的本实验的工作进行评论，同时也可以对老师提出建议。) 附录: Source Code(in C)

#include //需要正确安装GLUT，安装方法如预备知识中所述void myDisplay(void) { glClearColor, , , ; glClear(GL_COLOR_BUFFER_BIT); glColor3f , , ; glRectf, , , ; glBegin (GL_TRIANGLES); glColor3f , , ; glVertex2f , ; glColor3f , , ; glVertex2f , ; glColor3f , , ; glVertex2f , ; glEnd (); glColor3f(1,0,0); glBegin(GL_LINE_LOOP); glVertex2f , ; glVertex2f , ; glVertex2f , ; glEnd (); glPointSize(3); glBegin (GL_POINTS); glColor3f , , ; glVertex2f , ; glColor3f , , ; glVertex2f , ; glColor3f , , ; glVertex2f , ; glEnd (); glFlush(); } int main(int argc, char *argv[]) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);

计算机图形学常用算法及代码大全

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(fNum+0.5):static_cast(fNum-0.5)) /*! * @brief DDA画线函数 * * @param pDC [in]窗口DC * @param BeginPt [in]直线起点 * @param EndPt [in]直线终点 * @param LineCor [in]直线颜色 * @return 无 */ void CDrawMsg::DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor) { l ong YDis = (EndPt.y - BeginPt.y); l ong XDis = (EndPt.x-BeginPt.x); l ong MaxStep = max(abs(XDis),abs(YDis)); // 步进的步数 f loat fXUnitLen = 1.0f; // X方向的单位步进 f loat fYUnitLen = 1.0f; // Y方向的单位步进

直线的Bresenham算法

生成直线的B resenham算法 从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。 在生成直线的算法中，B resenham算法是最有效的算法之一。B resenham算法是一种基于误差判别式来生成直线的方法。 一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。 我们首先讨论m=△y/△x，当0≤m≤1且x1

这两个距离差是 我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(x i+1，y i+1)象素较近，下一个象素点应取(x i+1，y i+1)。 (2)当此值为负时，d10，因此p i与(d1-d2)有相同的符号； 这里△y=y2-y1，m=△y/△x；c=2△y+△x(2b-1)。 下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。 将式(2-11)中的下标i改写成i+1，得到： 将式(2-12)减去(2-11)，并利用x i+1=x i+1，可得： 再假设直线的初始端点恰好是其象素点的坐标，即满足： 由式(2-11)和式(2-14)得到p1的初始值： 这样，我们可利用误差判别变量，得到如下算法表示：

直线Bresenham算法原理及其实现

实现绘制各种情况直线的Bresenham算法，并将实现的算法应用于任意多边形的绘制，要求多边形的顶点由键盘输入或鼠标拾取，绘制的多边形顶点要准确，图形应该封闭。要求掌握Bresenham算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者VC++实现算法，并演示。-Implementation of the Bresenham line drawing algorithm for various situations, and to achieve an arbitrary polygon rendering algorithm is applied to require the polygon vertices from the keyboard input or mouse pick up and draw the polygon vertices to accurately, graphics should be closed. Bresenham algorithm required to master the basic theory and algorithm design, draw algorithm flow chart of procedures for the use of C or VC++ algorithm, and demonstrate. 文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉): ii\Debug\ii.exe ..\.....\ii.ilk ..\.....\ii.obj ..\.....\ii.pch ..\.....\ii.pdb ..\.....\ii.res ..\.....\iiDoc.obj ..\.....\iiView.obj ..\.....\MainFrm.obj ..\.....\StdAfx.obj ..\.....\vc60.idb ..\.....\vc60.pdb

实验报告(Bresenham画线算法)

实验报告（Bresenham 画线算法） 一、实验目的 根据Bresenham 画线算法，掌握绘制直线的程序设计方法。 二、实验原理 为了说明算法原理，我们首先考虑斜率非负且不超过 1 的直线的光栅化过程。设直线的起点坐标为 (x s , y s )，终点坐标为(x e , y e )，则直线的方程为： dy y x B dx =+ 因此，其隐函数表示为：(,)0F x y dy x dx y B dx ax by c =?-?+?=++= 其中：,,a dy b dx c B dx ==-=? 显然，对于直线上的点，F(x , y) 等于零；对于直线下方的点，F(x , y) 大于零；而对直线上方的点，F(x,y) 小于零。 假设当前选择的像素点是 (xi , yi)，那么下一步要选择的像素点可能是 NE (xi+1 , yi+1)，也可能是 E (xi+1 , yi)。选择的原则是看哪一个离直线与 x = xi+1 的交点最近。 运用中点法则，我们只需考察中点 M 在直线的哪一侧，即计算： F(M) = F(xi + 1, yi + 1/2) = a(xi + 1) + b( yi + 0.5) + c 并确定其正负号。由于根据函数值 F(xi+1, yi + 1/2) 进行判定，所以我们定义一个判定函数如下： di = 2F(xi + 1, yi + 1/2) 根据定义：di = 2a(xi + 1) + 2byi + b + 2c 当 d i < 0 时，M 在直线的上方，取 E 为下一个像素点；当 d > 0时， M 在直线的下方，取 NE 为下一个像素点；当 d = 0时，两者都可以选，我们约定选 E 。 di 的计算需要做 4 次加法和两次乘法。因此，为了有效地计算判定函数，我们需要建立关于 di 的递推公式。显然，di 的变化依赖于下一个像素点选的是 NE 还是 E 。

Bresenham算法画直线

Bresenham算法画直线： Matlab函数代码： function drawline(startX,startY,endX,endY) deltaX=endX-startX; deltaY=endY-startY; k=deltaY/deltaX; X=startX:endX;Y=k.*(X-startX)+startY;plot(X,Y,'-');hold on; if k>=0 x=startX; y=startY; if k<=1 for x1=startX:endX y1=(deltaY/deltaX*(x1-startX)+startY)*deltaX; dist=y1-y*deltaX; dist=dist*2; if dist>deltaX || dist<-deltaX y=y+1; end plot(x1,y,'r*'); hold on; end else for y1=startY:endY x1=((deltaX/deltaY*(y1-startY))+startX)*deltaY; dist=x1-x*deltaY; dist=dist*2; if dist>deltaY || dist<-deltaY x=x+1; end plot(x,y1,'r*'); hold on; end end end if k<0 x=endX;

y=startY; if k>=-1 for x1=startX:endX y1=(deltaY/deltaX*(x1-startX)+startY)*deltaX; dist=y1-y*deltaX; dist=dist*2; if dist>deltaX || dist<-deltaX y=y-1; end plot(x1,y,'r*'); hold on; end else for y1=endY:startY x1=((deltaX/deltaY*(y1-startY))+startX)*deltaY; dist=x1-x*deltaY; dist=dist*2; if dist-deltaY x=x-1; end plot(x,y1,'r*'); hold on; end end end Matlab测试代码： drawline(0,0,50,0); drawline(0,0,50,25); drawline(0,0,25,50); drawline(0,0,50,50); drawline(0,0,0,50); drawline(0,0,50,-25); drawline(0,0,25,-50); drawline(0,0,50,-50); drawline(0,0,0,-50) Matlab输出图像：