【图形学】探秘图形学奥秘：区域填充的解密与实战-阿里云开发者社区

🌌1. 初识模式识别

图形学技术是一门涉及计算机图形和图像处理的学科，其目标是通过算法和数学模型来创建、处理和呈现图形和图像。这项技术的应用范围非常广泛，涵盖了许多领域，包括计算机游戏、虚拟现实、计算机辅助设计（CAD）、医学图像处理、动画制作等。

以下是图形学技术的一些关键方面：

图形生成和渲染： 图形学技术用于生成和呈现视觉图像。这包括三维图形的创建、光照、阴影、颜色和纹理等方面的处理，以产生逼真的图形。

计算机辅助设计（CAD）： 在工程学和设计领域，图形学技术被广泛用于创建和编辑数字化的设计图纸，促进设计过程的可视化和交互。

计算机游戏和虚拟现实： 图形学技术是游戏开发和虚拟现实领域的核心。它用于创建游戏中的角色、场景、特效以及虚拟现实环境，提供沉浸式的视觉体验。

医学图像处理： 在医学领域，图形学技术被用于处理和呈现医学图像，如CT扫描、MRI等，以协助医生进行诊断和手术规划。

动画制作： 图形学技术是制作动画的关键。通过在计算机上生成图形帧并进行渲染，动画制作得以实现。

图像处理： 图形学技术也包括对静态图像的处理，如图像编辑、滤镜应用、图像合成等。

在图形学技术的发展中，硬件加速、实时渲染、虚拟现实和增强现实等方面的创新不断推动着图形学的前沿。这门技术为数字世界的可视化和交互提供了强大的工具和方法。

🌌2. 区域填充

🌍2.1 开发环境及实现

语言: C++
平台: Microsoft Visual Studio 2022

🌍2.2 实验目的

掌握图形填充的基本技能；
理解区域填充算法，重点掌握扫描线填色算法。

🌍2.3 实验要求

使学生用Microsoft Visual Studio 2022编程；
掌握扫描线填色算法（要求yaoqiu 要求构造几何图形并填充）。

🌍2.4 实验原理

区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。

填色算法分为两大类：

扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。
种子填色（Seed Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。

扫描线填色算法的基本思想是：用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。

🌍2.5 实验步骤

新建工程，绘制几何图形，同时进行扫描线添色。

🌕2.5.1 扫描线填色算法

#define NDEBUG
#ifndef GLUT_DISABLE_ATEXIT_HACK
#define GLUT_DISABLE_ATEXIT_HACK
#endif
#include <windows.h>
#include <gl/glut.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
void setPixel(int xCoord, int yCoord) {
  glBegin(GL_POINTS); {
    glVertex2i(xCoord, yCoord);
  }
  glEnd();
}
//点类
struct Point {
  int x, y;
  Point() :x(0), y(0) {}
  Point(int nx, int ny) :x(nx), y(ny) {}
};
//边类
struct Edge {
  float x;
  float dx;
  int yMax;
  Edge() :x(0), dx(0), yMax(0) {}
  Edge(float nx, float ndx, int nyMax) :x(nx), dx(ndx), yMax(nyMax) {}
};
bool cmp_x(Point p1, Point p2) {
  return p1.x < p2.x;
}
bool cmp_y(Point p1, Point p2) {
  return p1.y < p2.y;
}
void boundaryFill(vector <Point> pointList) {
  int pointNum = pointList.size();
  vector<Point> pointListCopy(pointList);
  sort(pointListCopy.begin(), pointListCopy.end(), cmp_y);
  int yMin = pointListCopy.at(0).y;
  int yMax = pointListCopy.at(pointNum - 1).y;
  //初始化边表ET & 活动边表AET
  list<Edge> ET[500];
  list<Edge> AET;
  AET.push_back(Edge());
  //建立边表ET
  for (int i = 0; i < pointNum; ++i) {
    int x0 = pointList.at(i).x;
    int y0 = pointList.at(i).y;
    int x1 = pointList.at((i + 1) % pointNum).x;
    int y1 = pointList.at((i + 1) % pointNum).y;
    if (y0 == y1) {
      continue;
    }
    int yMinNow = min(y0, y1);
    int yMaxNow = max(y0, y1);
    float x = y0 < y1 ? x0 : x1;
    float dx = (x0 - x1) * 1.0 / (y0 - y1);
    ET[yMinNow].push_back(Edge(x, dx, yMaxNow));
  }
  for (int i = yMin; i < yMax; ++i) {
    for (auto j = ET[i].begin(); j != ET[i].end();) {
      auto pAET = AET.begin();
      auto end = AET.end();
      for (; pAET != end; ++pAET) {
        if (pAET->x > j->x) {
          break;
        }
        if (j->x == pAET->x && j->dx < pAET->dx) {
          break;
        }
      }
      AET.insert(pAET, *j);
      j = ET[i].erase(j);
    }
    for (auto temp = AET.begin(); temp != AET.end();) {
      if (temp->yMax == i) {
        temp = AET.erase(temp);
      }
      else {
        temp++;
      }
    }
    auto pAET = AET.begin();
    pAET++; 
    auto pAET_next = pAET;
    pAET_next++;
    int count = AET.size() - 1;
    while (count >= 2) {
      for (int x = pAET->x; x < pAET_next->x; ++x) {
        setPixel(x, i);
      }
      pAET++;
      pAET++;
      pAET_next = pAET;
      count -= 2;
    }
    for (auto& temp : AET) {
      temp.x += temp.dx;
    }
  }
  return;
}
//绘制程序
void display() {
  vector <Point> pointList1;
  pointList1.push_back(Point(100, 100));
  pointList1.push_back(Point(300, 100));
  pointList1.push_back(Point(100, 500));
  pointList1.push_back(Point(300, 500));
  pointList1.push_back(Point(50, 350));
  pointList1.push_back(Point(350, 350));
  vector <Point> pointList2;
  pointList2.push_back(Point(100, 300));
  pointList2.push_back(Point(280, 285));
  pointList2.push_back(Point(280, 170));
  pointList2.push_back(Point(340, 100));
  pointList2.push_back(Point(340, 340));
  pointList2.push_back(Point(100, 340));
  glClear(GL_COLOR_BUFFER_BIT);
  glColor3f(0.0, 1.0, 1.0);
  boundaryFill(pointList1);
  boundaryFill(pointList2);
  glutSwapBuffers();
  return;
}
void init() {
  glClearColor(1.0, 0.8, 1.0, 1.0);
  glColor3f(0.0, 0.5, 0.5);
  glPointSize(1.0);
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  gluOrtho2D(0.0, 1000.0, 0.0, 1000.0);
}
int main(int argc, char** argv) {
  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
  glutInitWindowPosition(250, 250);
  glutInitWindowSize(600, 500);
  glutCreateWindow("GLUT_Project_1");
  init();
  glutDisplayFunc(display);
  glutMainLoop();
  return 0;
}

