其他計算機圖形學實驗
傳送門
前言
實現(xiàn)多邊形掃描線填充算法，并和鼠標進行交互。
具體原理略過，會貼上完整代碼，可直接運行。
環(huán)境：
vs2019,OpenGL的庫（可以搜索如何用vs使用OpenGL的庫，可以使用vs自帶的插件或者其他方法，很方便）
要點：
1.NET和AET的創(chuàng)建，改動
2.改變鼠標點擊和鼠標拖拽的響應事件。
最終效果：
用鼠標隨意畫頂點，然后展示填充過程
對應控制臺會輸出頂點坐標和個數(shù)
思路借鑒
文章1
文章2文章來源：http://www.zghlxwxcb.cn/news/detail-400768.html
步驟
1.點的結構體
struct point
{
float x, y;
point(){}
point(int xx, int yy):
x(xx), y(yy) {}
};
vector<point> vertice; //頂點
2. AET 活性邊表、NET新邊表 的結構體
typedef struct XET
{
float x;
float dx; // 從當前掃描線到下一條掃描線間x的增量，即斜率的倒數(shù)
float ymax; //該邊所交的最高掃描線的坐標值ymax
XET* next;
}AET, NET; //AET 活性邊表； NET新邊表
3. 掃描線算法實現(xiàn)
void PolyScan()
{
/*得到最高點的y坐標*/
int Max_Y = 0;
for (int i = 0; i < vertice.size(); i++)
/*Max_Y = max(Max_Y, vertice[i].y);*/
if (vertice[i].y > Max_Y)
Max_Y = vertice[i].y;
//初始化AET表
AET* pAET = new AET;
pAET->next = NULL;
//初始化NET表
NET* pNET[800]; //吊桶
for (int i = 0; i <= Max_Y; i++)
{
pNET[i] = new NET;
pNET[i]->next = NULL;;
}
//掃描并且建立NET表
int len = vertice.size(); //頂點個數(shù)
for (int i = 0; i <= Max_Y; i++)
{
for (int j = 0; j < len; j++) //掃描每個點
{
if (i == vertice[j].y)
{
//如果一個點和前一個點有一條邊相連，則該點和后面一個點也相連
//！這個式子 便于最后一個頂點和第一個點相連 和 防止出現(xiàn)負數(shù)
//判斷當前點的高低，使ymax、DX、DY的計算有變化
if (vertice[(j - 1 + len) % len].y > vertice[j].y)
{
//前一個點在當前點的上方
NET* p = new NET;
p->x = vertice[j].x;
p->ymax = vertice[(j - 1 + len) % len].y;//與當前掃描線相交的活性邊 的 最高點即為相鄰頂點的y
float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
p->dx = DX / DY;//dx為直線斜率的倒數(shù)
p->next = pNET[i]->next;
pNET[i]->next = p;
}
if (vertice[(j + 1) % len].y > vertice[j].y)
{
//后一個點在當前點的上方
NET* p = new NET;
p->x = vertice[j].x;
p->ymax = vertice[(j + 1) % len].y;
float DX = vertice[(j + 1) % len].x - vertice[j].x;
float DY = vertice[(j + 1) % len].y - vertice[j].y;
p->dx = DX / DY;//dx為直線斜率的倒數(shù)
p->next = pNET[i]->next;
pNET[i]->next = p;
}
}
}
}
//建立并且更新活性邊表AET
//各條掃描線i
for (int i = 0; i <= Max_Y; i++)
{
/*把新邊表NET[i] 中的邊結點用插入排序法插入AET表，使之按x坐標遞增順序排列*/
//計算每條掃描線上不同線產(chǎn)生的新的交點x，更新AET
NET* p = pAET->next;
while (p)
{
p->x = p->x + p->dx; //更新x坐標
p = p->next;
}
//斷表排序,不再開辟空間
AET* tq = pAET;
p = pAET->next;
tq->next = NULL;
while (p)//順著鏈表往下走
{
//找到第一個比它大的數(shù)字tq->next->next->x，則從p->next到tq->next都是比p->x小的
while (tq->next != NULL && tq->next->x <= p->x)
tq = tq->next;
//插入p到tq和tq->next之間
NET* t = p->next;
p->next = tq->next;
tq->next = p;
p = t;
tq = pAET;//回到頭
}
/*(改進算法) 取消求交，減少計算量*/
//先從AET表中刪除ymax==i的結點****************************************/
//像素的取舍問題，保證多邊形的“下閉上開”，避免填充擴大化（交點的個數(shù)應保證為偶數(shù)個）
AET* q = pAET;
p = q->next;
while (p)
{
if (p->ymax == i)
{
q->next = p->next;
delete p;
p = q->next;
}
else
{
q = q->next;
p = q->next;
}
}
//若NET中有新點，將其用插入法插入AET，按x遞增的順序排列
p = pNET[i]->next;
q = pAET;
while (p)
{
while (q->next && p->x >= q->next->x)
q = q->next;
//插入p
NET* t = p->next;
p->next = q->next;
q->next = p;
p = t;
q = pAET;//回到頭
}
//配對后填充顏色
p = pAET->next;
while (p && p->next != NULL)
{
for (float j = p->x; j <= p->next->x; j++)
{
//掃描線畫點
draw_a_point(j, i);
//cout << "(" << j << ", " << i << ")" << endl;
}
p = p->next->next;//考慮端點情況
}
}
glFlush();
}
4. 改變鼠標響應函數(shù)
void mymouse(int button, int state, int x, int y)
{
//左鍵
if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
{
draw_a_point(x, window_height - y);
point p(x, window_height - y);
vertice.push_back(p);
cout << "頂點" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
}
//右鍵
if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
{
glClearColor(1, 1, 1, 1);//設置繪制窗口顏色為白色
glColor3f(0, 1, 1);
//繪制多邊形
glBegin(GL_LINES);
for (int i = 0; i < vertice.size(); i++)
{
if (i == vertice.size() - 1)//畫完最后一個點，使其閉合
{
glVertex2f(vertice[0].x, vertice[0].y);
glVertex2f(vertice[i].x, vertice[i].y);
}
else
{
glVertex2f(vertice[i].x, vertice[i].y);
glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
}
}
glEnd();
glFlush();
}
//鼠標中間
if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
{
//cout << "center: (" << x << ", " << y << ")" << endl;
//BoundaryFill4(x, window_height - y);
//BoundaryFill4_Stack(x, window_height - y);
cout << "多邊形頂點個數(shù)為" << vertice.size() << "。 " << "開始掃描線填充。" << endl;
PolyScan();
}
}
完整代碼
//掃描線算法
#include<iostream>
#include<gl/glut.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int window_width = 800, window_height = 600;
const int maxn = 99999;
struct point
{
float x, y;
point(){}
point(int xx, int yy):
x(xx), y(yy) {}
};
vector<point> vertice; //頂點
typedef struct XET
{
float x;
float dx; // 從當前掃描線到下一條掃描線間x的增量，即斜率的倒數(shù)
float ymax; //該邊所交的最高掃描線的坐標值ymax
XET* next;
}AET, NET; //AET 活性邊表； NET新邊表
void draw_a_point(int x, int y);
void PolyScan();
void mymouse(int button, int state, int x, int y);
void display();
int main(int argc, char* argv[])
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowPosition(100, 50);
glutInitWindowSize(window_width, window_height);
glutCreateWindow("掃描線填充");
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, window_width, 0, window_height);
glClearColor(1, 1, 1, 1);
glClear(GL_COLOR_BUFFER_BIT);
glutMouseFunc(&mymouse);
glutDisplayFunc(&display);
glutMainLoop();
return 0;
}
//畫點函數(shù)
void draw_a_point(int x, int y)
{
glBegin(GL_POINTS);
glColor3f(0, 1, 1);
glVertex2f(x, y);
glEnd();
glFlush();
}
void PolyScan()
{
/*得到最高點的y坐標*/
int Max_Y = 0;
for (int i = 0; i < vertice.size(); i++)
/*Max_Y = max(Max_Y, vertice[i].y);*/
if (vertice[i].y > Max_Y)
Max_Y = vertice[i].y;
//初始化AET表
AET* pAET = new AET;
pAET->next = NULL;
//初始化NET表
NET* pNET[800]; //吊桶
for (int i = 0; i <= Max_Y; i++)
{
pNET[i] = new NET;
pNET[i]->next = NULL;;
}
//掃描并且建立NET表
int len = vertice.size(); //頂點個數(shù)
for (int i = 0; i <= Max_Y; i++)
{
for (int j = 0; j < len; j++) //掃描每個點
{
if (i == vertice[j].y)
{
//如果一個點和前一個點有一條邊相連，則該點和后面一個點也相連
//！這個式子 便于最后一個頂點和第一個點相連 和 防止出現(xiàn)負數(shù)
//判斷當前點的高低，使ymax、DX、DY的計算有變化
if (vertice[(j - 1 + len) % len].y > vertice[j].y)
{
//前一個點在當前點的上方
NET* p = new NET;
p->x = vertice[j].x;
p->ymax = vertice[(j - 1 + len) % len].y;//與當前掃描線相交的活性邊 的 最高點即為相鄰頂點的y
float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
p->dx = DX / DY;//dx為直線斜率的倒數(shù)
p->next = pNET[i]->next;
pNET[i]->next = p;
}
if (vertice[(j + 1) % len].y > vertice[j].y)
{
//后一個點在當前點的上方
NET* p = new NET;
p->x = vertice[j].x;
p->ymax = vertice[(j + 1) % len].y;
float DX = vertice[(j + 1) % len].x - vertice[j].x;
float DY = vertice[(j + 1) % len].y - vertice[j].y;
p->dx = DX / DY;//dx為直線斜率的倒數(shù)
p->next = pNET[i]->next;
pNET[i]->next = p;
}
}
}
}
//建立并且更新活性邊表AET
//各條掃描線i
for (int i = 0; i <= Max_Y; i++)
{
/*把新邊表NET[i] 中的邊結點用插入排序法插入AET表，使之按x坐標遞增順序排列*/
//計算每條掃描線上不同線產(chǎn)生的新的交點x，更新AET
NET* p = pAET->next;
while (p)
{
p->x = p->x + p->dx; //更新x坐標
p = p->next;
}
//斷表排序,不再開辟空間
AET* tq = pAET;
p = pAET->next;
tq->next = NULL;
while (p)//順著鏈表往下走
{
//找到第一個比它大的數(shù)字tq->next->next->x，則從p->next到tq->next都是比p->x小的
while (tq->next != NULL && tq->next->x <= p->x)
tq = tq->next;
//插入p到tq和tq->next之間
NET* t = p->next;
p->next = tq->next;
tq->next = p;
p = t;
tq = pAET;//回到頭
}
/*(改進算法) 取消求交，減少計算量*/
//先從AET表中刪除ymax==i的結點****************************************/
//像素的取舍問題，保證多邊形的“下閉上開”，避免填充擴大化（交點的個數(shù)應保證為偶數(shù)個）
AET* q = pAET;
p = q->next;
while (p)
{
if (p->ymax == i)
{
q->next = p->next;
delete p;
p = q->next;
}
else
{
q = q->next;
p = q->next;
}
}
//若NET中有新點，將其用插入法插入AET，按x遞增的順序排列
p = pNET[i]->next;
q = pAET;
while (p)
{
while (q->next && p->x >= q->next->x)
q = q->next;
//插入p
NET* t = p->next;
p->next = q->next;
q->next = p;
p = t;
q = pAET;//回到頭
}
//配對后填充顏色
p = pAET->next;
while (p && p->next != NULL)
{
for (float j = p->x; j <= p->next->x; j++)
{
//掃描線畫點
draw_a_point(j, i);
//cout << "(" << j << ", " << i << ")" << endl;
}
p = p->next->next;//考慮端點情況
}
}
glFlush();
}
void mymouse(int button, int state, int x, int y)
{
//左鍵
if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
{
draw_a_point(x, window_height - y);
point p(x, window_height - y);
vertice.push_back(p);
cout << "頂點" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
}
//右鍵
if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
{
glClearColor(1, 1, 1, 1);//設置繪制窗口顏色為白色
glColor3f(0, 1, 1);
//繪制多邊形
glBegin(GL_LINES);
for (int i = 0; i < vertice.size(); i++)
{
if (i == vertice.size() - 1)//畫完最后一個點，使其閉合
{
glVertex2f(vertice[0].x, vertice[0].y);
glVertex2f(vertice[i].x, vertice[i].y);
}
else
{
glVertex2f(vertice[i].x, vertice[i].y);
glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
}
}
glEnd();
glFlush();
}
//鼠標中間
if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
{
//cout << "center: (" << x << ", " << y << ")" << endl;
//BoundaryFill4(x, window_height - y);
//BoundaryFill4_Stack(x, window_height - y);
cout << "多邊形頂點個數(shù)為" << vertice.size() << "。 " << "開始掃描線填充。" << endl;
PolyScan();
}
}
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.0, 0.4, 0.2);
glPointSize(1);
glBegin(GL_POINTS);
PolyScan();
glEnd();
glFlush();
}
總結
掃描線算法部分，建立NET 和 建立并且更新活性邊表AET 這兩個地方比較復雜，可以帶入圖中多想文章來源地址http://www.zghlxwxcb.cn/news/detail-400768.html
到了這里，關于【計算機圖形學 】掃描線多邊形填充算法 | OpenGL+鼠標交互的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
