图形学篇：图形学基础知识汇总（上：基础知识和图形扫描转换及填充）

导论

计算机图形学的概念

计算机图形学是一门研究如何利用计算机表示，生成，处理和显示图形的学科。
计算机图形学是建立在“线性代数”，“数据结构”和“程序设计语言”基础上的一门学科。
图形主要分为两类，一类是基于线条表示的几何图形，如线框图，工程制图，等高线地图等，另一类是基于材质，纹理和光照表示的真实感图形。

图形显示器的发展及其工作原理

阴级射线管（CRT）

CRT是光栅扫描显示器的显示部件，主要由电子枪，偏转系统，荫罩板，荧光粉层以及玻璃外壳五大部分组成。
当平布刷新率大于或等于60Hz时，人眼就不会感到图像的闪烁。目前常用的屏幕刷新率为85Hz。
CRT的一个重要技术指标是分辨率，即CRT在水平方向上能识别出的最大光点数。

随机扫描显示器（RSD:random scan display）

广泛推广使用于20世纪60年代，如今随机扫描显示器的应用范围已经非常有限，电学实验中仍然在使用的示波器就是其中一种。

直视存储管显示器（DVST）

发展于20世纪70年代，DVST使用紧贴在荧光粉层后的存储栅的电荷分布来存储图形。
DVST有两只电子枪，一支是写电子枪，用以储存图形；另一只是读电子枪，用来显示图形。
DVST不能局部刷新图像，不能用光笔进行交互，反差弱。

光栅扫描显示器（RSD:raster scan display）（我们的童年，大头显示器）

画点设备

RSD是画点设备，可以看做是一个点阵单元发生器，并可控制每个点阵单元的颜色，这些点阵单元被称为像素。

位面与帧缓冲

帧缓冲器是显存内用于储存帧图像的一块连续内存空间。

视频控制器

视频控制器用于在帧缓冲与屏幕之间建立起一一对应的关系

液晶显示器（LCD）

LCD是采用了液晶控制透光度技术来生成图形的显示器。

三维图形显示原理及立体显示器

利用视差的高级玩意。

MFC绘图基础

双缓冲动画技术的原理

双缓冲是一种基本的动画技术，主要用于解决单缓冲擦除图像时所带来的屏幕闪烁问题。
所谓双缓冲是指一个屏幕设备上下文和一个内存设备上下文。

基本图形的扫描转换

光栅扫描显示器是画点设备，基本图形的光栅化就是在像素点阵中确定最佳逼近于理想图形的像素点集，并用指定颜色显示这些像素点集的过程。
当光栅化与按扫描线顺序绘制图形的过程结合在一起时，也称为扫描转换。

直线的扫描转换

直线扫描转换是在屏幕像素点阵中确定最佳逼近于理想直线的像素点集的过程。
计算机图形学要求直线的绘制速度要快，即尽量使用加减法，避免乘，除，开方，三角等复杂运算。

算法原理

直线中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走取决于重点误差项的值。
给定理想直线的起始点坐标为$P_0(x_0,y_0)$，终点坐标为$P_1(x_1,y_1)$，则直线的隐函数方程为

$F(x,y)=y-kx-b=0$

其中，直线的斜率$k=\frac{\operatorname\Delta y}{\operatorname\Delta x}=\frac{y_1-y_0}{x_1-x_0}$,$\operatorname\Delta x=x_1-x_0$为直线水平方向位移，$\operatorname\Delta y=y_1-y_0$为直线垂直方向位移，b是直线在y轴上的截距。
理想直线将平面划分为3个区域：对于直线上的点，F(x,y)=0；对于直线上方的点F(x,y)>0；对于直线下方的点，F(x,y)<0
然后根据中点误差项判断哪个像素点距离直线近，便选取那个像素点作为下一目标点即可。

圆的扫描转换

算法原理

圆心在原点，半径为R的圆方程的隐函数表达式为