运行结果：

🌕2.5.2 动态烟花算法

#include <easyx.h>
#include <cmath>
#include <ctime>
#include <list>
long ret_useless = 0;       
const int GW = 640;       
const int GH = 480;       
const double g = 9.8;       
const double PI = 3.1415926;
const int len_max = 80;     
const int h_max = GH - len_max;   
const double v_max = sqrt(2 * g * h_max / 10);
//除以10的缘故是公式是用m做单位,1m代表10个像素点
const int n_max = 5;        // Maximum number of fireworks on the screen烟花在屏幕上同时存在最多的数量
/* *************** LightLine *************** */
class LightLine
{
public:
  LightLine(int, double);
  void Draw() const;
  void Move();
  bool Stopped() const { return v == 0; }
  bool OverLine() const { return py < h_max* n_max / (n_max + 1); } 
  int GetX() const { return px; }
  int GetY() const { return py; }
private:
  int px;       // Position_x
  int py;       // Position_y
  int len;      // Length
  double v;     // Velocity (The -y axis is positiva)速度(Y轴是正的)
  clock_t ct = 0;   
};
LightLine::LightLine(int x = rand() % (GW - 80) + 40, double vv = (rand() % 20 + 80.0) / 100 * v_max) :px(x), py(h_max)
{
  v = vv;               //初始速度决定了可以达到的高度
  len = int(v / v_max * len_max);   // v : v_max = len : len_max速度快的，尾影会拖得长一些
}
void LightLine::Draw() const
{
  srand((unsigned)(time)(NULL));
  int Light_color = rand() % 360;
  //绘制上升曲线，是一列圆的绘制，第一个圆形亮度最高，后面的亮度逐渐减少，达到渐变的效果
  for (int j = py; j < py + len; ++j)
  {
    float hsv_v = 0.8f * (len - (j - py)) / len + 0.2f;   // Gradient color这是亮度
    setfillcolor(HSVtoRGB(float(Light_color), 1.0f, hsv_v));
    solidcircle(px, j, 1);
  }
}
void LightLine::Move()
{
  if (v == 0)
    return;
  if (ct == 0)
  {
    ct = clock();
    Draw();
    return;
  }
  clock_t t = clock() - ct;
  ct = clock();
  double v_cur = v - g * t / 1000.0;
  //除以1000的原因是，公式是以s做单位，程序里是ms作为单位，1s=1000ms
  if (v_cur > 0)
  {
    py += int(10 * (v_cur * v_cur - v * v) / 2 / g);//上升运动高度  vt^2-v0=2gh
    v = v_cur;
  }
  else
  {
    //如果v_cur<0，则表示可以到顶点了。
    py -= int(10 * v * v / 2 / g);//自由落体的高度 0-vt^2=2gh
    v = 0;//因为顶点烟花爆炸
  }
  len = int(v / v_max * len_max);
  Draw();
}
/* *************** ParticleSwarm *************** */
class ParticleSwarm
{
  struct Particle
  {
    int x;      //表示粒子的运动过程的x坐标
    int y;      //表示粒子的运动过程的y坐标
    int z = 0;    // Z axis vertical screen inword Z轴垂直屏幕输入
    double vy;    //  The y axis is positiva for the velocity结构体里面的vy是每个粒子的y方向速度
    Particle(int xx, int yy, double vv) :x(xx), y(yy), vy(vv) {}
  };
public:
  ParticleSwarm(int, int, float);
  void Draw() const;
  void Move();
  bool Finish() const { return vec.size() <= 1; }
private:
  double vx;
  double vz = 0;
  float hsv_h;          // Color parameter
  clock_t ct = 0;
  std::list<Particle> vec;    // For saving particles
};
ParticleSwarm::ParticleSwarm(int x, int y, float colorh = float(rand() % 256))
{
  hsv_h = colorh + rand() % 20;
  hsv_h = hsv_h > 255 ? hsv_h - 256 : hsv_h;
  //Z轴的负向对着人，即人对着屏幕的方向为Z轴的正向
  double vm = v_max / 2 * (rand() % 5 + 15.0) / 25.0;
  double radian_xz = (rand() % 360) * PI / 180;//X轴偏向Z轴的角度0--2*PI
  double radian_xy = (rand() % 90) * PI / 180 + PI / 2;//X轴偏向Y轴的角度PI/2--PI
  vx = vm * cos(radian_xy) * cos(radian_xz);//向量在X轴的投影
  vz = vm * cos(radian_xy) * sin(radian_xz);//向量在Z轴的投影
  double vy = vm * sin(radian_xy); //向量在Y轴的投影
  //len表示粒子运动轨迹的长度，也可以认为是装填粒子的数量
  int len = rand() % 30 + 50;//rand() % 30 + 50这个是源代码的数值，数值越大，烟花爆炸的范围，散开的范围就越大。
  //这一段刻画的是爆炸花束粒子中的其中一条线
  while (len)
  {
    // Use len as time parameter
    //目标像素位置＝初始像素位置+偏移米×10
    int xx = x + int(10 * vx * len / 200.0);
    //int zz = int(10 * vz * len / 200.0);
    double cvy = vy - g * len / 200.0;
    int yy = y + int(10 * (cvy * cvy - vy * vy) / 2 / g);
    vec.push_back(Particle(xx, yy, cvy));
    --len;
  }
}
void ParticleSwarm::Draw() const
{
  int n = 0;
  auto size = vec.size();
  for (auto& x : vec)
  {
    if (x.x >= 0 && x.x < GW && x.y >= 0 && x.y < GH)
    {
      //烟花线条的尾端亮度最低，反之首端是比较亮的
      float cv = 0.2f + 0.8f * (size - n) / size - x.z; //原来的float cv = 0.2f + 0.8f * (size - n) / size - x.z / 40 * 0.1f
      auto color = HSVtoRGB(hsv_h, 1.0f, cv > 0 ? cv : 0);
      if (x.z < 0)    // Z axis vertical screen inword如果烟花是往屏幕外扩散的话，就把像素点变大
      {
        setfillcolor(color);
        solidcircle(x.x, x.y, abs(x.z) / 80 > 1 ? 2 : 1);
      }
      else
        putpixel(x.x, x.y, color);
    }
    ++n;
  }
}
void ParticleSwarm::Move()
{
  if (ct == 0)
  {
    ct = clock();
    Draw();
    return;
  }
  for (int i = 0; i < 3 && vec.size() > 1; i++)//
    vec.pop_back();   // Delete particles for shortening length画面每次刷新删除3个末尾粒子
  clock_t t = clock() - ct;
  ct = clock();
  for (auto& x : vec)//爆炸花束之中一条光纤的粒子持续运动
  {
    double vy_cur = x.vy - g * t / 1000.0;
    x.x += int(10 * vx * t / 1000.0);
    x.y += int(10 * (vy_cur * vy_cur - x.vy * x.vy) / 2 / g);
    x.z += int(10 * vz * t / 1000.0);
    x.vy = vy_cur;
  }
  Draw();
}
/* *************** Fireworks *************** */
class Fireworks
{
public:
  Fireworks(int, int);
  void Move();
  bool Empty() const { return vec.empty(); }
private:
  std::list<ParticleSwarm> vec;
};
Fireworks::Fireworks(int x, int y)
{
  bool colorful = rand() % 100 < 20 ? true : false;//1/5的几率判断
  float h = float(rand() % 256);
  int n = rand() % 5 + 45;//烟花升到顶点后，爆炸出来的光线量
  for (int i = 0; i < n; i++)
  {
    if (colorful)//决定烟花的爆炸光线，每一条是否是同一颜色的。1/5的几率判断
      vec.push_back(ParticleSwarm(x, y));
    else
      vec.push_back(ParticleSwarm(x, y, h));
  }
}
void Fireworks::Move()
{
  std::list<decltype(vec.begin())> toDel;
  for (auto it = vec.begin(); it != vec.end(); ++it)
  {
    if (it->Finish())//如果该粒子群里的粒子数只剩下一个，则跳过
    {
      toDel.push_back(it);
      continue;
    }
    it->Move();//如果粒子群里的粒子数不只是剩下一个，则继续描画它的轨迹
  }
  for (auto& x : toDel)
    vec.erase(x);
}
/* *************** main *************** */
int main()
{
  initgraph(GW, GH);
  setrop2(R2_MERGEPEN);
  srand((unsigned)time(nullptr));
  // Refresh once in 50ms
  clock_t ct = clock();
  // LightLine list
  std::list<LightLine> vec;
  vec.push_back(LightLine());
  // Fireworks list
  std::list<Fireworks> vec2;
  BeginBatchDraw();
  while (!(GetAsyncKeyState(VK_ESCAPE) & 0x8000))
  {
    if (clock() - ct > 50)
    {
      cleardevice();
      ct = clock();
      std::list<decltype(vec.begin())> toDel;
      if (vec.size() == 0)
        vec.push_back(LightLine());
      else if (vec.size() < n_max && rand() % 100 < 20 && (--vec.end())->OverLine())
        vec.push_back(LightLine());
      for (auto it = vec.begin(); it != vec.end(); ++it)
      {
        if (it->Stopped())
        {
          vec2.push_back(Fireworks(it->GetX(), it->GetY()));
          toDel.push_back(it);
          continue;
        }
        it->Move();
      }
      for (auto& it : toDel)
        vec.erase(it);
      std::list<decltype(vec2.begin())> toDel2;
      for (auto it = vec2.begin(); it != vec2.end(); ++it)
      {
        if (it->Empty())
        {
          toDel2.push_back(it);
          continue;
        }
        it->Move();
      }
      for (auto& it : toDel2)
        vec2.erase(it);
      FlushBatchDraw();
    }
    Sleep(1);
  }
  EndBatchDraw();
  closegraph();
  return 0;
}

