扫描线填充算法

1、任意封闭多边形的扫描线填充算法类 收藏 这个代码不是我写的，但是我肯定这代码是一个牛人写的，放在这里供大家学习和使用啦！感谢原作者！ 我在这里做了些改进： 1 去除了绘制多边形的函数，使其成为了一个纯的填充算法模块 2 改进了其成员变量，使其更容易让大多数人所使用 3 改进了填充，使其“看”（代码上）起来更像用扫描线在填充 改进后的扫描线算法类如下： /扫描线填充算法类 class CPFill public: CPoint *Point; /指向点坐标的指针 int Count; /多边形点的个数 public: CPFill(int,int,int);/构造函数 bool FillPoly

2、gon(CDC*);/填充多边形 bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);/判断两条线段是否相交 int GetAi(int);/获取下一个点的索引号 int GetBi(int);/获取前一个点的索引号 bool Sort(int*,int);/冒泡排序 CPFill();/析构函数 ; /构造函数 （模块入口，koradji 注，合理的设计这个地方，就可以完全不用改动其他的地方就可以使用这个类） CPFill:CPFill() /获取前一个点的索引号 int CPFill:GetBi(int i) return (i=0)?

3、 Count-1:i-1; /获取下一个点的索引号 int CPFill:GetAi(int i) return (i=Count-1)?0:i+1; /在指定的pDC设备中，填充多边形 bool CPFill:FillPolygon(CDC* pDC) /获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围 int minX=Point0.x , minY=Point0.y; int maxX=Point0.x , maxY=Point0.y; for(int i=1;iPointi.x) minX=Pointi.x; if(minYPointi.y) minY=Pointi.y;

4、if(maxXPointi.x) maxX=Pointi.x; if(maxYPointi.y) maxY=Pointi.y; CUIntArray xArray; int y; for(y=minY;ymaxY;y+) /扫描线从minY开始到maxY for(i=0;iPointCross.y)&(PointAi.yPointCross.y) /边顶点的y值大于交点的y值，x坐标取两次 xArray.Add(PointCross.x); xArray.Add(PointCross.x); else /边顶点的y值在交点的y值之间，即一个顶点的y值大于交点的y值，而另一个小于，相应的x坐标取

5、一次 if(PointBi.y-PointCross.y)*(PointAi.y-PointCross.y)0) xArray.Add(PointCross.x); else if(PointCross.y=PointAi.y) xArray.Add(PointCross.x); else if(PointCross=PointBi) continue; else xArray.Add(PointCross.x);/当交点不在线段的顶点时，x坐标只取一次 int *scanLineX,num=xArray.GetSize(); scanLineX=new intnum; for(i=0;inu

6、m;i+) scanLineXi=xArray.GetAt(i);/获取扫描线x值，以构成填充区间 xArray.RemoveAll(); Sort(scanLineX,num);/对scanLine（扫描线x坐标进行排序） for(i=0;i=num) break; pDC-MoveTo(scanLineXi,y);pDC-LineTo(scanLineXi+1,y);/填充（Koradji改进） Sleep(1);/CPU暂停1ms，以体现出多边形是以扫描线的方式，一条一条的填充的 delete scanLineX; return true; /判断两条线段是否相交 bool CPFill

7、:CrossJudge(CPoint L1P1,CPoint L1P2,CPoint L2P1,CPoint L2P2,CPoint& coordinate) /L1P1、L1P2是一条线段的顶点坐标，而L2P1、L2P2是另一条线段的顶点坐标 if(L1P1=L1P2) return false;/若L1P1、L1P2相等，则构不成线段，退出 if(L2P1=L2P2) return false;/若L2P1、L2P2等，则构不成线段，退出 if(L1P1.y-L1P2.y)*(L2P1.x-L2P2.x)=(L2P1.y-L2P2.y)*(L1P1.x-L1P2.x)/对斜率相等的情况下的

