计算机图形学-Bresenham算法画圆

第5章本案例知识要点●掌握八分法中点Bresenham 算法绘制圆的原理 ●设计八分法绘制圆的中点Bresenham 算法 ●编写八分法绘制圆的CirclePoint(x,y) 子函数 ● 编写绘制整圆的Mbcircle()子函数一、案例需求1．案例描述使用中点Bresenham 算法绘制圆心位于屏幕客户区中心的圆。

2．案例效果图案例输入对话框及效果如图3-1所示。

（a ）输入对话框 （b ）效果图3-1 圆中点Bresenham 算法效果图 3．功能说明（1）要求使用对话框输入圆的半径。

（2）圆的颜色为蓝色。

三、算法设计1. 输入圆的半径R 。

2. 定义圆当前点坐标x ，y 、定义中点偏差判别式d 、定义像素点颜色rgb 。

3. 计算R d -=25.1，x=0，y=R ，rgb ＝RGB(0,0,255)。

案例三 圆中点Bresenham 算法4.绘制点（x，y）及其在八分圆中的另外7个对称点。

5.判断d的符号。

若d<0，则（x，y）更新为（x＋1，y），d更新为d+2x＋3；否则（x，y）更新为（x＋1，y－1），d更新为d＋2（x－y）＋5。

6.当x小于等于y，重复步骤⑷和⑸，否则结束。

四、案例实现1．CTestView.h文件// TestView.h : interface of the CTestView class/////////////////////////////////////////////////////////////////////////////#if !defined(AFX_TESTVIEW_H__A75FDCFB_621C_4E38_A154_C344803E6372__INCLUDED_)#define AFX_TESTVIEW_H__A75FDCFB_621C_4E38_A154_C344803E6372__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000#include "InputDlg.h"//包含对话框头文件class CTestView : public CView{protected: // create from serialization onlyCTestView();DECLARE_DYNCREATE(CTestView)// Attributespublic:CTestDoc* GetDocument();// Operationspublic:void GetMaxY();//获得屏幕的最大x值函数void GetMaxX();//获得屏幕的最大y值函数void CirclePoint(double x,double y);//八分法画圆子函数void Mbcircle();//圆中点Bresenham算法// Overrides// ClassWizard generated virtual function overrides//{{AFX_VIRTUAL(CTestView)public:virtual void OnDraw(CDC* pDC); // overridden to draw this viewvirtual BOOL 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 AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:int MaxX,MaxY; //屏幕x和y的最大坐标double R; //圆的半径// Generated message map functionsprotected://{{AFX_MSG(CTestView)afx_msg void OnMENUMbcircle();//}}AFX_MSGDECLARE_MESSAGE_MAP()};#ifndef _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__INCLUDED_) 2．CTestView. 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_DYNCREATE(CTestView, CView)BEGIN_MESSAGE_MAP(CTestView, CView)//{{AFX_MSG_MAP(CTestView)ON_COMMAND(ID_MENU_Mbcircle, OnMENUMbcircle)//}}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()///////////////////////////////////////////////////////////////////////////// // CTestView construction/destructionCTestView::CTestView(){// TODO: add construction code here}CTestView::~CTestView(){}BOOL CTestView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// 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 preparationreturn 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::AssertValid() const{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 CTestView::GetMaxX()//得到客户区的最大横坐标{CRect Rect;GetClientRect(&Rect);MaxX=Rect.right;}void CTestView::GetMaxY()//得到客户区最大纵坐标{R=dlg.m_R;}AfxGetMainWnd()->SetWindowText("基本图形扫描转换:Mbcircle");RedrawWindow();GetMaxX();GetMaxY();Mbcircle();}五、案例说明因为设备坐标系的原点在屏幕左上角，所以为了在屏幕中心绘制圆，定义了GetMaxX()和GetMaxY()函数来获得屏幕的MaxX和MaxY，参见案例1的实现部分。

bresenham圆生成算法Bresenham圆生成算法是一种经典的计算机图形学算法，用于在计算机屏幕上绘制圆形。

该算法是由美国计算机科学家Jack E. Bresenham于1965年发明的。

这个算法非常简单，但是它却非常有效，因为它只需要使用整数运算。

Bresenham圆生成算法的基本思想是使用一个叫做“决策参数”的变量来决定下一个像素点的位置。

该变量根据当前像素点到圆心的距离和半径之间的差异进行调整。

如果该差异小于0，则移动到右上方的像素点；否则，移动到右上方和正上方之间的像素点。

具体来说，Bresenham圆生成算法可以通过以下步骤来实现：1. 输入圆心坐标和半径。

2. 初始化x和y坐标为0，并计算出初始决策参数d=3-2r。

3. 在每个步骤中，检查当前像素点是否在圆内。

