计算机图形学课程设计报告--直线和圆中点Bresenham算法

1、一、设计任务及要求：设计任务：掌握中点Bresenham算法绘制直线的原理，设计中点 Bresenham算法, 编写Mbline()子函数，使用中点Bresenham算法绘制斜率为0三k三1的直线。掌握八分法中点Bresenham算法绘制圆的原理，设计八分法绘制圆的中 点Bresenham算法，编写八分法绘制圆的 CirclePoint(x,y)子函数，编写绘制 整圆的Mbcircle()子函数，使用中点Bresenham算法绘制圆心位于屏幕客户区 中心的圆。要 求：此次课程设计的课题为通过编程，实现圆和直线等基本图形的绘制。要求用 Bresenham算法实现圆和直线等基本图形的绘制，并给出代

2、码和结果截图。指导教师签名：年 月 日、指导教师评语:指导教师签名：年 月 日、成绩 TOC o 1-5 h z 1、课程设计目的 22、课程设计描述及要求 23、系统开发环境 24、直线的 Bresenham算法原理 2中点 Bresenham算法 2该进的Bresenham算法 55、圆的 Bresenham 算法原理 7 HYPERLINK l bookmark37 o Current Document 6、程序运行结果 9 HYPERLINK l bookmark39 o Current Document 7、总结 11 HYPERLINK l bookmark43 o Current

3、 Document 8、参考资料 119、附录 11计算机图形学课程设计报告.课程设计目的本学期系统学习了计算机图形学的概论原理，在学期期末按课程要求进行实验。通过实验，进一步理解和掌握中点算法、Bresenham算法和二阶差分算法，并掌握以上算法生成圆和直线等图形的基本过程，提高学生对计算机图形学的了解与运用技巧，同时通过此次课程设计提高动手实践能力与学习分析能力。 2.课程设计描述及要求直线中点Bresenham算法掌握中点Bresenham算法绘制直线的原理，设计中点 Bresenham算法，编写 Mbline()子函数，使用中点Bresenham算法绘制斜率为0三k三1的直线圆中点Br

