Zdfgg
范文一：有效边表填充算法
实验二 有效边表填充算法
实验题目： 有效边表填充算法 学号：
姓名： 班级：
指导老师： 完成日期：
1. 实验目的：
设计有效边表结点和边表结点数据结构
设计有效边表填充算法
编程实现有效边表填充算法
2. 实验描述：
下图 1 所示多边形覆盖了 12 条扫描线，共有 7 个顶点和 7 条边。7 个顶点分别为：P0（7，8） ，P1（3，12） ，P2（1，7） ，P3（3，1）, P4（6，5）, P5（8，1）, P6（12，
9）。在 1024×768 的显示分辩率下，将多边形顶点放大为 P0（500,400） ，P1（350，600） ，P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。
图1示例多边形
图2屏幕显示多边形
3. 算法设计：
多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x 值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。
4. 源程序：
1）//AET.h和AET..cpp
class AET
{
public:
AET();
virtual ~AET();
double x;
int yMax;
double k; //代替1/k
AET *next;
}
2）//Bucket.h和Bucket.cpp
class Bucket
{
public:
Bucket();
virtual ~Bucket();
int ScanLine;
AET *p;//桶上的边表指针
Bucket *next;
}
3) // TestView.h
#include "AET.h"//包含有效边表类
#include "Bucket.h"//包含桶类
#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中 class CTestView : public CView
{
。。。。。。。。。
public:
void PolygonFill();//上闭下开填充多边形
void CreatBucket();//建立桶结点桶
void Et();//构造边表
void AddEdge(AET *);//将边插入AET 表
void EdgeOrder();//对AET 表进行排序
。。。。。。。。。。
protected:
COLORREF GetColor;//调色板
CPoint Point[7];//定义多边形
Bucket *HeadB,*CurrentB;//桶的头结点和当前结点
AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点
4)// TestView.cpp
CTestView::CTestView()
{
//设置多边形的7个顶点
Point[0]=CPoint(550,400);//P0
Point[1]=CPoint(350,600);//P1
Point[2]=CPoint(250,350);//P2
Point[3]=CPoint(350,50);//P3
Point[4]=CPoint(500,250);//P4
Point[5]=CPoint(600,50);//P5
Point[6]=CPoint(800,450);//P6
}
void CTestView::OnDraw(CDC* pDC)
{
CTestDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
pDC->Polygon(Point,7);//绘制多边形
//输出多边形的顶点编号
pDC->TextOut(550,410,"P0");
pDC->TextOut(350,600,"P1");
pDC->TextOut(230,340,"P2");
pDC->TextOut(350,30,"P3");
pDC->TextOut(490,220,"P4");
pDC->TextOut(600,30,"P5");
pDC->TextOut(805,450,"P6");
}
void CTestView::OnMenuAET() //菜单函数
{
AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标题
CColorDialog ccd(GetColor);
if(ccd.DoModal()==IDOK)//调用调色板选取前景色
{
GetColor=ccd.GetColor();
}
RedrawWindow();//刷新屏幕
CreatBucket();//初始化桶
Et();//建立边表
PolygonFill();//多边形填充
}
void CTestView::CreatBucket()//初始化桶
{
int ScanMin,ScanMax;//确定扫描线的最小值和最大值
ScanMax=ScanMin=Point[0].y;
for(int i=1;i<>
{
if(Point[i].y<>
{
ScanMin=Point[i].y;//扫描线的最小值
}
if(Point[i].y>ScanMax)
{
ScanMax=Point[i].y;//扫描线的最大值
}
}
for(i=ScanMin;i<=scanmax;i++)>
{
if(ScanMin==i)//桶头结点
{
HeadB=new Bucket;//建立桶的头结点
CurrentB=HeadB;//CurrentB为Bucket 当前结点指针
CurrentB->ScanLine=ScanMin;
CurrentB->p=NULL;//没有连接边链表
CurrentB->next=NULL;
}
else//建立桶的其它结点
{
CurrentB->next=new Bucket;//新建一个桶结点
CurrentB=CurrentB->next;//使CurrentB 指向新建的桶结点
CurrentB->ScanLine=i;
CurrentB->p=NULL;//没有连接边链表
CurrentB->next=NULL;
}
}
}
void CTestView::Et()//构造边表
{
for(int i=0;i
{
CurrentB=HeadB;//从桶链表的头结点开始循环
int j=i+1;//边的第二个顶点，Point[i]和Point[j]构成边
if(j==Number) j=0;//保证多边形的闭合
if(Point[j].y>Point[i].y)//终点比起点高
{
while(CurrentB->ScanLine!=Point[i].y)//在桶内寻找该边的yMin
{
CurrentB=CurrentB->next;//移到下一个桶结点
}
E[i].x=Point[i].x;//计算AET 表的值
E[i].yMax=Point[j].y;
E[i].k=double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/k
E[i].next=NULL;
CurrentE=CurrentB->p;//获得桶上链接边表的地址
if(CurrentB->p==NULL)//当前桶结点上没有链接边结点
{
CurrentE=&E[i];//赋边的起始地址
CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中
}
else
{
while(CurrentE->next!=NULL)//如果当前边已连有边结点
{
CurrentE=CurrentE->next;//移动指针到当前边的最后一个边结点
}
CurrentE->next=&E[i];//把当前边接上去
}
}
if(Point[j].y
{
while(CurrentB->ScanLine!=Point[j].y)
{
CurrentB=CurrentB->next;
}
E[i].x=Point[j].x;
E[i].yMax=Point[i].y;
E[i].k=double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y); E[i].next=NULL;
CurrentE=CurrentB->p;
if(CurrentE==NULL)
{
CurrentE=&E[i];
CurrentB->p=CurrentE;
}
else
{
while(CurrentE->next!=NULL)
{
CurrentE=CurrentE->next;
}
CurrentE->next=&E[i];
}
}
}
CurrentB=NULL;
CurrentE=NULL;
}
void CTestView::AddEdge(AET *NewEdge)//插入临时边表函数
{
T1=HeadE;
if(T1==NULL)//边表为空, 将边表置为TempEdge
{
T1=NewEdge;
HeadE=T1;
}
else
{
while(T1->next!=NULL)//边表不为空, 将TempEdge 连在该边之后
{
T1=T1->next;
}
T1->next=NewEdge;
}
}
void CTestView::EdgeOrder()//对边表进行排序函数
{
T1=HeadE;
if(T1==NULL)
{
return;
}
if(T1->next==NULL)//如果该边表没有再连边表
{
return;//桶结点只有一条边，不需要排序
}
else
{
if(T1->next->x { T2=T1->next; T1->next=T2->next; T2->next=T1; HeadE=T2; } T2=HeadE; T1=HeadE->next; while(T1->next!=NULL)//继续两两比较相连的边表的x 值, 进行排序 { if(T1->next->x { T2->next=T1->next; T1->next=T1->next->next; T2->next->next=T1; T2=T2->next; } else { T2=T1; T1=T1->next; } } } } void CTestView::PolygonFill()//多边形填充函数 { HeadE=NULL; for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)//访问所有桶结点 { for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)//访问桶中排序前的边结点 { AET *TempEdge=new AET; TempEdge->x=CurrentE->x; TempEdge->yMax=CurrentE->yMax; TempEdge->k=CurrentE->k; TempEdge->next=NULL; AddEdge(TempEdge);//将该边插入临时Aet 表 } EdgeOrder();//使得边表按照x 递增的顺序存放 T1=HeadE;//根据ymax 抛弃扫描完的边结点 if(T1==NULL) { return; } while(CurrentB->ScanLine>=T1->yMax)//放弃该结点，Aet 表指针后移（下闭上开） { T1=T1->next; HeadE=T1; if(HeadE==NULL) { return; } } if(T1->next!=NULL) { T2=T1; T1=T2->next; } while(T1!=NULL) { if(CurrentB->ScanLine>=T1->yMax)//跳过一个结点 { T2->next=T1->next; T1->next=NULL; T1=T2->next; } else { T2=T1; T1=T2->next; } } BOOL In=false;//设置一个BOOL 变量In ，初始值为假 double xb,xe;//扫描线的起点和终点 for(T1=HeadE;T1!=NULL;T1=T1->next)//填充扫描线和多边形相交的区间 { if(In==false) { xb=T1->x; In=true;//每访问一个结点, 把In 值取反一次 } else//如果In 值为真，则填充从当前结点的x 值开始到下一结点的x 值结束的区间 { xe=T1->x-1;//左闭右开 CClientDC dc(this); for(double x=xb;x<> dc.SetPixel(ROUND(x),CurrentB->ScanLine,GetColor);//填充语句 Sleep(1);//延时1ms, 提高填充过程的可视性 In=FALSE; } } for(T1=HeadE;T1!=NULL;T1=T1->next)//边连贯性 { T1->x=T1->x+T1->k;//x=x+1/k } } delete HeadB; delete CurrentB; delete CurrentE; delete HeadE; } 5. 运行结果：(屏幕截图) 实验二 有效边表填充算法 1.实验目的: 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述: 下图 1 所示多边形覆盖了 12 条扫描线，共有 7 个顶点和 7 条边。7 个顶点分别为:P0(7，8) ，P1(3，12) ，P2(1，7) ，P3(3，1), P4(6，5), P5(8，1), P6(12，9)。在 1024×768 的显示分辩率下，将多边形顶点放大为 P0(500,400) ，P1(350，600) ，P2(250，350)，P3(350，50), P4(500，250), P5(600，50), P6(800，450)。请使用有效边表算法填充该多边形。 图1示例多边形 图2 屏幕显示多边形 3.算法设计: 4.源程序: 1)//AET.h和AET..cpp class AET { } 2)//Bucket.h和Bucket.cpp class Bucket { } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中 class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 。。。。。。。。。。 protected: COLORREF GetColor;//调色板 CPoint Point[7];//定义多边形 Bucket *HeadB,*CurrentB;//桶的头结点和当前结点 AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点 4)// TestView.cpp CTestView::CTestView() { //设置多边形的7个顶点 Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6 } void CTestView::OnDraw(CDC* pDC) { CTestDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); pDC->Polygon(Point,7);//绘制多边形 //输出多边形的顶点编号 pDC->TextOut(550,410,"P0"); pDC->TextOut(350,600,"P1"); pDC->TextOut(230,340,"P2"); pDC->TextOut(350,30,"P3"); pDC->TextOut(490,220,"P4"); pDC->TextOut(600,30,"P5"); pDC->TextOut(805,450,"P6"); } void CTestView::OnMenuAET() //菜单函数 { AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标题 CColorDialog ccd(GetColor); if(ccd.DoModal()==IDOK)//调用调色板选取前景色 { GetColor=ccd.GetColor(); } RedrawWindow();//刷新屏幕 CreatBucket();//初始化桶 Et();//建立边表 PolygonFill();//多边形填充 } void CTestView::CreatBucket()//初始化桶 { } void CTestView::Et()//构造边表 { } void CTestView::AddEdge(AET *NewEdge)//插入临时边表函数 { } void CTestView::EdgeOrder()//对边表进行排序函数 { } void CTestView::PolygonFill()//多边形填充函数 { } 5.运行结果:(屏幕截图) 实验二 有效边表填充算法 实验题目: 有效边表填充算法 学号: 姓名: 班级: 指导老师: 完成日期: 1.实验目的: 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述: 下图 1 所示多边形覆盖了 12 条扫描线，共有 7 个顶点和 7 条边。7 个顶点分别为:P0(7，8) ，P1(3，12) ，P2(1，7) ，P3(3，1), P4(6，5), P5(8，1), P6(12，9)。在 1024×768 的显示分辩率下，将多边形顶点放大为 P0(500,400) ，P1(350，600) ，P2(250，350)，P3(350，50), P4(500，250), P5(600，50), P6(800，450)。 , 图1示例多边形 图2屏幕显示多边形 3.算法设计: 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。 4.源程序: 1)//AET.h和AET..cpp class AET { public: AET(); virtual ~AET(); double x; int yMax; double k; //代替1/k AET *next; } 2)//Bucket.h和Bucket.cpp class Bucket , { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; } 3) // TestView.h #include "AET.h"//包含有效边表类 #include "Bucket.h"//包含桶类 #define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中 class CTestView : public CView { 。。。。。。。。。 public: void PolygonFill();//上闭下开填充多边形 void CreatBucket();//建立桶结点桶 void Et();//构造边表 void AddEdge(AET *);//将边插入AET表 void EdgeOrder();//对AET表进行排序 。。。。。。。。。。 protected: COLORREF GetColor;//调色板 CPoint Point[7];//定义多边形 Bucket *HeadB,*CurrentB;//桶的头结点和当前结点 AET E[Number],*HeadE,*CurrentE,*T1,*T2;//有效边表的结点 4)// TestView.cpp CTestView::CTestView() { //设置多边形的7个顶点 Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6 } void CTestView::OnDraw(CDC* pDC) { , CTestDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); pDC->Polygon(Point,7);//绘制多边形 //输出多边形的顶点编号 pDC->TextOut(550,410,"P0"); pDC->TextOut(350,600,"P1"); pDC->TextOut(230,340,"P2"); pDC->TextOut(350,30,"P3"); pDC->TextOut(490,220,"P4"); pDC->TextOut(600,30,"P5"); pDC->TextOut(805,450,"P6"); } void CTestView::OnMenuAET() //菜单函数 { AfxGetMainWnd()->SetWindowText("多边形有效边表填充算法");//显示标题 CColorDialog ccd(GetColor); if(ccd.DoModal()==IDOK)//调用调色板选取前景色 { GetColor=ccd.GetColor(); } RedrawWindow();//刷新屏幕 CreatBucket();//初始化桶 Et();//建立边表 PolygonFill();//多边形填充 } void CTestView::CreatBucket()//初始化桶 { int ScanMin,ScanMax;//确定扫描线的最小值和最大值 ScanMax=ScanMin=Point[0].y; for(int i=1;i { if(Point[i].y { ScanMin=Point[i].y;//扫描线的最小值 } if(Point[i].y>ScanMax) { ScanMax=Point[i].y;//扫描线的最大值 } } for(i=ScanMin;i<=scanmax;i++) 建立桶结点=""> { , if(ScanMin==i)//桶头结点 { HeadB=new Bucket;//建立桶的头结点 CurrentB=HeadB;//CurrentB为Bucket当前结点指针 CurrentB->ScanLine=ScanMin; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } else//建立桶的其它结点 { CurrentB->next=new Bucket;//新建一个桶结点 CurrentB=CurrentB->next;//使CurrentB指向新建的桶结点 CurrentB->ScanLine=i; CurrentB->p=NULL;//没有连接边链表 CurrentB->next=NULL; } } } void CTestView::Et()//构造边表 { for(int i=0;i { CurrentB=HeadB;//从桶链表的头结点开始循环 int j=i+1;//边的第二个顶点，Point[i]和Point[j]构成边 if(j==Number) j=0;//保证多边形的闭合 if(Point[j].y>Point[i].y)//终点比起点高 { while(CurrentB->ScanLine!=Point[i].y)//在桶内寻找该边的yMin { CurrentB=CurrentB->next;//移到下一个桶结点 } E[i].x=Point[i].x;//计算AET表的值 E[i].yMax=Point[j].y; E[i].k=double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/k E[i].next=NULL; CurrentE=CurrentB->p;//获得桶上链接边表的地址 if(CurrentB->p==NULL)//当前桶结点上没有链接边结点 { CurrentE=&E[i];//赋边的起始地址 CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中 } else , { while(CurrentE->next!=NULL)//如果当前边已连有边结点 { CurrentE=CurrentE->next;//移动指针到当前边的最后一个边结点 } CurrentE->next=&E[i];//把当前边接上去 } } if(Point[j].y { while(CurrentB->ScanLine!=Point[j].y) { CurrentB=CurrentB->next; } E[i].x=Point[j].x; E[i].yMax=Point[i].y; E[i].k=double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y); E[i].next=NULL; CurrentE=CurrentB->p; if(CurrentE==NULL) { CurrentE=&E[i]; CurrentB->p=CurrentE; } else { while(CurrentE->next!=NULL) { CurrentE=CurrentE->next; } CurrentE->next=&E[i]; } } } CurrentB=NULL; CurrentE=NULL; } void CTestView::AddEdge(AET *NewEdge)//插入临时边表函数 { T1=HeadE; if(T1==NULL)//边表为空,将边表置为TempEdge { , T1=NewEdge; HeadE=T1; } else { while(T1->next!=NULL)//边表不为空,将TempEdge连在该边之后 { T1=T1->next; } T1->next=NewEdge; } } void CTestView::EdgeOrder()//对边表进行排序函数 { T1=HeadE; if(T1==NULL) { return; } if(T1->next==NULL)//如果该边表没有再连边表 { return;//桶结点只有一条边，不需要排序 } else { if(T1->next->x { T2=T1->next; T1->next=T2->next; T2->next=T1; HeadE=T2; } T2=HeadE; T1=HeadE->next; while(T1->next!=NULL)//继续两两比较相连的边表的x值,进行排序 { if(T1->next->x { T2->next=T1->next; T1->next=T1->next->next; T2->next->next=T1; T2=T2->next; } , else { T2=T1; T1=T1->next; } } } } void CTestView::PolygonFill()//多边形填充函数 { HeadE=NULL; for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)//访问所有桶结点 { for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)//访问桶中排 序前的边结点 { AET *TempEdge=new AET; TempEdge->x=CurrentE->x; TempEdge->yMax=CurrentE->yMax; TempEdge->k=CurrentE->k; TempEdge->next=NULL; AddEdge(TempEdge);//将该边插入临时Aet表 } EdgeOrder();//使得边表按照x递增的顺序存放 T1=HeadE;//根据ymax抛弃扫描完的边结点 if(T1==NULL) { return; } while(CurrentB->ScanLine>=T1->yMax)//放弃该结点，Aet表指针后移(下闭上开) { T1=T1->next; HeadE=T1; if(HeadE==NULL) { return; } } if(T1->next!=NULL) { T2=T1; T1=T2->next; } , while(T1!=NULL) { if(CurrentB->ScanLine>=T1->yMax)//跳过一个结点 { T2->next=T1->next; T1->next=NULL; T1=T2->next; } else { T2=T1; T1=T2->next; } } BOOL In=false;//设置一个BOOL变量In，初始值为假 double xb,xe;//扫描线的起点和终点 for(T1=HeadE;T1!=NULL;T1=T1->next)//填充扫描线和多边形相交的区间 { if(In==false) { xb=T1->x; In=true;//每访问一个结点,把In值取反一次 } else//如果In值为真，则填充从当前结点的x值开始到下一结点的x值结束的 区间 { xe=T1->x-1;//左闭右开 CClientDC dc(this); for(double x=xb;x<=xe;x++)> dc.SetPixel(ROUND(x),CurrentB->ScanLine,GetColor);//填充语句 Sleep(1);//延时1ms,提高填充过程的可视性 In=FALSE; } } for(T1=HeadE;T1!=NULL;T1=T1->next)//边连贯性 { T1->x=T1->x+T1->k;//x=x+1/k } } delete HeadB; delete CurrentB; delete CurrentE; delete HeadE; } , 5.运行结果:(屏幕截图) ,, 导读:就爱阅读网友为您分享以下“多边形的有效边表填充算法-”资讯，希望对您有所帮助，感谢您对92to.com的支持! 实验三 实验三 多边形的有效边表填充算法 一、实验目的与要求1、理解多边形的扫描转换原理、方法; 2、掌握有效边表填充算法; 3、掌握链表的建立、添加结点、删除节点的基本方法; 3、掌握基于链表的排序操作。二、实验内容在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现;三、实验原理 请同学们根据教材及上课的 PPT 独立完成。 四、实验步骤(程序实现) 。1、建立并选择工程项目。打开 VC6.0-菜单 File 的 New 项,在 projects 属性页选择 MFC AppWizard(exe)项，在 Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。 1 选择菜单 Insert New class，Class type 选择“Generic Class”， Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数(实际就是加入实验要求实现的图形生成算法的 实现代码) 。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加 绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数: 添加其他成员函数: CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。参考实现: 参考实现: 多边形的有效边表填充算法的基本过程为: 多边形的有效边表填充算法的基本过程为: 1、定义多边形: 2、初始化桶 3、建立边表 4、多边形填充 1) 对每一条扫描线，将该扫描线上的边结点插入到临时 AET 表中，HeadE. 2) 对临时 AET 表排序，按照 x 递增的顺序存放。 3) 根据 AET 表中边表结点的 ymax 抛弃扫描完的边结点，即 ymax=scanline 4) 扫描 AET 表，填充扫描线和多边形相交的区间。 2 5) 根据的边连贯性，更新 AET 表。 0、构造桶结点的数 据结构和有效边表的数据结构: 有效边表的数据结构:类 AET class AET { public: AET(); virtual ~AET(); double x; int yMax; double k;//代替 1/k AET *next; } 桶结点的数据 结构:类 Bucket class Bucket { public: Bucket(); virtual ~Bucket(); int ScanLine; AET *p;//桶上的边表指针 Bucket *next; } 1、定义多边形: CPoint Point[7];//定义多边形 定 义多边形 //设置多边形的 个顶点 设置多边形的7个顶点 设置多边形的 Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6 2、初始化桶 Bucket* CreatBucket(int number,CPoint *Point) { int ScanMin,ScanMax; Bucket *HeadB,*CurrentB; ScanMin = ScanMax = Point[0].y; for(int i = 1;inumber;i++) { //找最低 和最高 扫描线 找最低和最高扫描线 } for(i = ScanMin;i=ScanMax;i++) 3 { if(i == ScanMin) //桶头结点 桶头结点 { HeadB = new Bucket(); //建立桶的头结点 建立桶的头结点 CurrentB = HeadB; //CurrentB为Bucket当前结点指针 为 当前结点指 针 CurrentB-ScanLine = i; //没有连接边链表 CurrentB-p = NULL; 没有连接边链表 CurrentB-next = NULL; } Else//建 立桶的其它结点 建立桶的其它结点 { } } return HeadB; } 3、建立边表 Bucket * CreatET(int number,CPoint *Point) { Bucket *HeadB; Bucket *CurrentB; AET *CurrentE,*Edge; HeadB = CreateBucket(number,Point); for (int i = 0;inumber;i++) //访问每个顶点 访问每个顶点 { int j = i + 1; //边的第二个顶点，Point[i]和Point[j]构成边 边的第二个顶点， 边的第二个顶点 和 构成边 if (j == number) //保证多边形的闭合 保证多边形的闭合 { j = 0; } CurrentB = HeadB; //从桶链表的头结点开始搜索边(i,j)放 入哪个桶 从桶链表的头结点开始搜索边 从桶链表的头结 点开始搜索边( ) if(Point[i].yPoint[j].y) //终点比起点高 终 点比起点高 { while(Point[i].yCurrentB.ScanLine) //在桶内 寻找该边的 在桶内寻找该边的yMin 在桶内寻找该边的 { CurrentB = CrrentB-next; //移到下一个桶结点 移到下一 个桶结点 } Edge = new AET(); //构造有效边表结点，计算 构造有效边表结点， 构造有效边表结点 计算AET表的值 表的值 Edge-x = Point[i].x; Edge-ymax = Point[j].y; Edge-k 4 = double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表 代表1/k 代表 if(CurrentB-p == NULL) { //当前桶结点上没有链接边结点 当前桶结点上没有链接边结点 5 Current-p = Edge; } else {//第一个边结点直接连接到对应的 桶中 第一个边结点直接连接到对应的桶中//如果当前边已 连有边结点 如果当前边已连有边结点 CurrentE = CurrentB-p; //移动指针到当前边的最后一个边结点 移动指 针到当前边的最后一个边结点 //把当前边接上去 把当前边 接上去} } if(Point[j].yPoint[i].y) { //终点比起点高 终点比起 点高 } } CurrentE = NULL; CurrentB = NULL; AET = NULL; return HeadB; } 4、多边形填充 1) 对每一条扫描线， 将该扫描线上的边结点插入到临时 AET 表中，HeadE. 2) 对临时 AET 表排序，按照 x 递增的顺序存放。 3) 根据 AET 表中边表结点的 ymax 抛弃扫描完的边结点，即 ymax=scanline 4) 扫描 AET 表，填充扫描线和多边形相交 的区间。 5) 根据的边连贯性，更新 AET 表。 void PolygonFill (int number,CPoint *p,COLORREF fillcolor,CDC *pDC)//多边形填充 多边形填充 { HeadE=NULL; for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=Curren tB-next)//访问所有桶结点 访问所有桶结点 { 1) 对每一条 扫描线，将该扫描线上的边结点插入到临时AET表中， HeadE for(CurrentE=CurrentB-p;CurrentE!=NULL;CurrentE=Cu rrentE-next) //访问桶中排 6 序前的边结点 访问桶中排序前的边结点 { AET *TempEdge=new AET; TempEdge-x=CurrentE-x; TempEdge-yMax=CurrentE-yMax; TempEdge-k=CurrentE-k; TempEdge-next=NULL; AddEdge(TempEdge);//将该边插入临时 表 将该边插入临 时Aet表 将该边插入临时 } 2) 对临时 AET 表排序，按照 x 递增的顺序存放。 EdgeOrder();//使得边表按照 递增的 顺序存放 使得边表按照x递增的顺序存放 使得边表按照 // 终点比起点低 终点比起点低 7 3) 根据 AET 表中边表结点的 ymax 抛弃扫描完的边结点，即 ymax=scanline T1=HeadE;//根据 根据ymax抛弃扫描完的边结点 根据 抛弃扫描完的边结点 if(T1==NULL) { return; } while(CurrentB-ScanLine=T1-yMax)//放弃该结点， 表指针后移 下闭上开) 放弃该结点， 放弃该结点 Aet表指针后移 下闭上开) ( { T1=T1-next; HeadE=T1; if(HeadE==NULL) { return; } } if(T1-next!=NULL) { T2=T1; T1=T2-next; } while(T1!=NULL)// { //根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax=ScanLine 根据AET表中边表结点的ymax抛弃扫描完的边结点， ymax=ScanLin ine 根据AET表中边表结点的ymax抛弃扫描完的边结点 } 4) 扫描 AET 表，填充扫描线和多边形相交的区间。 bool In=false;//设置一个 设置一个BOOL变量 ，初始值为假 变量In， 设置一个 变量 double xb,xe;//扫描线的起点和终点 扫描线的起点和终点 for(T1=HeadE;T1!=NULL;T1=T1-next)//填充扫描线和多边形相交的区间 填充扫描线和多边形相交的区间 { if(In==false) { xb=T1-x; In=true;//每访问一个结点 把In值取反一次 每访问一个结点,把 值取反一次 每访问一个结点 } else //如果 值为真，则填充从当前结点的 值开始到下一结点的 值结束的区间 如果In值为真 值开始到下一结点的x值结束的区间 如果 值为真，则填充从当前结点的x值 8 开始到下一结点的 { xe=T1-x-1;//左闭右开 左闭右开 //填充 填充 Sleep(1);//延时 延时1ms,提高填充过程的可视性 延时 提高填充过程的可视性 In=FALSE; } 9 } 5) 根据的边连贯性，更新 AET 表。 //利用边的连贯性，更新交点信息 利用边的连贯性， 利用边的连贯性 } delete HeadB; delete CurrentB; delete CurrentE; delete HeadE; }5、图形类的使用 (1) 、图形类对象的定义。首先在“C*View”(本例中是 CSampleView)类的头文件 中加入图形类的头文件，使图形类能在 C*View 中被辨识和使用;然后，在 C*View 类头文件中实例化图形类，即定义一个图形类的对象。 属性区加入: 在 public 属性区加入: CmyCG m_cg; (2) 、图形类对象的使用。在“C*View”类中有一个成员函数 void OnDraw(CDC* pDC),找到该函数的实现。在其中加入对图形类对象的使用代码: m_cg- PolygonFill(_____,_____,_____,_____); //测试:填充的多边形的七个顶点为: 测试: 测试 填充的多边形的七个顶点为: Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6 在进行填充之前先绘制多边 形的轮廓。 在进行填充之前先绘制多边形的轮廓。 6、程序的调试、运行。五、实验结果抓图与结果分析1、请给出 10 顶点数 7 个，Point[0]=CPoint(550,400);//P0 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(500,250);//P4 Point[5]=CPoint(600,50);//P5 Point[6]=CPoint(800,450);//P6的多边形，填充颜色为红色的 填充效果。 2、请给出顶点数 6 个， Point[0]=CPoint(550,400);//P0 11 Point[1]=CPoint(350,600);//P1 Point[2]=CPoint(250,350);//P2 Point[3]=CPoint(350,50);//P3 Point[4]=CPoint(600,50);//P4 Point[5]=CPoint(800,450);//P5的多边形，填充颜色为兰色的填充效果。 注意: 在这个多 边形中有一条边为水平边， 上述的多边形有效边表填充算 法是否仍然有 效,六、参考文献 12 百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网 92to.com,您的在线图书馆 13 河南理工大学万方科技学院 电气与自动化工程系 课程设计报告 2010 — 2011学年第二学期 课程名称 计算机图形学 设计题目 计算机图形学基本算法 多边形有效边表填充算法 学生姓名 宗彦涛(0828030033) 李建飞(0828030019) 文欣伟(0828030002) 专业班级 计算机08—1 指导教师 侯守明 2011年 6 月 12日 目 录 目 录 目 录 ....................................................................................................................... I 第1章 设计内容与要求 ...................................................................................... 1 1.1总体目标和要求............................................... 1 1.2内容与要求................................................... 1 第2章 总体设计 ..................................................................................................... 4 2.1多边形定义................................................... 4 2.2多边形有效边表填充算法描述................................... 4 2.3多边形有效边表填充算法基本原理............................... 5 第3章 详细设计 ..................................................................................................... 7 第4章 功能实现 ..................................................................................................... 9 第5章 不足与改进 22 第6章 总结........................................................................................................... 23 参考文献 ................................................................................................................ 23 I 第1章 基础知识 第1章 设计内容与要求 1.1 总体目标和要求 目标:以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到: 1)巩固和实践计算机图形学课程中的理论和算法; 2)学习表现计算机图形学算法的技巧; 3)培养认真学习、积极探索的精神。 总体要求:策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。 开发环境:Viusal C++ 6.0，VC2005或其他你认为比较熟悉的环境。 1.2内容与要求 1.2.1实验分为两项内容。 (1)设计边表与活性链表数据结构; 1)边表的定义 有效边(Active Edge):指与当前扫描线相交的多边形的边，也称为活性边。 有效边表(Active Edge Table, AET):把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。 1 第1章 基础知识 2)边表的构造: (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标(ymin )相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。 (3)每条边的数据形成一个结点，内容包括:该扫描线与该边的初始交点x(即较低端点的x值)，1/k，以及该边的最大y值ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干条边按X|ymin由小到大排序，若X|ymin 相等，则按照1/m由小到大排序。 (2)根据多边形有效边表填充算法原理，设计相应算法; 算法步骤: (1)初始化:构造边表，AET表置空; (2)将第一个不空的ET表中的边与AET表合并; (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边; (4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表; (5)AET表不为空则转(3)，否则结束。 结果如下图所示 2 第1章 基础知识 1.2.2功能要求: (1)要求根据鼠标输入点来生成多边形; (2)通过右键菜单显示填充效果，右键菜单有两个选项:未填充 与填充; 3 第2章 总体设计 第2章 总体设计 2.1多边形定义 多边形是由折线段组成的封闭图形。它由有序顶点的点集 Pi(i,1,n )及有向边的线集 Ei(i,1,n)定义，n 为多边形的顶点数或边数，且 Ei,PiPi+1，i,1,n。这里 Pn+1,P1，用以保证了多边形的封闭性。多边形可以分为凸、凹多边形以及环， (1)凸多多边形 凸多多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于 180?，只具有凸点的多边形称为凸多边形。 (2)凹多边形 多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于 180?，有一个凹点的多边形称为凹多边形。 (3)环 多边形内包含有另外的多边形。如果规定:每条有向边的左侧为其内部实面积区域。则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。 2.2多边形有效边表填充算法描述 (1)多边形的填充 4 第2章 总体设计 以顶点法表示的多边形为例。多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，取为填充色，而将多边形外部的像素点保留为背景色。 多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。首先确定多边形覆盖的扫描线条数(y,ymin,ymax)，对每一条扫描线，计算扫描线与多边形边界的交点区间(xmin,xmax)，然后再将该区间内的像素赋予指定的颜色。在扫描线从多边形顶点的最小值ymin 到多边形顶点的最大值 ymax 的移动过程中，重复上述工作，就可以完成多边形的填充。 (2)区域填充 区域是指一组相邻而又具有相同属性的像素，可以理解为多边形的内部。区域的边界色和填充色不一致，填充算法只对区域内部进行填充。种子填充算法是从给定的种子位置开始，按填充颜色点亮种子的相邻像素直到颜色不同的边界像素为止。种子填充算法主要有 4 邻接点算法和 8 邻接点算法。 2.3多边形有效边表填充算法基本原理 多边形的有效边表填充算法的基本原理:按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按 x 值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。 有效边表填充算法是按扫描顺序计算扫描线与多边形的相交区 5 第2章 总体设计 间，再用要求的颜色显示这些区间的像素，即完成填充工作。 有效边表填充算法采用了较灵活的数据结构，通过边的分类表和活性链表访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。 6 第3章 详细设计 第3章 详细设计 首先建立ET表，如图所示。 边表一般是由一系列存储桶构成的，存储桶的数目和扫描线的数目一样多，按扫描线递减的顺序存放。 建立ET表后，扫描多边形填充算法可按如下步骤进行。 1)初始化AET，使之为空，取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 2)按从上到下的顺序对每条扫描线重复以下各步骤，知道AEL和ET为空。 (1)将ET中与当前y有关的结点加入至AEL，同时保存AEL中按x 7 第3章 详细设计 值从小到大实现的顺序序列。 (2)对于AEL中的扫描线y，在一对交点之间填充所需的像素值。 (3)从AEL中删掉y>=ymax结点。 (4)对于留在AEL中的每个结点，执行xi+1=xi+deltax。 (5)对于AEL中的各结点按x值从小到大排序。 (6)使y=y+1成为下一条扫描线的坐 8 第4章 功能实现 第4章 功能实现 案例效果如下: 具体实现: (1) 新建OPENGL工程: 9 第4章 功能实现 (2)在classview中输入: #include { int ymax; float x; float delx; Edge*next; 10 第4章 功能实现 }; struct SortEdge //分类表 { Edge*out; }; struct Point //点 { int x; int y; }; SortEdge sortEdge[500]; Edge*head; void display(void); void reshape(int width,int height); void keyboard(unsigned char key ,int x,int y); void fillPolygon(Point *pt,int n); void insertSortEdge(int n,Edge*edge);// void sortLife(Edge*lifehead);//对活性边表排序 void drawLife(Edge*lifehead,int y);//绘图 void deleLife(Edge*lifehead,int y);//在活性边表删除边 void addLife(Edge*lifehead,int y);//在活性边表中添加边 int initSort(Point*pt,int n);//初始化分类表 11 第4章 功能实现 void init(void) { glClearColor(0,0,0,0); glShadeModel(GL_SMOOTH); } int main(int argc,char**argv) { glutInit(&argc,argv); glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); glutInitWindowSize(640,480); glutInitWindowPosition(500,200); glutCreateWindow("Basic"); init(); glutDisplayFunc(display); glutReshapeFunc(reshape); glutKeyboardFunc(keyboard); glutMainLoop(); return 0; } void display(void) { 12 第4章 功能实现 glClear(GL_COLOR_BUFFER_BIT); Point pt[5]; pt[0].x=50;pt[0].y=50; pt[1].x=200;pt[1].y=100; pt[2].x=450;pt[2].y=50; pt[3].x=450;pt[3].y=200; pt[4].x=250;pt[4].y=250; fillPolygon(pt,5); glFlush(); } void reshape(int width,int height) { glViewport(0,0,width,height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0.0,width,0.0,height); } void keyboard(unsigned char key,int x,int y) { if(key==27) exit(0); } 13 第4章 功能实现 void fillPolygon(Point *pt,int n) { int max=0; int i=0,sweepY; Edge*lifeHead=new Edge; //初始化分类表 max=initSort(pt,n); //初始化活性表 while(sortEdge[i].out==NULL) i++; sweepY=i; lifeHead=sortEdge[i].out; glClear(GL_COLOR_BUFFER_BIT); glBegin(GL_LINES); glColor3f(1.0f,1.0f,1.0f); for (;i { //排序 sortLife(lifeHead); //绘图 14 第4章 功能实现 drawLife(lifeHead,sweepY); sweepY++; //添加 if(sortEdge[sweepY].out!=NULL) addLife(lifeHead,sweepY); //删除 deleLife(lifeHead,sweepY); } glEnd(); } int initSort(Point*pt,int n) { Edge*edge=new Edge[n]; int i,j; int max=0; for(i=0;i (edge+i)->next=NULL; for(i=0;i { if((pt+i)->y>max) max=(pt+i)->y; if(i==n-1) 15 第4章 功能实现 { (edge+i)->ymax=(pt+i)->y>pt->y?(pt+i)->y:(pt+0)->y; (edge+i)->x=((pt+i)->y)>((pt+0)->y)?((pt+0)->x):((pt+i)->x); (edge+i)->delx=(double)((pt+i)->x-(pt+0)->x)/((pt+i)->y-(pt+0)->y); if((pt+i)->y>pt->y) insertSortEdge(pt->y,edge+i); else insertSortEdge((pt+i)->y,edge+i); } else { (edge+i)->ymax=(pt+i)->y>(pt+i+1)->y?(pt+i)->y:(pt+i+1)->y; (edge+i)->x=((pt+i)->y)>((pt+i+1)->y)?((pt+i+1)->x):((pt+i)->x); (edge+i)->delx=(double)((pt+i+1)->x-(pt+i)->x)/((pt+i+1)->y-(pt+i)->y); if((pt+i)->y>(pt+i+1)->y) insertSortEdge((pt+i+1)->y,edge+i); 16 第4章 功能实现 else insertSortEdge((pt+i)->y,edge+i); } } return max; } void deleLife(Edge*lifehead,int y) { if(lifehead==NULL) return; else if(lifehead->ymax==y) { lifehead=lifehead->next; deleLife(lifehead,y); } else { Edge*curr,*pre; curr=lifehead; while(curr!=NULL) 17 第4章 功能实现 { if(curr->ymax==y) { pre->next=curr->next; curr=pre->next; } else { pre=curr; curr=curr->next; } } } } void addLife(Edge*lifehead,int y) { Edge*curr; curr=lifehead; while(curr->next!=NULL) curr=curr->next; curr->next=sortEdge[y].out; 18 第4章 功能实现 } void drawLife(Edge*lifehead,int y) { Edge*curr,*pre; curr=pre=lifehead; while(curr!=NULL) { pre=curr->next; glVertex2i(curr->x,y); glVertex2i(pre->x,y); curr->x+=curr->delx; pre->x+=pre->delx; curr=pre->next; } } void sortLife(Edge*lifehead) { Edge*curr,*pre; curr=pre=lifehead; int num=0; 19 第4章 功能实现 float min=0; while(curr!=NULL) { pre=curr; min=500; while(pre!=NULL) { if(pre->x min=pre->x; pre=pre->next; } pre=curr; while(pre->x!=min) pre=pre->next; if(pre!=curr) { int temp=pre->ymax; pre->ymax=curr->ymax; curr->ymax=temp; temp=pre->x; pre->x=curr->x; curr->x=temp; 20 第4章 功能实现 double delx=pre->delx; pre->delx=curr->delx; curr->delx=delx; } curr=curr->next; } } void insertSortEdge(int n,Edge*edge) { Edge*pre; if(sortEdge[n].out==NULL) sortEdge[n].out=edge; else { pre=sortEdge[n].out; while(pre->next!=NULL) pre=pre->next; pre->next=edge; } } 21 第5章 不足与改进 第5章 不足与改进 1)边表构造的算法: (1) 首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。 (2) 将每条边的信息链入与该边最小y坐标相对的桶处。也就是说，若某条边的较低点为ymin，则该边就放在相应的扫描线中。 (3) 每条边的数据形成一个结点，内容包括:该扫描线与该的初始交点x(即较低端点的x值),1/k，以及该边的最大y值ymax如下: x|ymin ymax 1/k next (4) 同一桶中若干条边按x|ymin由小到在大排序，若x|ymin相等，则按照1/k由小到大排序。 2)改进的有效边表填充算法步骤如下: (1) 初始化: 构造边表， AET表置空. (2) 将第一个不空的ET表中的边与AET表合并。 (3) 删除AET表中y = ymax的边后再填充，按“下闭上升”的原则进行填充，此时就无需缩短任何边。然后进行填充，填充时设置一个布尔量b(初值为假)，令指针从有效边表中第 一个结点到最后一个结点进行遍历一次。每访问一个结点，把b取反一次，若b为真，则把从当前结点的x值开始下一结点的x值结束的区间用多边形色填充。(填 充时需要对x坐标进行四舍五入处理)。 (4) yy + 1,根据x= x+ 1 / k计算并修改AET表，同时合并i+1 = ii+1 i 22 第5章 不足与改进 ET表中y = y i+1 桶的边，按次序插入到AET表中，形成新的AET表。(5) AET表不空则转(3)，否则结束。 23 第6章 总结 第6章 总结 这次的图形学课程设计让我收获不小，到真正自己动手做的时候才会发现不足之处。在做设计的期间，又温习了原来所学的知识，可以把知识系统的归纳。任何知识和理论都要归结于实践。 在做设计期间，多亏了同学的帮助和老师的细心指导。自己不懂的代码和原理可以有同学参考。 这次设计做得时间太短，大家都要帮着复习考试，没有全身心的投入，很多地方都没有深入的考虑，这也是这次设计的不足之处。 我要感谢辅导老师侯守明对我的教育培养，您细心指导我的学习与研究，在此，我要向您深深地鞠上一躬。还要感谢在我身边帮助过我的同学们，感谢你们热情的付出～你们兢兢业业，奋发向上的精神，将是我今后人生前进道路上的一种力量～ 再次感谢我的老师和我的同学们～ 24 参考文献 1.《计算机图形学》，徐文鹏，机械工业出版社 2.《计算机图形学课程设计》，唐敏，浙江大学出版社，2008年11月 3.《计算机图形学》，吴庆标，韩丹夫，浙江大学出版社，2006年6月 4. 《OpenGL 编程指南》，Dave Shreiner著，机械工业出版社，2008年3月 5. 中国地质大学信息工程学院，2010年6月， http://course.cug.edu.cn/cugThird/CGOL_NET/CLASS/course/3-2 -3-a.htm 25范文二：实验二 有效边表填充算法
范文三：有效边表填充算法.doc
范文四：多边形的有效边表填充算法-
范文五：有效边表填充算法.doc