8、处理 if(L1P1.y-L1P2.y)*(L2P1.x-L1P1.x)=(L1P1.x-L1P2.x)*(L2P1.y-L1P1.y)/判断两条线段是不是同一条线段 coordinate=L1P2; return true; else return false; if(L1P1.x=L1P2.x)/当第一条线段斜率不存在时的 double x,y; x=L1P1.x; y=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x)*(L1P1.x-L2P1.x)+L2P1.y; y=(float)(int)(y+0.5); if(L1P1.y-y)*(y-L1P2.y)=0)&(

9、L1P1.x-x)*(x-L1P2.x)=0)/判断交点是不是在该两条线段上 coordinate.x=L1P1.x; coordinate.y=(int)(y+0.5); return true; return false; else if(L2P1.x=L2P2.x)/当第二条线段斜率不存在时 double x,y; x=L2P1.x; y=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x)*(L2P1.x-L1P1.x)+L1P1.y; y=(float)(int)(y+0.5); if(L1P1.y-y)*(y-L1P2.y)=0) & (L1P1.x-x)*(x-

10、L1P2.x)=0)/判断交点是不是在该两条线段上 coordinate.x=L2P1.x; coordinate.y=(int)(y+0.5); return true; return false; else/两条线段斜率都存在时 double k1,k2; k1=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x); k2=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x); /k1,k2为计算的两线段的斜率 double x,y; x=(L2P1.y-L1P1.y-k2*L2P1.x+k1*L1P1.x)/(k1-k2); y=(k1*k2*L2P1

11、.x-k1*k2*L1P1.x+k2*L1P1.y-k1*L2P1.y)/(k2-k1); x=(float)(int)(x+0.5); y=(float)(int)(y+0.5); if(L1P1.y-y)*(y-L1P2.y)=0)&(L1P1.x-x)*(x-L1P2.x)=0)/判断交点是不是在该两条线段上 coordinate.x=(int)(x+0.5); coordinate.y=(int)(y+0.5); return true; return false; return true; /冒泡排序 bool CPFill:Sort(int* iArray,int iLength)

12、 int i,j,iTemp; bool bFlag; for(i=0;iiLength;i+) bFlag=true; for(j=0;j iArrayj+1) iTemp=iArrayj; iArrayj=iArrayj+1; iArrayj+1=iTemp; bFlag=false; if(bFlag) break; return true; /析构函数,删除动态生成的Point指针 CPFill:CPFill() if(Point) delete Point; 下面说说怎么为我所用这个类。 在MFC中，若多边形控制定点的变量是：CPoint *P，记录下标的变量为int 。index

13、则构造函数则变为 CPFill:CPFill(int index,CPoint *P) Point=new CPointindex-1; Count=index-1; for(int i=0;iCount;i+) Pointi=Pi; 如果多边形控制定点的变量是：int pxMAX int pyMAX，记录下标的变量为int index。 则构造函数是： CPFill:CPFill(int index,int px,int py) Point=new CPointindex-1; Count=index-1; for(int i=0;i2); ASSERT(nColor=0); / 边结构数据

14、类型 typedef struct Edge int ymax; / 边的最大y坐标 float x; / 与当前扫描线的交点x坐标 float dx; / 边所在直线斜率的倒数 struct Edge * pNext; / 指向下一条边 Edge, * LPEdge; int i=0,j=0,k=0; int y0=0,y1=0; / 扫描线的最大和最小 y坐标 LPEdge pAET=NULL; / 活化边表头指针 LPEdge * pET=NULL; / 边表头指针 pAET=new Edge; / 初始化表头指针，第一个元素不用 pAET-pNext=NULL; 方向扫描线边界y获取/