如果是，则将该像素点绘制出来；否则，不绘制。

4. 计算下一个像素点的位置。

如果d小于0，则移动到右上方；否则，移动到右上方和正上方之间。

5. 更新决策参数d。

Bresenham圆生成算法的优点是它非常快速和有效。

它只需要使用整数运算，因此可以在计算机上非常快速地执行。

此外，该算法还可以轻松地扩展到三维空间中的球体和其他形状。

尽管Bresenham圆生成算法已经有几十年的历史了，但它仍然是计算机图形学中最常用的算法之一。

它被广泛应用于游戏开发、计算机辅助设计、虚拟现实等领域。

此外，该算法还被用于许多其他领域，如数字信号处理和图像处理。

总之，Bresenham圆生成算法是一种简单而有效的计算机图形学算法。

它可以快速地绘制出圆形，并且可以轻松地扩展到其他形状。

尽管这个算法已经有几十年的历史了，但它仍然是计算机图形学中最常用的算法之一，并且在许多其他领域也得到了广泛应用。

计算机图形学实验报告姓名：张晓波学号：090081322010 年10月实验1 实用OpenGL 绘制二维图形实验目的1.进一步了解OpenGL程序的框架。

2.掌握利用OpenGL绘制简单视图的方法。

3.利用OpenGL中的Bresenham算法直接利用像素点绘制图形。

实验要求1.明确实验目的，按实验内容及基本步骤完成实验。

2.在实验过程中，结合思考与探究中的问题，通过实验进行理解。

3.理解并掌握本实验的内容。

实验内容及基本步骤1.绘制圆形分析：利用Bresenham算法，可以在自定了第一个点之后算出下一个点的位置，由于要保证斜率小于1，而且只在一个象限内绘制，所以找出的只是1/8圆弧，因此在找点的时候，利用对称性，同时找到8个点，进行绘制。

void Circle(int r){int x=0,y=r; //初始点int d=0; //声明决策变量d=3-2*r;while(x<=y){CircleVertex(x,y);//画圆上点FillCircle(x,y); //选取对应点，用矩形填充if(d<0)d=d+4*x+6;else{d=d+4*(x-y)+10;y --;}x++;}}void CircleVertex(int x, int y){glBegin(GL_POINTS);glVertex2f( x, y);//右上角glVertex2f(- x, y);//左上角glVertex2f( x,- y);//右下角glVertex2f(- x,- y);//左下角//上下侧四个点glVertex2f( y, x);//右上角glVertex2f(- y, x);//左上角glVertex2f( y,- x);//右下角glVertex2f(- y,- x);//左下角//左右侧四个点glEnd();}试验结果如下：2.填充圆形分析：在一次寻找确定出8个点之后，可以将其上下两端的点作为一组，左右两端的点作为一组分别绘制实心四边形。

画圆形（Bresenham算法）下⾯先简要介绍常⽤的画圆算法（Bresenham算法），然后再具体阐述笔者对该算法的改进。

⼀个圆，如果画出了圆上的某⼀点，那么可以利⽤对称性计算余下的七段圆弧：Plot(x，y)，Plot(y，x)，Plot(y，-x)，Plot(x，-y)，Plot(-x，-y)，Plot(-y，-x)，Plot(-y，x)，Plot(-x，y)。

1、Bresenham 画圆算法。

Bresenham算法的主要思想是：以坐标原点（0，0）为圆⼼的圆可以通过0度到45°的弧计算得到，即x从0增加到半径，然后利⽤对称性计算余下的七段圆弧。

当x从0增加到时，y从R递减到。

设圆的半径为R，则圆的⽅程为：f(x，y)＝(x+1)2+y2-R2＝0 (1)假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi，yi)，根据第⼆卦限1/8圆的⾛向，下⼀列（x=xi+1列）中最接近圆弧的像素只能在P的正右⽅点H(xi+1，yi)或右下⽅点L(xi+1，yi-1)中选择，如图1所⽰。

Bresenham画圆算法采⽤点T(x，y)到圆⼼的距离平⽅与半径平⽅之差D(T)作为选择标准，即D(T)=(x+1)2+y2-R2 (2)通过⽐较H、L两点各⾃对实圆弧上点的距离⼤⼩，即根据误差⼤⼩来选取，具有最⼩误差的点为绘制点。

根据公式(2)得：对H(xi+1，yi)点有：D(H)=(xi+1)2+yi2-R2；对L(xi+1，yi-1)点有：D(L)=(xi+1)2+(yi-1)2-R2；根据Bresenham画圆算法，则选择的标准是：如果|D(H)|<|D(L)|，那么下⼀点选取H(xi+1，yi)；如果|D(H)|>|D(L)|，那么下⼀点选取L(xi+1，yi-1)；如果|D(H)|=|D(L)|，那么下⼀点可以取L(xi+1，yi-1)，也可以选取H(xi+1，yi)，我们约定选取H(xi+1，yi)。

