计算机图形学 第4章 多边形填充
目录
- 前置知识点
-
多边形扫描转换技术
-
有效边界表填充算法
-
原理部分
-
边界像素处理原则
-
如何计算交点
- 有效边界
-
桶表与边表
-
- 桶表表示法
-
-
边缘填充算法
-
- 填充过程
- 在这里插入图片描述
-
区域填充算法/种子填充算法
-
- 种子填充算法
- 扫描线种子填充算法 （更有效）
-
前驱知识
- 掌握扫描转换的基本概念。
- 深入理解并熟练运用多边形有效边表填充算法。
- 熟悉并能正确应用多边形边缘填充算法。
- 深入理解并熟练运用区域四邻接点和八邻接点区域填充算法的具体实现细节。
- 准确理解和应用区域扫描线种子填充算法的原理与操作流程。
不论采用何种着色方案，即要求每个像素点都要按照预设的颜色对多边形边界内的区域进行填充。
多边形的表示 有两种：⑴顶点表示法；⑵点阵表示法
多边形的扫描转换
定义：将其称为多边形的扫描转换的过程。其顶点坐标转换为栅格点阵数据的过程。
具体来说，在分析一个多边形时, 我们会计算出其内部区域内的所有像素点信息, 并将这些像素的颜色值记录到相应的存储位置中
多边形可采用平面着色方案（flat shading mode）及光滑着色方案（smooth shading mode）进行填充。
该数据结构用于存储非水平多边形的所有边界信息。
此数据字段则记录了与当前扫描线相交的所有相关多边形边界。
多边形填充的核心算法采用** scanline algorithm **进行处理。首先计算多边形覆盖的所有 scanline 数量；随后针对每一根 scanline，请计算该 scanline 与 polygon 边界所形成的交点范围；若能确定该范围落在 polygon 内部区域，则将该范围内的 pixels 设置为预设颜色值。
当处理每一根扫描线时，在多边形的所有边上进行求交运算会导致较高的计算开销
对一条扫描线的填充一般分为以下4个步骤
- 计算多边形各边与扫描线的相交点：求取并存储所有可能的相交坐标；
- 将所有相交点按照从小到大的顺序排列：完成有序排列以便后续处理；
- 配对相邻的两个相交点为一组：形成连续区间以表示扫描线穿过多边形的情况；
- 将落在该区间范围内的像素设置为填充颜色：完成填充区域的确定和显示。
该算法 从选定的起始点出发，在图像内部按照层次逐步填充指定的颜色直至遇到与当前颜色不一致的边界像素时停止。
该方法可分为基于4-邻域和8-邻域两种实现方式。
有效边表填充算法
原理
在遵循由小到大的扫描线移动顺序下，在每一条新的扫描线上计算该扫描线与有效边界的交点位置，并将这些交点按照x坐标递增的顺序进行排序并配对从而确定要填充的区域范围随后使用指定的颜色将该区域内所有像素填入完成这一轮的填充操作
有效边表填充算法已成为目前最为有效的多边形填充算法之一。
边界像素处理原则
在指定区域从坐标（1,1）延伸至（3,3）的正方形部分进行像素填充操作时，在边界像素上实施全填充值策略即可获得预期效果。
在多边形填充算法中通常遵循"左闭右开"和"下闭上开"的区间处理原则来确定边界像素的具体归属。
怎么算交点
这里 边 相对于 扫描线 的位置都是上下关系，不是左右关系。
有效边
为了识别在哪个扫描线上插入新边的操作需要建立一个边表（edge table ET）用于记录每一条边的相关数据
由于水平边上k分之1等于无穷大，并且这一条边本身就是一条扫描线，在构造边表的过程中无需对此进行处理。
桶表与边表
在确定如何将新边界插入到哪一条特定的扫描线上时 ，必须构建一个包含该 scan 线上所有多边形各条边界信息的结构体 ... 。该结构体用于记录该 scan 线上所有多邊形各條存在的邊界信息。由于水平方向上的线条具有无限大的斜率，并且这些线条本身就是当前的 scan 线，在构建结构体时无需特别处理这些线条。
桶表表示法
桶表是按照扫描线顺序 管理边出现情况的一个数据结构。
- 建立一个垂直方向上的扫描线链表 ，其长度等于多边形覆盖的最大扫描线条数；每个链表中的节点被称作桶（bucket），它们分别对应多边形覆盖的每一条扫描线。*
桶类的代码
class CBucket
{
public:
CBucket();
virtual ~CBucket();
public:
int ScanLine; //扫描线
CAET *p; //桶上的边表指针
CBucket *next;
};
代码解读
实际上，并非是我们额外添加新的边界线
我们需要明确的是
在这个过程中
基于上述的理解，我们接下来系统地探讨桶表与边表这一核心概念及其相互关系。值得注意的是，桶表和边表实际上是一个统一的数据结构，在其设计上与有效边表有着相似之处而非完全分离的存在形式。具体而言，在一个多面体映射过程中，假设存在一组连续的水平扫描线范围是从y=1到y=10之间，在这种情况下我们需要按照层次顺序逐一处理这些水平扫描线：从y=1的位置开始初始化其对应的有效边上链入该位置对应的链式数据存储单元（即所谓的桶），随后依次向y=2的位置一直到y=10的位置推进同样的操作步骤。在此过程中若发现某个水平位置上已经存在过有效的边上链接记录，则必须跳过不再重复添加新的链接项直至完成所有有效边上全部处理完毕为止。在实际的手工绘制过程中我们可以先建立一个表格来记录多面体覆盖的所有水平扫描线信息，并从下往上逐行处理：当到达y=1时就开始在表格中使用箭头标出尚未出现的有效边上链接起来即可完成整个数据流程的操作流程图绘制工作
最后桶表于边表中链表的内容，记住即可。有4个部分，第一部分按书上的理解很容易出错。第一部分中x|y(min)指的不是x除以y，也不是x整除y，这儿书上没说清楚，这儿的**x|y(min)指的就是在对应的有效边中与之相交的最低扫描线与这条边相交的点的x值。**第二部分是ymax，就是对应有效边与之相交的最高的扫描线。第三部分k/1是指对应有效边的斜率的倒数。第四部分是next指针，上一个链表连接下一个链表，最后一个单元指针为空。在找到所有不重复的有效边后，按照x|ymin从小到大的顺序构建（x|ymin相等则按照1/k从小到大的顺序构建）链表即可。如果一条扫描线没有任何不重复的有效边，不写就行了。理解了以上内容，便可以写桶表与边表了。是不是和数据结构构建多边形的算法类似?因为本质上都是树相关的算法，只不过图形学这方面很多没有说清楚。
————————————————
版权声明：本文为博主「SN川川」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：
边缘填充算法
该算法首先通过计算得到多边形每条边与扫描线的交点位置；随后将位于这些交点右侧的所有像素的颜色值设置为其补色（亦即反色）；无论处理顺序如何，在完成所有多边形边界的所有计算后；从而实现了该区域内部像素的填充过程。
边缘填充算法基于图像处理中的求"补"或"反"原理运作，在黑白图像中，默认将RGB(1,1,1)（白色）像素转换为RGB(0,0,0)（黑色），而彩色图像则将背景色设为填充色并反之亦然。这一基本性质表明：当多边形内部像素接受两次求补操作后会恢复原色；若被奇数次求补操作处理，则显示填充色。
填充过程
过程：
（下图顺序）从左到右从上到下
代码：
void CTestView::FillPolygon(CDC *pDC)
{
COLORREF BClr=RGB(255,255,255);//背景色
COLORREF FClr=GetClr;//填充色
int yMin,yMax;//边的最小y值与最大y值
double x,y,k;//x,y当前点，k斜率的倒数
for(int i=0;i<7;i++)//循环多边形所有边
{
int j=(i+1)%7;
k=(P[i].x-P[j].x)/(P[i].y-P[j].y);//计算1/k
if(P[i].y<P[j].y)//得到每条边y的最大值与最小值
{
yMin=Round(P[i].y);
yMax=Round(P[j].y);
x=P[i].x;//得到x|ymin
}
else
{
yMin=Round(P[j].y);
yMax=Round(P[i].y);
x=P[j].x;
}
for(y=yMin;y<yMax;y++)//沿每一条边循环扫描线
{
//对每一条扫描线与边的交点的右侧像素循环
for(int m=Round(x);m<MaxX;m++)
//MaxX为包围盒的右边界
{
if(FClr==pDC->GetPixel(m,Round(y))) pDC->SetPixelV(m,Round(y),BClr);
else
pDC->SetPixelV(m,Round(y),FClr);
}
x+=k;
}
}
}
代码解读
区域填充算法/种子填充算法
原理
种子填充法从区域内的任意一个起始像素点开始，并向内部向外扩展至整个多边形区域完成填涂过程。
优点 是能对具有任意复杂闭合边界 的区域进行填充。
种子填充算法
定义;
- 基于种子像素点展开，采用四邻域搜索策略来确定相邻像素的填充算法即为四邻域填充算法。
- 基于种子像素点展开，采用八邻域搜索策略来确定相邻像素的填充算法即为八邻域填充算法。
基于8-邻域的填充算法设计与基于4-邻域的填充算法本质上相同，只需将搜索策略从4-邻域升级为8-邻域即可实现
该算法通常需要满足以下条件：即区域边界的颜色与填充的颜色必须不同；其输入参数仅包括 种子的坐标位置 和 填充的颜色 。
原理
代码：
void CTestView::FillPolygon(CDC *pDC)//填充多边形
{
COLORREF BoundaryClr=RGB(0,0,0);//边界色
COLORREF PixelClr;//当前像素的颜色
pHead=new CStackNode;//建立栈头结点
pHead->next=NULL;//栈的头结点总是为空
Push(Seed); //种子像素入栈
while(NULL!=pHead->next)//如果栈不为空
{
CP2 PopPoint;
Pop(PopPoint); //种子像素出栈
pDC->SetPixelV(Round(PopPoint.x),
Round(PopPoint.y),SeedClr);
PointLeft.x=PopPoint.x-1;//左方像素
PointLeft.y=PopPoint.y;
PixelClr=pDC->GetPixel(Round(PointLeft.x),
Round(PointLeft.y));
if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
Push(PointLeft);//左方像素入栈
PointTop.x=PopPoint.x;
PointTop.y=PopPoint.y+1;//上方像素
PixelClr=pDC->GetPixel(Round(PointTop.x),
Round(PointTop.y));
if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
Push(PointTop); //上方像素入栈
PointRight.x=PopPoint.x+1;//右方像素
PointRight.y=PopPoint.y;
PixelClr=pDC->GetPixel(Round(PointRight.x),
Round(PointRight.y));
if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
Push(PointRight);//右方像素入栈
PointBottom.x=PopPoint.x;
PointBottom.y=PopPoint.y-1;//下方像素
PixelClr=pDC->GetPixel(Round(PointBottom.x),
Round(PointBottom.y));
if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
Push(PointBottom);//下方像素入栈
}
pDC->TextOut(rect.left+50,rect.bottom-20,"填充完毕");
delete pHead;
pHead = NULL;
}
代码解读扫描线种子填充算法 （更有效）