$F\left(x,y\right)=x^2+y^2-R^2=0$

圆将平面划分为3个区域：对于圆上的点，$F\left(x,y\right)=0$；对于圆外的点,$F\left(x,y\right)>0$，对于圆内的点，$F\left(x,y\right)<0$
根据圆的对称性，可以用4条对称轴x=0;y=0;x=y;x=-y将圆分成8等份。只要绘制出第一象限内的1/8圆弧，就能根据对称性绘制出整圆。
根据中点误差项取得下一像素点方法与直线的扫描转换类似。

反走样技术

直线扫描转换算法在处理非水平，非垂直且非45°的直线段时会出现锯齿，这是因为直线段在光栅扫描显示器上显示的图像是由一系列亮度相同而面积不为0的离散像素点构成的。这种离散量表示连续量而引起的失真称为走样。
用于减轻走样现象的技术称为反走样或者称为抗锯齿。
走样是理想直线（理想直线宽度为0）扫描转换后（真实像素点面积不为0）的必然结果。
走样是光栅扫描显示器的一种固有现象，不可避免，只能减轻。
反走样技术主要分为两类：一类是硬件技术，通过提高显示器的分辨率来实现，另一类是软件技术，通过改进软件算法来实现。

直线反走样Wu算法

Wu反走样算法是根据像素和理想直线的距离对相邻两个像素的亮度等级进行调节。
Wu反走样算法是采用空间混色原理来对走样进行修正，
空间混色原理指出，人眼对某一区域颜色的识别是取这个区域颜色的平均值。
Wu反走样算法原理是对于理想直线上的任意一点，同时用两个不同亮度等级的相邻像素来表示。

RGB小插曲

在RGB(bRed,bGreen,bBlue)宏中，当bRed，bGreen，bBlue这三个值得变化率不同步时，出现彩色；
当bRed，bGreen，bBlue这三个值的变化率同步时，出现不同等级的亮度。
bRed，bGreen，bBlue这三个分量的值都在0~255之间，共有256种亮度等级并且规定亮度等级越大，也就是亮度值越大，像素越亮。
如RGB(255,255,255)表示白色，RGB(0,0,0)表示黑色。
Wu算法将亮度等级规范化到[0,1]闭区间，使用时乘以255即可。

使用距离误差项进行加权操作

设通过原点的直线方程为

$y=kx+b$

设理想直线段当前像素点为${\mathrm P}_{\mathrm i}\left({\mathrm x}_{\mathrm i},{\mathrm y}_{\mathrm i}\right)$在主位移x方向上走一步，下一像素点只能在${\mathrm P}_{\mathrm u}\left({\mathrm x}_{\mathrm i+1},{\mathrm y}_{\mathrm i+1}\right)$和${\mathrm P}_{\mathrm d}\left({\mathrm x}_{\mathrm i+1},{\mathrm y}_{\mathrm i}\right)$中选取。
理想直线段${\mathrm P}_{\mathrm u}$和${\mathrm P}_{\mathrm d}$像素中心连线的交点为${\mathrm Q}_{\mathrm i}$。${\mathrm e}_{\mathrm i}$为${\mathrm Q}_{\mathrm i}$到${\mathrm P}_{\mathrm d}$的距离。
设${\mathrm P}_{\mathrm d}\left({\mathrm x}_{\mathrm i+1},{\mathrm y}_{\mathrm i}\right)$像素的亮度等级为$RGB\left(e_ix255,e_ix255,e_ix255\right)$,${\mathrm P}_{\mathrm u}\left({\mathrm x}_{\mathrm i+1},{\mathrm y}_{\mathrm i+1}\right)$像素的亮度等级为$RGB\left((1-e_i)x255,(1-e_i)x255,(1-e_i)x255\right)$。
当$e_i>0.5$时，直线更接近于像素点$P_u$；当$e_i<0.5$时，直线更接近于像素点$P_d$；当$e_i=0.5$时，约定取$P_d$

