圖形學篇：多邊形有效邊表填充算法
什麼是多邊形？算法
- 多邊形是由折線段組成的封閉圖形
多邊形的表示方法有哪些？數組
- 頂點表示法：使用頂點進行描述，但此時多邊形僅僅是一些封閉線段，內部是空的，且不能直接進行填充上色
- 點陣表示法：使用大量的點進行描述，描述完成以後，獲得的就是完整形態的多邊形，內部已被填充，可直接針對點來進行上色
多邊形的掃描轉換就是從頂點表示法轉換到點陣表示法的過程。安全
基礎的填充多邊形方式：數據結構
- 檢查光柵上的每個像素是否位於多邊形內
光柵到底是什麼？函數
- 由大量等寬等間距的平行狹縫構成的光學器件稱爲光柵，這是專業且準確的方法，然而明顯不是給人看的（觀衆：？？？）
- 光柵是鏈接幀緩衝和具體的電腦屏幕的橋樑（這是很老的大頭顯示器上的，如今的液晶顯示器不存在光柵，它的成像依靠的是電場，液晶，濾光膜等，因此咱們暫且把這裏說的的光柵理解爲像素）
光柵化到底是什麼？性能
- https://blog.csdn.net/waitforfree/article/details/10066547
- 光柵化是一切屏幕成像的基礎，沒有它，就沒有圖像
- 光柵化不依賴於光柵，它依賴於CPU和GPU的交互和運算
有效邊表填充算法：spa
- 基本原理：按照掃描線從小到大的移動順序，計算當前掃描線與有效邊的交點，而後把這些交點按x的值遞增順序進行排序，配對，以肯定填充去間，最後用指定顏色填充區間內的全部像素，即完成填充工做
- 優點：經過維護邊表和有效邊表，避開了掃描線與多邊形全部邊求交的複雜運算，性能提高巨大
- 邊界像素處理原則：對於邊界像素，採用「左閉右開」和「下閉上開」的原則
- 有效邊：多邊形與當前掃描線相交的邊
- 有效邊表：把有效邊按照與掃描線交點x座標遞增的順序存放在一個鏈表中，稱爲有效邊表
- 桶表：按照掃描線順序管理邊的數據結構
算法實現：.net
將VC 6.0 調整到ClassView視圖3d
建立有效邊表和桶表類指針
將VC 6.0調整到FileView視圖，對兩個類進行定義
AET.h
class CAET
{
public:
CAET();
virtual ~CAET();
public:
double x;//當前掃描線與有效邊交點的x座標
int yMax;//邊的最大y值
double k;//斜率的倒數(x的增量)
CAET *pNext;
};
Bucket.h
#include "AET.h"
#include "Bucket.h"
class CBucket
{
public:
CBucket();
virtual ~CBucket();
public:
int ScanLine; //掃描線
CAET *pET; //桶上的邊表指針
CBucket *pNext;
};
回到ClassView視圖，像以前那樣建立CFill類，再回到FileView視圖，對CFill類進行定義
Fill.h
#include "AET.h"
#include "Bucket.h"
class CFill
{
public:
CFill();
virtual ~CFill();
void SetPoint(CPoint *p,int);//初始化頂點和頂點數目
void CreateBucket();//建立桶
void CreateEdge();//邊表
void AddET(CAET *);//合併ET表
void ETOrder();//ET表排序
void Gouraud(CDC *);//填充多邊形
void ClearMemory();//清理內存
void DeleteAETChain(CAET* pAET);//刪除邊表
protected:
int PNum;//頂點個數
CPoint *P;//頂點座標動態數組
CAET *pHeadE,*pCurrentE,*pEdge; //有效邊表結點指針
CBucket *pHeadB,*pCurrentB; //桶表結點指針
};
Fill.cpp
// Fill.cpp: implementation of the CFill class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "Study3.h"
#include "Fill.h"
#include "AET.h"
#include "Bucket.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CFill::CFill()
{
PNum=0;
P=NULL;
pEdge=NULL;
pHeadB=NULL;
pHeadE=NULL;
pCurrentB = NULL;
pCurrentE = NULL;
}
CFill::~CFill()
{
if(P!=NULL)
{
delete[] P;
P=NULL;
}
ClearMemory();
}
void CFill::SetPoint(CPoint *p,int m)////初始化頂點和頂點數目
{
P=new CPoint[m];//建立一維動態數組，轉儲CTestView類中P數組中的頂點
for(int i=0;i<m;i++)
{
P[i]=p[i];
}
PNum=m;//記錄頂點數量
}
void CFill::CreateBucket()//建立桶表
{
int yMin,yMax;
yMin = yMax = P[0].y;
for(int i = 0;i<PNum;i++)
{
if(P[i].y<yMin)
{
yMin = P[i].y;
}
if(P[i].y>yMax)
{
yMax = P[i].y;
}
}
for(int y = yMin;y<=yMax;y++)
{
if(yMin == y)
{
pHeadB = new CBucket;
pCurrentB = pHeadB;
pCurrentB->ScanLine = yMin;
pCurrentB->pET = NULL;
pCurrentB->pNext = NULL;
}
else
{
pCurrentB->pNext = new CBucket;
pCurrentB=pCurrentB->pNext;
pCurrentB->ScanLine = y;
pCurrentB->pET=NULL;
pCurrentB->pNext=NULL;
}
}
}
void CFill::CreateEdge()//建立邊表，即將各邊鏈入到相應的桶節點
{
for(int i = 0;i<PNum;i++)
{
pCurrentB=pHeadB;
int j = (i+1)%PNum;
if(P[i].y<P[j].y)
{
pEdge = new CAET;
pEdge->x=P[i].x;
pEdge->yMax=P[j].y;
pEdge->k = (double)(P[j].x-P[i].x)/((double)(P[j].y-P[i].y));
pEdge->pNext = NULL;
while(pCurrentB->ScanLine!=P[i].y)
{
pCurrentB=pCurrentB->pNext;
}
}
if(P[j].y<P[i].y)
{
pEdge=new CAET;
pEdge->x=P[j].x;
pEdge->yMax=P[i].y;
pEdge->k = (double)(P[i].x-P[j].x)/((double)(P[i].y-P[j].y));
pEdge->pNext = NULL;
while(pCurrentB->ScanLine!=P[j].y)
{
pCurrentB=pCurrentB->pNext;
}
}
if(P[j].y!=P[i].y)
{
pCurrentE=pCurrentB->pET;
if(pCurrentE==NULL)
{
pCurrentE=pEdge;
pCurrentB->pET=pCurrentE;
}
else
{
while(NULL!=pCurrentE->pNext)
{
pCurrentE=pCurrentE->pNext;
}
pCurrentE->pNext=pEdge;
}
}
}
}
void CFill::AddET(CAET *pNewEdge)//合併ET表
{
CAET *pCE=pHeadE;//邊表頭結點
if(pCE==NULL)//若邊表爲空，則pNewEdge做爲邊表頭結點
{
pHeadE=pNewEdge;
pCE=pHeadE;
}
else//將pNewEdge連接到邊表末尾（未排序）
{
while(pCE->pNext!=NULL)
{
pCE=pCE->pNext;
}
pCE->pNext=pNewEdge;
}
}
void CFill::ETOrder()//邊表的冒泡排序算法
{
CAET *pT1,*pT2;
int Count=1;
pT1=pHeadE;
if(pT1==NULL)//沒有邊，不須要排序
{
return;
}
if(pT1->pNext==NULL)//若是該ET表沒有再連ET表
{
return;//只有一條邊，不須要排序
}
while(pT1->pNext!=NULL)//統計邊結點的個數
{
Count++;
pT1=pT1->pNext;
}
for(int i=0;i<Count-1;i++)//冒泡排序
{
CAET **pPre=&pHeadE;//pPre記錄當面兩個節點的前面一個節點，第一次爲頭節點
pT1=pHeadE;
for (int j=0;j<Count-1-i;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
{
pPre=&(pT1->pNext);
pT1=pT1->pNext;
}
}
}
}
void CFill::Gouraud(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=new CAET;
pEdge->x=pCurrentE->x;
pEdge->yMax=pCurrentE->yMax;
pEdge->k=pCurrentE->k;
pEdge->pNext=NULL;
AddET(pEdge);
}
ETOrder();
pT1=pHeadE;
if(pT1==NULL)
{
return ;
}
while(pCurrentB->ScanLine>=pT1->yMax)
{
CAET *pAETTEmp = pT1;
pT1=pT1->pNext;
delete pAETTEmp;
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;
delete pAETTemp;
}
else
{
pT2=pT1;
pT1=pT2->pNext;
}
}
BOOL In = FALSE;
int xb,xe;
for(pT1=pHeadE;pT1!=NULL;pT1=pT1->pNext)
{
if(FALSE==In)
{
xb = (int)pT1->x;
In=TRUE;
}
else
{
xe = (int)pT1->x;
for(int x = xb;x<xe;x++)
{
pDC->SetPixel(x,pCurrentB->ScanLine,RGB(0,0,255));
}
In = FALSE;
}
}
for(pT1=pHeadE;pT1!=NULL;pT1=pT1->pNext)
{
pT1->x=pT1->x+pT1->k;
}
}
}
void CFill::ClearMemory()//安全刪除全部桶與桶上鍊接的邊
{
DeleteAETChain(pHeadE);//刪除邊表
CBucket *pBucket=pHeadB;
while (pBucket!=NULL)//針對每個桶
{
CBucket *pBucketTemp=pBucket->pNext;
DeleteAETChain(pBucket->pET);//刪除桶上面的邊
delete pBucket;
pBucket=pBucketTemp;
}
pHeadB=NULL;
pHeadE=NULL;
}
void CFill::DeleteAETChain(CAET *pAET)//刪除邊表
{
while (pAET!=NULL)
{
CAET *pAETTemp=pAET->pNext;
delete pAET;
pAET=pAETTemp;
}
}
一切準備就緒，進入CXXXView.cpp（「XXX」爲你項目名稱）
給OnDraw函數添加如下語句
CRect rect;
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);
rect.OffsetRect(-rect.Width()/2,-rect.Height()/2);
//聲明Fill類
CFill *cFill = new CFill;
//聲明多邊形的七個頂點
CPoint points[7] = {CPoint(50,70),CPoint(-150,270),CPoint(-250,20),CPoint(-150,-280),CPoint(0,-80),CPoint(100,-280),CPoint(300,120)};
//設置頂點
cFill->SetPoint(points,7);
//建立桶表
cFill->CreateBucket();
//建立邊表
cFill->CreateEdge();
//填充多邊形
cFill->Gouraud(pDC);
運行結果
你們對於填充算法要多看看，很重要