一、实验背景圆是几何图形中最基本的图形之一，在计算机图形学中，绘制圆是图形处理的基础。

本实验旨在通过实现圆的绘制算法，加深对计算机图形学基本概念和方法的理解，提高编程能力。

二、实验目的1. 掌握圆的基本绘制方法；2. 熟悉Bresenham算法和中点算法的原理；3. 理解并实现圆的绘制算法；4. 分析不同算法的优缺点，提高算法选择能力。

三、实验内容1. Bresenham算法画圆2. 中点算法画圆四、实验原理1. Bresenham算法画圆Bresenham算法是一种光栅扫描算法，用于绘制圆、椭圆、直线等图形。

该算法的基本思想是：根据圆的几何特性，计算出每个像素点是否应该被绘制。

对于圆的绘制，我们可以利用以下公式：\[ x^2 + y^2 = r^2 \]其中，\( x \) 和 \( y \) 分别表示圆上一点的横纵坐标，\( r \) 表示圆的半径。

Bresenham算法的步骤如下：（1）初始化参数：设置起始点（0, r），终止点（r, 0），步长 \( p \)；（2）计算判别式 \( p = 2x - y \)；（3）根据判别式的值，更新 \( x \) 和 \( y \) 的值；（4）重复步骤（2）和（3），直到 \( x = y \)；（5）绘制圆。

2. 中点算法画圆中点算法是一种基于Bresenham算法的改进算法，它利用圆的对称性，减少了计算量。

中点算法的步骤如下：（1）初始化参数：设置起始点（0, r），终止点（r, 0），步长 \( p \)；（2）计算判别式 \( p = 1 - 2x \)；（3）根据判别式的值，更新 \( x \) 和 \( y \) 的值；（4）重复步骤（2）和（3），直到 \( x = y \)；（5）绘制圆。

五、实验步骤1. 创建一个OpenGL窗口，用于显示绘制的圆；2. 使用Bresenham算法绘制圆；3. 使用中点算法绘制圆；4. 比较两种算法的绘制效果，分析优缺点；5. 编写代码实现两种算法，并进行测试。

§3.2圆的生成——Bresenham算法条件：给定圆心(x c,y c)和半径R约定：只考虑圆心在原点，半径为整数R的圆x2+y2.=R2。

对于圆心不在原点的圆，可先通过平移转换，化为圆心在原点的圆，再进行扫描转换，把所得到的像素集合加上一个位移量，就可以把目标圆光栅化。

在众多圆的生成算法，如逐点比较法、角度DDA法、Bresenham算法中，Bresenham画圆法是一种最简单有效的的方法。

首先注意到只要生成一个八分圆，那么，圆的其它部分就可以通过一系列的对成变换得到。

12345678由算法生成y=x第一八分圆关于y=x对称变换第一四分圆关于x=0对称变换上半圆关于y=0对称变换如果以点x=0，y=R为起点按顺时针方向生成圆，则在第一象限内y是x 的单调递减函数。

要在这三个像素中选择一个使其与理想圆的距离的平方达到最小，即下列数值中的最小者。

R(0,R)(R,0)xy这样，从圆上任一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一像素的取法只有三种可能的选择，即正右方像素、正下方像素和右下角像素，分别记作：m H、m V、m D。

(x i，y i)(x i，y i-1)(x i+1，y i)(x i+1，y i-1)m Hm Dm Vm H=|(x i+1)2+(y i)2-R2|m V=|(x i)2+(y i+1)2-R2|m D=|(x i+1)2+(y I-1)2-R2|m H(x i,y i)(x i+1,y i)(x i+1,y i+1)(x i+1,y i-1)(x i-1,y i-1)(x i,y i-1)m Vm D12354圆与点(x i，y i)附近光栅格网的相交关系只有五种可能。

从圆心到右下角像素(x i+1,y i-1)的距离平方m D与圆心到圆上点的距离平方R2之差等于：Δi=(x i+1)2+(y i-1)2-R2如果Δi<0,那么右下角像素(x i+1,y i-1)在该圆内(图中①、②)，显然这时只能取像素(x i+1,y i)，即m H；或像素(x i+1,y i-1)，即m D。

计算机图形学编程实习一之Bresenham画圆算法
实习报告
学号2014301750057 姓名李帅旗一、实习目的
1.熟悉Visual C++开发环境，能够自己搭建OpenGL图形开发框架，并用C/C+语言实现Bresenham画圆算法。