对于$e_i$的计算机化

取$e_i$得初始值为0，主位移方向每走一步，即$x_{i+1}=x_i+1$时，有$e_{i+1}=e_i+k$。
如果${\mathrm e}_{\mathrm i}\geq1$，那么$y_{i+1}=y_i+1$，$e_{i+1}=e_i-1$
例如P点距离理想直线距离为0.5个像素远，那么该像素的亮度就为50%
Wu算法是用两个像素来共同表示理想直线上一个点，依据两个像素与理想直线的距离而调节其亮度等级，使所绘制的直线达到视觉上消除锯齿的效果。实际使用中，两个像素宽的直线反走样的效果更好，视觉效果上直线的宽度会有所减少，看起来好像是一个像素宽度的直线。

多边形填充

前言

在真实感图形的绘制过程中，三维物体表面常被网格化成多个三角形网格或者四边形网格，由于所划分的网格数量众多，所以三角形网格或四边形网格的填充效率直接决定了真实感图形的渲染速度。

多边形的表示

顶点表示法

多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观，占内存少，易于进行几何变换。但由于没有明确指出那些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换后才能逐条扫描线填充。

点阵表示法

多边形的点阵表示法是用位于多边形内的像素点集来描述，这种表示方法虽然失去了许多重要的几何信息，如顶点，边界等，但便于运用帧缓冲来表示图形，方便直接读取像素来更改多边形的填充色。

多边形的扫描转换

将多边形的描述从顶点表示法变换到点阵表示法的过程，成为多边形的扫描转换。
即从多边形的顶点信息出发，求出位于多边形内部的的各个像素点信息，并将其颜色值写入帧缓冲的相应单元中。

有效边表填充算法

https://www.lfzxb.top/graphicslearning_rectbucket/

多边形边缘填充算法的基本原理

边缘填充算法是先求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部取反色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。

区域填充算法

填充原理

对于多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子算法进行填充。
种子填充算法是从
区域内任意个种子像素开始，由内向外将填充色扩散到整个多边形区域的填充过程。
种子填充算法突出的优点是能对具有任意复杂边界的区域进行填充。

四邻接点与八邻接点

四邻接点定义

对于多边形区域内部任意一个种子像素，其左，上，右，下这4个像素成为四邻接点。

八邻接点定义

对于多边形区域内部任意一个种子像素，其左，上，右，下以及左上，右上，右下，左下这8个像素称为八邻接点。

四连通域和八连通域

四连通域定义

从多边形区域内部任意一个种子像素出发，通过访问其左，上，右，下这4个邻接点可以遍历区域内的所有像素，该多边形称为四连通域。

八连通域定义

从多边形区域内部任意一个种子像素出发，通过访问其左，上，右，下，左上，右上，右下，左下这8个邻接点可以遍历区域内的所有像素，该多边形称为八连通域。

四连通域和八连通域的关系

对于四连通域，其边界既可以是四连通的也可以是八连通的。
对于八连通域，其边界必须是四连通的，而不能是八连通的。
四连通域一定是八连通域，而八连通域不一定是四连通域。

种子填充算法

算法定义

从种子像素点开始，使用四邻接点方式搜索下一像素点的填充算法称为四邻接点种子填充算法。
从种子像素点开始，使用八邻接点方式搜索下一像素点的填充算法称为八邻接点种子填充算法。
四邻接点种子填充算法的缺点是不能通过狭窄区域，即不能填充八连通域。
八邻接点种子填充算法既能填充四连通域，也能填充八连通域。

算法原理

先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行以下三步

• 栈顶像素出栈
• 按填充色绘制出栈像素
• 按左，上，右，下（或左，左上，上，右上，右，右下，下，左下）顺序搜索与出栈像素相邻的4（或8）个像素，若该像素的颜色不是边界色并且未设置成填充色，则把该像素入栈，否则丢弃该像素。