图形学课堂笔记1-图元
Published:
生活，我想，自有道理。假如它嘲笑了我的美梦，一定是我的梦太蠢，错得太离谱。
图元
图元通常是不可再分的独立的图形实体
基本二维图元包括点、直线、圆弧、多边形、字体符号和位图
点是由其坐标$(x,y)$来描述的, 直线由其两端点坐标来描述
基于光栅扫描器上, 所有的图形的显示都归结为按照图形描述将显示设备上的光栅像素点亮
基于光栅扫描的二维图形生成算法
曲线和各种复杂的图形均是离散成许多直线段来绘制，因而直线是二维图形生成技术的基础。 直线的绘制就是根据两端点坐标的描述来绘制两点间的直线路径。 理论上认为，根据直线的数学方程算出直线上的一个个点即可，但这样做运算效率不高。
直线绘制算法
直线的扫描变换 – 画直线的一般准则：
- 线条应该显得笔直
- 直线的端点应该准确
- 线宽均匀，且与斜率无关
- 显示线段的速度要快
直线的扫描变换 直线的扫描算法就是在显示器所给定的有限个象素组成的矩阵中，获得一系列像素的坐标，使得这些像素落在所要逼近的理想直线上或位于该直线的附近，并且按扫描线顺序，以指定的方式对这些象素进行写操作。
直线绘制的三个著名算法
- 数值微分法(Digtial Differential Analyzer Algorithm, DDA)
- 中点画线法
- Bresenham 算法
1、基本增量算法
对于线上的所有点$(x_i, y_i)$, 如果$x_{i+1} = x_i +1$, 那么$y_{i+1} = y_i +m$
其实这个很好理解, 之后也是经常使用到, 就是根据前一步算下一步,看 m 的取值范围来决定下一个点的位置, 因为这里x是均匀增加的, 每次求出x对应的y值, 再将$y’ = (int) (y+0.5)$下取整, 得到$(x, y’)$像素点坐标.
2、中点画线法
重点画线法其实也很好理解, 就是你想知道 $x_{k+1}$ 对应的 $y_{k+1}$ 是 $y_k$ 还是$y_k+1$. 中点画线法选用的是 $y_k$ 和 $y_k+1$ 的中点M来比较, 看中点M在直线上方还是下方, 如果是在直线上方, 说明直线更偏下一点.
中点画线法将算法提高到整数加法, 优于DDA算法
1、构造判别式
假定直线斜率 0 < k < 1，且已确定当前处理过的像素点$P(x_p,y_p)$，则下一个与直线最接近的像素只能是P1或P2。设M为P1与P2的中点，Q为交点。现确定下一个要画的像素的位置.
- 如果M在Q下方，则P2离直线近，取P2
- 如果M在Q上方，则P1离直线近，取P1
- M与Q重合，P1、P2任取一点。
问题转换为如何判断M与Q点的关系。
求解过程
假设直线方程为
\[F(x,y)=ax+by+c\]根据斜截方程
\[y=mx+b = (\dfrac{\Delta y}{\Delta x}x + B)\]从而我们可以得到
\[F(x,y) = \Delta y \cdot x -\Delta x \cdot y +B\cdot\Delta x = 0\]其中$a=y_1-y_2$, $b = x_0 - x_1$, $c = B\cdot(x_1 - x_0)$
则由数学知识可知有下面的关系：
- F(x, y) = 0，点在直线上方
- F(x, y) > 0，点在直线下方
- F(x, y) < 0，点在直线上方
所以，欲判断M点在Q点上方还是在Q点下方，只需要把中点M代入F(x,y)，并检查它的符号。
构造判别式：
\[d = F(M) = F(x_p+1, y_p+0.5) = a(x_p+1) + b(y_p+0.5) + c\]当d ≥ 0，M在直线(Q)下方，取右上方P2
当d < 0，M在直线(Q)上方，取右方P1
2、判别式的增量算法
其实这里就是通过p→d→d’→d’’→·····这里每次d都需要求P1和P2, 这里好的地方是我能通过d的符号直接递归来计算下一个d
当 d < 0, 此时取P1, 新的判别式为(将 $x_p+ 1$ 代入 $x_p$)
\[\begin{aligned} d_1 & = F(x_p+2, y_p+0.5) \\ & = a(x_p+2)+b(y_p+0.5)+c \\ & = a(x_p+1)+b(y_p+0.5)+c+a \\ & = d+a \end{aligned}\]此时的增量为 a
若 d ≥ 0, 此时取P2, 新的判别式为(将 $x_p+ 1$ , $y_p+ 1$ 代入 )
\[\begin{aligned} d_1 & = F(x_p+2, y_p+1.5) \\ & = a(x_p+2)+b(y_p+1.5)+c \\ & = a(x_p+1)+b(y_p+1.5)+c+a+b \\ & = d+a+b \end{aligned}\]增量为 a + b
3、判别式的初始值
画线从$(x_0, y_0)$开始, d 的初值
\[\begin{aligned} d_1 & = F(x_p+1, y_p+0.5) \\ & = a(x_p+1)+b(y_p+0.5)+c \\ & = F(x_0, y_0)+a+0.5b \\ & = a + 0.5b \end{aligned}\]由于只用d的符号作判断，为了只包含整数运算，可以用2d代替d来摆脱小数，提高效率。
4、其它斜率情形 用同样的推导过程，不难得出当直线斜率-1<k<0时： 当d≥0，此时再下一个像素的判别式为d1=d-a； 当d<0，此时再下一个像素的判别式为d2=d-a+b；
当斜率$\vert k\vert>1$时，将x,y坐标互换以完成递推过程。在画点时再将x,y坐标互换。
3、Bresenham算法
算法思想是通过各行、各列像素中心构造一组虚拟网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。
根据当前点，决定下一个（像素）点画在哪儿。要么在相邻点，要么在对角点。相邻点是指(x+1, y)，或者(x+1, y+1)
要确定2个备选点中的哪一个，可根据它们到直线的距离远近决定：如果相邻点更近，下一点选相邻点；如果对角点更近，下一点就选对角点。
为减少误差，用光栅直线逼近理论直线，Bresenham算法按变化大的轴（x轴或y轴）逐像素绘制线段。
这里是按x轴递增绘制像素点, 即$x_{k+1} = x_k +1$
首先假设斜率 0 < m < 1. 我们可以得到$\Delta x > \Delta y$. 所以$y_{k+1}$ 的值为$y_k$或者$y_{k}+1$. 所以第 k + 1 个点的选择为$(x_k +1 , y_k)$ 或者$(x_k +1, y_k+1)$
为了简化运算，Bresenham算法并没有用点到线的垂直距离，而是利用y轴或x轴方向的偏移替代。
我们先算一下理论值
\[y = mx_{k+1} = m(x_k+1)+b\]我们记刚刚选的两个备选点$(x_k +1 , y_k)$ 和 $(x_k +1, y_k+1)$ 到直线的偏移分别为$d_1$和$d_2$, 我们可以得到
\[\begin{aligned} d_1 &= y-y_k \\ & = m(x_k + 1) + b - y_k \end{aligned}\] \[\begin{aligned} d_2 &= (y_k+1) - y \\ & = y_k + 1 -m(x_k + 1) - b \end{aligned}\]这里利用了m范围 0 < m < 1, 有$d_1 > 0$, $d_2 > 0$, 可知
\[y_{x+1} = \begin{cases} y_k &\quad d_1 < d_2, \quad y_k更近\\ y_{k+1} &\quad d_2 \leq d_1, \quad y_{k+1}更近 \end{cases}\]这里要判断哪个点最近, 比较自然的想到将两个 d 做差值
\[d_1-d_2 = 2m(x_k+1) -2y_k+2b-1\]其中, 斜率 m, 截距 b 都是常数
将 $m = \dfrac{\Delta y}{\Delta x}$, 两边都同时乘以$\Delta x$, 可以得到
\[(d_1-d_2)\Delta x = 2(x_k+1) \Delta y-2y_k\Delta x+(2b-1)\Delta x\]令常数 $c= (2b-1)\Delta x$, 可以得到第 k 步的决策参数
\[\begin{aligned} p_k &= (d_1-d_2)\Delta x \\ & = 2(x_k+1) \Delta y-2y_k\Delta x+c \end{aligned}\]因为 m > 0, 所以 $\Delta x >0$ , 所以$p_k$和$d_1-d_2$同号
所以现在选P1还是P2的问题转变到了d1和d2的大小关系, 转变到了求$p_k$上
第一步、求$p_k$的递推公式
当 k = k + 1 时
\[p_{k+1} = 2(x_{k+1}+1) \Delta y-2y_k\Delta x+c\]我们得到递推公式
\[p_{k+1} - p_k = 2(x_{k+1} - x_k) \Delta y+2(y_{k+1} - y_k) \Delta x\]这里$x_{k+1} = x_k +1$, $y_{k+1} - y_k$的取值取决于$p_k$的符号
\[p_{x+1} = \begin{cases} p_k + 2\Delta y - 2\Delta x &\quad p_k \geq0 \\ p_{k}+ 2\Delta y &\quad p_k<0 \end{cases}\]第二步、求初始值$p_0$
起始点$(x_0, y_0)$在直线上
\[\begin{aligned} p_0 &= 2(x_{0}+1) \Delta y-2y_0\Delta x+c \\ & = 2(x_0+1) \Delta y-2y_0\Delta x+(2b-1)\Delta x \end{aligned}\] \[b=y_0 - m x_0 = y_0 - x_0 \dfrac{\Delta y}{\Delta x} = \Delta x y_0 - x_0 \Delta y\]所以我们能够得到
\[p_0 = 2\Delta y - \Delta x\]综上，可将 0 < m < 1 时，Bresenham画线算法归纳为如下步骤：
- 输入线段2端点，左端点存储在$(x_0,y_0)$；
- 将$(x_0,y_0)$装入帧缓存，画出第一个点；
- 计算常量$∆x,∆y,2∆y,2∆y−2∆x$，得到决策参数初值：$p_0=2∆y−∆x$
- 从k=0开始，沿着线段路径，每个$x_k$处，计算下一个要绘制的点位置：如果$p_k<0$，下一个要绘制点$(x_k+1,y_k)$，且$p_{k+1}=pk+2∆y$；否则，下一个要绘制点$(x_k+1,y_k+1)$，且$p{k+1}=p_k+2∆y−2∆x$；
- 重复步骤4)，共计∆x-1次。
圆弧绘制算法
二次曲线是指那些能用二次函数
\[Ax^2+Bxy+Cy^2+Dx+Ey+F=0\]表示的曲线，包括圆弧、椭圆以及抛物线。它们的绘制通常是离散成相互连接的小直线段来逼近理想曲线的。这里主要介绍圆的绘制，其它曲线不再赘述。 圆的绘制算法有
- 逐点比较法
- Bresenham算法
- 中点画圆法
这些方法因为圆的对称性, 能够用四路或者八路对称来加速.
四路是生成1/4象限的圆弧, 其他的对称得到就行
八路的话是生成1/8象限的圆弧, 其他部分全部由对称规则生成
1、Bresenham算法
Bresenham画圆算法适合于生成整圆，它使用八路对称法，只计算出90º到45º范围内的点，移动方向为+x, -y。设$(x_i, y_i)$是扫描到第i步时选定的坐标，下一个被选定的可能是T或S。
令D(T)为T点到原点距离的平方与半径的平方之差，D(S)为S点到原点距离与半径平方之差。令P的坐标为$(x_i, y_i)$，则T点的坐标为$(x_i+1, y_i)$，S的坐标为$(x_i+1, y_i-1)$。则
因为 $D(T) >0, D(S)<0$, 令变量$d_i = D(T)+D(S)$
\[d_i = 2(x_i + 1)^2 + y^2_i + (y_i - 1)^2 -2r^2\]- 当 $d_i < 0, \vert D(T)\vert < \vert D(S)\vert $ 选择像素 T；
- 当 $d_i \geq 0, \vert D(T)\vert \geq \vert D(S)\vert $, 选择像素 S。
判别式增量法
将 $d_i$ 的下标增1后得
\[d_{i+1} = 2(x_{i+1}+1)^2+y_{i+1}^2+(y_{i+1}-1)^2-2r^2,\quad x_{i+1}=x_i+1\]因此
\[d_{i+1}=d_i+4x_i+2(y_{i+1}-y_i)^2-2(y_{i+1}-y_i)+6\]如果$d_i<0$, 此时应该选 T, $y_{i+1}=y_i$, 上式变为
\[d_{i+1} = d_i +4x_i+6\]如果$d_i>0$, 此时应该选S, $y_{i+1}=y_i-1$, 上式变为
\[d_{i+1} = d_i+4(x_i-y_i)+10\]设(0, r)为递推公式的初始像素, 则shshshsh
\[\begin{aligned} d_0&=2(0+1)^2+r^2+(r-1)^2-2r^2\\ &=3-2r \end{aligned}\]
2、中点画圆算法
中点画圆法和Bresenham画圆法类似, 利用圆的八路对称法, 只需讨论1/8圆弧
假设P为当前点亮象素，那么下一个点亮的象素可能是$T(x_p+1, y_p)$或$S(x_p+1, y_p - 1)$。 令M为T和S和中点，M的坐标为$(x_p + 1, y_p - 0.5)$。构造一个函数
\[F(x, y)=x^2+y^2-r^2\]将中点M的坐标代入函数
若F(M) < 0，M在圆内，此时下一个点取T；
若F(M) ≥ 0，M在圆上或圆外，此时下一个点取S。
可采用判别式
\[\begin{aligned} d=F(M)&=F(x_p+1, y_p-0.5)\\ &=(x_p+1)^2+(y_p-0.5)^2-r^2 \end{aligned}\]假定当前判别式d为已知，且d<0，则T被选为新的点亮像素，
若d≥0，则S被选为新的点亮像素，则再下一个像素的判别式为
判别式增量法 假定当前判别式d为已知
若d<0，则T被选为新的点亮像素，那么再下一个像素的判别式为
\[\begin{aligned} d_1 &= F(M)=F(x_p+2, y_p-0.5)\\ &=(x_p+2)^2+(y_p-0.5)^2-r^2\\ &=d+2x_p+3 \end{aligned}\]故d的增量$2x_p+3$
若d≥0, 则S被选为新的点亮像素，则再下一个像素的判别式为
\[\begin{aligned} d_1 &= F(M)=F(x_p+2, y_p-1.5)\\ &=(x_p+2)^2+(y_p-1.5)^2-r^2\\ &=d+(2x_p+3) +(-2y_p+2) \end{aligned}\]即d的增量为$2(x_p - y_p) + 5$。
由于这里讨论的是按顺时针方向生成k>1的1/8圆弧，因此首点的坐标为(0, r)，因此d的初值为
\[\begin{aligned} d_1 &=F(0+1, r-0.5)\\ &=1+(r-0.5)^2-r^2\\ &=1.25-r \end{aligned}\]
3、角度离散法绘制圆弧
若已知圆心坐标为$(x_c, y_c)$，半径r，则以角度t为参数的圆的参数方程为
\[\begin{cases} x=x_c+r\cos t\\ y=y_c+r\sin t \end{cases}\]这里我们定义角度的正方向是逆时针方向，因此绘制方向也是逆时针的。
当t从0变化至2π时，上述方程所表示的轨迹是一整圆；当 t 从 $t_s$ 变化至 $t_e$ 时，则产生一段圆弧。 借助参数方程绘制曲线的方法都是将圆弧离散化为短直线段，该方法的好处是不需要直接处理每个像素点，这些像素点完全交由直线绘制算法来完成。
椭圆绘制算法
椭圆弧定义：到两个定点的距离之和为定长的点的集合。
假设：椭圆中心在坐标原点。
椭圆弧的几何特点
- 具有与圆弧类似的属性：
- 对称性
- 空间的正负划分性
椭圆标准方程:
\[\dfrac{x^2}{a^2}+\dfrac{y^2}{b^2}=1\]引入方程
\[f(x,y) = (bx)^2+(ay)^2-(ab)^2=0\]则 $f(x,y) >0$ 时, 点在椭圆外. $f(x,y) <0$ 时, 点在椭圆内
1、椭圆中点扫描转化算法
生成椭圆的中点算法和生成圆的中点算法在基本处理方法上是完全一致的，只不过椭圆的方程复杂一些，相应的计算过程也复杂一些。 中心在圆点的椭圆的方程为：
由于椭圆的对称性，我们只需要讨论第一象限内椭圆弧的生成。在第一象限内，我们进一步将该段椭圆弧分为上、下两部分，分界点为切线斜率等于-1的点（法向量的两个分量相等）
椭圆弧上一点处的切线
由椭圆方程
\[f(x,y) = (bx)^2+(ay)^2-(ab)^2=0\]得到微分方程
\[b^2\cdot x\cdot dx + a^2\cdot y \cdot dy=0\]即切线斜率为
\[k=\dfrac{\mathrm{d}y}{\mathrm{d}x}=-\dfrac{b^2\cdot x}{a^2\cdot y}\]割点位置计算:
- 切线斜率为–1的点
- 等价于计算梯度矢量斜率为1的点
这里我们回顾一下梯度点定义
\[F(x,y) = \dfrac{\partial F}{\partial x}\mathbf{i} + \dfrac{\partial F}{\partial y}\mathbf{j} = 2b^2x\mathbf{i} + 2a^2y\mathbf{j}\]
椭圆弧上任一点$(x,y)$的法向量
\[(\dfrac{\partial F(x,y)}{\partial x},\dfrac{\partial F(x,y)}{\partial y}) = (2b^2x, 2a^2y)\]由于切向量与法向量是垂直的，则分界点法向量斜率为1
还要注意到，上半部分的法向量斜率大于1，下半部分小于1
\[\begin{cases} b^2x=a^2y \quad分界点 \\ b^2x<a^2y \quad上半部分\\ b^2x>a^2y \quad下半部分\\ \end{cases}\]$(x,y)$点的切向与法向垂直, 为$(-2a^y, 2b^2x)$, 从而切线斜率为-1的点满足于
\[2b^2x=2a^2y\iff b^2x=a^2y\]代入椭圆方程可以求的斜率为-1的点点坐标为$P(\dfrac{a^2}{\sqrt{a^2+b^2}},\dfrac{b^2}{\sqrt{a^2+b^2}})$
如果我们从区域1到区域2, 下一个点满足$b^2(x_p+1)≥a^2\left(y_p-\dfrac{1}{2}\right)$
假设已计算出当前像素为$P=(X_p,Y_p)$，则下一个扫描列只可能是E和SE。中点$M=(X_p+1,Y_p-\dfrac{1}{2}))$。令$d=F(M)$
对于上半部分，切线斜率>-1
d=0 中点在椭圆上; 可取E 或 SE
d<0 中点在椭圆内; 取E
d>0 中点在椭圆外; 取SE
\[d_p = F(M) = F\left(x_p + 1, y_p - \dfrac{1}{2}\right) = b^2 (x_p + 1)^2 + a^2 \left(y_p - \dfrac{1}{2}\right)^2 - a^2 b^2\] \[\begin{aligned} d_{p+1} &= \begin{cases} F\left(x_p + 2, y_p - \dfrac{1}{2}\right) & d_p \leq 0, \quad\text{ 取 } E(x_p + 1, y_p) \\ F\left(x_p + 2, y_p - \dfrac{3}{2}\right) & d_p > 0, \quad\text{ 取 } SE(x_p + 1, y_p - 1) \end{cases}\\ &= \begin{cases} b^2 (x_p + 2)^2 + a^2 \left(y_p - \dfrac{1}{2}\right)^2 - a^2 b^2 \quad d_p \leq 0 \\ b^2 (x_p + 2)^2 + a^2 \left(y_p - \dfrac{3}{2}\right)^2 - a^2 b^2 \quad d_p > 0 \end{cases} \end{aligned}\] \[d_{p+1} = \begin{cases} d_p + b^2 (2x_p + 3) & d_p \leq 0 \\d_p + b^2 (2x_p + 3) + 2a^2 (1 - y_p) & d_p > 0 \end{cases}\]初始条件
\[\begin{cases} (x_0,y_0)=(0,b)\\ d_0=b^2+a^2(0.25-b) \end{cases}\]对于下半部分，切线斜率<-1
从点(a,0)开始，按每一扫描列由下往上扫描转换
假设已计算出当前像素为P=(Xp,Yp)，则下一个扫描列只可能是N和WN。中点$M=(X_p-\dfrac{1}{2},Y_p+1)$。
令d=F(M)
d=0 中点在椭圆上; 可取N 或WN
d<0 中点在椭圆内; 取N
d>0 中点在椭圆外; 取WN
\[d_p = F(M) = F\left(x_p - \dfrac{1}{2}, y_p +1\right) = b^2 (x_p -\dfrac{1}{2})^2 + a^2 \left(y_p + 1\right)^2 - a^2 b^2\] \[\begin{aligned} d_{p+1} &= \begin{cases} F\left(x_p -\dfrac{1}{2}, y_p +2\right) & d_p \leq 0, \quad\text{ 取 } N(x_p, y_p + 1) \\ F\left(x_p -\dfrac{3}{2}, y_p +2\right) & d_p > 0, \quad\text{ 取 } WN(x_p - 1, y_p + 1) \end{cases}\\ &= \begin{cases} b^2 \left(x_p -\dfrac{1}{2}\right)^2 + a^2 \left(y_p +2 \right)^2 - a^2 b^2 \quad d_p \leq 0 \\ b^2 \left(x_p -\dfrac{3}{2}\right)^2 + a^2 \left(y_p +2 \right)^2 - a^2 b^2 \quad d_p > 0 \end{cases} \end{aligned}\] \[d_{p+1} = \begin{cases} d_p + b^2 (2y_p + 3) & d_p \leq 0 \\d_p + b^2 (2y_p + 3) + 2a^2 (1 - x_p) & d_p > 0 \end{cases}\] \[\begin{cases} (x_0,y_0)=(a,0)\\ d_0=a^2+b^2(0.25-a) \end{cases}\]因为每次比较的都是中点的正负判别性，则从上半区转到下半区的过程中满足$b^2(x_p+1)≥a^2\left(y_p-\dfrac{1}{2}\right)$
由于初始条件包含小数，为避免浮点运算，可以采取两边乘以4的做法。
上半区
\[\begin{cases} (x_0,y_0)=(0,b)\\ d_0=b^2+a^2(0.25-b) \end{cases}\] \[\begin{cases} (x_0,y_0)=(0,b)\\ e_0=4b^2+a^2(1-4b) \end{cases}\] \[d_{p+1} = \begin{cases} d_p + b^2 (2x_p + 3) & d_p \leq 0 \\ d_p + b^2 (2x_p + 3) + 2a^2 (1 - y_p) & d_p > 0 \end{cases}\] \[e_{p+1} = \begin{cases} e_p + 4b^2 (2x_p + 3) & e_p \leq 0 \\ e_p + 4b^2 (2x_p + 3) + 8a^2 (1 - y_p) & e_p > 0 \end{cases}\]下半区
\[\begin{cases} (x_0,y_0)=(a,0)\\ d_0=a^2+b^2(0.25-a) \end{cases}\] \[\begin{cases} (x_0,y_0)=(a,0)\\ e_0=4a^2+b^2(1-4a) \end{cases}\] \[d_{p+1} = \begin{cases} d_p + b^2 (2y_p + 3) & d_p \leq 0 \\ d_p + b^2 (2y_p + 3) + 2a^2 (1 - x_p) & d_p > 0 \end{cases}\] \[e_{p+1} = \begin{cases} e_p + 4b^2 (2y_p + 3) & e_p \leq 0 \\ e_p + 4b^2 (2y_p + 3) + 8a^2 (1 - x_p) & e_p > 0 \end{cases}\]区域填充
具有相同颜色或图案属性的连片像素即区域。对区域中所有像素的填充着色的过程称为区域填充。
一类是给定顶点序列定义的封闭多边形。该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。
第二类区域是由所有已知边界像素包围起来的部分，即它是由点阵方式描述的区域。该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式。
第二类区域又有两种不同的定义：
一种是边界定义的区域(boundary-defined). 区域边界上像素颜色（亮度）已确定，但区域内部像素仍没有设置为指定的颜色(亮度). 将该区域中所有像素都着色的算法称为边界填充算法. 该区域的边界上和区域内的目标颜色值可以相同，也可以不同
另一种是内定义区域（interior-defined）. 这种方式下区域并无边界的概念，只划分为区域内和区域外两部分，区域外的所有像素已有特定的颜色（亮度）值. 区域内与区域外颜色（亮度）值不同，区域内所有像素的颜色需要修改为目标颜色。对内定义区域中的全部像素着色的算法称为漫水法（flood-fill algorithm）。经过漫水法填充后，区域内与区域外的颜色值不同
第一步先确定需要填充哪些像素
第二步确定用什么颜色填充
第三部确定填充类型
- 多边形填充
- 园域填充
- 图案填充
多边形扫描转换算法
多边形扫描转换算法是一种用于图形渲染的技术，用于将二维多边形转换为像素级别的图像。该算法基于以下原理：
- 连续性原理：多边形内部点的连续性表明，在一条扫描线与多边形的交点中，入点和出点之间的所有点都是多边形的内部点。因此，通过对所有扫描线填充入点到出点之间的所有点，可以实现多边形的填充。
- 局部连续性原理：该算法充分利用了同一扫描线上像素之间的连续性以及多边形的边与上下两条相邻扫描线的交点之间的连续性。这使得算法能够在局部范围内高效地处理像素填充。
算法步骤：
- 计算扫描线与多边形的相交区间：按照扫描线顺序，计算每条扫描线与多边形的相交区间。这些区间表示了多边形在每条扫描线上的可见部分。
- 确定区间的端点：区间的端点通过计算扫描线与多边形边界的交点而得到。这通常涉及解线性方程以确定交点的坐标。
- 填充区间内的像素：使用要求的颜色显示这些区间内的像素，从而实现多边形的填充。填充过程可以在硬件级别或软件级别实现，具体取决于所使用的图形系统。
算法优化：
为了提高算法的性能，可以采用以下优化策略：
- 边表（Edge Table）：使用边表数据结构存储多边形的边信息，以便快速查找与特定扫描线相交的边。
- 活性边表（Active Edge Table）：维护一个活性边表，用于存储当前扫描线与多边形相交的所有边。这有助于减少不必要的计算。
- 扫描线排序：对扫描线进行排序，以便更高效地处理相邻扫描线之间的连续性。
- 区域细分：对于复杂的多边形，可以将多边形细分为更小的区域，然后分别对这些区域进行扫描转换。这有助于减少计算复杂性并提高渲染质量。
多边形采用顶点序列表示时，如$P_0P_1P_2P_3P_4P_5$ ，把扫描线6分别与边$P_0P_1$，$P_1P_2$，$P_2P_3$，$P_3P_4$，$P_4P_5$，$P_5P_0$，相交，得到的交点序列是D、C、B、A. 必须经过重新排序，最终得到从左到右，按x递增顺序排列的交点.再根据x坐标序列配对，划分出填充区间
在多边形的填充算法中，关键是求扫描线与各边的交点问题，这里面有两个问题需要解决
- 当扫描线与多边形顶点相交时，交点的取舍问题，保证交点正确配对
- 多边形边界上像素的取舍问题，用于避免填充扩大化。