2.初步了解图元生成算法的实现过程、验证方法，通过实现Bresenham画圆算法，理解图元的参数表示法、光栅扫描、显示输出的概念。

二、实习内容与过程
1. 熟悉Visual C++开发环境；
2.了解Win32控制台开发框架；
3.完成Bresenham画圆算法程序的输入、编译和运行；
4.掌握程序调试的方法。

三、遇到的问题
Bresenman画圆算法和中点画圆算法非常相似，参考着老师提供的中点画圆法的代码，在理解其要义的基础上，再写Bresenman画圆的代码就很简单了。

唯一的疑难点是教材上的Bresenman算法的推导过程有些问题，它省略了重要的步骤，在老师的提示下方才理解明白。

四、实习总结
本次实习还是比较简单的，重点是理解Bresenman画圆算法的过程，在此基础上才可能写出正确的代码。

易懂的Bresenham布雷森汉姆算法画圆的原理与Python编程实现教程Bresenham 布雷森汉姆算法画圆的原理与编程实现教程注意：Bresenham的圆算法只是中点画圆算法的优化版本。

区别在于Bresenham的算法只使⽤整数算术，⽽中点画圆法仍需要浮点数。

注意：不要因为我提到了中点画圆法你就去先看完再看Bresenham算法，这样是浪费时间。

中点画圆法和Bresenham画圆法只是思想⼀样，但是思路并没有很⼤关联。

所以直接看Bresenham算法就可以。

看下⾯这个图，这就是⼀个像素⼀个像素的画出来的。

我们平常的圆也是⼀个像素⼀个像素的画出来的，你可以试试在“画图”这个软件⾥⾯画⼀个圆然后放⼤很多倍，你会发现就是⼀些像素堆积起来的。

我们看出来圆它是⼀个上下左右都对称，⽽且也是中⼼对称的。

所以我们只⽤画好⼋分之⼀圆弧就可以，其他地⽅通过对称复制过去就好。

看下⾯这幅图，绿线夹住的那部分就是⼋分之⼀圆弧。

注意我们是逆时针画圆的（即从⽔平那个地⽅即(r,0)开始画因为⼀开始我们只知道⽔平位置的像素点该放哪其他地⽅我们都不知道）。

Bresenham 算法画完⼀个点(x,y)后注意x,y都是整数。

他们代表的是x,y⽅向上的第⼏个像素。

，它下⼀步有两个选择(x,y+1),(x-1,y+1)。

也就是说y⼀定增加,但是x要么保持不变要么减⼀（你也可以让x⼀定增加y要么不变要么加⼀，其实差不多的）。

当程序画到粉红⾊那个像素点的时候，程序选择下⼀步要绘制的点为(x-1，y+1)。

当程序画到黄⾊的那个像素点时候，程序选择下⼀步要绘制的点为(x,y+1)。

我们看看粉⾊的那个点的下⼀步是如何抉择的。

Bresenham是根据待选的两个点哪个离圆弧近就下⼀步选哪个。

那它是怎么判断的呢？这两个点⼀定有⼀个在圆弧内⼀个在圆弧外。

到底选哪个？Bresenham的⽅法就是直接计算两个点离圆弧之间的距离，然后判断哪个更近就选哪个。

1.中点Bresenham 算法的原理圆心在原点、半径为R 的圆方程的隐函数表达式为：圆将平面划分成三个区域：对于圆上的点，F(x ，y)＝0；对于圆外的点，F （x ，y ）＞0；对于圆内的点，F （x ，y ）＜0。

事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。

用四条对称轴x ＝0，y ＝0， x ＝y,x ＝－y 把圆分成8等份。

只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。

假定第一象限内的任意点为P （x,y ），可以顺时针确定另外7个点：P （y ，x ）,P （y ，－x ）,P （x,－ y ）,P （－x ，－y ），P （－y ，－x ），P （－y ，x ），P （－x ，y ）。

2.构造中点偏差判别式从P （xi ，yi ）开始，为了进行下一像素点的选取，需将Pu 和Pd 的中点M （x i+1，y i-0.5）代入隐函数，构造中点偏差判别式：⑴当d<0时，下一步的中点坐标为：M （xi ＋2，yi －0.5）。

下一步中点偏差判别式为：⑵当d ≥0时，下一步的中点坐标为：M （xi ＋2，yi －1.5）。

),(222=-+=R y x y xF )5.0,1(),(-+==i i M M y x F y x F d ⎩⎨⎧≥<=+)0( 1-)0(1d y d y y i i i 2221)5.0()2()5.0,2(R y x y x F d i i i i i --++=-+=+3232)5.0()1(222++=++--++=i i i i i x d x R yx2221)5.1()2()5.1,2(R y x y x F d i i i i i --++=-+=+。