图形学中的光栅化与三角形填充算法
光栅化和三角形填充算法是图形学中常用的技术，用于在计算机图形学中将2D或3D场景转换为最终在屏幕上呈现的图像。本文将介绍光栅化和三角形填充算法的原理、应用和实现。
一、光栅化算法
光栅化算法是指将连续的几何图形转化为离散的像素点的过程。在计算机图形学中，屏幕被划分为一个个像素点的网格，每个像素点的颜色值由计算机确定。通过光栅化算法，可以将几何图形的顶点信息转化为像素点的颜色值，从而实现图形的显示。
常用的光栅化算法有扫描线光栅化算法和射线光栅化算法。
1.扫描线光栅化算法
扫描线光栅化算法逐行扫描图形，通过判断扫描线与几何图形的交点，确定像素点的颜色值。这种算法适用于任意形状的几何图形。在扫描线光栅化算法中，一般需要考虑图形的边界条件、插值计算和像素点的填充等问题。 2.射线光栅化算法
射线光栅化算法通过从特定点向几何图形发射射线，并计算射线与几何图形的交点，确定像素点的颜色值。这种算法适用于封闭的几何图形，如圆、椭圆等。在射线光栅化算法中，常用的算法有中点画圆算法、Bresenham算法等。
光栅化算法广泛应用于计算机图形学中，用于生成点、线、多边形等几何图形的像素点的颜色值，从而实现图像的显示。光栅化算法在计算机游戏、计算机辅助设计等领域有着广泛的应用。
二、三角形填充算法
三角形填充算法是指将一个给定的三角形填充为实心或渐变颜色的过程。在计算机图形学中，三角形是最基本的几何图形，通过三角形填充算法可以实现更复杂图形的显示和渲染。
常用的三角形填充算法有扫描线填充算法和边缘填充算法。
1.扫描线填充算法 扫描线填充算法是通过遍历三角形内的每一行像素点，并判断像素点是否在三角形内部，从而确定像素点的颜色值。该算法简单直观，但对于复杂的三角形可能效率较低。
2.边缘填充算法
边缘填充算法是通过扫描三角形的边缘，并根据每个像素点的位置关系确定颜色值。常用的边缘填充算法有中点边缘填充算法、贝塞尔曲线填充算法等。边缘填充算法相对于扫描线填充算法更高效，尤其适用于大规模的三角形填充。
扫描线多边形填充算法例题
扫描线多边形填充算法是一种常用的计算机图形学算法，用于对多边形进行填充。下面我将以一个例题来说明该算法的步骤和原理。
假设有一个凸多边形，顶点坐标分别为A(2, 4)，B(6, 6)，C(8, 4)，D(6, 2)，E(4, 2)。现在我们要使用扫描线多边形填充算法对该多边形进行填充。
步骤如下：
1. 首先，确定扫描线的范围。扫描线的范围由多边形的最高点和最低点决定，即在本例中扫描线的范围为y=2到y=6。
2. 从最高点开始，逐行进行扫描线填充。在本例中，从y=6开始扫描。
3. 对于每一条扫描线，确定与多边形交点的x坐标。在本例中，对于y=6，与多边形交点的x坐标为x=2和x=6。
4. 将交点按照升序排列，得到交点序列。在本例中，交点序列为(2, 6)，(6, 6)。
5. 根据交点序列，对每一对交点进行填充。在本例中，对于(2,
6)和(6, 6)，在扫描线y=6上的像素点进行填充。
6. 继续向下扫描，重复步骤3至步骤5，直到扫描到最低点y=2。
通过以上步骤，我们可以完成对该凸多边形的填充。
需要注意的是，如果多边形是凹多边形，那么在步骤3中，可能会出现多个交点。此时，需要根据扫描线与多边形的交点个数的奇偶性来确定填充的规则。
扫描线多边形填充算法的原理是通过扫描线与多边形的交点来确定填充的区域。该算法的优点是简单易懂，适用于凸多边形和简单的凹多边形。然而，对于复杂的凹多边形，该算法可能会遇到一些困难。
希望以上回答能够满足你的要求。如果还有其他问题，请随时提出。
佛山科学技术学院
实 验 报 告
课程名称 计算机图形学基础
实验项目 多边形的区域填充
一、实验目的
1. 通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理
2. 掌握多边形区域填充算法的基本过程
3. 掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。
二、实验内容
用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。
三、实验原理
种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。
四向连通填充算法：
a） 种子像素压入栈中；
b） 如果栈为空，则转e)；否则转c)；
c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；
d） 转b）；
e） 结束。
扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。
区域填充的扫描线算法可由下列四个步骤实现：
(1)初始化：堆栈置空。将种子点(x,y)入栈。
(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。
(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。
(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。
计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念
区域：指已经表⽰成点阵形式的填充图形，是象素的集合。
区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。
区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。
1、区域有两种表⽰形式
1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。
2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。
2、区域连通
1）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。
2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区
域内的任意象素。⼆、简单种⼦填充算法基本思想
给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点
（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。
这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三
步：算法代码
这⾥给出⼋连通的种⼦填充算法的代码：
void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color)
{
if(x0&&y0)
{
if (pixels[y*w+x]==old_color)
{
pixels[y*w+x]== new_color);
flood_fill_8(pixels, x,y+1,old_color,new_color);
flood_fill_8(pixels, x,y-1,old_color,new_color);
