下载文档原格式
dda算法画直线例题dda算法是一种常用于计算机图形学中的算法，用于在计算机中绘制直线或其他几何形状。
本例题将通过dda算法绘制一条直线，帮助读者了解该算法的基本原理和应用。
一、算法概述dda算法是一种分治算法，它将原始的直线绘制问题分解为更小的子问题，逐个解决这些子问题，最终得到完整的绘制结果。
该算法的核心思想是通过逐点地更新像素位置，逐步逼近目标位置，从而实现直线的绘制。
二、实现步骤1.初始化：设置绘图窗口大小，确定要绘制的直线起点和终点。
2.循环迭代：对于每个像素点，按照dda算法的步骤进行更新。
具体步骤如下：a.计算当前像素点到直线起点的距离（dx），并将其与偏移量（delta）比较。
b.如果dx小于或等于delta，则当前像素点已经在直线上，无需进一步更新。
c.否则，根据dda算法的公式计算新的像素位置（new_x），并将其与当前像素位置进行比较。
d.如果new_x小于或等于当前像素位置，则将当前像素位置更新为new_x；否则，继续迭代下一个像素点。
3.重复步骤2直到绘制完整个窗口。
三、代码实现以下是一个简单的代码实现，使用c语言描述dda算法绘制直线的过程：```c#include<stdio.h>#include<stdlib.h>#include<math.h>#defineWIDTH800//绘图窗口宽度#defineHEIGHT600//绘图窗口高度voiddraw_line(intstart_x,intstart_y,intend_x,intend_y){inti,j,dx,dy,delta,new_x,new_y;for(i=0;i<HEIGHT;i++){for(j=0;j<WIDTH;j++){dx=end_x-start_x;dy=end_y-start_y;delta=sqrt(dx*dx+dy*dy);//计算偏移量if(dx<=delta||j==0){//如果当前像素点到直线起点的距离小于或等于偏移量，或者当前像素位置是第一帧，直接输出当前像素位置printf("%d,%d",j,i);}else{//否则，根据dda算法的公式计算新的像素位置并输出new_x=start_x+(j-WIDTH/2)*dx/delta;new_y=start_y+(i-HEIGHT/2)*dy/delta;printf("%d,%d",new_x,new_y);}}printf("\n");//换行}}intmain(){intstart_x=50,start_y=50;//直线起点坐标intend_x=200,end_y=150;//直线终点坐标draw_line(start_x,start_y,end_x,end_y);//绘制直线并输出结果return0;}```这段代码通过循环迭代的方式，逐点更新像素位置，从而实现直线的绘制。
计算机图形学实验指导书袁科计算机技术实验中心目录实验一实现DDA、中点画线算法和Bresenham画线算法 (24)实验二实现Bezier曲线 (25)实验三实现B样条曲线 (26)实验四实现多边形填充的边界标志算法 (27)实验五实现裁剪多边形的Cohen-Sutherland算法 (28)实验六二维图形的基本几何变换 (30)实验七画图软件的编制 (31)实验一实现DDA、中点画线算法和Bresenham画线算法【实验目的】1、掌握直线的多种生成算法；2、掌握二维图形显示原理。
【实验环境】VC++6.0/ BC【实验性质及学时】验证性实验，2学时，必做实验【实验内容】利用任意的一个实验环境，编制源程序，分别实现直线的三种生成算法，即数字微分法(DDA)、中点画线法以及Bresenham画线算法。
【实验原理】1、数字微分法(Digital Differential Analyzer，DDA)算法思想：基于直线的微分方程来生成直线。
ε=1/max(|△x|,|△y|)max(|△x|,|△y|)=|△x|，即|k|≤1 的情况：max(|△x|,|△y|)=|△y|，此时|k|≥1：2、中点画线法算法思想：每次在最大位移方向上走一步，另一方向是否走步取决于误差项的判断。
3、Bresenham画线算法算法思想：其基本思想同中点算法一样，即每次在最大位移方向上走一步，而另一个方向是否走步取决于误差项的判断。
【实验要求】1．上交源程序；2．上交实验报告，实验报告内容如下：(1) 实验名称(2) 实验目的(3) 算法实现的设计方法及程序流程图(4) 程序结果分析【分析与思考】(1) 上述所阐述的三个算法，其基本算法只能适用于直线的斜率(|K|<=1) 的情形，如何将上述算法进行推广，使其能够处理任意斜率的直线？(2) 计算机显示屏幕的坐标圆心在哪里，与我们平时的习惯有什么差异，如何协调二者？实验二 实现Bezier 曲线【实验目的】1、掌握Bezier 曲线的定义；2、能编程实现N 次Bezier 曲线的绘制与显示。
实验一 DDA 画线算法一、实验学时：2 二、实验类型：验证性实验 三、实验要求和目的初步了解Tc 下画图基本程序结构。
初步了解DDA 画线算法的思想和基本方法。
四、实验内容DDA 画线算法画一段直线 1．算法思路1．算法描述：设直线方程为：b mxy +=，对于直线，其数值微分是 )()1()()1(i x i x i y i y x y m -+-+=∆∆=,由上式得，y(i+1)=y(i)+m(x(i+1)-x(i))，于是知，使x(i)增1，即x(i+1)=x(i)+1时，y(i+1)=y(i)+m,为画线精确，应使相邻的画出点的坐标值相差最大值为1，这样可以得到画线段的数值微分分析器（Digital Differential Analyzer,简称DDA ），算法如下：2．C 程序代码#include<graphics.h> #include<math.h> #include<stdio.h>void DDALine(int x1,int y1,int x2,int y2,int color) { double dx,dy,e,x,y,i; dx=x2-x1; dy=y2-y1; e=(fabs(dx)>fabs(dy))?fabs(dx):fabs(dy); dx/=e; dy/=e; x=x1; y=y1; for(i=1;i<=e;i++) {putpixel((int)(x+0.5),(int)(y+0.5),color);x+=dx; y+=dy; } }void main(){ int driver=DETECT; int gmode; int x1,y1,x2,y2,color; printf("please input x1,y1,y1,y2,color\n"); scanf("%d,%d,%d,%d,%d",&x1,&y1,&x2,&y2,&color); initgraph(&driver,&gmode,""); DDALine(x1,y1,x2,y2,color); getch(); closegraph(); }实验二 Bresenham 画线算法一、实验学时：2 二、实验类型：验证性实验 三、实验要求和目的掌握中点画线算法的思想和基本方法四、实验内容用Bresenham 画线算法画直线,并完善算法功能,使之适应更广 1．算法思路假定直线段的斜率0≤m≤ 1，且x2>x1，122)1(2)1()1()1()1(2121-+-+=--+-+=-+=-++=-=b y x m d d b x m y y y d y b x m y y d i i i i i i i i 若差为正，即21d d ≥，下一个象素应取)1,1(＋＋i i y x ；若为负，即21d d <，下一个象素应取),1(i iy x ＋。
课程名称计算机图形学实验名称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）实验一算法//采用了DDA算法//画直线时通过鼠标点击两点确定起点和终点#include#include#include#include"windows.h"#include"gl/gl.h"#include"gl/glu.h"#include"gl/glaux.h"#include"stdlib.h"struct GLintPoint{GLint x;GLint y;};GLintPoint p[2];bool sig=false;int scrw=640,scrh=480;void drawline(){int dx=p[1].x-p[0].x,dy=p[1].y-p[0].y;int steps, k;float xIncrement, yIncrement, x = p[0].x, y = p[0].y; // 初始化if (fabs(dx) > fabs(dy)){steps = fabs(dx);} // 判断定长方向else{steps = fabs(dy);}xIncrement = float(dx) / float(steps); // 计算两个方向的增量yIncrement = float(dy) / float(steps);glClear(GL_COLOR_BUFFER_BIT);glColor3f(1.0f, 0.0f, 0.0f);glBegin(GL_LINES);glVertex2i(x,y);// 绘制起点for (k = 0; k < steps; k++){x += xIncrement;y += yIncrement;glVertex2i(x,y);}glEnd();glFlush();}void myDisplay(){glClear(GL_COLOR_BUFFER_BIT);glMatrixMode(GL_MODELVIEW);glLoadIdentity();glColor3f(0.0,0.0,1.0);if(sig)drawline();glutSwapBuffers();}void myMouse(int button,int state,int x,int y){if(button==GLUT_LEFT_BUTTON && state==GLUT_DOWN){ p[0].x=x;p[0].y=scrh-y;sig=true;}glutPostRedisplay();}//void myPassiveMotion(int x,int y)void myMotion(int x,int y){p[1].x=x;p[1].y=scrh-y;glutPostRedisplay();}int main(int argc,char **argv){glutInit(&argc,argv);glutInitWindowSize(scrw,scrh); glutInitWindowPosition(0,0);glutInitDisplayMode(GLUT_RGB|GLUT_DOUBLE); glutCreateWindow("Yangyu!");glMatrixMode(GL_PROJECTION);glLoadIdentity();gluOrtho2D(0,scrw,0,scrh);glMatrixMode(GL_MODELVIEW);glClearColor(0.0f,0.0f,0.0f,0.0f); glViewport(0,0,scrw,scrh); glutMouseFunc(myMouse); glutDisplayFunc(myDisplay); glutMotionFunc(myMotion); glutMainLoop();return 0;}。
实验一、直线的生成一、实验目的1、掌握DDA直线画法、中点画线法和Bresenham画线法2、掌握VC++简单程序设计方法二、实验内容根据提供的程序框架，修改部分代码，完成画一条直线的功能（中点画线法或者Bresenham画线法任选一），只要求实现在第一象限内的直线。
三、算法原理介绍双击直线生成.dsw打开给定的程序，或者先启动VC++，文件（file）→打开工作空间（open workspace）。
打开直线生成view.cpp，按注释改写下列函数：1.void CMyView::OnDdaline() （此为DDA生成直线）2.void CMyView::OnBresenhamline()（此为Bresenham画直线）3.void CMYView::OnMidPointLine()（此为中点画线法）四、程序文档说明与程序源代码1.DDA生成直线画法程序：float x,y,dx,dy,k;dx=(float)(xb-xa);dy=(float)(yb-ya);k=dy/dx;x=xa;y=ya;if(abs(k)<1){for (x=xa;x<=xb;x++){pdc->SetPixel(x, int(y+0.5),COLOR);y=y+k;}}if(abs(k)>=1){for(y=ya;y<=yb;y++){pdc->SetPixel(int(x+0.5),y,COLOR);x=x+1/k;}}//DDA画直线结束}2.Bresenham画直线源程序：float b,d,xi,yi;int i;float k;k=(yb-ya)/(xb-xa);b=(ya*xb-yb*xa)/(xb-xa);if(k>0&&k<=1)for(i=0;i<abs(xb-xa);i++){ d=ya+0.5-k*(xa+1)-b;if(d>=0){ xi=xa+1;yi=ya;xa++;ya=ya+0.5;}if(d<0){ xi=xa+1;yi=ya+1;xa++;ya=ya+1.5;}pdc->SetPixel(xi,yi,COLOR);}//BresenHam画直线结束}3.中点画线法源程序：float b,d,xi,yi;int i;float k;k=(yb-ya)/(xb-xa);b=(ya*xb-yb*xa)/(xb-xa);if(k>0&&k<=1)for(i=0;i<abs(xb-xa);i++){ d=ya+0.5-k*(xa+1)-b;if(d>=0){ xi=xa+1;yi=ya;xa++;ya=ya+0.5;}if(d<0){ xi=xa+1;yi=ya+1;xa++;ya=ya+1.5;}pdc->SetPixel(xi,yi,COLOR); }//BresenHam画直线结束}五、实验结果抓图与分析一、DDA生成直线二、Bresenham画直线三、中点画线法实验二、bresenham画圆一、实验目的1、掌握bresenham画圆的算法。
生成直线的dda算法
DDA算法是一种简单而有效的直线生成算法，可以使用数值计算来生成线段坐标。
本文将介绍DDA算法的实现原理、优缺点以及在实际应用中的使用情况。
一、DDA算法的实现原理：
DDA算法使用数值计算来计算每个像素的坐标，然后在屏幕上直接画出直线。
具体实现步骤如下：
1. 取两个端点（x1，y1）和（x2，y2）。
2. 计算dx，dy，m（斜率）和steps（使用的步骤）。
3. 计算xinc和yinc以确定绘制的方向。
4. 分配像素的坐标并在屏幕上绘制直线。
二、DDA算法的优缺点：
1. 优点：
（1）DDA算法能够生成直线。
（2）算法简单，易于实现。
（3）计算速度快，对硬件要求低。
2. 缺点：
（1）DDA算法产生的直线锯齿状。
（2）当线的斜率趋近于无穷大时，计算会出现分母无限大的错误，需要特殊处理。
（3）当线的斜率趋近于0时，计算会出现分母为0的错误，需要特殊处理。
三、DDA算法的应用：
DDA算法被广泛应用于计算机图形学中，常被用来生成直线和绘制几何图形。
例如，绘制线条、矩形、椭圆等形状，都会使用DDA算法。
此外，还有一些基于DDA算法的算法，如圆算法、填充算法等。
四、总结：
DDA算法是一种简单而有效的直线生成算法，具有计算速度快、对硬件要求低等优点。
然而，由于其产生的直线锯齿状，导致其在某些应用场景下难以满足要求。
在实际应用中，DDA算法被广泛应用于生成直线和绘制几何图形的场景中。
