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