计算机图形学图形填充.ppt

计算机图形学图形填充
第1页，此课件共50页哦
图形分类
线段图形
直线、圆以及自由曲线等，用于表现物体的几何轮廓
实面积图形
封闭图形，在其封闭的区域内具有相同的颜色。既表现了物体的几何轮廓，也反映了物体表面的4
P5
扫描线5
扫描线4
扫描线3
扫描线2
扫描线1
I5
I6
检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数
计数0次
计数1次
计数2次
*
*
第15页，此课件共50页哦
总结：简单地数交点不能解决所有的问题，需要补充规则完善此射线交点计数法：
（1）忽略多边形的水平边；
（2）与多边形的极值点端点相交时，该点算做两个；
（3）其余的非极值点端点，仅计算一次。
实际操作任务：
（1）判断水平边；
（2）判断奇点；
在求交点过程中，因为是依次计算扫描线与各条边的交点，因此奇点也自然被计算两次。但造成另一个问题是非极值点的顶点也被计算了两次。
第16页，此课件共50页哦
对此问题的一种处理办法是，计算前，先将每条斜边的低端点在y方向上缩小一个屏幕坐标单位，这将忽略极小值
第17页，此课件共50页哦
另一种预处理办法是，通过判断每条斜边的端点y值是否单调来找出奇点，对极值端点不作处理，而对非极值端点则缩短其中一条斜边的端点。
此法的缺点是，填充的图形可能会出现残缺
第18页，此课件共50页哦
这样处理后，极值点仍计算两次，而非极值点的斜边交点只计算一次。
经上述约定及处理后，可保证同一扫描线与多边形的交点成对出
现，因此只要算出交点，填充就可以利用画直线算法快速完成。
第19页，此课件共50页哦
扫描线算法步骤如下：
（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。
（2）从y=ymin到y=ymax，每次用一条扫描线进行填充。
（3）对一条扫描线填充的过程可分为四个步骤：
a、求交：计算扫描线与多边形各边的交点；
b、排序：把所有交点按递增顺序进行排序；
c、交点配对：第一个与第二个，第三个与第四个 等等，每对交点就
代表扫描线与多边形的一个相交区间；
d、区间填色：把这些相交区间内的像素置成不同于背景色的填充色。
第20页，此课件共50页哦
如何计算下一条扫描线与边的交点。
直线方程：ax+by+c = 0
当前交点坐标：(xi, yi)
下一交点坐标：(xi+1,yi+1)
xi+1= ((-byi+1)-c)/a = ((-byi+1)-c)/a =xi-b/a=xi+1/mi
第21页，此课件共50页哦
扫描线算法特点
特点：算法效率较高。
缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。
第22页，此课件共50页哦
填充图元生成原理
多边形扫描转换
区域填充
第23页，此课件共50页哦
区域填充
区域指已经表示成点阵形式的填充图形，它是象素的集合。
区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。
第24页，此课件共50页哦
区域填充
表示方法：内点表示、边界表示
内点表示
枚举出区域内部的所有像素
内部的所有像素着同一个颜色
边界像素着与内部像素不同的颜色
边界表示
枚举出边界上所有的像素
边界上的所有像素着同一颜色
内部像素着与边界像素不同的颜色
第25页，此课件共50页哦
区域填充—区域的连通性
连通性
4连通、8连通、16连通
4连通 像素（P(xp,yp)）
N4(p)={r|d4(p,r)=1}
d4(p,r)=|xp-xr|+ |yp-yr|
8连通 N8(p)={r|d8(p,r)=1}
d8(p,r)=max(|xp-xr|,|yp-yr|)
p
r
r
r
r
r
r
r
r
p
r
r
r
r
第26页，此课件共50页哦
区域填充—区域的连通性
16连通
N16(p)= N8(p)∪ Nk(p)
Nk(p)={dk(p,r)=1}:马步邻域
马步距离
r
r
r
r
p
r
r
r
r
r
r
r
r
r
r
r
r