多边形填充.docx
- 文档编号:17250820
- 上传时间:2023-07-23
- 格式:DOCX
- 页数:19
- 大小:367.81KB
多边形填充.docx
《多边形填充.docx》由会员分享,可在线阅读,更多相关《多边形填充.docx(19页珍藏版)》请在冰点文库上搜索。
多边形填充
计算机图形学实验报告
班级:
学号:
姓名:
实验三多边形填充
一实验目的
1)掌握多边形的有效边表填充算法;
2)掌握边界像素处理原则;
3)掌握菱形图形的填充方法。
二实验要求
1)设计实现多边形填充类,可以设置顶点序列,调用填充函数。
2)多边形填充采用有效边表填充算法进行实现,通过建立多边形的桶表和边表数据,按照算法步骤依次扫描填充;
3)调用设计实现的多边形填充类,对菱形线框进行颜色填充。
三实验步骤
第1步:
创建MFC应用程序框架
参照第一章的步骤建立空的MFC应用程序框架。
第2步:
设计实现直线绘制类
设计实现多边形填充类
1)有效边表填充算法原理
在多边形填充过程中,常采用:
“下闭上开”和“左闭右开”的原则对边界像素进行处理。
有效边表填充算法通过维护“桶表和边表”数据,节省了有效数据存储空间,避免了扫描线与多边形所有边求交的运算耗时。
x|ymin
ymax
1/k
next
图1边表结点数据结构
有效边表填充算法实现步骤为:
a)根据多边形的顶点序列,建立其“桶表和边表”数据。
b)按照扫描线从小到大的移动顺序,取出当前扫描线对应桶的边表数据。
c)如果“桶表”数据已经取完,则填充结束;否则,继续后续填充操作。
d)将当前桶里的边表数据加入到有效边表,根据“下闭上开”的原则,删除已经到ymax的无效边。
e)对当前扫描线的有效边表按x值递增的顺序进行排序、配对,以确定填充区间;根据“左闭右开”的原则,对两两配对的填充空间进行像素填充。
f)继续回到步骤b。
1)新建多边形填充类CFillPoly头文件
首先声明二维点类“CP2”、边表类“CAET”和桶表类“CBucket”,用于存储和传递多边形“桶表和边表”数据。
多边形填充类中主要包括存放多边形顶点数据、有效边表结点指针和桶表结点指针的成员变量,以及创建桶表、边表、有效边表排序和填充多边形等成员函数。
“FillPoly.h”头文件中具体类型声明代码如下:
#pragmaonce
classCP2
{
public:
CP2();
virtual~CP2();
CP2(double,int);
doublex;
inty;
COLORREFc;
};
classCAET
{
public:
CAET();
virtual~CAET();
public:
doublex;
intyMax;
doublek;
CP2ps;
CP2pe;
CAET*pNext;
};
classCBucket
{
public:
CBucket();
virtual~CBucket();
public:
intScanLine;
CAET*pET;
CBucket*pNext;
};
classCFillPoly
{
public:
CFillPoly();
virtual~CFillPoly();
voidSetPoint(CP2*p,int);
voidCreateBucket();
voidCreateEdge();
voidAddET(CAET*);
voidETOrder();
voidPlaneFill(CDC*);
voidClearMemory();
voidDeleteAETChain(CAET*pAET);
protected:
intPNum;
CP2*P;
CAET*pHeadE,*pCurrentE,*pEdge;
CBucket*pHeadB,*pCurrentB;
};
(2)新建多边形填充类CFillPoly.cpp
#include"stdafx.h"
#include"FillPoly.h"
#include"math.h"
#defineRound(d)int(floor(d+0.5))
CP2:
:
CP2()
{
x=0.0;
y=0;
c=RGB(0,0,255);
}
CP2:
:
~CP2()
{}
CP2:
:
CP2(doublex,inty)
{
this->x=x;
this->y=y;
}
CAET:
:
CAET()
{}
CAET:
:
~CAET()
{}
CBucket:
:
CBucket()
{}
CBucket:
:
~CBucket()
{}
CFillPoly:
:
CFillPoly()
{
PNum=0;
P=NULL;
pEdge=NULL;
pHeadB=NULL;
pHeadE=NULL;
}
CFillPoly:
:
~CFillPoly()
{
if(P!
=NULL)
{
delete[]P;
P=NULL;
}
ClearMemory();
}
voidCFillPoly:
:
SetPoint(CP2*p,intm)
{
P=newCP2[m];
for(inti=0;i { P[i]=p[i]; } PNum=m; } voidCFillPoly: : CreateBucket() { intyMin,yMax; yMin=yMax=P[0].y; for(inti=0;i { if(P[i].y { yMin=P[i].y; } if(P[i].y>yMax) { yMax=P[i].y; } } for(inty=yMin;y<=yMax;y++) { if(yMin==y) { pHeadB=newCBucket; pCurrentB=pHeadB; pCurrentB->ScanLine=yMin; pCurrentB->pET=NULL; pCurrentB->pNext=NULL; } else { pCurrentB->pNext=newCBucket; pCurrentB=pCurrentB->pNext; pCurrentB->ScanLine=y; pCurrentB->pET=NULL; pCurrentB->pNext=NULL; } } } voidCFillPoly: : CreateEdge() { for(inti=0;i { pCurrentB=pHeadB; intj=(i+1)%PNum; if(P[i].y { pEdge=newCAET; pEdge->x=P[i].x; pEdge->yMax=P[j].y; pEdge->k=(P[j].x-P[i].x)/(P[j].y-P[i].y); pEdge->ps=P[i]; pEdge->pe=P[j]; pEdge->pNext=NULL; while(pCurrentB->ScanLine! =P[i].y) { pCurrentB=pCurrentB->pNext; } } if(P[j].y { pEdge=newCAET; pEdge->x=P[j].x; pEdge->yMax=P[i].y; pEdge->k=(P[i].x-P[j].x)/(P[i].y-P[j].y); pEdge->ps=P[i]; pEdge->pe=P[j]; pEdge->pNext=NULL; while(pCurrentB->ScanLine! =P[j].y) { pCurrentB=pCurrentB->pNext; } } if(P[i].y! =P[j].y) { pCurrentE=pCurrentB->pET; if(pCurrentE==NULL) { pCurrentE=pEdge; pCurrentB->pET=pCurrentE; } else { while(pCurrentE->pNext! =NULL) { pCurrentE=pCurrentE->pNext; } pCurrentE->pNext=pEdge; } } } } voidCFillPoly: : PlaneFill(CDC*pDC) { CAET*pT1=NULL,*pT2=NULL; pHeadE=NULL; for(pCurrentB=pHeadB;pCurrentB! =NULL;pCurrentB=pCurrentB->pNext) { for(pCurrentE=pCurrentB->pET;pCurrentE! =NULL;pCurrentE=pCurrentE->pNext) { pEdge=newCAET; pEdge->x=pCurrentE->x; pEdge->yMax=pCurrentE->yMax; pEdge->k=pCurrentE->k; pEdge->ps=pCurrentE->ps; pEdge->pe=pCurrentE->pe; pEdge->pNext=NULL; AddET(pEdge); } ETOrder(); pT1=pHeadE; if(pT1==NULL) return; while(pCurrentB->ScanLine>=pT1->yMax) { CAET*pAETTEmp=pT1; pT1=pT1->pNext; deletepAETTEmp; pHeadE=pT1; if(pHeadE==NULL) return; } if(pT1->pNext! =NULL) { pT2=pT1; pT1=pT2->pNext; } while(pT1! =NULL) { if(pCurrentB->ScanLine>=pT1->yMax) { CAET*pAETTemp=pT1; pT2->pNext=pT1->pNext; pT1=pT2->pNext; deletepAETTemp; } else { pT2=pT1; pT1=pT2->pNext; } } BOOLbInFlag=FALSE; doublexb,xe; for(pT1=pHeadE;pT1! =NULL;pT1=pT1->pNext) { if(FALSE==bInFlag) { xb=pT1->x; bInFlag=TRUE; } else { xe=pT1->x; for(doublex=xb;x { pDC->SetPixelV(Round(x),pCurrentB->ScanLine,pT1->ps.c); } bInFlag=FALSE; } } for(pT1=pHeadE;pT1! =NULL;pT1=pT1->pNext) { pT1->x=pT1->x+pT1->k; } } } voidCFillPoly: : AddET(CAET*pNewEdge) { CAET*pCE=pHeadE; if(pCE==NULL) { pHeadE=pNewEdge; pCE=pHeadE; } else { while(pCE->pNext! =NULL) { pCE=pCE->pNext; } pCE->pNext=pNewEdge; } } voidCFillPoly: : ETOrder() { CAET*pT1,*pT2; intCount=1; pT1=pHeadE; if(pT1==NULL) { return; } if(pT1->pNext==NULL) { return; } while(pT1->pNext! =NULL) { Count++; pT1=pT1->pNext; } for(inti=0;i { CAET**pPre=&pHeadE; pT1=pHeadE; for(intj=0;j { pT2=pT1->pNext; if((pT1->x>pT2->x)||((pT1->x==pT2->x)&&(pT1->k>pT2->k))) { pT1->pNext=pT2->pNext; pT2->pNext=pT1; *pPre=pT2; pPre=&(pT2->pNext); } else { pPre=&(pT1->pNext); pT1=pT1->pNext; } } } } voidCFillPoly: : ClearMemory() { DeleteAETChain(pHeadE); CBucket*pBucket=pHeadB; while(pBucket! =NULL) { CBucket*pBucketTemp=pBucket->pNext; DeleteAETChain(pBucket->pET); deletepBucket; pBucket=pBucketTemp; } pHeadB=NULL; pHeadE=NULL; } voidCFillPoly: : DeleteAETChain(CAET*pAET) { while(pAET! =NULL) { CAET*pAETTemp=pAET->pNext; deletepAET; pAET=pAETTemp; } } 第三步调用多边形填充类填充菱形线框图 #include"FillPoly.h" voidCCheerView: : OnDraw(CDC*pDC) { CCheerDoc*pDoc=GetDocument(); ASSERT_VALID(pDoc); //TODO: adddrawcodefornativedatahere CRectrect; GetClientRect(&rect); pDC->SetMapMode(MM_ANISOTROPIC); pDC->SetWindowExt(rect.Width(),rect.Height()); pDC->SetViewportExt(rect.Width(),-rect.Height()); pDC->SetViewportOrg(rect.Width()/2,rect.Height()/2); inta=200; CP2Pi[4]; Pi[0].x=0;Pi[0].y=a;Pi[0].c=RGB(0,125,170); Pi[1].x=a;Pi[1].y=0;Pi[1].c=RGB(0,125,125); Pi[2].x=0;Pi[2].y=-a;Pi[2].c=RGB(0,105,99); Pi[3].x=-a;Pi[3].y=0;Pi[3].c=RGB(19,125,125); CFillPoly*fill=newCFillPoly; fill->SetPoint(Pi,4); fill->CreateBucket(); fill->CreateEdge(); fill->PlaneFill(pDC); deletefill; } 四实验效果 五实验总结 最初编写代码完成的时候编译运行,出现很多错误,然后根据提示去修改发现总是莫名其妙的,然后就对照课本认认真真对照最终实现0个错误,都是一下编写时候的粗心导致的。 对多边形填充原理理解的较为浅显,MFC一些函数掌握不够完整。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多边形 填充