4、esenham算法掌握八分法中点Bresenham算法绘制圆的原理，设计八分法绘制圆的中点 Bresenham算法，编写八分法绘制圆的 CirclePoint(x,y)子函数，编写绘制整圆的 Mbcircle()子函数，使用中点Bresenham算法绘制圆心位于屏幕客户区中心的圆。此次课程设计的课题为通过编程，实现圆和直线等基本图形的绘制。要求用 Bresenham算法实现圆和直线等基本图形的绘制，并给出代码和结果截图。 3.系统开发环境开发工具：VC 6.0操作系统：Microsoft Windows XP4.直线的Bresenham算法原理中点Bresenham算法给定直线的两个端点P(X

5、, Y0)和P(Xi, Yi),可得到直线方程 F(x,y)=y-kx-b=0 且kdUx X1X0这时直线将平面分为三个区域：对于直线上的点，F(x,y)=0 ;对于直线上方的点， F(x,y)0 ;对于直线下方的点，F(x,y) F (x 1,y0 .5 )y 0. 5 x ( - b当di0时，则应取正右方的 2。当di=0时，二者一样合适，可以随便取一个。我们约定取Pd,即:y 十19 0) y =y (di - 0)当di0时，取正右方像素Pd,要判断再下一个像素应取哪一个，应计算di 1 =F(x 2, Yi 0.5)=yi +0.5k x(十 2b=y +0.5k x( + 1b

6、-k=di -k此时，dj的增量为-k下面计算4的初值。显然，直线的第一个像素 B(x,yo)在直线上，因此相应 的4的初始值计算如下：do =F(% 1,yo 0.5) =y0 0.5 -k(x0 2) -b =y0 - kx0 - b - k 0.5 =0. 5 k由于我们使用的只是di的符号，因此可以用2d Ax代替di来摆脱小数。此时 算法只涉及整数运算。这样，0&k01时，Bresenham算法的绘图过程如下： 输入直线的两端点P0(X, YJ和PKX1, Y1);计算初始值 Ax, Ay, d =Ax 2Ay,x = X0,y =Y0 ;绘制点(x,y)。判断d的符号，若d0,则(

7、x,y)更新为(x+1 , y+1), d更 新为d+2 Ax-2凶;否贝U (x,y)更新为(x+1 , y), d更新为d-2Ay ;当直线没有画完时，重复步骤，否则结束。 kx1)(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(x0.5时, 直线更接近于像素点Pu(xj+1,另+1);当di 0.5)yi 十 一 II yi (di 0时，下一像素的y坐标 增加1；否则，下一像素的y坐标不增，即有x 1 =x

8、1yi i 二yi 1(e 0) .yi (0 M0)此时，e的初值为-0.5,每走一步有ei+=e+k。当e0时，将e减1.改进的Bresenham算法还有一个缺点：在计算直线斜率与误差时，要用到小数与除法，不利于硬件实现。因此改进如下：由于算法中只用到误差项的符号，于是可以用2eAx来替换e。这样就能获得整数 Bresenham算法且可避免除法。 其算法步骤如下： 输入直线的两端点P0(X, YJ和PKX1, Y1)；计算初始值 Ax, Ay , e = -Ax, x=X0,y=Y0绘制点(x,y) oe更新为e+2Ay。判断e的符号，若e0,则(x,y)更新为(x+1, y+1),同 时

9、将e更新为e-2ix ；否则(x,y)更新为(x+1, y)；当直线没有画完时，重复步骤，否则结束。0 k 1时改进的Bresenham算法绘制直线的程序如下：void BresenhamLine(int x0,int y0,int x1,int y1,int color)int x,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;while(x0)y+;e=e-2*dx;5、圆的Bresenham算法原理给定圆心在原点，半径为R的圆，其方程为 x2 + y2 = R2。构造函数F(x, y)=x + y - R20对于圆上的点，有 F(x,y)=0;对

10、于圆外的点，F(x,y)0;而2对于圆内的点，F(x,y)0.这里只考虑如下图所示的第一象限内x0，R2的八分八分之一圆弧。此时中点Bresenham画圆算法要从点顺时针地确定最佳逼近于该圆弧的像素序列对于该圆弧，由于最大位移方向为 x,因此其基本原理是：每次沿 x方向上走一步，而y方向上或减1,或减00如图所示，假定当前与圆弧最近的像素点已确定为P (xi,yi),那么，下一候选像素点只能是正右方的Pu(xi+1，yJ和右下方的Pd(x +1，y -1)。到底选取哪一个候选点依旧用中点进行判别x假设M是Pu和Pd的中点，即有M(x +1，y -0.5)。则当F(xM，yM)0, 说明Pd离圆

11、弧更近，应取Pd(x十l，yi -1)。当F(xM，yM)=0时，在R和Pd之中随 便选取一个即可，约定取Pd。构造判别式di =F (xm，yM )= F (x 1，y- 0.5)x(1) y -(2 度&)当dj0,下一点取B(为+1，y);当di0时，下一点取Fd (x+1，y 1)。现在进行误差项的递推。40,取正右方像素 巳(为+1,另)，欲判断再下一个像素应取哪一个，应计算dp =F(x 2,yi -0.5)三 (xi 2j乂 一 0 25R 2=供 12)yi - 0 25)R2x2 3=dj 2x 3所以，沿正右方向，dj的增量为2为+3。di0时，应取右下方像素RXi+l%

12、-1),要判断再下一个像素,则要计算d=F(Xi 2,yi -1.5)-(Xi 2+ - 1 25R 2= (Xi 12)y - 0 25 )R2x( 23 ) y( 22 )=di +2 (x -yi 巧所以，沿右下方向，判别式di的增量为2(x-y) +5。显然所绘制圆弧段的第一个像素点为 P(0,R),因此判别式di的初始值d0 -F(1,R -0.5)_2_2=1 (R -0.5) -R= 1.25-R由于使用的只是di的符号，因此可以用di-0.25代替di来摆脱小数。此时算法只涉及整数运算。这样初始化运算d0 =1.25-R对应于d0 =1-R。判别式dj0对应于 di-0.25。

13、di-0.25 等价于 di0。于是可写出中点Bresenham画圆算法的步骤如下：输入圆半径R;计算初始值d0=1R, x=0, y=R; 绘制点(x,y)及其在八分圆中的另外7个对称点；判断d的符号。若d0,则先将d更新为d+2x+3,再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5 ,再将(x,y)更新为(x+1,y-1); 当xy时，重复步骤和；否则结束程序。用中点Bresenham算法画圆的程序如下：void MidBresenhamCircle(int r,int color)int x,y,d;x=0;y=r;d=1-r;while (x=y)Circle

14、Point(x,y,color);if(d 1000#pragma once#endif / _MSC_VER 1000#include InputDlg.h/ 对话框头文件#include InputDlg2.hclass CTestView : public CViewprotected: / create from serialization onlyCTestView();DECLARE_DYNCREATE(CTestView)/ Attributespublic:CTestDoc* GetDocument();/ Operationspublic:void Mbline();Bres

15、enham 函数void GetMaxY();获得屏幕的最大x值函数void GetMaxX();获得屏幕的最大y值函数void CirclePoint(double x,double y);八分法画圆子函数void Mbcircle();/Bresenham 算法/ Overrides/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CTestView)-11 -public:virtual void OnDraw(CDC* pDC); / overridden to draw this viewvirtual BO

16、OL PreCreateWindow(CREATESTRUCT& cs);protected:virtual BOOL OnPreparePrinting(CPrintInfo* pInfo);virtual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo);virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo);/AFX_VIRTUAL/ Implementationpublic:virtual CTestView();#ifdef _DEBUGvirtual void AssertVa

17、lid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:double x0, y0, x1, y1;/直线的起点和终点坐标int MaxX,MaxY;/屏幕x和y的最大坐标double R;/圆的半径/ Generated message map functionsprotected:/AFX_MSG(CTestView)afx_msg void OnMENUMbline();afx_msg void OnMENUMbcircle();/AFX_MSGDECLARE_MESSAGE_MAP();#ifndef

18、_DEBUG / debug version in TestView.cppinline CTestDoc* CTestView:GetDocument() return (CTestDoc*)m_pDocument; #endif/AFX_INSERT_LOCATION/ Microsoft Visual C+ will insert additional declarations immediately before the previous line.#endif/ !defined(AFX_TESTVIEW_H_A75FDCFB_621C_4E38_A154_C344803E6372_

19、 _INCLUDED_)-12 - TestView.cpp/ TestView.cpp : implementation of the CTestView class /#include stdafx.h#include Test.h#include TestDoc.h#include TestView.h#define ROUND(a) int(a+0.5) 四舍五入#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE口 = _FILE_;#endif/ CTestViewIMPLEMENT_DYNC

