扫描线算法 ■扫描线算法 目标:利用相邻像素之间的连贯性,提高算 法效率 n处理对象:非自交多边形(边与边之间除 了顶点外无其它交点) 2021/1/21 浙江大学计算机图形学 12
2021/1/21 浙江大学计算机图形学 12 扫描线算法 ◼ 扫描线算法 ◼ 目标：利用相邻像素之间的连贯性，提高算 法效率 ◼ 处理对象：非自交多边形 （边与边之间除 了顶点外无其它交点）
扫描线算法 n交点的取整规则 要求:使生成的像素全部位于多边形之内 假定非水平边与扫描线y=e 相交,交点的横坐标为x, 规则如下 2021/1/21 浙江大学计算机图形学 13
2021/1/21 浙江大学计算机图形学 13 扫描线算法 ◼ 交点的取整规则 ◼ 要求：使生成的像素全部位于多边形之内 ◼ 假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下
岁扫描线算法 ●规则1: Ⅹ为小数,即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上,向右取整 (b)交点位于右边之上,向左取整 (x,e) (x,e) 2021/1/21 浙江大学计算机图形学 14
2021/1/21 浙江大学计算机图形学 14 扫描线算法 ●规则1： X为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整
扫描线算法 ●规则2: 边界上象素的取舍问题,避免填充扩大化。 ●解决方法: 边界象素:规定落在右上边界的象素不予填充 具体实现时,只要对扫描线与多边形的相交区间左闭右开 (x,e) (x, 2021/1/21 浙江大学计算机图形学 15
2021/1/21 浙江大学计算机图形学 15 ●规则2： 边界上象素的取舍问题，避免填充扩大化。 ●解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开 扫描线算法
扫描线算法 ●规则3: 扫描线与多边形的顶点相交时,交点的取舍,保证交点正 确配对。 ●解决方法: 检查两相邻边在扫描线的哪一侧。 只要检査顶点的两条边的另外两个端点的Y值,两个Y值 中大于交点Y值的个数是0,1,2,来决定取0,1,2个交点 y=e 22 FP
2021/1/21 浙江大学计算机图形学 16 ●规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正 确配对。 ●解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值 中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 扫描线算法