运行结果：

🌍2.6 研究体会

图形填充技能的掌握：通过本次实验，我成功掌握了图形填充的基本技能，了解了区域填充算法，并重点掌握了扫描线填色算法。在使用Visual Studio 2022开发平台编程的过程中，我能够在自己构造的几何区域进行填充操作。这为我在图形学领域的实际应用提供了坚实的基础。
烟花程序的实现：这次实验不仅帮助我完成了图形填充技能的学习，还让我圆了大一时候的烟花程序的愿望。之前由于使用dev-c++平台，无法成功搭建环境，但这次在Visual Studio 2022中成功搭建了相应的环境，并尝试实现了烟花爆炸的程序。这使我对C++的制图能力更加自信，也为我在图形学领域的兴趣提供了更多的可能性。
学习过程中的挑战和成长：在实验过程中，我花费了较多的时间在控制图像生成方面，包括输出面板的底色、图像初始位置的控制以及输出框的大小控制。由于之前使用的是dev-c++平台，初次使用Visual Studio 2022并不是很顺手，因此我不得不花费一些时间在网络上自学。最终，通过付出的努力，我成功解决了这些挑战，看到最终的运行结果，我感到付出的努力得到了回报。这次学习也让我更加注重虚心学习，静心思考，相信这样的态度将在以后的学习和工作中带来更多的成长。

📝总结

图形学领域宛如一片广阔而未被完全探索的创意海洋，邀请你勇敢踏足数字艺术和计算机图形学的神秘领域。这是一场富有创意和技术挑战的学习之旅，从基础概念到算法实现，逐步揭示更深层次的图形分析、渲染技术和智能图形识别的奥秘。

【图形学】探秘图形学奥秘：区域填充的解密与实战

🌌1. 初识模式识别

🌌2. 区域填充

🌍2.1 开发环境及实现

🌍2.2 实验目的

🌍2.3 实验要求

🌍2.4 实验原理

🌍2.5 实验步骤

🌕2.5.1 扫描线填色算法

🌕2.5.2 动态烟花算法

🌍2.6 研究体会

📝总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景