OpenGL掃描線填充算法詳解
更新時(shí)間：2020年02月19日 15:32:49 作者：Frank（Zhiyang-Dou）
這篇文章主要為大家詳細(xì)介紹了OpenGL實(shí)現(xiàn)掃描線填充算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
本文實(shí)例為大家分享了OpenGL掃描線填充算法，供大家參考，具體內(nèi)容如下
說(shuō)明
把最近一系列的圖形學(xué)經(jīng)典算法實(shí)現(xiàn)了一下。課業(yè)繁忙，關(guān)于該系列的推導(dǎo)隨后再寫(xiě)。但是在注釋里已經(jīng)有較為充分的分析。
分情況討論
注意對(duì)于橫線需要特別討論，但是對(duì)于垂直線卻不必特別討論。想一想為什么？
代碼
#include <iostream>
#include <GLUT/GLUT.h>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int hmin,hmax; //記錄掃描線開(kāi)始和結(jié)束的位置
struct Line { //定義線段的結(jié)構(gòu)體
float dx,x,y,ym; //不用記錄K直接記錄dx和x即可
Line(float x1,float y1,float x2,float y2) {
if(y1==y2){ //單獨(dú)討論橫直線的情況
this->y = y1;
this->ym = y1;
if(x1 < x2){
dx = x1; x = x2;
}else{
dx =x2;x = x1;}
}else if(y2<y1){ //選擇靠上者的x值
this -> x = x2; //記錄上方的x值一方便處理關(guān)鍵時(shí)刻（用于插入AET排序）
this ->y = y2; //記錄上方的y值，用于排序
this -> ym = y1; //靠下者ym
}else{
this -> x = x1;
this ->y = y1;
this -> ym = y2;
}
dx = (x2-x1)/(y2-y1);
}
};
typedef list<Line> TESTLIST;
vector<vector<Line>> con; //記錄重要事件表（有序），當(dāng)然這個(gè)也可以使用優(yōu)先隊(duì)列
list<Line> AET; //滾動(dòng)記錄活動(dòng)邊表,這里將
//該邊表完整存儲(chǔ)的意義不大所以采用滾動(dòng)存儲(chǔ)的方式
map<int, int> mapper; //用于數(shù)據(jù)（y值）離散化處理
int x1,y1,x2,y2; //描述構(gòu)成直線的兩個(gè)端點(diǎn)
int x0,y0; //記錄圖形開(kāi)始位置
float h_min,h_max; //畫(huà)線開(kāi)始和結(jié)束的位置
int flag = 1; //用于記錄用戶點(diǎn)擊的次數(shù)，單次畫(huà)點(diǎn)，雙次畫(huà)線。
int if_drawable = 1; //當(dāng)用戶再次點(diǎn)擊鼠標(biāo)時(shí)不在更改信息
int window_size=600; //這是我們顯示界面的大小
vector<vector<Line>> con2;
int level = 1;
/*
操作說(shuō)明：算法沒(méi)有嚴(yán)格的圖形繪制檢查。僅為了圖形學(xué)算法的演示。
您使用鼠標(biāo)【左鍵】進(jìn)行繪制點(diǎn)，請(qǐng)您保證沒(méi)有線是交叉的。
當(dāng)您點(diǎn)擊鼠標(biāo)【右鍵】繪制最后一個(gè)點(diǎn)。系統(tǒng)會(huì)自動(dòng)將其與起始點(diǎn)相連。
整體思路描述：使用map將y的值離散化，用有序表記錄“關(guān)鍵事件”主要
是加入邊（一條或者兩條）刪除邊操作。在用一個(gè)滾動(dòng)的活動(dòng)邊表進(jìn)行遍歷畫(huà)線。
*/
void show_v(Line a){
/*
函數(shù)說(shuō)明：顯示點(diǎn)的信息
*/
cout << "(" <<a.x << "," << a.y <<")";
cout << " (" <<a.dx<<")" << "下限："<<a.ym;
cout << " -- "<<endl;
}
bool higher(const vector<Line> & l1, const vector<Line>& l2) {
//將關(guān)鍵事件表中的line按照y值進(jìn)行排序；
//注意我們的畫(huà)布是從上到下不斷遞增從左到右不斷遞增
return l1[0].y < l2[0].y;//可以保證一定至少有一個(gè)不然map不會(huì)映射到
}
bool AET_lefter(const Line & l1, const Line & l2) {
//將AET表中的line按照x值進(jìn)行排序；
return l1.x < l2.x;//可以保證一定至少有一個(gè)不然map不會(huì)映射到
}
bool lefter(const Line & l1, const Line & l2) {
/*
函數(shù)說(shuō)明：將關(guān)鍵事件表中的line按照x值以及dx進(jìn)行排序；
*/
if(l1.x < l2.x){
return 1;
}else if (l1.x == l2.x){
if(l1.dx<0&&l2.dx>0)
return 1;
else
return 0;
}else
return 0;
}
void sort_con(){
/*
函數(shù)說(shuō)明：對(duì)關(guān)鍵事件表進(jìn)行排序處理
其中y從小到大遞增，x方向按照斜率和x大小由左到右排序
*/
for (int i = 0 ; i < con.size(); i++)
if (con[i].size()>=2)
sort(con[i].begin(),con[i].end(),lefter);
for (int i = 0;i < con.size(); i++) {
vector<Line> a;
for (int j =0; j < con[i].size(); j++)
a.push_back(con[i][j]);
con2.push_back(a); //這里將事件表進(jìn)行拷貝，另一種方式是將map的映射對(duì)應(yīng)改變
}
sort(con.begin(), con.end(), higher);
}
void draw_lines(float x1,float y1,float x2,float y2){
glBegin(GL_LINES);
glColor3f(1.0,1.0,0.0);
glVertex2f(x1,window_size-y1);
glVertex2f(x2,window_size-y2);
glEnd();
glFlush();
}
void show_con(){
//輸出排序后的關(guān)鍵事件表
for (int i = 0; i < con.size(); i++) {
cout <<"number : "<<i <<endl;
for (int j = 0; j < con[i].size(); j++) {
vector<Line> a = con[i];
show_v (a[j]);
}cout <<"================"<<endl;
}
}
void lines_filling(){ //真正的掃描線填充過(guò)程
if (con.empty()) //為了展示過(guò)程細(xì)節(jié)，部分功能沒(méi)有使用函數(shù)ti
return;
int h_leveler = 0; //高度遍歷器
map<int,int>::iterator iter; //定義一個(gè)迭代指針iter
for(h_leveler = h_min;h_leveler <= h_max;h_leveler++){//開(kāi)始掃描
int id = mapper[h_leveler];
if (!id) { //說(shuō)明沒(méi)有到達(dá)關(guān)鍵節(jié)點(diǎn)，我們只需要進(jìn)行繪制和更新即可；
float xx = 0.0; flag = 1; //flag用于控制每?jī)山M畫(huà)一次線
for(list<Line> ::iterator it=AET.begin();it!=AET.end();)
{ if (flag%2==0) { //該畫(huà)線了！
draw_lines(xx, h_leveler,it->x,h_leveler);
for (TESTLIST::iterator pl = AET.begin(); pl != AET.end();)
if (pl->ym == h_leveler)
AET.erase(pl++);
else
pl++; //這個(gè)負(fù)責(zé)刪除的for循環(huán)在畫(huà)線后執(zhí)行可以避免留白情況
it->x = it->x +it->dx;
}else{
if (it->y == it->ym) {
xx = x1;
}else{
xx =it->x;
it->x = it->x +it->dx;
}
}flag++;it++;}
}else{ //如果到了關(guān)鍵事件，那么加線、去線
list<Line> ::iterator it;
float xx = 0.0;int counter = 1;
for(it=AET.begin();it!=AET.end();it++)
{ Line temp= *it;
if (counter%2==0) //該畫(huà)線了！
draw_lines(xx, h_leveler,temp.x,h_leveler);
else
xx =temp.x; //刪除邊前先畫(huà)好線避免留白
counter++;
}
for (TESTLIST::iterator it = AET.begin(); it != AET.end();)
if (it->ym == h_leveler)
AET.erase(it++);
else
it++; //關(guān)鍵時(shí)間刪除邊
for (int i =0 ; i < con2[id-1].size(); i++)
if (con2[id-1][i].y == con2[id-1][i].ym)
continue; //如果是橫線直接不用添加該橫線
else
AET.push_back(con2[id-1][i]);
AET.sort(AET_lefter); //維持滾動(dòng)活動(dòng)邊表的有序性
}}}
void InitEnvironment() //對(duì)環(huán)境進(jìn)行初始化操作
{ glClearColor(0.0,0.0,0.0,0);
glClear(GL_COLOR_BUFFER_BIT);
glPointSize(7);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluOrtho2D(0,window_size,0,window_size);
}
void myDisplay(void)
{ glClear(GL_COLOR_BUFFER_BIT);
glFlush();
}
void OnMouse(int button,int state,int x,int y)
/*
函數(shù)說(shuō)明：進(jìn)行用戶交互的操作
每?jī)蓚€(gè)點(diǎn)一組進(jìn)行操作。設(shè)置左鍵、右鍵手勢(shì)動(dòng)作
*/
{if(button==GLUT_LEFT_BUTTON&&state==GLUT_DOWN&&if_drawable)
{if (flag ==1 &&if_drawable) {
glColor3f(1,0,0);
glBegin(GL_POINTS);
glVertex2f(x,window_size-y);
x0 = x;y0 =y;
x1 = x;y1 = y;
h_min = y0;
h_max = y0;
glEnd();
glFlush();
flag++;
}else{
glColor3f(1,0,0);
glBegin(GL_POINTS);
glVertex2f(x,window_size-y);
glEnd();
x2 = x;y2 = y;
glBegin(GL_LINES);
glColor3f(1.0,0.0,0.0);
glVertex2f(x1,window_size-y1);
glVertex2f(x2,window_size-y2);
if (y1 !=y2) {
Line a(x1,y1,x2,y2);
int r_y = min (y1,y2);
if (y1 < h_min)
h_min = y1;
if (y2 < h_min)
h_min = y2;
if (y1 > h_max)
h_max = y1;
if (y2 >h_max)
h_max = y2;
int pos = mapper[r_y];
if (pos==0) { //說(shuō)明該變量還沒(méi)有離散化
mapper[r_y] = level++;
vector<Line> lines;
lines.push_back(a);
con.push_back(lines);}
else
con[pos-1].push_back(a);
}
x1 = x2; y1 = y2;
glEnd();
glFlush();
}
}
if(button==GLUT_RIGHT_BUTTON&&state==GLUT_DOWN&&if_drawable)
{ //點(diǎn)擊右鍵
glColor3f(1,0,0);
glBegin(GL_POINTS);
glVertex2f(x,window_size-y);
glEnd();
x2 = x;y2 = y;
glBegin(GL_LINES);
glColor3f(1.0,0.0,0.0);
glVertex2f(x1,window_size-y1);
glVertex2f(x2,window_size-y2);
Line a(x1,y1,x2,y2);
int r_y = min (y1,y2);
int pos = mapper[r_y];
if (pos==0) { //說(shuō)明該變量還沒(méi)有離散化
mapper[r_y] = level++;
vector<Line> lines;
lines.push_back(a);
con.push_back(lines);}
else
con[pos-1].push_back(a);
glEnd();
glFlush();
glBegin(GL_LINES);
glColor3f(1.0,0.0,0.0);
glVertex2f(x0,window_size-y0);
glVertex2f(x2,window_size-y2);
glEnd();
glFlush();
Line aa(x0,y0,x2,y2);
r_y = min (y0,y2);
pos = mapper[r_y];
if (pos==0) { //說(shuō)明該變量還沒(méi)有離散化
mapper[r_y] = level++;
vector<Line> lines;
lines.push_back(aa);
con.push_back(lines);}
else
con[pos-1].push_back(aa);
sort_con();
lines_filling();
if_drawable = 0;
}
}
int main(int argc, char *argv[])
{ glutInit(&argc, argv); //初始化GLUT
glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
glutInitWindowPosition(300, 100);
glutInitWindowSize(window_size, window_size);
glutCreateWindow("hw2_filling_line");
InitEnvironment(); //初始化
glutMouseFunc(&OnMouse); //注冊(cè)鼠標(biāo)事件
glutDisplayFunc(&myDisplay); //回調(diào)函數(shù)
glutMainLoop(); //持續(xù)顯示，當(dāng)窗口改變會(huì)重新繪制圖形
return 0;
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++實(shí)現(xiàn)轉(zhuǎn)置矩陣的循環(huán)
大家好，本篇文章主要講的是C++實(shí)現(xiàn)轉(zhuǎn)置矩陣的循環(huán)，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
Visual?Studio下Eigen庫(kù)環(huán)境配置方式
這篇文章主要介紹了Visual?Studio下Eigen庫(kù)環(huán)境配置方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
C++ 的開(kāi)發(fā)者認(rèn)為數(shù)據(jù)輸入和輸出的過(guò)程也是數(shù)據(jù)傳輸?shù)倪^(guò)程，數(shù)據(jù)像水一樣從一個(gè)地方流動(dòng)到另一個(gè)地方，所以 C++ 中將此過(guò)程稱為“流”，實(shí)現(xiàn)此過(guò)程的類稱為“流類”。下面小編將詳細(xì)介紹這個(gè)話題,需要的朋友可以參考一下2021-09-09
C/C++ 多線程的學(xué)習(xí)心得總結(jié)
本篇文章是對(duì)C/C++中多線程的學(xué)習(xí)心得總結(jié)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
本篇文章是對(duì)java線程池的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
本文主要介紹了Qt6安裝教程(使用國(guó)內(nèi)源)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
這篇文章主要介紹了C++中g(shù)etline()的用法詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱2022-11-11
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言基于哈希表實(shí)現(xiàn)通訊錄，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02