一。Bresenham算法介绍
Bresenham算法，是由Bresenham在1965年提出的。最初，此算法是在绘图仪上进行画线而设计的，但是后来被运用到了计算机图形学上。类似的画先算法还有DDA（数值微分）法，中点算法等。感兴趣的读者可以在计算机图形学上进行了解，毕竟画直线算法是计算机图形学的基础知识。（虽然是基础知识，但是我也搞了一早上，汗！！！深切感觉到数学功底不扎实）。
二。Bresenham算法原理
才开始的时候，我在想，画条直线而已，很简单啊，就一个像素一个像素点的进行绘制不就可以了嘛。可是，当我们仔细的观察或者进行实践的时候，就会发现很多的问题。比如，设直线y=mx+b,（x0,y0）和(x1,y1)分别为终点和起点。有人提出，由于像素都是一个一个的，所以我们可以根据x方向的移动一个像素，然后计算出相应的y值，这样就得到了一个像素的坐标了，然后就可以进行绘制。的确，这样的方法在某些情况下可以实现。但是，当我们的m值很大的时候，直线的绘制就变成了很多间断的点。
如下图所示：
上图中，虚拟的构造了一些网格来表示，我们可以看到，但斜率m的绝对值过大的时候，这样画出来的直线很明显的会出现间断的样子，所以这不是一个好的办法。
而Bresenham算法就可以很好的解决这个问题。
简单的说，Bresenham算法，就是通过一个误差项的符号，来判断y的坐标，从而最大限度的逼近直线。(好空的话哦！！！)
好吧 ，我也觉的一下的这样讲等于白讲，我们还是看张图吧，有图有真相。
为了方便看出来直线和像素的关系，我使用红色来进行了分隔，这样只要你不是色盲应该能够很清楚的看见这条直线的是怎么绘制的吧。上面的图，是将一条直线，放大很多倍，直到每个像素都可以很清楚的看见。
从上面的图，你应该知道了直线绘制的过程。加入我们以左下角的点为起点，右上角的点为终点。好啦，现在还是按照x方向来进行步进，那么观察先这条直线，会发现下一个点要么在前面一个点的右边，要么就是在前面一个点的右上角。（注意哦，现在只讨论这条线，不是其他的线，如果你说你自己画了条线，而朝向和我的不一样，非要说我这里说的有错，额。。。那我也没办法了。。。。）
也就是说，在我们自己实现的时候，知道了起点，和终点，我们只要判断下个点到底是在右边，还是右上角的问题，对吧？
这个问题，应该很简单吧，我们看看哪个离真实的点更近就选哪个不就可以了吗？
嗯，是这样的，Bresenham的核心思想就是这么做。但是，如果你仅仅用上面的方法来进行实现的话，会不可避免的需要使用浮点数来进行，这样就会造成一点精度的缺失。最好的方法，就是使用整数来进行，毕竟计算机使用整数更溜。
三。Bresenham算法推导过程
还是以上面的那条放大的线为主体进行讨论。假设这条线的方程为：y=mx+b 起点为(x1,y1)终点为(x2,y2)。
我们设当前的点(就是在进行点绘制的时候，肯定是循环来的，所以设置一个当前点)为(xi,yi)。
那么根据前面的描述，下一个点可能是(xi+1,yi)或者是(xi+1,yi+1)。
所以，问题就明朗了，我们需要在这两个值中进行选择。
为了推导这个问题，我们设置以下的一些变量：
dy = y2 - y1 ; 表示y方向的间距
dx = x2 - x1 ; 表示x方向的间距
好了 ，下面开始推导吧。
当x = xi+1 的时候 ，
y的实际值(就是在直线方程中的值):y = m(xi+1)+b,
则，实际值与右边点(xi+1,yi)的误差为：
d1 = y - yi = m(xi+1)+b-yi ;
实际值与右上角点(xi+1,yi+1)的误差为：
d2 = yi+ 1 - y = yi+ 1 - m(xi+ 1)-b ;
所以，当d1 > d2 的时候，就表示右边点的误差大，右上角的点误差小，所以选择右上角的点，反之则选择右边点。
这里的d1,和d2在进行了一轮计算中，很有可能会出现是浮点数的情况，所以我们需要对这些值进行放大。
根据上面的推导，也就是说，我们可以根据d1-d2的值的符号来进行判断。
下面我们来创建一个误差项，Pi = (d1-d2)*dx ；由于dx为正，所以，Pi的符号就是d1-d2的符号，这样就进行了放大，很容易判断了。
Pi = (d1-d2)*dx
使用xi,yi的值来进行带入，得
Pi = 2*xi*dy - 2*yi*dx + 2*dy+(2*b-1)*dx ;
故，
P(i+1) = 2*x(i+1)*dy - 2*y(i+1)*dx + 2*dy+(2*b-1)*dx
=2*(xi+1)*dy - 2*y(i+1)*dx+2*dy+(2*b-1)*dx
=2*xi*dy+2*dy- 2*y(i+1)*dx+2*dy+(2*b-1)*dx
=[2*xi*dy - 2*yi*dx + 2*dy+(2*b-1)*dx ] + 2*dy + 2*yi*dx
- 2*y(i+1)
- 2*y(i+1)
=Pi + 2*dy - 2*[y(i+1) - yi]*dx
(注意啦，上面的推导中，像x(i+1)，其中的(i+1)表示的是下标哦，千万别理解成x*(i+1)^_^)
所以，P(i+1) = Pi + 2*dy - 2*[y(i+1) - yi]*dx ;
这里的y(i+1)-yi的值，要根据Pi的符号来进行。
如果Pi是负的，那么就表示前面的在计算选择下一个点的时候，选择的是右边的点，也就是说y(i+1)-yi= 0 ；反之，就是1了。 应该很容易理解吧！！！^_^
至此，我们已经推导了一遍上面的直线的情况了。所以我们只要进行循环的计算就可以进行了像素坐标的确定了，然后在进行绘制。
等等。。。。。。你这个只是对上面那条直线的推导啊，能通用吗？别糊弄我啊？？？你是不是正在这样想了？
呵呵，这里的关键就是步进了(我称之为步进，就是在X方向，或者Y方向上进行像素移动是，每一次移动多少个单位)还有到底是按照x的步进来计算，还是按照y方向的步进来计算。
接下来我们来讨论下，有几种直线，先根据斜率来：
我们将斜率分为两种,一种是|m|<1的，可以称之为近x直线；
还有就是|m|>1的，可以称之为近y直线；
我上面讨论的情况是近X直线的情况。
还有就是起点和终点的位置关系来分类：
x2-x1 > 0 ; x2-x1 < 0 ;
y2-y1 > 0 ; y2-y1 < 0 ;
这四种情况。
根据上面的推导，我们可以进一步推导出：
当|m|<1的时候，我们以X方向进行步进,
x2-x1 > 0 时，步进为1 ，也就是说x(i+1)=xi+1 ;
x2 - x1 < 0 时，步进为-1 ， 也就是说x(i+1)=xi-1 ;
当|m|>1的时候，我们以Y方向进行步进，
y2-y1 > 0时，步进为1 ， 也就是说y(i+1) = yi+1 ;
y2-y1 < 0时，步进为-1，也就是说y(i+1)=yi-1 ;
好了吧，差不多说到这里，你们应该能够使用自己的编程语言和设置像素的函数进行直线的绘制了吧。如果能的话，那我会非常的感到欣慰的！！！^_^
四。Bresenham代码实现
先来看看这个函数的实现吧：
//定义画线函数
int Draw_Line(int x0,int y0, int x1, int y1 , DWORD color , UINT *video_buffer, int stepx,int stepy)
{
int dx , //起点与终点的X方向间距
dy , //起点与终点的Y方向间距
dx2, //两倍的dx
dy2, //两倍的dy
x_inc , //实际的x步长值，带有符号
y_inc , //实际的y步长值，带有符号
p ; //误差项
dx = x1 - x0 ; //计算x间距
dy = y1 - y0 ; //计算y间距
//计算起点的缓冲地址
video_buffer+=x0+y0*stepy ;
//确定x方向的步进值
if(dx>=0)
{
x_inc = stepx;
}
else
{
x_inc = -stepx ;
dx = -dx ;
}
//确定y方向的步进值
if(dy>=0)
{
y_inc = stepy ;
}
else
{
y_inc = -stepy ;
dy = -dy ;
}
//确定dx2,dy2的值
dx2 = dx<<1;
dy2 = dy<<1 ;
//进行步进的选择
if(dx <= dy) //斜率绝对值大于1
{
Swap(dx,dy);
Swap(x_inc,y_inc);
Swap(dx2,dy2);
}
else //斜率绝对值小于1，不需要交换
{
}
//绘制直线
p = dy2 - dx ; //计算起点的误差值
for(int i = 0 ; i < dx ; i++)
{
*video_buffer = color ;
video_buffer += x_inc ;
if(p>=0)
{
video_buffer += y_inc ;
p = p + dy2 - dx2 ;
}
else
{
p = p + dy2 ;
}
}// end for
return 0 ;
}// end Draw_Line
注意了，上面的函数是在DirectX中使用的，如果你直接拿过去用的话，我想应该会很糟糕，这个要根据具体的情况具体的来写。如果你掌握了我说的全部，那么应该有能力将这个函数改成适合你自己的版本。
下面是整个DirectX的实现：
// DEMO7_11.CPP 此Demo演示32位窗口模式下，使用GDI
// INCLUDES ///////////////////////////////////////////////
#define WIN32_LEAN_AND_MEAN // just say no to MFC
#define INITGUID // make sure directX guids are included
#include <windows.h> // include important windows stuff
#include <windowsx.h>
#include <mmsystem.h>
#include <iostream> // include important C/C++ stuff
using namespace std ;
#include <conio.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>
#include <math.h>
#include <io.h>
#include <fcntl.h>
#include <ddraw.h> // include directdraw
#pragma comment(lib,"ddraw.lib")
// DEFINES ////////////////////////////////////////////////
// defines for windows
#define WINDOW_CLASS_NAME L"WINCLASS1"
// default screen size
#define SCREEN_WIDTH 640 // size of screen
#define SCREEN_HEIGHT 480
#define SCREEN_BPP 32 // bits per pixel
#define MAX_COLORS 256 // maximum colors
// TYPES //////////////////////////////////////////////////////
// basic unsigned types
typedef unsigned short USHORT;
typedef unsigned short WORD;
typedef unsigned char UCHAR;
typedef unsigned char BYTE;
// MACROS /////////////////////////////////////////////////
#define KEYDOWN(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 1 : 0)
#define KEYUP(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 0 : 1)
// initializes a direct draw struct
#define DD_INIT_STRUCT(ddstruct) { memset(&ddstruct,0,sizeof(ddstruct)); ddstruct.dwSize=sizeof(ddstruct); }
//initializes a RGB value
#define _RGB16BIT565(r,g,b) ((b & 31) + ((g & 63) << 5) + ((r & 31) << 11))
#define _RGB32BIT(a,r,g,b) ((b) + ((g) << 8) + ((r) << 16) + ((a) << 24))
// GLOBALS ////////////////////////////////////////////////
HWND main_window_handle = NULL; // globally track main window
HINSTANCE hinstance_app = NULL; // globally track hinstance
// directdraw stuff
LPDIRECTDRAW7 lpdd = NULL; // dd object
LPDIRECTDRAWSURFACE7 lpddsprimary = NULL; // dd primary surface
LPDIRECTDRAWSURFACE7 lpddsback = NULL; // dd back surface
LPDIRECTDRAWPALETTE lpddpal = NULL; // a pointer to the created dd palette
LPDIRECTDRAWCLIPPER lpddclipper = NULL; // dd clipper
PALETTEENTRY palette[256]; // color palette
PALETTEENTRY save_palette[256]; // used to save palettes
DDSURFACEDESC2 ddsd; // a direct draw surface description struct
DDBLTFX ddbltfx; // used to fill
DDSCAPS2 ddscaps; // a direct draw surface capabilities struct
HRESULT ddrval; // result back from dd calls
DWORD start_clock_count = 0; // used for timing
LPDIRECTDRAWSURFACE7 lpddsOffScreen = NULL ; //离屏表面
int window_close = 0 ; //标识窗口是否关闭
// these defined the general clipping rectangle
int min_clip_x = 0, // clipping rectangle
max_clip_x = SCREEN_WIDTH-1,
min_clip_y = 0,
max_clip_y = SCREEN_HEIGHT-1;
// these are overwritten globally by DD_Init()
int screen_width = SCREEN_WIDTH, // width of screen
screen_height = SCREEN_HEIGHT, // height of screen
screen_bpp = SCREEN_BPP; // bits per pixel
char buffer[80]; // general printing buffer
//申明画线方法
int Draw_Line(int x0, int y0, int x1, int y1, DWORD color , UINT * video_buffer , int stepx , int stepy);
//交换值
void Swap(int &x , int &y) ;
// FUNCTIONS //////////////////////////////////////////////
LRESULT CALLBACK WindowProc(HWND hwnd,
UINT msg,
WPARAM wparam,
LPARAM lparam)
{
// this is the main message handler of the system
PAINTSTRUCT ps; // used in WM_PAINT
HDC hdc; // handle to a device context
char buffer[80]; // used to print strings
// what is the message
switch(msg)
{
case WM_CREATE:
{
// do initialization stuff here
// return success
return(0);
} break;
case WM_PAINT:
{
// simply validate the window
hdc = BeginPaint(hwnd,&ps);
// end painting
EndPaint(hwnd,&ps);
// return success
return(0);
} break;
case WM_DESTROY:
{
// kill the application, this sends a WM_QUIT message
PostQuitMessage(0);
// return success
return(0);
} break;
default:break;
} // end switch
// process any messages that we didn't take care of
return (DefWindowProc(hwnd, msg, wparam, lparam));
} // end WinProc
///////////////////////////////////////////////////////////
//程序主循环
int Game_Main(void *parms = NULL, int num_parms = 0)
{
// this is the main loop of the game, do all your processing
// here
// for now test if user is hitting ESC and send WM_CLOSE
if(window_close)
return 1 ;
if (KEYDOWN(VK_ESCAPE))
{
PostMessage(main_window_handle,WM_CLOSE,0,0);
window_close = 1 ;
}
//清空表面
DDBLTFX bltfx ;
DD_INIT_STRUCT(bltfx);
bltfx.dwFillColor = 0 ;
if(FAILED(lpddsOffScreen->Blt(NULL,NULL,NULL,DDBLT_WAIT|DDBLT_COLORFILL,&bltfx)))
{
OutputDebugString(L"OffScreen Blt error");
return 1 ;
}
//锁定
DDSURFACEDESC2 ddsd ;
DD_INIT_STRUCT(ddsd);
if(FAILED(lpddsOffScreen->Lock(NULL,&ddsd,DDLOCK_WAIT|DDLOCK_SURFACEMEMORYPTR,NULL)))
{
OutputDebugString(L"Lock error");
return 1 ;
}
//获取窗口位置
RECT rect ;
GetWindowRect(main_window_handle,&rect);
//画线
int x0 = rand()%SCREEN_WIDTH;
int x1 = rand()&SCREEN_WIDTH;
int y0 = rand()%SCREEN_HEIGHT;
int y1 = rand()%SCREEN_HEIGHT;
Draw_Line(rect.left+x0,rect.top+y0,rect.left+x1,rect.top+y1,(DWORD)_RGB32BIT(0,255,255,0),(UINT*)ddsd.lpSurface,1,ddsd.lPitch>>2);
//解锁
if(FAILED(lpddsOffScreen->Unlock(NULL)))
{
OutputDebugString(L"Unlock error");
return 1 ;
}
//Blt到主表面
if(FAILED(lpddsprimary->Blt(NULL,lpddsOffScreen,NULL,DDBLT_WAIT,NULL)))
{
OutputDebugString(L"Blt error");
return 1 ;
}
// return success or failure or your own return code here
return(1);
} // end Game_Main
////////////////////////////////////////////////////////////
int Game_Init(void *parms = NULL, int num_parms = 0)
{
// this is called once after the initial window is created and
// before the main event loop is entered, do all your initialization
// here
// create IDirectDraw interface 7.0 object and test for error
if (FAILED(DirectDrawCreateEx(NULL, (void **)&lpdd, IID_IDirectDraw7, NULL)))
return(0);
// set cooperation to normal since this will be a windowed app
if(FAILED(lpdd->SetCooperativeLevel(main_window_handle, DDSCL_NORMAL)))
{
MessageBox(NULL,L"SetCooperativeLevel error",L"error",MB_OK);
return 0 ;
}
//创建裁剪器
if(FAILED(lpdd->CreateClipper(0,&lpddclipper,NULL)))
{
OutputDebugString(L"CreateClipper error");
return 1 ;
}
//将裁减器关联窗口，也就是用窗口的尺寸作为裁剪器的裁剪序列
if(FAILED(lpddclipper->SetHWnd(0,main_window_handle)))
{
OutputDebugString(L"SetHWnd error");
return 1 ;
}
//创建主表面
memset(&ddsd,0,sizeof(ddsd));
ddsd.dwSize = sizeof(ddsd);
ddsd.dwFlags = DDSD_CAPS ;
ddsd.ddsCaps.dwCaps = DDSCAPS_PRIMARYSURFACE;
if(FAILED(lpdd->CreateSurface(&ddsd,&lpddsprimary,NULL)))
{
MessageBox(NULL,L"CreateSurface error",L"error",MB_OK);
return 0 ;
}
//将裁减器关联到表面
if(FAILED(lpddsprimary->SetClipper(lpddclipper)))
{
OutputDebugString(L"SetClipper error");
return 1 ;
}
//创建一个离屏表面
DD_INIT_STRUCT(ddsd);
ddsd.ddsCaps.dwCaps = DDSCAPS_OFFSCREENPLAIN | DDSCAPS_VIDEOMEMORY;
ddsd.dwFlags = DDSD_CAPS | DDSD_WIDTH | DDSD_HEIGHT ;
ddsd.dwHeight = 786 ;
ddsd.dwWidth = 1366 ;
if(FAILED(lpdd->CreateSurface(&ddsd,&lpddsOffScreen,NULL)))
{
OutputDebugString(L"OffScreen CreateSurface error");
return 1 ;
}
// return success or failure or your own return code here
return(1);
} // end Game_Init
/////////////////////////////////////////////////////////////
int Game_Shutdown(void *parms = NULL, int num_parms = 0)
{
// this is called after the game is exited and the main event
// loop while is exited, do all you cleanup and shutdown here
// simply blow away the IDirectDraw4 interface
if(lpddclipper)
{
lpddclipper->Release();
lpddclipper = NULL ;
}
if(lpddsprimary)
{
lpddsprimary->Release();
lpddsprimary = NULL ;
}
if (lpdd)
{
lpdd->Release();
lpdd = NULL;
} // end if
// return success or failure or your own return code here
return(1);
} // end Game_Shutdown
// WINMAIN ////////////////////////////////////////////////
int WINAPI WinMain( HINSTANCE hinstance,
HINSTANCE hprevinstance,
LPSTR lpcmdline,
int ncmdshow)
{
WNDCLASSEX winclass; // this will hold the class we create
HWND hwnd; // generic window handle
MSG msg; // generic message
HDC hdc; // graphics device context
// first fill in the window class stucture
winclass.cbSize = sizeof(WNDCLASSEX);
winclass.style = CS_DBLCLKS | CS_OWNDC |
CS_HREDRAW | CS_VREDRAW;
winclass.lpfnWndProc = WindowProc;
winclass.cbClsExtra = 0;
winclass.cbWndExtra = 0;
winclass.hInstance = hinstance;
winclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
winclass.hCursor = LoadCursor(NULL, IDC_ARROW);
winclass.hbrBackground = (HBRUSH)GetStockObject(BLACK_BRUSH);
winclass.lpszMenuName = NULL;
winclass.lpszClassName = WINDOW_CLASS_NAME;
winclass.hIconSm = LoadIcon(NULL, IDI_APPLICATION);
// save hinstance in global
hinstance_app = hinstance;
// register the window class
if (!RegisterClassEx(&winclass))
return(0);
// create the window
if (!(hwnd = CreateWindowEx(NULL, // extended style
WINDOW_CLASS_NAME, // class
L"DirectDraw Initialization Demo", // title
WS_OVERLAPPED|WS_VISIBLE,
0,0, // initial x,y
SCREEN_WIDTH,SCREEN_HEIGHT, // initial width, height
NULL, // handle to parent
NULL, // handle to menu
hinstance,// instance of this application
NULL))) // extra creation parms
return(0);
// save main window handle
main_window_handle = hwnd;
// initialize game here
Game_Init();
//调整窗口大小
RECT window_rect = {0,0,SCREEN_WIDTH,SCREEN_HEIGHT} ;
AdjustWindowRectEx(&window_rect,GetWindowStyle(main_window_handle),GetMenu(main_window_handle)!=NULL,GetWindowExStyle(main_window_handle));
// enter main event loop
while(TRUE)
{
// test if there is a message in queue, if so get it
if (PeekMessage(&msg,NULL,0,0,PM_REMOVE))
{
// test if this is a quit
if (msg.message == WM_QUIT)
break;
// translate any accelerator keys
TranslateMessage(&msg);
// send the message to the window proc
DispatchMessage(&msg);
} // end if
// main game processing goes here
Game_Main();
} // end while
// closedown game here
Game_Shutdown();
// return to Windows like this
return(msg.wParam);
} // end WinMain
//定义交换函数
void Swap(int &x , int &y)
{
int temp = y ;
y = x ;
x = temp ;
}
//定义画线函数
int Draw_Line(int x0,int y0, int x1, int y1 , DWORD color , UINT *video_buffer, int stepx,int stepy)
{
int dx , //起点与终点的X方向间距
dy , //起点与终点的Y方向间距
dx2, //两倍的dx
dy2, //两倍的dy
x_inc , //实际的x步长值，带有符号
y_inc , //实际的y步长值，带有符号
p ; //误差项
dx = x1 - x0 ; //计算x间距
dy = y1 - y0 ; //计算y间距
//计算起点的缓冲地址
video_buffer+=x0+y0*stepy ;
//确定x方向的步进值
if(dx>=0)
{
x_inc = stepx;
}
else
{
x_inc = -stepx ;
dx = -dx ;
}
//确定y方向的步进值
if(dy>=0)
{
y_inc = stepy ;
}
else
{
y_inc = -stepy ;
dy = -dy ;
}
//确定dx2,dy2的值
dx2 = dx<<1;
dy2 = dy<<1 ;
//进行步进的选择
if(dx <= dy) //斜率绝对值大于1
{
Swap(dx,dy);
Swap(x_inc,y_inc);
Swap(dx2,dy2);
}
else //斜率绝对值小于1，不需要交换
{
}
//绘制直线
p = dy2 - dx ; //计算起点的误差值
for(int i = 0 ; i < dx ; i++)
{
*video_buffer = color ;
video_buffer += x_inc ;
if(p>=0)
{
video_buffer += y_inc ;
p = p + dy2 - dx2 ;
}
else
{
p = p + dy2 ;
}
}// end for
return 0 ;
}// end Draw_Line
///////////////////////////////////////////////////////////
附上运行结果图：
五。休闲时刻
由于以后想做游戏了，现在开始学2D游戏的制作，期待将来能够自己编写出游戏引擎ing^_^
所以，最近下了几个比较好玩的2D游戏，在这里介绍给大家啊！！！
首先是，微软老大出的游戏
《尘埃幸福轨迹》
这是一款动作的游戏，画面很好很精美，并且人物都是森林里的小动物什么的，很萌的。动作也是华丽丽的，很酷很炫的游戏。
《雷曼：起源》
这是育碧公司出的一个冒险类的游戏，很多的关卡，很多种玩法，非常的刺激。喜欢冒险的同学，可以玩下啊！！！
《闪克2》
这个游戏怎么说了，让我很纠结，好玩是好玩，不过，哎不知道是技术原因，还是什么，至今才玩到第四关，太TMD难玩了。不过对于喜欢暴力美学的和挑战的大大，可以尝试下啊。
(注：以上所有图片，取材之网络)