浙江大学：《计算机图形学》课程教学资源（PPT课件）第四章 光栅图形的扫描转换与区域填充（二维填充图元的生成）

s第四章光栅图形的 扫描转换与区域填充 扫描转换矩形 扫描转换多边形 区域填充 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 1 第四章 光栅图形的 扫描转换与区域填充 扫描转换矩形 扫描转换多边形 区域填充

缈v扫描转换矩形 ■问题 n矩形是简单的多边形,那么为什么要单独处 理矩形? 比一般多边形可简化计算 应用非常多,窗口系统。 n共享边界如何处理? 原则:左闭右开,下闭上开 属于谁? 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 2 扫描转换矩形 ◼ 问题： ◼ 矩形是简单的多边形，那么为什么要单独处 理矩形？ 比一般多边形可简化计算。 应用非常多，窗口系统。 ◼ 共享边界如何处理？ ◼ 原则：左闭右开，下闭上开 属于谁？

扫描转换多边形 ■多边形分为凸多边形、凹多边形、含内环的多 边形。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 4 扫描转换多边形 ◼ 多边形分为凸多边形、凹多边形、含内环的多 边形

YD扫描转换多边形 n多边形的表示方法 n顶点表示 进H n点阵表示 ■顶点表示:用多边形顶点的序列来刻划多边形。 直观、几何意义强、占内存少;不能直接用于 面着色。 ■点阵表示:用位于多边形内的象素的集合来刻 划多边形。失去了许多重要的几何信息;便于 运用帧缓冲存储器表示图形,易于面着色。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 5 扫描转换多边形 ◼ 多边形的表示方法 ◼ 顶点表示 ◼ 点阵表示 ◼ 顶点表示：用多边形顶点的序列来刻划多边形。 直观、几何意义强、占内存少；不能直接用于 面着色。 ◼ 点阵表示：用位于多边形内的象素的集合来刻 划多边形。失去了许多重要的几何信息；便于 运用帧缓冲存储器表示图形，易于面着色

M多边形的扫描转换 ■多边形的扫描转换:把多边形的顶点表示转 换为点阵表示,也就是从多边形的给定边界 出发,求出位于其内部的各个象素,并给帧 缓冲器内的各个对应元素设置相应的灰度和 颜色,通常称这种转换为多边形的扫描转换。 ■几种方法:逐点判断法;扫描线算法;边缘 填充法;栅栏填充法;边界标志法。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 6 多边形的扫描转换 ◼ 多边形的扫描转换：把多边形的顶点表示转 换为点阵表示，也就是从多边形的给定边界 出发，求出位于其内部的各个象素，并给帧 缓冲器内的各个对应元素设置相应的灰度和 颜色，通常称这种转换为多边形的扫描转换。 ◼ 几种方法：逐点判断法；扫描线算法；边缘 填充法；栅栏填充法；边界标志法

v逐点判断法 FANG UNINES #define maX 100 Typedef struct{ int PolygonUm;∥多边形顶点个数 Point vertexes MAX]∥多边形顶点数组 } Polygon∥多边形结构 void FillPolygon P(Polygon*Pint polygon Color for(y=ymin; y <=ymax; y++) forex=xmin; x <=xmax; x++) if(iNside (p x, y)) PutPixel(x, v, polygoncolor); else PutPixel(x, y, backgroundcolor); B/*end of fillPolygonPbyP0*/ 2021/1/21 浙江大学计算机图形学 7

2021/1/21 浙江大学计算机图形学 7 void FillPolygonPbyP(Polygon *P,int polygonColor) { int x,y; for(y = ymin;y <= ymax;y++) for(x = xmin;x <= xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor); }/*end of FillPolygonPbyP() */ #define MAX 100 Typedef struct { int PolygonNum; // 多边形顶点个数 Point vertexces[MAX] //多边形顶点数组 } Polygon // 多边形结构 逐点判断法

逐点判断法 逐个判断绘图窗口内的像素: n如何判断点在多边形的内外关系? 1)射线法: 2)累计角度法 3)编码法; 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 8 逐点判断法 ◼ 逐个判断绘图窗口内的像素： ◼ 如何判断点在多边形的内外关系？ 1）射线法： 2）累计角度法 3）编码法；

逐点判断法 1)射线法 步骤: 从待判别点v发出射线 2.求交点个数k K的奇偶性决定了点与多边形的内外关系 2021/1/21 冽让人子昇饥囹形字

2021/1/21 浙江大学计算机图形学 9 逐点判断法 1）射线法 ◼ 步骤： 1. 从待判别点v发出射线 2. 求交点个数k 3. K的奇偶性决定了点与多边形的内外关系

逐点判断法 2)累计角度法 步骤 从v点向多边形P顶点发出射线,形成有向角O 2.计算有相交的和,得出结论 0,w位于P之外 0 ±2x,n位于P之内 B 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 10 逐点判断法 2）累计角度法 ◼ 步骤 1. 从v点向多边形P顶点发出射线，形成有向角 2. 计算有相交的和，得出结论      = = 位于 之内 ， 位于 之外 v P n v P i i 2 , 0 0    i

逐点判断法 ■逐点判断的算法虽然程序简单,但不可取。原 因是速度太慢,主要是由于该算法割断了各象 素之间的联系,孤立地考察各象素与多边形的 内外关系,使得几十万甚至几百万个象素都要 判别,每次判别又要多次求交点,需要做 大量的乘除运算,花费很多时间。 2021/1/21 浙江大学计算机图形学

2021/1/21 浙江大学计算机图形学 11 逐点判断法 ◼ 逐点判断的算法虽然程序简单，但不可取。原 因是速度太慢，主要是由于该算法割断了各象 素之间的联系，孤立地考察各象素与多边形的 内外关系，使得几十万甚至几百万个象素都要 一一判别，每次判别又要多次求交点，需要做 大量的乘除运算，花费很多时间