上一篇文章介绍了填充四边形及三角形,那么对于五边形,六边形呢?当然也可以把五边形分解成3个三角形,六边形分解成4个三角形进行填充。推而广之,可以把n边形分解成n-2个三角形来进行填充。这里介绍另一个方法。如图所示。
这是更为一般化的填充(光栅化?)实心多边形方法。找到多边形各顶点中y轴坐标最小的点作为起始点,按顺时针设置各顶点标号,然后从逆时针方向和顺时针方向同时出发,当一条边到达一个终点(另一个顶点)时,重新计算插值,继续下去直到完成光栅化。代码清单如下:
- /* 2008/9/6
- 代码功能:光栅化
- 多边形的一般方法*/
- #define WIN32_LEAN_AND_MEAN //不使用MFC
- #define INITGUID //使用GUID
- #include <windows.h>
- #include <windowsx.h>
- #include <mmsystem.h> //多媒体API
- #include <iostream.h>
- #include <conio.h> //控制台IO支持
- #include <stdlib.h> //声明定义的一些常用标准函数库
- #include <malloc.h> //声明或定义一些内存的函数
- #include <memory.h> //提供了内存操作相关的一些函数及声明
- #include <string.h> //字符串的一些功能
- #include <stdarg.h> //defines ANSI-style macros for variable argument functions
- #include <stdio.h> //efinitions/declarations for standard I/O routines
- #include <math.h> //一些数学方法
- #include <io.h> //declarations for low-level file handling and I/O functions
- #include <fcntl.h> //file control options used by open()
- #include <ddraw.h>
- //windows类名
- #define WINDOW_CLASS_NAME "WINCLASS1"
- //宽,高,色深(像素)
- #define SCREEN_WIDTH 640
- #define SCREEN_HEIGHT 480
- #define SCREEN_BPP 8
- #define MAX_COLORS_PALETTE 256
- #define PI 3.1415926535
- typedef unsigned short USHORT;
- typedef unsigned short WORD;
- typedef unsigned char UCHAR;
- typedef unsigned char BYTE;
- typedef struct VERTEX2DF_TYP
- {
- float x,y;
- }VERTEX2DF,*VERTEX2DF_PTR;
- typedef struct POLYGON2D_TYP
- {
- int state;
- int num_vert;
- int x0,y0;
- int xv,yv;
- DWORD color;
- VERTEX2DF* vlist;
- }POLYGON2D,*POLYGON2D_PTR;
- //GDI文字函数
- int Draw_Text_GDI(char* text,int x,int y,int color,LPDIRECTDRAWSURFACE7 lpdds);
- //填充表面
- int DDraw_Fill_Surface(LPDIRECTDRAWSURFACE7 lpdds,int color);
- //旋转图形
- int Rotate_Polygon2D(POLYGON2D_PTR poly,int theta);
- //填充2D图形
- int Draw_Filled_Polygon2D(POLYGON2D_PTR poly,UCHAR* vbuffer,int mempitch);
- //设置调色板入口
- int Set_Palette_Entry(int color_index,LPPALETTEENTRY color);
- //键盘按键宏
- #define KEYDOWN(vk_code) ((GetAsyncKeyState(vk_code)&0x8000)?1:0)
- #define KEYUP(vk_code) ((GetAsyncKeyState(vk_code)&0x8000)?0:1)
- //初始化结构体
- #define DDRAW_INIT_STRUCT(ddstruct) { memset(&ddstruct,0,sizeof(ddstruct));ddstruct.dwSize=sizeof(ddstruct); }
- HWND main_window_handle =NULL;
- int window_closed =0;
- HINSTANCE hinstance_app =NULL;
- LPDIRECTDRAW7 lpdd =NULL;
- LPDIRECTDRAWSURFACE7 lpddsprimary =NULL; //主缓存
- LPDIRECTDRAWSURFACE7 lpddsback =NULL; //后备缓冲
- LPDIRECTDRAWPALETTE lpddpal =NULL; //调色板接口
- LPDIRECTDRAWCLIPPER lpddclipper =NULL; //裁剪器
- PALETTEENTRY palette[256]; //调色板
- DDSURFACEDESC2 ddsd;
- DDBLTFX ddbltfx;
- DDSCAPS2 ddscaps;
- /*裁剪区域*/
- int min_clip_x = 0,
- max_clip_x =SCREEN_WIDTH-1,
- min_clip_y = 0,
- max_clip_y = SCREEN_HEIGHT-1;
- char buffer[80];
- float cos_look[360],
- sin_look[360];
- POLYGON2D object;
- int Draw_Text_GDI(char* text,int x,int y,int color,LPDIRECTDRAWSURFACE7 lpdds)
- {
- HDC xdc;
- if(FAILED(lpdds->GetDC(&xdc)))
- return(0);
- SetTextColor(xdc,RGB(palette[color].peRed,palette[color].peGreen,palette[color].peBlue));
- SetBkMode(xdc,TRANSPARENT);
- TextOut(xdc,x,y,text,strlen(text));
- lpdds->ReleaseDC(xdc);
- return(1);
- }
- int DDraw_Fill_Surface(LPDIRECTDRAWSURFACE7 lpdds,int color)
- {
- DDRAW_INIT_STRUCT(ddbltfx);
- ddbltfx.dwFillColor=color;
- lpdds->Blt(NULL,
- NULL,
- NULL,
- DDBLT_COLORFILL|DDBLT_WAIT,
- &ddbltfx);
- return(1);
- }
- int Set_Palette_Entry(int color_index,LPPALETTEENTRY color)
- {
- lpddpal->SetEntries(0,color_index,1,color);
- memcpy(&palette[1],color,sizeof(PALETTEENTRY));
- return(1);
- }
- int Rotate_Polygon2D(POLYGON2D_PTR poly, int theta)
- {
- // this function rotates the local coordinates of the polygon
- // test for valid pointer
- if (!poly)
- return(0);
- // loop and rotate each point, very crude, no lookup!!!
- for (int curr_vert = 0; curr_vert < poly->num_vert; curr_vert++)
- {
- // perform rotation
- float xr = (float)poly->vlist[curr_vert].x*cos_look[theta] -
- (float)poly->vlist[curr_vert].y*sin_look[theta];
- float yr = (float)poly->vlist[curr_vert].x*sin_look[theta] +
- (float)poly->vlist[curr_vert].y*cos_look[theta];
- // store result back
- poly->vlist[curr_vert].x = xr;
- poly->vlist[curr_vert].y = yr;
- } // end for curr_vert
- // return success
- return(1);
- } // end Rotate_Polygon2D
- int Draw_Filled_Polygon2D(POLYGON2D_PTR poly,UCHAR *vbuffer,int mempitch)
- {
- int ydiff1,ydiff2,
- xdiff1,xdiff2,
- start,
- length,
- errorterm1,errorterm2,
- offset1,offset2,
- count1,count2,
- xunit1,xunit2;
- int edgecount = poly->num_vert-1;
- int firstvert=0;
- int min_y=poly->vlist[0].y;
- for (int index=1;index<poly->num_vert;index++)
- {/*找到y轴坐标最小的顶点*/
- if ((poly->vlist[index].y)<min_y)
- {
- firstvert=index;
- min_y=poly->vlist[index].y;
- }
- }
- int startvert1=firstvert;
- int startvert2=firstvert;
- int xstart1=poly->vlist[startvert1].x+poly->x0; //逆时针移动的初始位置
- int ystart1=poly->vlist[startvert1].y+poly->y0;
- int xstart2=poly->vlist[startvert2].x+poly->x0; //顺时针移动的初始位置
- int ystart2=poly->vlist[startvert2].y+poly->y0;
- /*取得逆时针移动遇到的第1个顶点坐标*/
- int endvert1=startvert1-1;
- if (endvert1<0)
- endvert1=poly->num_vert-1;
- int xend1=poly->vlist[endvert1].x+poly->x0;
- int yend1=poly->vlist[endvert1].y+poly->y0;
- /*取得顺时针移动遇到的第1个顶点坐标*/
- int endvert2=startvert2+1;
- if(endvert2==(poly->num_vert))
- endvert2=0;
- int xend2=poly->vlist[endvert2].x+poly->x0;
- int yend2=poly->vlist[endvert2].y+poly->y0;
- //绘制并填充多边形
- while (edgecount>0)
- {
- offset1=mempitch*ystart1+xstart1; //左边缘偏移量
- offset2=mempitch*ystart2+xstart2; //右边缘偏移量
- //初始化误差额
- errorterm1=0;
- errorterm2=0;
- //初始化左边与右边x&y方向的偏移差
- if ((ydiff1=yend1-ystart1)<0)
- ydiff1=-ydiff1;
- if ((ydiff2=yend2-ystart2)<0)
- ydiff2=-ydiff2;
- if ((xdiff1=xend1-xstart1)<0)
- {
- xunit1=-1;
- xdiff1=-xdiff1;
- }
- else
- {
- xunit1=1;
- }
- if ((xdiff2=xend2-xstart2)<0)
- {
- xunit2=-1;
- xdiff2=-xdiff2;
- }
- else
- {
- xunit2=1;
- }
- //选择使用哪种情况
- if (xdiff1>ydiff1)
- {/*|k1|<1*/
- if (xdiff2>ydiff2)
- {/*|k2|<1*/
- count1=xdiff1; //左边X的增量
- count2=xdiff2; //右边X的增量
- while (count1&&count2)
- {
- while ((errorterm1<xdiff1)&&(count1>0))
- {
- if(count1--)
- {
- offset1+=xunit1;
- xstart1+=xunit1;
- }
- errorterm1+=ydiff1;
- if (errorterm1<xdiff1)
- {
- vbuffer[offset1]=(UCHAR)poly->color;
- }
- }
- errorterm1-=xdiff1;
- while ((errorterm2<xdiff2)&&(count2>0))
- {
- if (count2--)
- {
- offset2+=xunit2;
- xstart2+=xunit2;
- }
- errorterm2+=ydiff2;
- if (errorterm2<xdiff2)
- {
- vbuffer[offset2]=(UCHAR)poly->color;
- }
- }
- errorterm2-=xdiff2;
- length=offset2-offset1;
- if (length<0)
- {
- length=-length;
- start=offset2;
- }
- else
- start=offset1;
- for (int index=start;index<start+length+1;index++)
- {
- vbuffer[index]=(UCHAR)poly->color;
- }
- offset1+=mempitch;
- ystart1++;
- offset2+=mempitch;
- ystart2++;
- }
- }
- else
- {/*|k2|>1*/
- count1=xdiff1;
- count2=ydiff2;
- while (count1&&count2)
- {
- while ((errorterm1<xdiff1)&&(count1>0))
- {
- if(count1--)
- {
- offset1+=xunit1;
- xstart1+=xunit1;
- }
- errorterm1+=ydiff1;
- if (errorterm1<xdiff1)
- {
- vbuffer[offset1]=(UCHAR)poly->color;
- }
- }
- errorterm1-=xdiff1;
- errorterm2+=xdiff2;
- if (errorterm2>=ydiff2)
- {
- errorterm2-=ydiff2;
- offset2+=xunit2;
- xstart2+=xunit2;
- }
- count2--;
- length=offset2-offset1;
- if (length<0)
- {
- length=-length;
- start=offset2;
- }
- else
- start=offset1;
- for (int index=start;index<start+length+1;index++)
- {
- vbuffer[index]=(UCHAR)poly->color;
- }
- offset1+=mempitch;
- ystart1++;
- offset2+=mempitch;
- ystart2++;
- }
- }
- }
- else
- {/*|k1|>1*/
- if (xdiff2>ydiff2)
- {/*|k2|<1*/
- count1=ydiff1;
- count2=xdiff2;
- while (count1&&count2)
- {
- errorterm1+=xdiff1;
- if (errorterm1>=ydiff1)
- {
- errorterm1-=ydiff1;
- offset1+=xunit1;
- xstart1+=xunit1;
- }
- count1--;
- while ((errorterm2<xdiff2)&&(count2>0))
- {
- if (count2--)
- {
- offset2+=xunit2;
- xstart2+=xunit2;
- }
- errorterm2+=ydiff2;
- if (errorterm2<xdiff2)
- {
- vbuffer[offset2]=(UCHAR)poly->color;
- }
- }
- errorterm2-=xdiff2;
- length=offset2-offset1;
- if (length<0)
- {
- length=-length;
- start=offset2;
- }
- else
- start=offset1;
- for (int index=start;index<start+length+1;index++)
- {
- vbuffer[index]=(UCHAR)poly->color;
- }
- offset1+=mempitch;
- ystart1++;
- offset2+=mempitch;
- ystart2++;
- }
- }
- else
- {/*|k2|>1*/
- count1=ydiff1;
- count2=ydiff2;
- while (count1&&count2)
- {
- errorterm1+=xdiff1;
- if (errorterm1>=ydiff1)
- {
- errorterm1-=ydiff1;
- offset1+=xunit1;
- xstart1+=xunit1;
- }
- count1--;
- errorterm2+=xdiff2;
- if (errorterm2>=ydiff2)
- {
- errorterm2-=ydiff2;
- offset2+=xunit2;
- xstart2+=xunit2;
- }
- count2--;
- length=offset2-offset1;
- if (length<0)
- {
- length=-length;
- start=offset2;
- }
- else
- start=offset1;
- for (int index=start;index<start+length+1;index++)
- {
- vbuffer[index]=(UCHAR)poly->color;
- }
- offset1+=mempitch;
- ystart1++;
- offset2+=mempitch;
- ystart2++;
- }
- }
- }
- if (!count1)
- {/*首先到达逆时针顶点*/
- --edgecount;
- startvert1=endvert1;
- --endvert1;
- if (endvert1<0)
- endvert1=poly->num_vert-1;
- xend1=poly->vlist[endvert1].x+poly->x0;
- yend1=poly->vlist[endvert1].y+poly->y0;
- }
- if (!count2)
- {/*首先到达顺时针顶点*/
- --edgecount;
- startvert2=endvert2;
- ++endvert2;
- if(endvert2==(poly->num_vert))
- endvert2=0;
- xend2=poly->vlist[endvert2].x+poly->x0;
- yend2=poly->vlist[endvert2].y+poly->y0;
- }
- }
- return(1);
- }
- LRESULT CALLBACK WindowProc(HWND hwnd,
- UINT msg,
- WPARAM wparam,
- LPARAM lparam)
- {
- PAINTSTRUCT ps;
- HDC hdc;
- switch(msg)
- {
- case WM_CREATE:
- {
- return(0);
- } break;
- case WM_PAINT:
- {
- hdc = BeginPaint(hwnd,&ps);
- EndPaint(hwnd,&ps);
- return(0);
- } break;
- case WM_DESTROY:
- {
- PostQuitMessage(0);
- return(0);
- } break;
- default:break;
- }
- return (DefWindowProc(hwnd, msg, wparam, lparam));
- }
- int Game_Init(void *parms=NULL,int num_parms=0)
- {
- if(FAILED(DirectDrawCreateEx(NULL,(void **)&lpdd,IID_IDirectDraw7,NULL)))
- return(0);
- if(FAILED(lpdd->SetCooperativeLevel(main_window_handle,
- DDSCL_FULLSCREEN|DDSCL_ALLOWMODEX|
- DDSCL_EXCLUSIVE|DDSCL_ALLOWREBOOT)))
- return(0);
- if(FAILED(lpdd->SetDisplayMode(SCREEN_WIDTH,SCREEN_HEIGHT,SCREEN_BPP,0,0)))
- return(0);
- DDRAW_INIT_STRUCT(ddsd);
- ddsd.dwFlags=DDSD_CAPS | DDSD_BACKBUFFERCOUNT;
- ddsd.dwBackBufferCount=1;
- ddsd.ddsCaps.dwCaps=DDSCAPS_PRIMARYSURFACE|DDSCAPS_COMPLEX|
- DDSCAPS_FLIP;
- if(FAILED(lpdd->CreateSurface(&ddsd,&lpddsprimary,NULL)))
- return(0);
- ddsd.ddsCaps.dwCaps=DDSCAPS_BACKBUFFER;
- if(FAILED(lpddsprimary->GetAttachedSurface(&ddsd.ddsCaps,&lpddsback)))
- return(0);
- for (int color=1; color < 255; color++)
- {
- palette[color].peRed = rand()%256;
- palette[color].peGreen = rand()%256;
- palette[color].peBlue = rand()%256;
- palette[color].peFlags = PC_NOCOLLAPSE;
- }
- palette[0].peRed = 0;
- palette[0].peGreen = 0;
- palette[0].peBlue = 0;
- palette[0].peFlags = PC_NOCOLLAPSE;
- palette[255].peRed = 255;
- palette[255].peGreen = 255;
- palette[255].peBlue = 255;
- palette[255].peFlags = PC_NOCOLLAPSE;
- palette[1].peRed = 0;
- palette[1].peGreen = 16;
- palette[1].peBlue = 0;
- palette[1].peFlags = PC_NOCOLLAPSE;
- if(FAILED(lpdd->CreatePalette(DDPCAPS_8BIT|DDPCAPS_ALLOW256|
- DDPCAPS_INITIALIZE,palette,&lpddpal,NULL)))
- return(0);
- if(FAILED(lpddsprimary->SetPalette(lpddpal)))
- return(0);
- DDraw_Fill_Surface(lpddsprimary,0);
- DDraw_Fill_Surface(lpddsback,0);
- //顺时针画出各点!!!
- VERTEX2DF object_vertices[4]={-100,-100,100,-100,100,100,-100,100};
- object.state=1;
- object.num_vert=4;
- object.color=1;
- object.xv=0;
- object.yv=0;
- object.x0=SCREEN_WIDTH/2;
- object.y0=SCREEN_HEIGHT/2;
- object.vlist=new VERTEX2DF[object.num_vert];
- for (int index=0;index<object.num_vert;index++)
- object.vlist[index]=object_vertices[index];
- for (int ang=0;ang<360;ang++)
- {
- float theta=(float)ang*PI/(float)180;
- cos_look[ang]=cos(theta);
- sin_look[ang]=sin(theta);
- }
- return(1);
- }
- int Game_Main(void *parms = NULL, int num_parms = 0)
- {
- static int green_inc=4;
- if(window_closed)
- return(0);
- if(KEYDOWN(VK_ESCAPE))
- {
- PostMessage(main_window_handle,WM_CLOSE,0,0);
- window_closed=1;
- }
- DDraw_Fill_Surface(lpddsback,0);
- DDRAW_INIT_STRUCT(ddsd);
- if(FAILED(lpddsback->Lock(NULL,&ddsd,DDLOCK_WAIT|DDLOCK_SURFACEMEMORYPTR,NULL)))
- return(0);
- Draw_Filled_Polygon2D(object, (UCHAR *)ddsd.lpSurface, ddsd.lPitch);
- Rotate_Polygon2D(object,5);
- if (FAILED(lpddsback->Unlock(NULL)))
- return(0);
- Set_Palette_Entry(1, &palette[1]);
- palette[1].peGreen+=green_inc;
- if (palette[1].peGreen > 255 || palette[1].peGreen < 16)
- {
- green_inc=-green_inc;
- palette[1].peGreen+=green_inc;
- }
- while(FAILED(lpddsprimary->Flip(NULL,DDFLIP_WAIT)));
- Sleep(33);
- return(1);
- }
- int Game_Shutdown(void *parms = NULL, int num_parms = 0)
- {/*清除资源*/
- if (lpddpal)
- {
- lpddpal->Release();
- lpddpal = NULL;
- }
- if(lpddsback)
- {
- lpddsback->Release();
- lpddsback=NULL;
- }
- if (lpddsprimary)
- {
- lpddsprimary->Release();
- lpddsprimary = NULL;
- }
- if (lpdd)
- {
- lpdd->Release();
- lpdd = NULL;
- }
- return(1);
- }
- int WINAPI WinMain( HINSTANCE hinstance,
- HINSTANCE hprevinstance,
- LPSTR lpcmdline,
- int ncmdshow)
- {
- WNDCLASSEX winclass;
- HWND hwnd;
- MSG msg;
- //HDC hdc;
- 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);
- hinstance_app = hinstance;
- if (!RegisterClassEx(&winclass))
- return(0);
- if (!(hwnd = CreateWindowEx(NULL,
- WINDOW_CLASS_NAME,
- "DirectDraw 8-Bit Line Drawing Demo",
- WS_POPUP | WS_VISIBLE,
- 0,0,
- SCREEN_WIDTH,SCREEN_HEIGHT,
- NULL,
- NULL,
- hinstance,
- NULL)))
- return(0);
- main_window_handle = hwnd;
- Game_Init();
- while(TRUE)
- {
- if (PeekMessage(&msg,NULL,0,0,PM_REMOVE))
- {
- if (msg.message == WM_QUIT)
- break;
- TranslateMessage(&msg);
- DispatchMessage(&msg);
- }
- Game_Main();
- }
- Game_Shutdown();
- return(msg.wParam);
- }
一定要注意调用光栅化函数时传入的参数为顺时针在笛卡尔坐标系中设置的各多边形坐标!!!