15、 y0=y1=lpPoints0.y; for(i=1;inCount;i+) if(lpPointsi.yy1) y1=lpPointsi.y; if(y0=y1) return; / 初始化边表，第一个元素不用 pET=new LPEdgey1-y0+1; for(i=0;ipNext=NULL; for(i=0;ilpPointsj.y)?i:j; peg-ymax=lpPointsk.y; / 该边最大y坐标 k=(k=j)?i:j; peg-x=(float)lpPointsk.x; / 该边与扫描线焦点x坐标 if(lpPointsi.y != lpPointsj.y) peg-d

16、x=(float)(lpPointsi.x-lpPointsj.x)/(lpPointsi.y-lpPointsj.y);/ 该边斜率的倒数 peg-pNext=NULL; / 插入边 ppeg=pETlpPointsk.y-y0; while(ppeg-pNext) ppeg=ppeg-pNext; ppeg-pNext=peg; / end if / end for i / 扫描 for(i=y0;ipNext; LPEdge peg1=pETi-y0; if(peg0)/ 有新边加入 while(peg1-pNext) peg1=peg1-pNext; peg1-pNext=pAET-p

17、Next; pAET-pNext=peg0; / 按照x递增排序pAET peg0=pAET; while(peg0-pNext) LPEdge pegmax=peg0; LPEdge peg1=peg0; LPEdge pegi=NULL; while(peg1-pNext) if(peg1-pNext-xpegmax-pNext-x) pegmax=peg1; peg1=peg1-pNext; pegi=pegmax-pNext; pegmax-pNext=pegi-pNext; pegi-pNext=pAET-pNext; pAET-pNext=pegi; if(peg0 = pAET)

18、 peg0=pegi; / 遍历活边表，画线 peg0=pAET; while(peg0-pNext) if(peg0-pNext-pNext) DrawLine(int)peg0-pNext-x,i,(int)peg0-pNext-pNext-x,i,pD C,nColor); peg0=peg0-pNext-pNext; else break; / 把ymax=i的节点从活边表删除并把每个节点的x值递增dx peg0=pAET; while(peg0-pNext) if(peg0-pNext-ymax pNext; peg0-pNext=peg0-pNext-pNext; / 删除 del

19、ete peg1; continue; peg0-pNext-x+=peg0-pNext-dx; /把每个节点的 x值递增dx peg0=peg0-pNext; / 删除边表 for(i=0;i New中建立项目，基于单文档，View类基于Cview 添加库：在project-Setting中指定库 初始化：选择View-Class Wizard,打开MFC对话框，添加相应的定义 添加类成员说明 基于OpenGL的程序框架已经构造好，以后用户只需要在对应的函数中添加程序代码即可。 下面介绍如何在 VC+ 上进行 OpenGL 编程。 OpenGL 绘图的一般过程可以看作这样的,先用 OpenG

20、L 语句在 OpenGL 的绘图环境 RenderContext (RC)中画好图, 然后再通过一个 Swap buffer 的过程把图传给操作系统的绘图环境 DeviceContext (DC)中,实实在在地画出到屏幕上. 下面以画一条 Bezier 曲线为例，详细介绍VC+ 上 OpenGL编程的方法。文中给出了详细注释，以便给初学者明确的指引。一步一步地按所述去做，你将顺利地画出第一个 OpenGL 平台上的图形来。 一、产生程序框架 Test.dsw New Project | MFC Application Wizard (EXE) | Test | OK *注* : 加“”者指要手

21、工敲入的字串 二、导入 Bezier 曲线类的文件 用下面方法产生 BezierCurve.h BezierCurve.cpp 两个文件： WorkSpace | ClassView | Test Classes| New Class | Generic Class(不用MFC类) | CBezierCurve | OK 三、编辑好 Bezier 曲线类的定义与实现 写好下面两个文件： BezierCurve.h BezierCurve.cpp 四、设置编译环境： 1. 在 BezierCurve.h 和 TestView.h 内各加上： #include #include #include

22、2. 在集成环境中 Project | Settings | Link | Object/library module | opengl32.lib glu32.lib glaux.lib | OK 五、设置 OpenGL 工作环境：(下面各个操作，均针对 TestView.cpp ) 绘图窗口的风格OpenGL 设置PreCreateWindow(): 处理1. cs.style |= WS_CLIPSIBLINGS | WS_CLIPCHILDREN | CS_OWNDC; 2. 处理 OnCreate():创建 OpenGL 的绘图设备。 OpenGL 绘图的机制是: 先用 OpenGL

23、 的绘图上下文 Rendering Context (简称为 RC )把图画好，再把所绘结果通过 SwapBuffer() 函数传给 Window 的 绘图上下文 Device Context (简记为 DC).要注意的是，程序运行过程中，可以有多个 DC，但只能有一个 RC。因此当一个 DC 画完图后，要立即释放 RC，以便其它的 DC 也使用。在后面的代码中，将有详细注释。 int CTestView:OnCreate(LPCREATESTRUCT lpCreateStruct) if (CView:OnCreate(lpCreateStruct) = -1) return -1; myI

24、nitOpenGL(); return 0; void CTestView:myInitOpenGL() m_pDC = new CClientDC(this); /创建 DC ASSERT(m_pDC != NULL); if (!mySetupPixelFormat() /设定绘图的位图格式，函数下面列出 return; m_hRC = wglCreateContext(m_pDC-m_hDC);/创建 RC wglMakeCurrent(m_pDC-m_hDC, m_hRC); /RC 与当前 DC 相关联 /CClient * m_pDC; HGLRC m_hRC; 是 CTestVi

25、ew 的成员变量 BOOL CTestView:mySetupPixelFormat() /我们暂时不管格式的具体内容是什么,以后熟悉了再改变格式 static PIXELFORMATDESCRIPTOR pfd = sizeof(PIXELFORMATDESCRIPTOR), / size of this pfd 1, / version number PFD_DRAW_TO_WINDOW | / support window PFD_SUPPORT_OPENGL | / support OpenGL PFD_DOUBLEBUFFER, / double buffered PFD_TYPE_

26、RGBA, / RGBA type 24, / 24-bit color depth 0, 0, 0, 0, 0, 0, / color bits ignored 0, / no alpha buffer 0, / shift bit ignored buffer accumulation no / 0, 0, 0, 0, 0, / accum bits ignored 32, / 32-bit z-buffer 0, / no stencil buffer 0, / no auxiliary buffer PFD_MAIN_PLANE, / main layer 0, / reserved

27、0, 0, 0 / layer masks ignored ; int pixelformat; if ( (pixelformat = ChoosePixelFormat(m_pDC-m_hDC, &pfd) = 0 ) MessageBox(ChoosePixelFormat failed); return FALSE; if (SetPixelFormat(m_pDC-m_hDC, pixelformat, &pfd) = FALSE) MessageBox(SetPixelFormat failed); return FALSE; return TRUE; 3. 处理 OnDestro

28、y() void CTestView:OnDestroy() wglMakeCurrent(m_pDC-m_hDC,NULL); /释放与m_hDC 对应的 RC wglDeleteContext(m_hRC); /删除 RC if (m_pDC) delete m_pDC; /删除当前 View 拥有的 DC CView:OnDestroy(); 4. 处理 OnEraseBkgnd() BOOL CTestView:OnEraseBkgnd(CDC* pDC) / TODO: Add your message handler code here and/or call default /

29、return CView:OnEraseBkgnd(pDC); /把这句话注释掉，若不然，Window /会用白色北景来刷新，导致画面闪烁 只要空返回即可。TRUE;/return 5. 处理 OnDraw() void CTestView:OnDraw(CDC* pDC) wglMakeCurrent(m_pDC-m_hDC,m_hRC);/使 RC 与当前 DC 相关联 myDrawScene( ); /具体的绘图函数，在 RC 中绘制 SwapBuffers(m_pDC-m_hDC);/把 RC 中所绘传到当前的 DC 上，从而 /在屏幕上显示 wglMakeCurrent(m_pDC-

30、m_hDC,NULL);/释放 RC，以便其它 DC 进行绘图 void CTestView:myDrawScene( ) glClearColor(0.0f,0.0f,0.0f,1.0f);/设置背景颜色为黑色 glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT); glPushMatrix(); glTranslated(0.0f,0.0f,-3.0f);/把物体沿(0,0,-1)方向平移 /以便投影时可见。因为缺省的视点在(0,0,0),只有移开 /物体才能可见。 /本例是为了演示平面 Bezier 曲线的，只要作一个旋转 /变换，可更清楚的看

31、到其 3D 效果。 /下面画一条 Bezier 曲线 bezier_curve.myPolygon();/画Bezier曲线的控制多边形 bezier_curve.myDraw(); /CBezierCurve bezier_curve /是 CTestView 的成员变量 /具体的函数见附录 glPopMatrix(); glFlush(); /结束 RC 绘图 return; 6. 处理 OnSize() void CTestView:OnSize(UINT nType, int cx, int cy) CView:OnSize(nType, cx, cy); VERIFY(wglMake

32、Current(m_pDC-m_hDC,m_hRC);/确认RC与当前DC关联 w=cx; h=cy; RC 释放DC确认VERIFY(wglMakeCurrent(NULL,NULL);/ 7 处理 OnLButtonDown() void CTestView:OnLButtonDown(UINT nFlags, CPoint point) CView:OnLButtonDown(nFlags, point); if(bezier_curve.m_NMAX-1) 敍獳条?硯尨顶点个数超过了最大数MAX=50); return; /以下为坐标变换作准备 GetClientRect(&m_Cli

33、entRect);/获取视口区域大小 w=m_ClientRect.right-m_ClientRect.left;/视口宽度 w h=m_ClientRect.bottom-m_ClientRect.top;/视口高度 h /w,h 是CTestView的成员变量 centerx=(m_ClientRect.left+m_ClientRect.right)/2;/中心位置， centery=(m_ClientRect.top+m_ClientRect.bottom)/2;/取之作原点 /centerx,centery 是 CTestView 的成员变量 GLdouble tmpx,tmpy;

34、 tmpx=scrx2glx(point.x);/屏幕上点坐标转化为OpenGL画图的规范坐标 tmpy=scry2gly(point.y); bezier_curve.m_Vertexbezier_curve.m_N.x=tmpx;/加一个顶点 bezier_curve.m_Vertexbezier_curve.m_N.y=tmpy; bezier_curve.m_N+;/顶点数加一 InvalidateRect(NULL,TRUE);/发送刷新重绘消息 double CTestView:scrx2glx(int scrx) return (double)(scrx-centerx)/dou

35、ble(h); double CTestView:scry2gly(int scry) 附录： 1.CBezierCurve 的声明: (BezierCurve.h) class CBezierCurve public: myPOINT2D m_VertexMAX;/控制顶点，以数组存储 /myPOINT2D 是一个存二维点的结构 /成员为Gldouble x,y int m_N; /控制顶点的个数 public: CBezierCurve(); virtual CBezierCurve(); void bezier_generation(myPOINT2D PMAX,int level);

36、/算法的具体实现 void myDraw();/画曲线函数 void myPolygon(); /画控制多边形 ; 2. CBezierCurve 的实现: (BezierCurve.cpp) CBezierCurve:CBezierCurve() m_N=4; m_Vertex0.x=-0.5f; m_Vertex0.y=-0.5f; m_Vertex1.x=-0.5f; m_Vertex1.y=0.5f; m_Vertex2.x=0.5f; m_Vertex2.y=0.5f; m_Vertex3.x=0.5f; m_Vertex3.y=-0.5f; CBezierCurve:CBezier

37、Curve() void CBezierCurve:myDraw() bezier_generation(m_Vertex,LEVEL); void CBezierCurve:bezier_generation(myPOINT2D PMAX, int level) /算法的具体描述，请参考相关书本 int i,j; level-; if(level0)return; if(level=0) glColor3f(1.0f,1.0f,1.0f); glBegin(GL_LINES); /画出线段 glVertex2d(P0.x,P0.y); glVertex2d(Pm_N-1.x,Pm_N-1.y

38、); glEnd();/结束画线段 return; /递归到了最底层，跳出递归 myPOINT2D QMAX,RMAX; for(i=0;i Q.x=P.x; Q.y=P.y; for(i=1;i=i;j-) Qj.x=(Qj-1.x+Qj.x)/double(2); Qj.y=(Qj-1.y+Qj.y)/double(2); R0.x=Qm_N-1.x; R0.y=Qm_N-1.y; bezier_generation(Q,level); bezier_generation(R,level); void CBezierCurve:myPolygon() 画出连线段 glBegin(GL_LI

39、NE_STRIP); / glColor3f(0.2f,0.4f,0.4f); for(int i=0;im_N;i+) glVertex2d(m_Vertex.x,m_Vertex.y); 结束画连线段 glEnd();/ OpenGL开发库的组成 开发基于OpenGL的应用程序，必须先了解OpenGL的库函数。它采用C语言风格，提供大量的函数来进行图形的处理和显示。OpenGL库函数的命名方式非常有规律。所有OpenGL函数采用了以下格式 库前缀有gl、glu、aux、glut、wgl、glx、agl等等，分别表示该函数属于OpenGL那个开发库等，从函数名后面中还可以看出需要多少个参数以

40、及参数的类型。I代表int型，f代表float型，d代表double型，u代表无符号整型。例如glVertex3fv()表示了该函数属于gl库，参数是三个float型参数指针。我们用glVertex*()来表示这一类函数。 OpenGL函数库相关的API有核心库(gl)、实用库(glu)、辅助库(aux)、实用工具库(glut)、窗口库(glx、agl、wgl)和扩展函数库等。从图1可以看出，gl是核心，glu是对gl的部分封装。glx、agl、wgl 是针对不同窗口系统的函数。glut是为跨平台的OpenGL程序的工具包，比aux功能强大。扩展函数库是硬件厂商为实现硬件更新利用OpenGL的

41、扩展机制开发的函数。下面逐一对这些库进行详细介绍。 1 OpenGL核心库 核心库包含有115个函数，函数名的前缀为gl。 这部分函数用于常规的、核心的图形处理。此函数由gl.dll来负责解释执行。由于许多函数可以接收不同数以下几类。据类型的参数，因此派生出来的函数原形多达300多个。核心库中的函数主要可以分为以下几类函数。 绘制基本几何图元的函数。如绘制图元的函数glBegain()、glEnd()、glNormal*()、glVertex*()。 矩阵操作、几何变换和投影变换的函数。如矩阵入栈函数glPushMatrix()、矩阵出栈 函数glPopMatrix()、装载矩阵函数glLoa

42、dMatrix()、矩阵相乘函数glMultMatrix()，当前矩阵函数glMatrixMode()和矩阵标准化函数glLoadIdentity()，几何变换函数glTranslate*()、glRotate*()和glScale*()，投影变换函数glOrtho()、glFrustum()和视口变换函数glViewport()等等。 颜色、光照和材质的函数。如设置颜色模式函数glColor*()、glIndex*()，设置光照效果的函数glLight*() 、glLightModel*()和设置材质效果函数glMaterial()等等。 显示列表函数、主要有创建、结束、生成、删除和调用显示列表的函数glNewList()、 glEndList()、glGenLists()、glCallList()和glDeleteLists()。 纹理映射函数，主要有一维纹理函数glTexImage1D()、二维纹理函数glTexImage2D()、 设置纹理参数、纹理环境和纹理坐标的函数glTexParameter*()、glTexEnv*()和glTetCoord*()等。 特殊效果函数。融合函数glBlendFunc()、反走样函数glHint()和雾化效果glFog*()。 光栅化、象素操作函数。如象素位置glRasterPos*()