20、REATE(CTestView, CView)BEGIN_MESSAGE_MAP(CTestView, CView)/AFX_MSG_MAP(CTestView)ON_COMMAND(ID_MENUMbline, OnMENUMbline) ON_COMMAND(ID_MENUMbcircle, OnMENUMbcircle) /AFX_MSG_MAP/ Standard printing commandsON_COMMAND(ID_FILE_PRINT, CView:OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CView:OnFilePrint)

21、ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView二OnFilePrintPreview) END_MESSAGE_MAP()/ CTestView construction/destructionCTestView:CTestView()/ TODO: add construction code hereCTestView:CTestView() -13 -BOOL CTestView二PreCreateWindow(CREATESTRUCT& cs) (/ TODO: Modify the Window class or styles here by modif

22、ying/ the CREATESTRUCT csreturn CView:PreCreateWindow(cs);)/ CTestView drawingvoid CTestView:OnDraw(CDC* pDC)(CTestDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/ TODO: add draw code for native data here)/ CTestView printingBOOL CTestView:OnPreparePrinting(CPrintInfo* pInfo)(/ default preparationretu

23、rn DoPreparePrinting(pInfo);)void CTestView:OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) (/ TODO: add extra initialization before printing)void CTestView:OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)(/ TODO: add cleanup after printing)/ CTestView diagnostics#ifdef _DEBUGvoid CTestView:A

24、ssertValid() const-14 -CView:AssertValid();)void CTestView:Dump(CDumpContext& dc) const(CView:Dump(dc);)CTestDoc* CTestView二GetDocument() / non-debug version is inline (ASSERT(m_pDocument-IsKindOf(RUNTIME_CLASS(CTestDoc); return (CTestDoc*)m_pDocument;).#endif/_DEBUG/ CTestView message handlersvoid

25、CTestView:Mbline()/Bresenham 函数(CClientDC dc(this);COLORREF rgb=RGB(0,0,255);/定义直线颜色为蓝色 double x,y,d,k;x=x0;y=y0;k=(y1-y0)/(x1-x0);d=0.5-k;/ 定义x, y, k及d的初始值for(x=x0;x=x1;x+)(dc.SetPixel(ROUND(x),ROUND(y),rgb);if(d0)(y+;d+=1-k;/d=0时，取正右方向像素点，d的增量为-k)void CTestView:OnMENUMbline()/ 菜单函数(/ TODO: Add you

26、r command handler code hereInputDlg dlg;if(dlg.DoModal()=IDOK)(x0=dlg.m_x0;/变量 x0 即为 InputDlg 中的 m_x0-15 -y0=dlg.m_y0;变量 y0 即为 InputDlg 中的 m_y0 x1=dlg.m_x1;变量 x1 即为 InputDlg 中的 m_x1y1=dlg.m_y1;变量 y1 即为 InputDlg 中的 m_y1)一一AfxGetMainWnd()-SetWindowText(实验:直线中点 Bresenhan#法) RedrawWindow();Mbline();) void CTestView:GetMaxX()/得到客户区的最大横坐标 CRect Rect;GetClientRect(&Rect);MaxX=Rect.right;)void CTestView:GetMaxY()/得到客户区最大纵坐标CRect Rect;GetClientRect(&Rect);MaxY=Rect.bottom;)void CTestView二Mbcircle()Bresenham 算法double x,y,d;d=1.25-R;x=0;y=R; 定义 d,x,y