OpenGL扫描线填充算法详解

本文实例为大家分享了OpenGL扫描线填充算法，供大家参考，具体内容如下

说明

把最近一系列的图形学经典算法实现了一下。课业繁忙，关于该系列的推导随后再写。但是在注释里已经有较为充分的分析。

分情况讨论

注意对于横线需要特别讨论，但是对于垂直线却不必特别讨论。想一想为什么？

代码

#include <iostream>
#include <GLUT/GLUT.h>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int hmin,hmax;         //记录扫描线开始和结束的位置
struct Line {         //定义线段的结构体
 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值一方便处理关键时刻（用于插入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; //记录重要事件表（有序），当然这个也可以使用优先队列
list<Line> AET;     //滚动记录活动边表,这里将
           //该边表完整存储的意义不大所以采用滚动存储的方式
map<int, int> mapper;   //用于数据（y值）离散化处理
int x1,y1,x2,y2;      //描述构成直线的两个端点
int x0,y0;       //记录图形开始位置
float h_min,h_max;    //画线开始和结束的位置
int flag = 1;       //用于记录用户点击的次数，单次画点，双次画线。
int if_drawable = 1;    //当用户再次点击鼠标时不在更改信息
int window_size=600;   //这是我们显示界面的大小
vector<vector<Line>> con2;
int level = 1;
/*
 操作说明：算法没有严格的图形绘制检查。仅为了图形学算法的演示。
 您使用鼠标【左键】进行绘制点，请您保证没有线是交叉的。
 当您点击鼠标【右键】绘制最后一个点。系统会自动将其与起始点相连。
 整体思路描述：使用map将y的值离散化，用有序表记录“关键事件”主要
 是加入边（一条或者两条）删除边操作。在用一个滚动的活动边表进行遍历画线。
 */
void show_v(Line a){
 /*
  函数说明：显示点的信息
  */
 cout << "(" <<a.x << "," << a.y <<")";
 cout << " (" <<a.dx<<")" << "下限："<<a.ym;
 cout << "  --  "<<endl;
}
bool higher(const vector<Line> & l1, const vector<Line>& l2) {
 //将关键事件表中的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) {
 /*
  函数说明：将关键事件表中的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(){
 /*
  函数说明：对关键事件表进行排序处理
  其中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的映射对应改变
 }
 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(){
 //输出排序后的关键事件表
 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())       //为了展示过程细节，部分功能没有使用函数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) {         //说明没有到达关键节点，我们只需要进行绘制和更新即可；
   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循环在画线后执行可以避免留白情况
     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{         //如果到了关键事件，那么加线、去线
   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++;       //关键时间删除边
   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()      //对环境进行初始化操作
{ 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)
/*
 函数说明：进行用户交互的操作
 每两个点一组进行操作。设置左键、右键手势动作
 */
{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); //回调函数
 glutMainLoop(); //持续显示，当窗口改变会重新绘制图形
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。