Details of OpenGL scanline filling algorithm

The example of this paper shares OpenGL scanline filling algorithm for your reference, the specific content is as follows

instructions

The latest 1 series of classical graphics algorithms to achieve 1. The derivation of this series will be written later. But it has been fully analyzed in the notes.

Case discussion

Note that we need to discuss horizontal lines in particular, but not vertical lines in particular. Think 1 Think why?

code

#include <iostream>
#include <GLUT/GLUT.h>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int hmin,hmax;     // Record where the scan line begins and ends 
struct Line {     // Defines the structure of a line segment 
 float dx,x,y,ym;    // Don't have to record K Direct recording dx and x Can be 
 Line(float x1,float y1,float x2,float y2) {
 if(y1==y2){    // Let's talk about horizontal lines separately 
  this->y = y1;
  this->ym = y1;
  if(x1 < x2){
  dx = x1; x = x2;
  }else{
  dx =x2;x = x1;}
 }else if(y2<y1){   // Choose those who depend on you x value 
  this -> x = x2;   // Top of record x value 1 Convenient for handling critical moments (for insertion AET Sort) 
  this ->y = y2;   // Top of record y Value for sorting 
  this -> ym = y1;   // By nobody ym
 }else{
  this -> x = x1;
  this ->y = y1;
  this -> ym = y2;
 }
 dx = (x2-x1)/(y2-y1);
 }
};
typedef list<Line> TESTLIST;
vector<vector<Line>> con; // Keep a list of important events (in order), but this can also use priority queues 
list<Line> AET;   // Scroll through the active side table , There will be 
      // The edge table full storage is of little significance so the scroll storage method is adopted 
map<int, int> mapper;  // For data ( y Value) discretization 
int x1,y1,x2,y2;   // Describe the two ends that make up the line 
int x0,y0;    // Record the starting position of the graph 
float h_min,h_max;  // Draw the beginning and end of the line 
int flag = 1;    // It is used to record the number of times the user clicks, draw a point once and draw a line twice. 
int if_drawable = 1;  // The user does not change the information when he clicks the mouse again 
int window_size=600;  // This is the size of our display interface 
vector<vector<Line>> con2;
int level = 1;
/*
  Operating instructions: The algorithm does not have strict graphics rendering inspection. Just for a graphical algorithm demonstration. 
  You use the left mouse button to draw points. Please make sure that no lines are crossed. 
  When you click the right mouse button to draw the last 1 A point. The system will automatically connect it to the starting point. 
  Overall idea description: use map will y Is discretized and the "key events" are recorded in an ordered table 
  Is to add edges ( 1 Delete edge operation. In the use 1 Five scrollable active edge tables are traversed to draw lines. 
 */
void show_v(Line a){
 /*
  Function description: display point information 
 */
 cout << "(" <<a.x << "," << a.y <<")";
 cout << " (" <<a.dx<<")" << " The lower limit: "<<a.ym;
 cout << " -- "<<endl;
}
bool higher(const vector<Line> & l1, const vector<Line>& l2) {
 // Will be in the key events table line In accordance with the y Values are sorted; 
 // Notice that our canvas is incrementing from top to bottom from left to right 
 return l1[0].y < l2[0].y;// Can guarantee 1 Set at least 1 An otherwise map Does not map to 
}
bool AET_lefter(const Line & l1, const Line & l2) {
 // will AET In the table line In accordance with the x Values are sorted; 
 return l1.x < l2.x;// Can guarantee 1 Set at least 1 An otherwise map Does not map to 
}
bool lefter(const Line & l1, const Line & l2) {
 /*
  Function description: put the key events in the table line In accordance with the x Values, and dx Sort; 
 */
 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(){
 /*
  Function description: key event table for sorting processing 
  Among them y From small to large, x The direction is the sum of the slopes x Sort size from left to right 
 */
 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);   // Copy the event table here, and 1 One way is to take map The mapping corresponds to the change 
 }
 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(){
 // Output the sorted table of key events 
 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(){    // The actual scanline filling process 
 if (con.empty())    // To show the details of the process, some functions do not use functions ti
 return;
 int h_leveler = 0;    // Height ergoer 
 map<int,int>::iterator iter;  // define 1 Multiple iteration pointer iter
 for(h_leveler = h_min;h_leveler <= h_max;h_leveler++){// Start scanning 
 int id = mapper[h_leveler];
 if (!id) {     // It indicates that the key node has not been reached, so we only need to draw and update. 
  float xx = 0.0; flag = 1; //flag Used to control every two groups of paintings 1 The time line 
  for(list<Line> ::iterator it=AET.begin();it!=AET.end();)
  { if (flag%2==0) {  // It's time to draw a line! 
   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++;  // This one is responsible for deleting for The loop executes after the line is drawn to avoid white space 
   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{     // If there is a critical event, then wire and unwire 
  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)  // It's time to draw a line! 
   draw_lines(xx, h_leveler,temp.x,h_leveler);
  else
   xx =temp.x;   // Draw a line to avoid white space before deleting an edge 
  counter++;
  }
  for (TESTLIST::iterator it = AET.begin(); it != AET.end();)
  if (it->ym == h_leveler)
   AET.erase(it++);
  else
   it++;    // Key time to remove edges 
  for (int i =0 ; i < con2[id-1].size(); i++)
  if (con2[id-1][i].y == con2[id-1][i].ym)
   continue;   // If it's a horizontal line you don't have to add the horizontal line 
  else
   AET.push_back(con2[id-1][i]);
  AET.sort(AET_lefter);  // Maintains the order of the scrolling active edge tables 
 }}}
void InitEnvironment()   // Initialize the environment 
{ 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)
/*
  Function description: to perform user interaction operations 
  Every two points 1 Groups perform operations. Set left and right hand gestures 
 */
{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) {  // This indicates that the variable has not been discretized 
  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)
 { // Click on the right 
 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) {  // This indicates that the variable has not been discretized 
  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) {  // This indicates that the variable has not been discretized 
  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); // Initialize the GLUT
 glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
 glutInitWindowPosition(300, 100);
 glutInitWindowSize(window_size, window_size);
 glutCreateWindow("hw2_filling_line");
 InitEnvironment(); // Initialize the 
 glutMouseFunc(&OnMouse); // Register mouse events 
 glutDisplayFunc(&myDisplay); // The callback function 
 glutMainLoop(); // Continues to display, when the window changes will redraw the graph 
 return 0;
}